线性表的链式表示和实现44284

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,2,章 线性表,2.1,线性表的逻辑结构,2.2,线性表的顺序表示和实现,2.3,线性表的链式表示和实现,2.4,一元多项式的表示和相加,1,2.3,线性表的链式表示和实现,2.3.1,链表的表示,2.3.2,链,表的实现,2.3.3,一个带头结点的单链表类型,2.3.4,其它形式的链表,2,链式存储结构特点：,其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。,如何实现？,通过,指针,来实现！,让每个存储结点都包含两部分：,数据域,和,指针域,指针,数据,指针,数据,指针,或,样式：,数据域：,存储元素数值数据,指针域：,存储直接后继或者直接前驱的存储位置,设计思想：牺牲空间效率换取时间效率,2.3.1,链表的表示,3,链表存放示意图如下：,a,1,head,a,2,/,a,n,讨论,1,：,每个存储结点都包含两部分：数据域和,讨论,2,：,在单链表中，除了首元结点外，任一结点的,存储位置由,指示。,其直接前驱结点的链域的值,(2),与链式存储有关的术语,：,1,）结点,：,数据元素的存储映像。由数据域和指针域两部分组成；,2,）链表,：,n,个结点由,指针链,组成一个链表。它是线性表的链式存储映像,，,称为线性表的链式存储结构,。,只包含一个指针域的称为单链表或线性链表,指针域,4,3,）头指针、头结点和首元结点的区别,头指针,头结点,首元结点,a,1,head,a,2,info,a,n,首元结点,是指链表中存储线性表第一个数据元素,a,1,的结点。,头结点,是在链表的首元结点之前,附设,的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。,头指针,是指向链表中第一个结点（或为头结点、或为首元结点）的指针；,示意图如下：,5,讨论,2,：,在链表中设置,头结点,有什么好处？,讨论,1,：,如何表示,空表,？,因为任何元素结点都有前驱结点，而在做插入和删除操作时，都需修改其前驱结点的指针域，因此对首元结点可以统一处理。即简化插入和删除操作；,表头指针是指向头结点的非空指针，因此空表和非空表的处理一样。,无头结点时，当,头指针,的值为,空,时表示空表；,头指针,无头结点,头指针,头,结点,有头结点,有头结点时，当,头结点,的,指针域为空,时表示空表。,头结点不计入链表长度！,6,一个线性表的逻辑结构为：（,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,称：头指针,H,的值是,31,（,3,）举例,例,1,：,7,现有一个具有五个元素的线性表,L=23,，,17,，,47,，,05,，,31,，,若它以链接方式存储在下列,100,119,号地址,空间中，每个结点由数据（占,2,个字节,）和指针（占,2,个字节,）组成，如下图所示。,其中指针,X,，,Y,，,Z,的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？,Z,47,Y,31,V,23,X,17,U,05,100,119,104,108,116,112,116,NULL(0),100,108,112,答：,X=,Y=,Z=,首址,=,末址,=,。,例,2,：,8,讨论,:,链表的数据元素有,两个域,，不再是简单数据类型，编程时该如何表示？,因每个结点至少有两个分量，且数据类型通常不一致，所以要采用,结构,数据类型。,答：,设每个结点用变量,node,表示，其指针用,p,表示，两个分量分别用,data,和,*,next,表示，这两个分量如何赋值？,p,*next,data,node,方式,1,：直接表示为,node,.,data,a,；,node,.,next,=,q;,方式,2,：,p,指向结点首地址,p,-,data,=,a,;,p,-,next,=,q,;,方式,3,：,p,指向结点首地址,(*p),.,data,=,a,；,(*p),.,next,q;,9,单链表的抽象数据类型描述,如下,（参见教材,P28,）,：,typedef,struct,LNode,ElemType,data;,/,数据域,struct,LNode,*next;,/,指针域,LNode,*,LinkList,;,/,*,LinkList,为,Lnode,类型的指针,Q1,：,第一行的,LNode,与最后一行的,LNode,是不是一回事？,A1,：,不是。前者,LNode,是结构名，后者,LNode,是对整个,struct,类型的一种“缩写”，是一种“,新定义名,”，它只是对现有类型名的补充，而不是取代。,请,注意：,typedef,不可能创造任何新的数据类型，而仅仅是在原有的数据类型中命名一个新名字，其目的是使你的程序更易阅读和移植。,10,Q2,：,那为何两处要同名,(,LNode,和,LNode,）？,太不严谨了吧？,A2,：,同名是为了表述起来方便。因为描述的对象相同，方便阅读和理解。,Q3,：,结构体中间的那个,struct,LNode,是何意？,A3,：,在“缩写”,LNode,还没出现之前，只能用原始的,struct,LNode,来,进行变量说明。此处说明了指针分量的数据类型是,struct,LNode,。,返 回,11,2.3.2,链表的实现,（,1,）,单链表的存取,（,2,）,单链表的插入,（,3,）,单链表的删除,（,4,）单链表的建立,12,（,1,）单链表的存取,思路：,要存取第,i,个,数据元素，必须从头指针起一直找到该结点的指针,p,，,然后才能执行,p-data=new_value,。,修改第,i,个数据元素的操作函数可写为：,Status,GetElem_L,(LinkList,L,int,i,ElemType,e,),p,=L-next;j=1;,/,带头结点的链表,while(,p,&,j,next,;+j;,if (,!p,|,ji,)return ERROR;,/i,不合法,p-data=,e,;,/,若是读取则为：,e=p-data,;,return OK;,/,GetElem_L,缺点：,想寻找单链表中第,i,个元素，只能从头指针开始逐一查询（,顺藤摸瓜,），无法随机存取,。,13,在链表中第,i,个位置前插入一个元素,x,的示意图如下：,X,s,a,i-1,a,i,p,链表插入的核心语句：,Step 1：,s-next=p-next;,p-next,s-next,思考：,Step1,和,2,能互换么？,X,结点的生成方式：,s=(,Lnode,*),malloc(m,);,s-data=,x,;,s-next=?,a,i,a,i-1,p,插 入,X,（,2,）单链表的插入,Step2:p-next=s;,14,Status,ListInsert_L(LinkList,L,int,i,ElemType,e),/,LinstInsert_L,算法的时间复杂度为,:,O(ListLength(L,),p=L;j=0;,while,(p,&,j next;+j;,/,寻找第,i-1,个结点,if,(,!,p,|,j i-1),return,ERROR;,/,i,不合法,s=(,LinkList),malloc(sizeof(LNode,),s,-,data=e;,s-next=p-next;p-next=s;,/,插入,return,OK;,15,在链表中删除某元素,a,i,的示意图如下：,a,i+1,a,i-1,a,i,p,删除动作的核心语句（要借助辅助指针变量,q,）：,q=p-next;,/,首先,保存,a,i,的指针，靠它才能找到,a,i+1,p-next,(p-next)-next,q,（,3,）单链表的删除,P-next=q-next,；,/,将,a,i-1,与,a,i+1,两结点相连,淘汰,a,i,结点,free(q,);,16,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,个结点，并令,p,指向其前趋,if,(,!,(p-next)|j i-1),return,ERROR;,/,删除位置不合理,q=p-next;p-next=q-next;,/,删除并释放结点,e=q-data;,free(q);,return,OK;,17,空间效率分析,链表中每个结点都要增加一个指针空间，相当于总共增加了,n,个整型变量，空间复杂度为,O(n),。,在,n,个结点的单链表中要删除已知结点,*,P,，,需找到它的 ，其时间复杂度,。,前驱结点的地址,/,指针,O(n),练习：,18,操作步骤：,一、建立一个,“,空表,”,；,二、输入数据元素,a,n,，,建立结点并插入；,三、输入数据元素,a,n-1,，,建立结点并插入表头；,a,n,a,n,a,n-1,四、依次类推，直至输入,a,1,为止,。,（,4,）单链表的建立,例如：逆位序输入,n,个数据元素的值，建立带头结点的单链表。,链表是一个动态的结构，它不需要预先分配空间，因此生成链表的过程是一个结点,“,逐个插入,”,的过程。,19,void,CreateList_L(LinkList,&,L,int,n),/,逆序输入,n,个数据元素，建立带头结点的单链表,/,CreateList_L,算法的时间复杂度,为,:,O(Listlength(L,),L=(,LinkList,),malloc,(,sizeof,(,LNode,);,L-next=NULL;,/,先建立一个带头结点的单链表,for,(i=n;i 0;-i),p=(,LinkList,),malloc,(,sizeof,(,LNode,);,scanf,(,&,p,-data);,/,输入元素值,p-next=L-next;L-next=p;,/,插入,20,算法要求：,已知：,线性表,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,）,例：两个链表的归并（教材,P31,例）,算法设计,：,算法主要包括搜索、比较、插入三个操作：,搜索：,需要设立三个指针来指向,La,、,Lb,和,Lc,链表；,21,La,3,5,8,11,Lb,2,6,8,11,9,Pa,Pb,Pa,Pb,Pa,、,Pb,用于搜索,La,和,Lb,，,Pc,指向新链表当前结点。归并过程示意如下：,Lc,=La,Pb,Pa,Pa,Pb,比较：,比较,La,和,Lb,表中结点数据的大小；,插入：,将,La,和,Lb,表中数据较小的结点插入新链表,Lc,。,请注意链表的特点，仅改变指针便可实现数据的移动,即,“数据不动，指针动”,22,void,MergeList_L(LinkList,&,La,LinkList,&,Lb,LinkList,&,Lc,),/,已知单链线性表,La,和,L