数据结构单链表.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 线性表,链表,单链表,定义,特点,C,描述,基本形态,基本操作实现,一组数据项的集合，其中每个数据项都是一个结点的一部分，每个结点都包含指向下一个结点的链接（即,指针,）。,1.,数据元素在“,逻辑,关系上的,相邻,”用“,指针,”来表示。,2.,单链表 中访问数据元素时需从头开始“,顺序访问,”。,3.,比顺序表的优势在于，提供高效地,重排,数据项的能力。,a,1,a,2,a,3,a,4,a,n,L,单链表的,C,描述,typedef,struct,LNode,ElemType,data;/,数据域,struct,LNode,*,next;/,指针域,LNode,*LinkList,;,LinkList,L,；,/L,为单链表的头指针,头指针指向单链表中的,第一个结点,用指针表示链接，用结构体表示结点，结点是由数据项和链接组成的，链接是指向下一结点的指针。,单链表的基本形态,空表,非空表,为了操作方便，在第一个结点之前虚加一个“头结点”,哑元结点,L,L-next=NULL;,不允许删除操作,a,1,a,2,a,3,a,n,L,可以进行插入、删除操作,单链表基本操作,1,、初始化（动态分配）,Stutas,InitList(LinkList,&L),L=(LinkList,),malloc(sizeof(LNode,);,if(!L)exit(overflow,);,L-next=NULL;,return OK;,L,头结点,L,21,18,30,75,42,56,p,p,p,j,1,2,3,单链表基本操作,2,、取单链表中指定位序的数据元素,演示例子：取单链表中第,3,个元素值,取元素的基本操作,单链表是一种,“,顺序访问,”,的结构，为找第,i,个数据元素，必须先找到第,(i-1,),个数据元素。,1.,指针,p,始终指向单链表中第,j,个结点；,2.,移动指针，比较,j,和,i,，相等则找到。,Status,GetElem_L(LinkList,L,int,i,ElemType,&,e),/L,是带头结点的链表的头指针，以,e,返回第,i,个元素,/GetElem_L,算法,时间复杂度,为,:,O(ListLength(L,),p=L-next;j=1;,/,p,指向第一个结点，,j,为计数器,while(p j,+;,/,顺指针向后查找，直到,p,指向第,i,个元素,/,或,p,为空,if,(,p&j,=i,),e=p-data;,return,OK;,/,取得第,i,个元素,else,/,第,i,个元素不存在,return,ERROR;,与顺序表相比，链表不适合于查找第,i,个元素的操作。,单链表基本操作,3,、插入（在第,i,个元素前插入,e,）,单链表中,：,a,i-1,有序对,改变为,和,e,a,i,a,i-1,在单链表中插入结点只需要修改指针。若要在第,i,个结点之前插入元素，修改的是第,(i-1),个结点的指针。,Status,ListInsert_L(LinkList,&L,int,i,ElemType,e),/,L,为带头结点的单链表的头指针，本算法,/,在链表中第,i,个结点之前插入新的元素,e,/LinstInsert_L,算法的时间复杂度,为,:,O(ListLength(L,),else return ERROR;,p=L;j=0;,while,(p,&,j next;+j;,/,寻找第,(i-1),个结点,if,(p,&,j=i-1),s=(LinkList,),malloc,(,sizeof,(LNode,);,/,生成新结点,s,-,data=e;,s-next=p-next;p,-,next=s;/,插入,return,OK;,e,a,i-1,a,i,a,i-1,s,p,有序对,和,改变为,a,i-1,a,i,a,i+1,a,i-1,单链表基本操作,4,、删除（第,i,个元素）,在单链表中删除第,i,个结点时，要找到单链表中第,(i-1,),个结点，修改其指向后继的指针。,a,i-1,a,i,a,i+1,a,i-1,q=p-next;p-next=q-next;,e=q-data;,free(q);,p,q,Status,ListDelete_L(,LinkList,&L,int,i,ElemType,&,e),/,删除以,L,为头指针,(,带头结点,),的单链表中第,i,个结点,/ListDelete_L,算法的时间复杂度,为,:,O(ListLength(L,),p=L;j=0;,while,(p-next,&,j next;+j;,/,寻找第,i-1,个结点，并令,p,指向它。,if,(p-next&j=i-1),q=p-next;p-next=q-next;,/,删除并释放结点,e=q-data;,free(q);,return,OK;,else,return,ERROR;/,删除位置不合理,对比单链表和顺序表的基本操作,插入和删除的简单性是链表存在的理由,只修改相关结点的指向保持链表特性,单链表的访问方式是顺序访问,查找第,i,个数据项的代价，沿着链表，一个一个结点地访问，直到找的这个数据项,算法时间复杂度：,O(ListLength(L,),单链表基本操作,5,、清空,while,(,L-next,),p=L-next;,L-next=p-next;,free(p,);,算法时间复杂度：,O(ListLength(L,),单链表基本操作,6,、销毁,while(L,),p=L-next;,free(L,);,L=p;,单链表基本操作,7,、判空,if(L,-next=NULL),return TRUE;,else,return FALSE;,8,、求表长,int ListLength(LinkList,L),p=L-next;,i=0;,while(p,),i+;,p=p-next;,return i;,单链表基本操作,9,、搜索（查找元素）,p=L-next;,i=1;,while(p&p,-data!=e),p=p-next;i+;,if(p,)return i;,else return 0;,从,第一个结点,开始搜索,搜索成功，返回位序；否则，返回,0,单链表的应用,1.,建立单链表,链表是一个动态结构，它不需要预分配空间，因此生成链表的过程是一个结点,“,逐个插入,”,的过程。,逆序建立单链表,顺序建立单链表,新结点插入在头结点的后面，作为重排链表后的第一个结点,新结点插入在尾结点的后面，作为重排链表后的最后一个结点,逆序建立单链表,操作步骤,建立一个带头结点的空单链表；,输入数据元素,a,i,，建立新结点,p,，并把,p,插入在头结点之后成为第一个结点。,重复执行,步，直到完成单链表的建立。,a,1,a,1,a,2,void,CreateList_N(LinkList,&,L,int,n),/,逆序输入,n,个数据元素，建立带头结点的单链表,/CreateList_L,算法的时间复杂度,为,:,O(Listlength(L,),L=(LinkList,),malloc,(,sizeof,(LNode,);,L-next=NULL;,/,先建立一个带头结点的单链表,for,(i=1;i data);/,输入元素值,p-next=L-next;L-next=p;/,插入,顺序建立单链表,操作步骤,建立一个带头结点的空单链表；,输入数据元素,a,i,，建立新结点，并把其插入在尾结点,p,之后成为最后一个结点。,重复执行,步，直到完成单链表的建立。,a,1,p,a,1,p,p,a,2,p,a,3,p,p,p,a,n,顺序建立单链表：即新元素插入表尾,L=(LinkList)malloc(sizeof(LNode,);,L-next=NULL;,/,先建立一个带头结点的单链表,时间复杂度为,O(n),p=L;,for(i=1;idata);,q-next=p-next;,p-next=q;,p=q;,单链表的应用,2.,归并有序链表,归并有序单链表,La,和有序单链表,Lb,得到有序单链表,Lc,。,链表结点之间的关系是通过指针指向建立起来的，所以用链表进行合并不需要另外开辟存储空间，可以直接利用原来两个表的存储空间，合并过程中只需要把,La,和,Lb,两个链表中的结点重新进行链接即可。,单链表的应用,归并思想：,需要设立,3,个指针,pa,、,pb,、,pc,，其中,pa,和,pb,分别指向,La,和,Lb,中当前待比较插入的结点，而,pc,指向,Lc,中当前最后一个结点（,Lc,的表头结点设为,La,的表头结点）。指针的初值为：,pa,和,pb,分别指向,La,和,Lb,表中的第一个结点，,pc,指向空表,Lc,中的头结点。通过比较指针,pa,和,pb,所指向的元素的值，依次从,La,或,Lb,中“摘取”元素值较小的结点插入到,Lc,的最后，当其中一个表变空时，只要将另一个表的剩余段链接在,pc,所指结点之后即可。,归并有序单链表,void,MergeList_L,(LinkList,&,La,LinkList,&,Lb,LinkList,&,Lc,),pa=La-next;pb,=Lb-next,;/pa,和,pb,初值指向第一个结点,Lc,=La;,/,用,La,的头作为,Lc,的头结点,pc=Lc,;,/pc,初值指向,Lc,的头结点,while(,pa&pb,)/La,和,Lb,均未到达表尾，依次“摘取”两表中值较小的结点插入到,Lc,的最后,if(pa,-datadata),pc-next=pa;,pc=pa;,pa=pa,-next;,else,pc-next=pb,;,pc=pb,;,pb=pb,-next;,pc-next=pa?pa:pb;free(Lb,);,算法时间复杂度：,O(m+n,),算法空间复杂度：,O(1),单链表的应用,3.,稀疏多项式的运算,稀疏多项式可以抽象成一个线性表。稀疏多项式的相加过程和归并两个有序表的过程极其类似。不同之处在于，多项式的相加过程在比较两个多项式指数时要考虑三种情况（等于、小于、大于）。链式存储结构更加灵活，合并过程空间复杂度为,O(1),。,多项式,A(x,)=7+3x+9x,8,+5x,17,和多项式,B(x,)=8x+22x,7,-9x,8,7 0,5 17,A,3 1,9 8,8 1,B,22 7,-9 8,单链表的应用,稀疏多项式的相加,规则：对于两个多项式中所有指数相同的项，对应系数相加，若其和不为零，则作为,“,和多项式,”,中的一项插入到,“,和多项式,”,链表中去；对于两个多项式中指数不相同的项，则将指数值较小的项插入到,“,和多项式,”,链表中去。,“,和多项式,”,链表中的结点无需生成，而应该从两个多项式链表中摘取。,7 0,5 17,11 1,22 7,A,稀疏多项式相加,typedef struct PNode,float coef,;,int expn,;,struct PNode,*next;,PNode,*Polynomial;,用单链表表示多项式时，每个链表结点存储多项式中的一个非零项，包括系数,（,coef,）,和指数,（,expn,）,两个数据域以及一个指针域,（,next,）,。,稀疏多项式相加,假设头指针,pa,和,pb,的单链表分别为多项式,A,和,B,的存储结构，指针,p1,和,p2,分别指向,A,和,B,中当前进行比较的某个结点，则逐一比较两个结点中的指数项，对于指数相同的项，对应系数相加，若其和不为零，则将插入到,“,和多项式,”,链表中去；对于指数不相同的项，则通过比较将指数较小的项插入到,“,和多项式,”,链表中去。,稀疏多项式相加,void AddPolyn(Polynomial&pa,Polynomial&pb,),p1=pa-next;p2=pb,-next;,p3=pa;,while(p1&p2),if(p1-expn=p2-expn,),sum=p1-coef+p2-coef,;,if(sum!=0),p1-coef,=sum;,p3-next=p1;,p3=p1;,p1=p1,-next;,r=p2;,p2=p2,-next;,free(r,);,else,稀疏多项式相加,r=p1;p1=p1-next;free(r,);,r=p2;p2=p2-next;free(r,);,else if(p1-expnexpn,),p3-next=p1;p3=p1;p1=p1-next;,else,p3-next=p2;p3=p2;p2=p2-next;,p3-next=p1?p1:p2;,free(pb,);,单链表的应用,稀疏多项式的创建,多项式的创建方法类似于链表的创建方法，区别在于多项式链表是一个有序表，每项的位置要经过比较才能确定。首先初始化一个空链表用来表示多项式，然后逐个输入各项，通过比较，找到第一个大于该输入项指数的项，将输入项插入到此项的前面，这样即可保证多项式链表的有序性。,稀疏多项式的创建,void CreatePolyn(Polynomial&p,int,n),p=(Polynomial)malloc(sizeof(PNode,);,p-next=NULL;,for(i=1;icoef,&s-expn,);,pre=p;,q=p-next;,while(q&q-expnexpn,),pre=q;,q=q-next;,s-next=q;,pre-next=s;,