《C++程序设计链表》由会员分享，可在线阅读，更多相关《C++程序设计链表（157页珍藏版）》请在金锄头文库上搜索。
1、链表链表 1 1什么叫链表什么叫链表 一个链表由n个结点链接而成(n0) ,每个结点包括两个域：存储数据元素信息的数据域和存放另一数据元素地址的指针域。请看下图： 2 2链表的种类链表的种类 链表通常以头指针命名，头指针指示了链表中第一个结点的存储位置，通过它能实现整个链表的存取。 分为单链表、循环链表和双向链表，下面分别简介： 1 1）单链表：）单链表：链表的每个结点只含一个指针域。 在单链表中，最后一个结点无后继，其指针域为空（NIL）。单链表的逻辑结构如上图所示。 单链表的存储映像单链表的存储映像2 2）循环链表）循环链表 若修改单链表，使最后一个元素的指针又指向第一个元素，则这种单链表
2、的改进形式称为循环链表，其逻辑结构如下图所示。 3 3）双向链表）双向链表 若表中每个结点都有两个指针，分别指向其前驱结点和后继结点，这样的链表称为双向链表，如下图所示。 3. 3. 链表的描述链表的描述 通常在链表的第一个结点前附设一个结点，称为头结点，并让链表的头指针指向头结点，如下图所示。 链表由结点和链组成，结点包括数据域和链域两部分，如下图所示： 链表结构类型和结点定义如下： 数据域指针域struct Node ; Node *next; Node *head; /与结构同类型的指针 注意：指针域（指针成员）的类型一定和包含该指针的结构同类型，也即链表结点数据类型的定义是递归的。 例
3、 将学生数据定义成链表结点类型。 struct STUDENT int num; char name9; char sex; struct BIRTHDAY int year; int month; int day; birthday; char NativePlace30; STUDENT *next; 数据域指针域4 4链表的用途链表的用途 链表的用途非常广泛，以下两个用途对数据处理是极其有用的： （1 1）支持建立动态结构数组）支持建立动态结构数组 我们在例中用到职工数组： 例 采用静态定义的方法： EMPLOYEE employeeNUM; 问题1：采用动态存储分配只支持动态建立数组，
4、并不支持建立动态数组。采用“准动态”的方法，先定义成结构指针，并采用动态存储分配，在程序运行过程中动态建立该数组的内存空间：EMP *employee； employee=(struct EMP*) calloc(NUM,sizeof(EMP)； 以上两种方法的共同点是：以上两种方法的共同点是： 在建立该数组前，数组的成员个数是确定的，在无法准确地确定成员个数时，必须考虑最大成员数，这样可能会造成内存空间的极大浪费。 问题2：如何实现建立真正的动态数组？ 可见链表有效地支持动态数组。 如果将每个结点视为一个数组元素，因为链表允许动态插入或追加结点，也即采用链表可以根据实际情况随时增减成员个数
5、。（2 2）在增减成员时可以减少数据的移动量）在增减成员时可以减少数据的移动量 假如有一个具有n个元素的结构数组，如果我们删除了第 i 个元素，那么必须向上移动n-i个元素，参见下图： 假设n=1000，i=10，那么需要移动的元素个数是990个。 如果用链表来存放同样的数据，情况将会大有改善： 当删除第i个记录时，只须改变第i-1个记录的链域，使其由原来指向第i个结点（记录）改为指向第i+1个结点，同时释放第i个结点所占的空间，根本无须移动数据，如下图： 用指针处理链表的操作n链表概述n建立链表n输出链表n对链表的删除操作n对链表的插入操作程序对数据的表示，不但要求存放基本信息，还要表示与其
6、它数据元素的关系线性表是最简单的数据组织形式链表链表1 1动态链表存储动态链表存储 3208Chen204630104016Li320532084048Zhang10454016NULLWang165040483010head结点结点链表1 1动态链表存储动态链表存储 3208Chen204630104016Li320532084048Zhang10454016NULLWang165040483010head数据元素信息数据元素信息链表1 1动态链表存储动态链表存储 3208Chen204630104016Li320532084048Zhang10454016NULLWang165040483
7、010head元素关系元素关系链表1 1动态链表存储动态链表存储 3208Chen204630104016Li320532084048Zhang10454016NULLWang165040483010head结点数据类型structnodecharname20;floatsalary;node*next;单向链表结点数据类型单向链表结点数据类型struct node dataType data ; node * next ; ; 2 2 2 2建立和遍建立和遍建立和遍建立和遍历链历链表表表表 建立链表的过程：建立链表的过程：生成头结点；while（未结束）生成新结点；把新结点插入链表；stru
8、ctnodeintdata;node*next;node*head;node*CreateList()node*s,*p;s=newnode;cins-data;head=NULL;while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;p-next=NULL;deletes;return(head);链表2 2 2 2建立和遍建立和遍建立和遍建立和遍历链历链表表表表 建立链表的过程：建立链表的过程：生成头结点；while（未结束）生成新结点；把新结点插入链表；structnodeintdata;node
9、*next;node*head;node*CreateList()node*s,*p;s=newnode;cins-data;head=NULL;while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;p-next=NULL;deletes;return(head);结构类型结构类型链表2 2 2 2建立和遍建立和遍建立和遍建立和遍历链历链表表表表 建立链表的过程：建立链表的过程：生成头结点；while（未结束）生成新结点；把新结点插入链表；structnodeintdata;node*next;node
10、*head;node*CreateList()node*s,*p;s=newnode;cins-data;head=NULL;while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;p-next=NULL;deletes;return(head);头指针头指针链表2 2 2 2建立和遍建立和遍建立和遍建立和遍历链历链表表表表 建立链表的过程：建立链表的过程：生成头结点；while（未结束）生成新结点；把新结点插入链表；structnodeintdata;node*next;node*head;node*C
11、reateList()node*s,*p;s=newnode;cins-data;head=NULL;while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;p-next=NULL;deletes;return(head);建立链表函数建立链表函数返回头指针返回头指针链表2 2 2 2建立和遍建立和遍建立和遍建立和遍历链历链表表表表 建立链表的过程：建立链表的过程：生成头结点；while（未结束）生成新结点；把新结点插入链表；structnodeintdata;node*next;node*head;no
12、de*CreateList()node*s,*p;s=newnode;cins-data;head=NULL;while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;p-next=NULL;deletes;return(head);声明局部量声明局部量链表2 2 2 2建立和遍建立和遍建立和遍建立和遍历链历链表表表表 建立链表的过程：建立链表的过程：生成头结点；while（未结束）生成新结点；把新结点插入链表；structnodeintdata;node*next;node*head;node*Creat
13、eList()node*s,*p;s=newnode;cins-data;head=NULL;while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;p-next=NULL;deletes;return(head);建立第一个结点建立第一个结点链表2 2 2 2建立和遍建立和遍建立和遍建立和遍历链历链表表表表 建立链表的过程：建立链表的过程：生成头结点；while（未结束）生成新结点；把新结点插入链表；structnodeintdata;node*next;node*head;node*CreateLis
14、t()node*s,*p;s=newnode;cins-data;head=NULL;while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;p-next=NULL;deletes;return(head);链表头指针初始化链表头指针初始化链表2 2 2 2建立和遍建立和遍建立和遍建立和遍历链历链表表表表 建立链表的过程：建立链表的过程：生成头结点；while（未结束）生成新结点；把新结点插入链表；structnodeintdata;node*next;node*head;node*CreateList(
15、)node*s,*p;s=newnode;cins-data;head=NULL;while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;p-next=NULL;deletes;return(head);向链表向链表插入新结点插入新结点链表2 2 2 2建立和遍建立和遍建立和遍建立和遍历链历链表表表表 建立链表的过程：建立链表的过程：生成头结点；while（未结束）生成新结点；把新结点插入链表；structnodeintdata;node*next;node*head;node*CreateList()n
16、ode*s,*p;s=newnode;cins-data;head=NULL;while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;p-next=NULL;deletes;return(head);释放释放值为值为0的结点的结点链表2 2 2 2建立和遍建立和遍建立和遍建立和遍历链历链表表表表 建立链表的过程：建立链表的过程：生成头结点；while（未结束）生成新结点；把新结点插入链表；structnodeintdata;node*next;node*head;node*CreateList()node
17、*s,*p;s=newnode;cins-data;head=NULL;while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;p-next=NULL;deletes;return(head);返回头指针返回头指针链表s=newnode;cins-data;head=NULL;链表s=newnode;cins-data;head=NULL;s链表s=newnode;cins-data;head=NULL;s1链表s=newnode;cins-data;head=NULL;s1head链表s1headwhi
18、le(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;链表s1headwhile(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;链表s1headwhile(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;链表s1headwhile(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newno
19、de;cins-data;链表while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;s1headp链表while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;s1headp链表while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;s1headp链表while(s-data!=0)if(head=NULL)head=s;els
20、ep-next=s;p=s;s=newnode;cins-data;s1headp3链表while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;s1headp3链表while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;s1headp3链表while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;s1headp3链表while(s
21、-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;s1headp3链表while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;s1headp3链表while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;s1headp3链表while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=new
22、node;cins-data;s1headp35链表while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;1headp3s5链表while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;1headp3s5链表while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;1headp3s5链表while(s-data!=0)if(hea
23、d=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;1headp3s5链表while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;1headp3s5链表while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;1headp3s5链表while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-da
24、ta;1headp3s57链表while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;1headp35s7链表while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;1headp35s7链表while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;1headp35s7链表while(s-data!=0)if(head=NULL)h
25、ead=s;elsep-next=s;p=s;s=newnode;cins-data;1headp35s7链表while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;1headp3s57链表while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;1headp3s57链表while(s-data!=0)if(head=NULL)head=s;elsep-next=s;p=s;s=newnode;cins-data;1h
26、eadp3s570 0链表while(s-data!=0):p-next=NULL;deletes;return(head);1headp3s570 0链表while(s-data!=0):p-next=NULL;deletes;return(head);1headp3s570 0链表while(s-data!=0):p-next=NULL;deletes;return(head);1headp3s570 0 链表while(s-data!=0):p-next=NULL;deletes;return(head);1headp3s570 0 链表while(s-data!=0):p-next=N
27、ULL;deletes;return(head);1headp357 链表while(s-data!=0):p-next=NULL;deletes;return(head);1headheadp357 链表在表头插入结点3 3 3 3插入插入插入插入结结点点点点s-next=head;head=s;2head357 s1 链表 在表头插入结点3 3 3 3插入插入插入插入结结点点点点s-next=head;head=s;2head357 s1 链表在表头插入结点3 3 3 3插入插入插入插入结结点点点点s-next=head;head=s;2head357 s1 链表在表头插入结点3 3 3
28、3插入插入插入插入结结点点点点s-next=head;head=s;2head357 s1 链表在表头插入结点3 3 3 3插入插入插入插入结结点点点点s-next=head;head=s;12head357 链表在*p之后插入*s3 3 3 3插入插入插入插入结结点点点点s-next=p-next;p-next=s;s4 12head357 p链表在*p之后插入*s3 3 3 3插入插入插入插入结结点点点点s-next=p-next;p-next=s;s412head357 p链表在*p之后插入*s3 3 3 3插入插入插入插入结结点点点点s-next=p-next;p-next=s;s41
29、2head357 p链表在*p之后插入*s3 3 3 3插入插入插入插入结结点点点点s-next=p-next;p-next=s;s412head357 p链表在*p之后插入*s3 3 3 3插入插入插入插入结结点点点点s-next=p-next;p-next=s;s412head357 p链表在*p之后插入*s3 3 3 3插入插入插入插入结结点点点点s-next=p-next;p-next=s;57 12head34链表在*p之前插入*s3 3 3 3插入插入插入插入结结点点点点s-next=p;q-next=s;3pqs57 12head4链表在*p之前插入*s3 3 3 3插入插入插入
30、插入结结点点点点s-next=p;q-next=s;3pqs57 12head4链表在*p之前插入*s3 3 3 3插入插入插入插入结结点点点点s-next=p;q-next=s;3pqs57 12head4链表在*p之前插入*s3 3 3 3插入插入插入插入结结点点点点s-next=p;q-next=s;3pqs57 12head4链表在*p之前插入*s3 3 3 3插入插入插入插入结结点点点点s-next=p;q-next=s;57 12head34pqs链表链表链表if(表空表空)生成链表的第一个结点；生成链表的第一个结点；elseif(numdata)把把num插入头结点之前；插入头结
31、点之前；/此时此时num是最小值是最小值else从表中找第一个大于从表中找第一个大于num的结点的结点*p；if(找到找到)把把num插入插入*p之前；之前；把把num插入表尾；插入表尾；/此时此时num是最大值是最大值例例 用插入法生成一个有序链表用插入法生成一个有序链表 #includestructlistintdata;list*next;list*head; list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-dat
32、a)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head);例例 用插入法生成一个有序链表用插入法生成一个有序链表
33、#includestruct list int data ; list * next ; ; list * head ; list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-nex
34、t=s;return(head);voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head);/ 声明结构类型，结构指针变量声明结构类型，结构指针变量structlistintdata;list*next;list*head;例例 用插入法生成一个有序链表用插入法生成一个有序链表 #includestruct list int data ; list * next ; ; list * head
35、 ; list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);voidshowlist(constlist*head)coutnowtheite
36、msoflistare:n;while(head)coutdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head);/ 声明结构类型，结构指针变量声明结构类型，结构指针变量structlistintdata;list*next;list * head ;头指针头指针是全局变量是全局变量例例 用插入法生成一个有序链表用插入法生成一个有序链表 #includestructlistintdata;list*next;list*head;list * insert ( int num ) list * s, *p, *q ; s = ne
37、w list ; s-data = num ; s-next = NULL ; if ( head = NULL ) head = s ; return( head ) ; if ( head-data s-data ) s-next = head ; head = s ; return ( head ) ; for ( q = head, p = head-next ; p ; q = p, p = p-next ) if ( p-data s-data ) s-next = p ; q-next = s ; return ( head ) ; q-next = s ; return ( h
38、ead ) ;voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head);/ 插入法生成有序链表插入法生成有序链表list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return
39、(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);例例 用插入法生成一个有序链表用插入法生成一个有序链表 voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head);/ 插入法生成有序链表插入法生成有序链表list*in
40、sert(int num)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);值参值参接受结点数据接受结点数据例例 用插入法生成一个有序链表用插入法生成一个有序链表 voidsh
41、owlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head);/ 插入法生成有序链表插入法生成有序链表list *insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return ( head ) ;if(head-datas-data)s-next=head;head=s;return ( head
42、) ;for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return ( head ) ;q-next=s;return ( head );返回结构指针返回结构指针（链表头指针）（链表头指针）例例 用插入法生成一个有序链表用插入法生成一个有序链表 voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head
43、);/ 插入法生成有序链表插入法生成有序链表list*insert(intnum)list * s, *p, *q ;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);声明局部指针变量声明局部指针变量例
44、例 用插入法生成一个有序链表用插入法生成一个有序链表 voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head);/ 插入法生成有序链表插入法生成有序链表list*insert(intnum)list*s,*p,*q;s = new list ; s-data = num ; s-next = NULL ;if(head=NULL)head=s;return(head);if(head-data
45、s-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);生成新结点生成新结点9shead例例 用插入法生成一个有序链表用插入法生成一个有序链表 voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutk;while(k!=0)head=insert(k)
46、;cink;showlist(head);/ 插入法生成有序链表插入法生成有序链表list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL; if ( head = NULL ) head = s ; return( head ) ; if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;r
47、eturn(head);建立第一个结点建立第一个结点9shead例例 用插入法生成一个有序链表用插入法生成一个有序链表 voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head);/ 插入法生成有序链表插入法生成有序链表list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;retu
48、rn(head);if ( head-data s-data ) s-next = head ; head = s ; return ( head ) ; for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);插入表头插入表头5shead91531例例 用插入法生成一个有序链表用插入法生成一个有序链表 voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)co
49、utdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head);/ 插入法生成有序链表插入法生成有序链表list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if ( head-data s-data ) s-next = head ; head = s ; return ( head ) ; for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-d
50、ata)s-next=p;q-next=s;return(head);q-next=s;return(head);插入表头插入表头例例 用插入法生成一个有序链表用插入法生成一个有序链表 5shead91531voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head);/ 插入法生成有序链表插入法生成有序链表list*insert(intnum)list*s,*p,*q;s=newlist;s-d
51、ata=num;s-next=NULL;if(head=NULL)head=s;return(head);if ( head-data s-data ) s-next = head ; head = s ; return ( head ) ; for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);插入表头插入表头例例 用插入法生成一个有序链表用插入法生成一个有序链表 5shead91531voidshowlist(constlist*h
52、ead)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head);/ 插入法生成有序链表插入法生成有序链表list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if ( head-data s-data ) s-next = head ; head = s ; return ( head ) ; for(q=
53、head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);插入表头插入表头head915315例例 用插入法生成一个有序链表用插入法生成一个有序链表 voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head);/ 插入法生成有序链表插入法生成有序链表li
54、st*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for ( q = head, p = head-next ; p ; q = p, p = p-next ) if ( p-data s-data ) s-next = p ; q-next = s ; return ( head ) ; q-next=s;return(head);搜索插入搜索插入he
55、ad91531520s例例 用插入法生成一个有序链表用插入法生成一个有序链表 voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head);/ 插入法生成有序链表插入法生成有序链表list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-data
56、s-data)s-next=head;head=s;return(head);for ( q = head, p = head-next ; p ; q = p, p = p-next ) if ( p-data s-data ) s-next = p ; q-next = s ; return ( head ) ; q-next=s;return(head);开始搜索开始搜索例例 用插入法生成一个有序链表用插入法生成一个有序链表 head91531520sqpvoidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)c
57、outdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head);/ 插入法生成有序链表插入法生成有序链表list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for ( q = head, p = head-next ; p ; q = p, p = p-next ) if ( p-data
58、 s-data ) s-next = p ; q-next = s ; return ( head ) ; q-next=s;return(head);搜索条件搜索条件p != NULL例例 用插入法生成一个有序链表用插入法生成一个有序链表 head91531520sqpvoidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head);/ 插入法生成有序链表插入法生成有序链表list*insert(i
59、ntnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for ( q = head, p = head-next ; p ; q = p, p = p-next ) if ( p-data s-data ) s-next = p ; q-next = s ; return ( head ) ; q-next=s;return(head);跟踪指针移动跟踪指针移动例例 用插入法生成
60、一个有序链表用插入法生成一个有序链表 head91531520sqpvoidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head);/ 插入法生成有序链表插入法生成有序链表list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-dat
61、a)s-next=head;head=s;return(head);for ( q = head, p = head-next ; p ; q = p, p = p-next ) if ( p-data s-data ) s-next = p ; q-next = s ; return ( head ) ; q-next=s;return(head);跟踪指针移动跟踪指针移动例例 用插入法生成一个有序链表用插入法生成一个有序链表 head91531520sq pvoidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)c
62、outdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head);/ 插入法生成有序链表插入法生成有序链表list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for ( q = head, p = head-next ; p ; q = p, p = p-next ) if ( p-data
63、 s-data ) s-next = p ; q-next = s ; return ( head ) ; q-next=s;return(head);跟踪指针移动跟踪指针移动例例 用插入法生成一个有序链表用插入法生成一个有序链表 head91531520sqpvoidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head);/ 插入法生成有序链表插入法生成有序链表list*insert(intnum
64、)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for ( q = head, p = head-next ; p ; q = p, p = p-next ) if ( p-data s-data ) s-next = p ; q-next = s ; return ( head ) ; q-next=s;return(head);找到位置，插入找到位置，插入例例 用插入法生成一个有
65、序链表用插入法生成一个有序链表 head91531520sqpvoidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head);/ 插入法生成有序链表插入法生成有序链表list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s
66、-next=head;head=s;return(head);for ( q = head, p = head-next ; p ; q = p, p = p-next ) if ( p-data s-data ) s-next = p ; q-next = s ; return ( head ) ; q-next=s;return(head);找到位置，插入找到位置，插入head例例 用插入法生成一个有序链表用插入法生成一个有序链表 head91531520sqpvoidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head
67、)coutdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head);/ 插入法生成有序链表插入法生成有序链表list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for ( q = head, p = head-next ; p ; q = p, p = p-next ) if ( p-da
68、ta s-data ) s-next = p ; q-next = s ; return ( head ) ; q-next=s;return(head);找到位置，插入找到位置，插入例例 用插入法生成一个有序链表用插入法生成一个有序链表 headhead91531520sqpvoidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head);/ 插入法生成有序链表插入法生成有序链表list*inser
69、t(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for ( q = head, p = head-next ; p ; q = p, p = p-next ) if ( p-data s-data ) s-next = p ; q-next = s ; return ( head ) ; q-next=s;return(head);找到位置，插入找到位置，插入head
70、91531520例例 用插入法生成一个有序链表用插入法生成一个有序链表 voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head);/ 插入法生成有序链表插入法生成有序链表list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-d
71、ata)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next = s ; return ( head ) ;插入表尾插入表尾head91531599sqp例例 用插入法生成一个有序链表用插入法生成一个有序链表 voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutk;while(k!=0)he
72、ad=insert(k);cink;showlist(head);/ 插入法生成有序链表插入法生成有序链表list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next = s ;
73、return ( head ) ;插入表尾插入表尾例例 用插入法生成一个有序链表用插入法生成一个有序链表 head91531599sqpvoidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutk;while(k!=0)head=insert(k);cink;showlist(head);/ 插入法生成有序链表插入法生成有序链表list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)hea
74、d=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next = s ; return ( head ) ;插入表尾插入表尾head91531599例例 用插入法生成一个有序链表用插入法生成一个有序链表 #includestructlistintdata;list*next;list*head;list*insert(intnum)list
75、*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);void showlist( const list * head ) cout now the items of list are:
76、n ; while( head ) cout data next ; cout k;while(k!=0)head=insert(k);cink;showlist(head);例例 用插入法生成一个有序链表用插入法生成一个有序链表 #includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;re
77、turn(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);void showlist( const list * head ) cout now the items of list are: n ; while( head ) cout data next ; cout k;while(k!=0)head=insert(k);cink;showlist(head);/ 输出链表结点输出链表结点voidshowlist(
78、constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutendl;例例 用插入法生成一个有序链表用插入法生成一个有序链表 #includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);fo
79、r(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);void showlist( const list * head ) cout now the items of list are: n ; while( head ) cout data next ; cout k;while(k!=0)head=insert(k);cink;showlist(head);/ 输出链表结点输出链表结点voidshowlist(constlist*hea
80、d)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutendl;形参指针形参指针head9152053199head例例 用插入法生成一个有序链表用插入法生成一个有序链表 #includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;re
81、turn(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);void showlist( const list * head ) cout now the items of list are: n ; while( head ) cout data next ; cout k;while(k!=0)head=insert(k);cink;showlist(head);/ 输出链表结点输出链表结点voidshowlist(
82、constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutendl;nowtheitemsoflistare:5915203199例例 用插入法生成一个有序链表用插入法生成一个有序链表 head9152053199head#includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(h
83、ead-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);void showlist( const list * head ) cout now the items of list are: n ; while( head ) cout data next ; cout k;while(k!=0)head=insert(k);cink;showli
84、st(head);/ 输出链表结点输出链表结点voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutendl;nowtheitemsoflistare:59153199例例 用插入法生成一个有序链表用插入法生成一个有序链表 head9152053199head#includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(
85、head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);void showlist( const list * head ) cout now the items of list are: n ; while( head ) cout data next ; cout k;whi
86、le(k!=0)head=insert(k);cink;showlist(head);/ 输出链表结点输出链表结点voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutendl;nowtheitemsoflistare:59153199例例 用插入法生成一个有序链表用插入法生成一个有序链表 head9152053199head#includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=
87、newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);void showlist( const list * head ) cout now the items of list are: n ; while(
88、head ) cout data next ; cout k;while(k!=0)head=insert(k);cink;showlist(head);/ 输出链表结点输出链表结点voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutendl;nowtheitemsoflistare:59153199nowtheitemsoflistare:59153199例例 用插入法生成一个有序链表用插入法生成一个有序链表 head9152053199head#includestructlis
89、tintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);void showlist(
90、const list * head ) cout now the items of list are: n ; while( head ) cout data next ; cout k;while(k!=0)head=insert(k);cink;showlist(head);/ 输出链表结点输出链表结点voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutendl;nowtheitemsoflistare:59153199例例 用插入法生成一个有序链表用插入法生成一个有序链表 h
91、ead9152053199head#includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-n
92、ext=s;return(head);void showlist( const list * head ) cout now the items of list are: n ; while( head ) cout data next ; cout k;while(k!=0)head=insert(k);cink;showlist(head);/ 输出链表结点输出链表结点voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutendl;nowtheitemsoflistare:591
93、53199例例 用插入法生成一个有序链表用插入法生成一个有序链表 head9152053199head#includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)
94、s-next=p;q-next=s;return(head);q-next=s;return(head);void showlist( const list * head ) cout now the items of list are: n ; while( head ) cout data next ; cout k;while(k!=0)head=insert(k);cink;showlist(head);/ 输出链表结点输出链表结点voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext
95、;coutendl;nowtheitemsoflistare:59153199例例 用插入法生成一个有序链表用插入法生成一个有序链表 head9152053199head#includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-ne
96、xt;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);void showlist( const list * head ) cout now the items of list are: n ; while( head ) cout data next ; cout k;while(k!=0)head=insert(k);cink;showlist(head);/ 输出链表结点输出链表结点voidshowlist(constlist*head)coutnowtheitemso
97、flistare:n;while(head)coutdatanext;coutendl;nowtheitemsoflistare:59152099例例 用插入法生成一个有序链表用插入法生成一个有序链表 head9152053199head#includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s
98、;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);void showlist( const list * head ) cout now the items of list are: n ; while( head ) cout data next ; cout k;while(k!=0)head=insert(k);cink;showlist(head);/ 输出链表结点输出链表结点voidshowli
99、st(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutendl;nowtheitemsoflistare:59152099例例 用插入法生成一个有序链表用插入法生成一个有序链表 head9152053199head#includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(
100、head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);void showlist( const list * head ) cout now the items of list are: n ; while( head ) cout data next ; cout k;while(k!=0)head=insert(k);cink;showl
101、ist(head);/ 输出链表结点输出链表结点voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutendl;nowtheitemsoflistare:59152031例例 用插入法生成一个有序链表用插入法生成一个有序链表 head9152053199head#includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if
102、(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);void showlist( const list * head ) cout now the items of list are: n ; while( head ) cout data next ; cout k;wh
103、ile(k!=0)head=insert(k);cink;showlist(head);/ 输出链表结点输出链表结点voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutendl;nowtheitemsoflistare:59152031例例 用插入法生成一个有序链表用插入法生成一个有序链表 head9152053199head#includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s
104、=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);void showlist( const list * head ) cout now the items of list are: n ; while(
105、 head ) cout data next ; cout k;while(k!=0)head=insert(k);cink;showlist(head);/ 输出链表结点输出链表结点voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutendl;nowtheitemsoflistare:5915203199例例 用插入法生成一个有序链表用插入法生成一个有序链表 head9152053199head#includestructlistintdata;list*next;list*he
106、ad;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);void showlist( const list * head ) cout n
107、ow the items of list are: n ; while( head ) cout data next ; cout k;while(k!=0)head=insert(k);cink;showlist(head);/ 输出链表结点输出链表结点voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;coutendl;nowtheitemsoflistare:5915203199例例 用插入法生成一个有序链表用插入法生成一个有序链表 head9152053199head#includ
108、estructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);void
109、showlist( const list * head ) cout now the items of list are: n ; while( head ) cout data next ; cout k;while(k!=0)head=insert(k);cink;showlist(head);nowtheitemsoflistare:5915203199例例 用插入法生成一个有序链表用插入法生成一个有序链表 / 输出链表结点输出链表结点voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanex
110、t ;head = head-next ;coutendl;headhead9152053199headhead+head+；可以吗？为什么？可以吗？为什么？#includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q
111、=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;cout k ; while( k != 0 ) head = insert(k) ; cin k ; showlist( head ) ; 例例 用插入法生成一个有序链表用插入法生成一个有序链表 #includestructlistintdata;list*next;list*
112、head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);voidshowlist(constlist*head)coutnowthei
113、temsoflistare:n;while(head)coutdatanext;cout k ; while( k != 0 ) head = insert(k) ; cin k ; showlist( head ) ; voidmain()intk;head=NULL;cink;while(k!=0)head=insert(k);cink;showlist(head);例例 用插入法生成一个有序链表用插入法生成一个有序链表 #includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newli
114、st;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;cout
115、 k ; while( k != 0 ) head = insert(k) ; cin k ; showlist( head ) ; voidmain()int k ; head = NULL ; cin k ;while(k!=0)head=insert(k);cink;showlist(head);headk9例例 用插入法生成一个有序链表用插入法生成一个有序链表 #includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(
116、head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;cout k ; while( k != 0 ) head = i
117、nsert(k) ; cin k ; showlist( head ) ; voidmain()intk;head=NULL;cink;while( k != 0 ) head = insert(k) ; cin k ; showlist(head);k9head调用函数调用函数向链表插入结点向链表插入结点例例 用插入法生成一个有序链表用插入法生成一个有序链表 #includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head
118、=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;cout k ; while( k != 0 ) head = inser
119、t(k) ; cin k ; showlist( head ) ; voidmain()intk;head=NULL;cink;while( k != 0 ) head = insert(k) ; cin k ; showlist(head);k9head9例例 用插入法生成一个有序链表用插入法生成一个有序链表 #includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head)
120、;if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;cout k ; while( k != 0 ) head = insert(k) ; cin k ; showlist(
121、head ) ; voidmain()intk;head=NULL;cink;while( k != 0 ) head = insert(k) ; cin k ; showlist(head);k5head9例例 用插入法生成一个有序链表用插入法生成一个有序链表 #includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-nex
122、t=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;cout k ; while( k != 0 ) head = insert(k) ; cin k ; showlist( head ) ; voidmain()intk;h
123、ead=NULL;cink;while( k != 0 ) head = insert(k) ; cin k ; showlist(head);k5head59例例 用插入法生成一个有序链表用插入法生成一个有序链表 #includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(hea
124、d);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;cout k ; while( k != 0 ) head = insert(k) ; cin k ; showlist( head ) ; voidmain()intk;head=NULL;cink;while( k !
125、= 0 ) head = insert(k) ; cin k ; showlist(head);k15head59例例 用插入法生成一个有序链表用插入法生成一个有序链表 #includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-ne
126、xt;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;cout k ; while( k != 0 ) head = insert(k) ; cin k ; showlist( head ) ; voidmain()intk;head=NULL;cink;while( k != 0 ) head = insert(k)
127、; cin k ; showlist(head);k15head5915例例 用插入法生成一个有序链表用插入法生成一个有序链表 #includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(
128、p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;cout k ; while( k != 0 ) head = insert(k) ; cin k ; showlist( head ) ; voidmain()intk;head=NULL;cink;while( k != 0 ) head = insert(k) ; cin k ; showlist(he
129、ad);k31head5915例例 用插入法生成一个有序链表用插入法生成一个有序链表 #includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p
130、;q-next=s;return(head);q-next=s;return(head);voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;cout k ; while( k != 0 ) head = insert(k) ; cin k ; showlist( head ) ; voidmain()intk;head=NULL;cink;while( k != 0 ) head = insert(k) ; cin k ; showlist(head);k31head591531例例 用
131、插入法生成一个有序链表用插入法生成一个有序链表 #includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(he
132、ad);q-next=s;return(head);voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;cout k ; while( k != 0 ) head = insert(k) ; cin k ; showlist( head ) ; voidmain()intk;head=NULL;cink;while( k != 0 ) head = insert(k) ; cin k ; showlist(head);k20head591531例例 用插入法生成一个有序链表用插入法生成一个
133、有序链表 #includestructlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return
134、(head);voidshowlist(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;cout k ; while( k != 0 ) head = insert(k) ; cin k ; showlist( head ) ; voidmain()intk;head=NULL;cink;while( k != 0 ) head = insert(k) ; cin k ; showlist(head);k20head59152031例例 用插入法生成一个有序链表用插入法生成一个有序链表 #includestru
135、ctlistintdata;list*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);voidshowli
136、st(constlist*head)coutnowtheitemsoflistare:n;while(head)coutdatanext;cout k ; while( k != 0 ) head = insert(k) ; cin k ; showlist( head ) ; voidmain()intk;head=NULL;cink;while( k != 0 ) head = insert(k) ; cin k ; showlist(head);k99head59152031例例 用插入法生成一个有序链表用插入法生成一个有序链表 #includestructlistintdata;lis
137、t*next;list*head;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);voidshowlist(constlist*head
138、)coutnowtheitemsoflistare:n;while(head)coutdatanext;cout k ; while( k != 0 ) head = insert(k) ; cin k ; showlist( head ) ; voidmain()intk;head=NULL;cink;while( k != 0 ) head = insert(k) ; cin k ; showlist(head);k99head5915203199例例 用插入法生成一个有序链表用插入法生成一个有序链表 #includestructlistintdata;list*next;list*hea
139、d;list*insert(intnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);voidshowlist(constlist*head)coutnowtheitem
140、soflistare:n;while(head)coutdatanext;cout k ; while( k != 0 ) head = insert(k) ; cin k ; showlist( head ) ; k0head5915203199voidmain()intk;head=NULL;cink;while( k != 0 ) head = insert(k) ; cin k ; showlist(head);例例 用插入法生成一个有序链表用插入法生成一个有序链表 #includestructlistintdata;list*next;list*head;list*insert(in
141、tnum)list*s,*p,*q;s=newlist;s-data=num;s-next=NULL;if(head=NULL)head=s;return(head);if(head-datas-data)s-next=head;head=s;return(head);for(q=head,p=head-next;p;q=p,p=p-next)if(p-datas-data)s-next=p;q-next=s;return(head);q-next=s;return(head);voidshowlist(constlist*head)coutnowtheitemsoflistare:n;whi
142、le(head)coutdatanext;cout k ; while( k != 0 ) head = insert(k) ; cin k ; showlist( head ) ; voidmain()intk;head=NULL;cink;while(k!=0)head=insert(k);cink;showlist( head ) ;k0head5915203199例例 用插入法生成一个有序链表用插入法生成一个有序链表 4 4删除删除结点结点删除头结点12head357 4 4删除删除结点结点删除头结点p=head;head=head-next;deletep;12head357 4 4
143、删除删除结点结点删除头结点p=head;head=head-next;deletep;p12head357 4 4删除删除结点结点删除头结点p=head;head=head-next;deletep;p12head357 4 4删除删除结点结点删除头结点p=head;head=head-next;deletep;12head357 p4 4删除删除结点结点删除头结点p=head;head=head-next;deletep;12head357 p4 4删除删除结点结点删除头结点p=head;head=head-next;deletep;2head357 4 4删除删除结点结点删除结点*p12head357 4 4删除删除结点结点删除结点*p12head357 pqq-next=p-next;deletep;4 4删除删除结点结点删除结点*p12head357 pqq-next=p-next;deletep;4 4删除删除结点结点删除结点*p12head357 pqq-next=p-next;deletep;4 4删除删除结点结点删除结点*p12head357 pqq-next=p-next;deletep;4 4删除删除结点结点删除结点*p12head57 q-next=p-next;deletep;
