数据结构 第2章 线性表2-链式表示和实现

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,2,章 线性表,数据结构讲义,-,链式表示和实现,2.3.1,链表的表示,特点：,用一组,任意,的存储单元存储线性表的数据元素,利用,指针,实现了用不相邻的存储单元存放逻辑上相邻的元素,每个数据元素,ai,，,除存储本身信息外，还需存储其直接后继的信息,结点,数据域：元素本身信息,指针域：指示直接后继的存储位置,2.3,线性表的链式表示和实现,ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG,H,例 线性表,(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG),43,13,1,NULL,37,7,19,25,数据域,指针域,LI,QIAN,SUN,WANG,WU,ZHAO,ZHENG,ZHOU,存储地址,1,7,13,19,25,31,37,43,31,H,头指针,与链式存储有关的术语：,1,、结点：,数据元素的存储映像。由数据域和指针域两部分组成；,2,、链表：,n,个结点由,指针链,组成一个链表。它是线性表的链式存储映像,，,称为线性表的链式存储结构,。,3,、单链表、双链表、多链表、循环链表,：,结点只有一个指针域的链表，称为,单链表,或,线性链表,；,有两个指针域的链表，称为,双链表,；,有多个指针域的链表，称为,多链表,；,首尾相接的链表称为,循环链表,。,a,1,head,a,2,a,n,head,循环链表,示意图：,何谓,头指针、头结点和首元结点,？,头指针,是指向链表中第一个结点（或为,头结点,或,为首元结点,）的指针。,单链表可由一个头指针唯一确定。,头结点,是在链表的,首元结点,之前,附设,的一个结点；数据域内只放空表标志和表长等信息,;,首元结点,是指链表中存储线性表第一个数据元素,a,1,的结点。,头指针,头,结点,首元,结点,a,1,一个线性表的逻辑结构为：（,ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG,），,其存储结构用单链表表示如下，,请问其,头指针,的,值,是多少？,存储地址,数据域,指针域,1,LI,43,7,QIAN,13,13,SUN,1,19,WANG,NULL,25,WU,37,31,ZHAO,7,37,ZHENG,19,43,ZHOU,25,例,：,答：,头指针,是指向链表中第一个结点的指针，因此关键是要寻找,第一个结点,的,地址,。,7,ZHAO,H,31,头指针的值是,31,上例链表的逻辑结构示意图有以下,两种形式,：,ZHAO,QIAN,LI,SUN,ZHOU,WU,ZHENG,/,WANG,H,ZHAO,QIAN,LI,SUN,ZHOU,WU,ZHENG,/,WANG,H,区别：,无头结点,有头结点,答：,讨论,1,.,在链表中设置,头结点,有什么好处？,讨论,2,.,如何表示,空表,？,头结点,即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对,空表、非空表,的情况以及对,首元结点,进行统一处理，编程更方便。,答：,无头结点时，,当头指针的值为空,时表示空表；,有头结点时，,当头结点的指针域为空,时表示空表。,头指针,头指针,头,结点,无头结点,有头结点,typedef,struct,Lnode,ElemType,data;,/,数据域,struct,Lnode,*next;,/,指针域,Lnode,*,LinkList,;,/*,LinkList,为,Lnode,类型的指针,教材,P28,对于单链表的,抽象,描述,:,结构类型的,C,语言表示法,介绍三个有用的库函数（都在,中）：,sizeof,(,x,),计算变量,x,的长度；,malloc,(,m,),开辟,m,字节长度的地址空间，并返回这段空间的首地址；,free(,p,),释放指针,p,所指变量的存储空间，即彻底删除一个变量。,链表的实现,1.,单链表的插入,2.,单链表的删除,3.,链表的合并,实例,1,（和顺序表一样）：一条记录有学号和成绩两个数据项，先不考虑有序的情况编写程序记录数据。,1.,单链表的插入,在链表中插入一个元素的示意图如下：,x,s,b,a,p,a,b,p,插入步骤（即核心语句）：,Step 1：,s-next=p-next;,Step 2：,p-next=s；,p-next,s-next,元素,x,结点应预先生成：,S=(,LinkList,),malloc,(m);,S-data=x;,S-next=p-next,Status,ListInsert,(,LinkList,&L,int,i,ElemType,e),p=L-next;j=1;,while,(p,&,jnext;+j;,if(!p|ji-1),return,ERROR;,S=(,LinkList,),malloc,(,sizeof,(,Lnode,);,S-data=x;,S-next=p-next;,P-next=s;,return,OK;,单链表结点插入的演示,2.,单链表的删除,在链表中删除某元素的示意图如下：,c,a,b,p,删除步骤（即核心语句）：,q=p-next;,/,保存,b,的,指针，靠它才能指向,c,p-next=q-next;,/a,、,c,两结点相连,free(q),；,/,删除,b,结点，彻底释放,p-next,思考：省略,free(q),语句,行不行？,(p-next)-next,Status,ListDelete,(,LinkList,&L,int,i,ElemType,&e),p=L-next;j=1;,while,(p,&,jnext;+j;,if(!p|ji-1),return,ERROR;,Q=p-next;,P-next=q-next;,E=q-data;,Free(q);,return,OK;,单链表结点的删除演示,3.,两个链表的归并（教材,P31,）,算法要求：,已知：,线性表,A,、,B,，,分别由,单链表,LA,LB,存储，其中数据元素按值,非递减有序,排列，,要求：,将,A,，,B,归并,为一个新的线性表,C,C,的数据元素仍按值非递减排列 。设线性表,C,由,单链表,LC,存储。,假设：,A=,（,3,，,5,，,8,，,11,），,B=,（,2,，,6,，,8,，,9,，,11,）,预测：,合并后,C=,（,2,3,5,6,8,8,9,11,，,11,）,用链表可表示为：,3,5,11,/,8,La,2,6,11,/,8,Lb,9,2,3,6,5,Lc,8,头,结点,算法分析：,算法主要包括：,搜索、比较、插入,三个操作：,搜索：,需要,两个指针,搜索两个链表；,比较：,比较结点数据域中数据的大小；,插入：,将两个结点中数据,小的结点插入新链表,。,La,3,5,8,11,Lb,2,6,8,11,9,Pa,Pb,Pa,Pb,Pa,、,Pb,用于搜索,La,和,Lb,，,Pc,指向新链表当前结点,Lc,Pa,3,Pc,Pa,5,Pc,11,Pc,2,Pb,Pc,Pa,算法实现：,Void,MergeList,_L(,LinkList,&La,LinkList,&Lb,LinkList,&,Lc,),/,按值排序的单链表,LA,LB,，,归并为,LC,后也按值排序,free(Lb);,/,释放,Lb,的头结点,/,MergeList,_L,pc-next,=pa?pa:pb;,/,插入剩余段,while(pa&pb)/,将,pa,、,pb,结点按大小依次插入,C,中,if,(pa-datadata),pc-next,=pa;,pc,=pa;pa=pa-next;,else,pc-next,=pb;,pc,=pb;pb=,pb,-next,pa=La-next;pb=Lb-next;,Lc,=pc,=La,；,/,初始化,其它链表形式,答：能。只要将表中最后一个结点的指针域指向头结点即可,(,P-next=head;,),。,这种形成环路的链表称为,循环链表,。,特别：带头结点的,空,循环链表样式,H,参见教材,P35,特点：,1,、从任一结点出发均可找到表中其他结点。,2,、操作仅有 一 点与单链表不同：,循环条件,单链表,-p=NULL,或,p-next=NULL,循环链表,-p=head,或,p-next=head,讨论,1,：链表能不能首尾相连？怎样实现？,讨论,2,：单链表只能查找结点的直接后继，能不能查找直接前驱？如何实现？,答：能。只要把单链表再多开一个指针域即可,(,例如用,*,next,和*,prior,;,),。,双向链表在非线性结构（如树结构）中将大量使用。,prior,data,next,这种有两个指针的链表称为,双向链表,。其特点是可以双向查找表中结点。参见教材,P3539,。,特别：带头结点的,空,双向链表样式：,链表的运算效率分析,1.,查找,因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为,O,(n),。,时间效率分析,2.,插入和删除,因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为,O,(1),。,但是，如果要在单链表中进行,前插,或,删除,操作，由于要从头查找前驱结点，所耗时间复杂度为,O,(n),。,空间效率分析,链表中每个结点都要增加一个指针空间，相当于总共增加了,n,个整型变量，空间复杂度为,O,(n),。,作业,用链表编写完整程序实现以下内容：,一条记录有学号和成绩两个数据项，建立两个有序表（按成绩由大到小），并合并成一个有序表。第一个表输入的数据如下（学号，成绩）：,(1,70),(2,85),(3,75),(4,90),；第二个表输入的数据如下：,(5,60),(6,80),(7,76),(8,50),。,