C++ppt课件简单链表及其应用

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,C+ppt课件简单链表及其应用,1,C+ppt课件简单链表及其应用,特点,每个元素(表项)由结点(,Node,)构成。,线性结构,结点可以不连续存储,表可扩充,单链表(Singly Linked List),data,link,a0,a1,a2,a3,a4,head,存储数据元素,存储后继结点,存储地址,头结点,空指针,特点单链表(Singly Linked List)data,单链表的存储映像,free,(a),可利用存储空间,a0,a2,a1,a3,free,head,(b),经过一段运行后的单链表结构,2000,A,2114,B,2056,C,NULL,2000,2114,2056,head,单链表的存储映像free(a)可利用存储空间a0a2a1a,某单链表示意图如下：,头指针 head,110,hat,200,.,130,cat,135,135,eat,170,.,160,mat,Null,165,bat,130,170,fat,110,200,jat,205,205,lat,160,165,head,bat,cat,eat,mat,某单链表示意图如下：头指针 head110 h,用C+语言描述的一个简单的单链表如下：,struct node,int data;,/值域,node *next;,/链域,;,用C+语言描述的一个简单的单链表如下：,例.建立一个简单的链表，它由3个学生数据的结点组成，,输出各结点中的数据。,#define NULL 0 p=head;,struct student,do,long num;,coutnumscore;,float score;,p=p-next;,student *next;,while(p!=NULL);,;,void main()student a,b,c,*head,*p;,a.num=99101;a.score=89.5;,b.num=99103;b.score=90;,c.num=99107;c.score=85;,head=/*将结点a的起始地址赋给头指针head*/,a.next=/*将结点b的起始地址赋给a结点的next成员*/,b.next=,c.next=NULL;,例.建立一个简单的链表，它由3个学生数据的结点组成，,.,创建无序链,表,一个链表是有若干个结点连接而成，创建链表实际上是创建链表中的各个结点，并将它们连接起来。,函数nosorted_create()实现创建链表，其算法为：如果链表为空,(head=0),，则将该结点设置为表头；如果链表非空，则将该结点加入到链表的末尾。,.创建无序链表 一个链表是有若干个结点连接而成，创建链,将结点设置为表头的过程如下图所示：,pNew,head,(b),加入结点后,head=pNew;,pEnd=pNew;,pEnd,头结点,加入结点前,head=0;,pEnd=pNew;,pEnd,head,pNew,将结点设置为表头的过程如下图所示：pNewhead(,将结点加到链表末尾的过程如下图所示：,next,data,next,next,data,data,头结点,结点n,新结点,pNew,pEnd,head,(a)加入前,pNew=new node;,next,next,data,data,头结点,结点n,next,data,结点n+1,head,(b)加入后,pEnd-next=pNew;,pEnd=pNew;,pEnd,pNew,将结点加到链表末尾的过程如下图所示：nextdatanext,链表创建结束,next,0,next,next,data,data,头结点,结点n,新结点,pNew,pEnd,head,(a)结束前,pNew=new node;,(b)结束后,pEnd-next=0；,delete pNew;,next,0,data,data,头结点,结点n,pEnd,head,链表创建结束next0nextnextdatadata头结,.,链,表的输出,void ShowList(node*head),if(,head=0,),coutList is empty!endl;,return,;,node*temp=head;,cout now the items of list are:n;,while(temp!=0),cout datanext;,.链表的输出void ShowList(node*hea,.,链,表某个结点的访问,node*access(node*head,int n)if(head=0)coutnext=0)coutnext;,return count;,.统计链表结点的个数int node_count(node,.访问,链,表尾结点,node*accessTail(node*head),if(head=0),return 0;,node*temp=head;,while(temp-next!=0),temp=temp-next;,return temp;,.访问链表尾结点node*accessTail(node,.无序链表的插入,第一种情况：插入一个空表,head=newnode;,head-next=0;,（插入前）（插入后）,head,newnode,newnode,head,.无序链表的插入 第一种情况：插入一个空表（插入前）,第二种情况：在第一个结点前插入,newnode-next=head;,head=newnode;,（插入前）（插入后）,head,newnode,newnode,head,第二种情况：在第一个结点前插入（插入前）,第三种情况：在链表中间插入,newnode-next=current-next;,current-next=newnode；,(插入前)(插入后),newnode,current,newnode,current,第三种情况：在链表中间插入(插入前),第四种情况：在链表末尾插入,tail-next=newnode；,newnode-next=0;,(插入前)(插入后),newnode,newnode,tail,tail,第四种情况：在链表末尾插入(插入前),第一种情况,:删除表中第一个元素,pcur=head;head=head-next;delete pcur;,a,1,a,1,a,2,a,2,a,3,a,3,head,删除前,删除后,.无序链表结点的删除,head,第一种情况:删除表中第一个元素pcur=head;head,p,第二种情况,:删除表中或表尾元素,p-next=q-next;delete q;,a,i-1,a,i-1,a,i,a,i,a,i+1,a,i+1,q,删除前,删除后,p第二种情况:删除表中或表尾元素p-next=q-ne,.创建有序链表,所谓,有序链表,，是指链表中的结点按结点的某个成员的大小进行排列。,将一个结点插入到有序链表中时，为了保持有序性，要判断插入的位置。函数 insert_sort_node(node*&,node*&)。,通过上述插入函数，可以创建一个有序链表。,函数 sorted_create()。,.创建有序链表 所谓有序链表，是指链表中的结点按结点的某个,.链表的删除,void deletelist(node*&head),node*temp;,while(head),temp=head;,head=head-next;,delete temp;,.链表的删除void deletelist(node*&h,.无序链表的排序,void convert()int temp,i,j;node*pcur=head;for(i=1;idatapcur-next-data)temp=pcur-data;pcur-data=pcur-next-data;pcur-next-data=temp;pcur=pcur-next;pcur=head;,.无序链表的排序void convert()int,谢谢大家！,谢谢大家！,25,