第4课-循环链表及应用.课件.ppt

1、一、链表的其它几种形式： 静态链表（理解） 循环链表（掌握） 双向链表（掌握插入/ 删除算法）二、链表的应用（了解） 一元高次多项式的存储 集合类型的实现 有些高级程序设计语言中没有指针类型，但为了实现链表结构，有些高级程序设计语言中没有指针类型，但为了实现链表结构，应用其优点，可以通过定义一个结构体数组实现类似于应用其优点，可以通过定义一个结构体数组实现类似于“链表链表” 的的存储结构。存储结构。 该数组中的每个元素类似与线性表的该数组中的每个元素类似与线性表的“结点结点”，只是将结点中，只是将结点中的指针改为下标，用于指出后继在数组中的序号（相对位置），从的指针改为下标，用于指出后继在数组

2、中的序号（相对位置），从而形成静态链表结构。而形成静态链表结构。 由于它是由于它是利用数组定义利用数组定义的，数组的长度在编译时就确定，因此的，数组的长度在编译时就确定，因此在整个运算过程中链表存储空间的大小不会发生变化，故称这种结在整个运算过程中链表存储空间的大小不会发生变化，故称这种结构为构为静态链表。静态链表。 2.3.1 静态链表静态链表 #define MaxSize 1000 /*链表的最大长度链表的最大长度*/ /*定义存储数据元素的定义存储数据元素的“结点结点”类型类型 Snode*/ typedef struct ElemType data; /*存储数据元素的值存储数据元素

3、的值*/ int cur ; /*存储元素直接后继的下标存储元素直接后继的下标*/ Snode; /*定义静态链表类型定义静态链表类型SlinkList结构体数组类型结构体数组类型*/ typedef Snode SlinkListMaxSize; 理解：理解： 静态链表中的用于存储每个数据元素的静态链表中的用于存储每个数据元素的结点也结点也有数据域有数据域datadata和指向和指向下个元素存储位置的域下个元素存储位置的域curcur，不过这里的，不过这里的curcur是个下标是个下标, ,是相对数组第一是相对数组第一个元素的偏移个元素的偏移, ,属于相对地址属于相对地址. .但是所起的作用

4、与线性链表中的指针但是所起的作用与线性链表中的指针nextnext相同，因此称为静态指针。相同，因此称为静态指针。 为了简化链表操作算法为了简化链表操作算法, ,静态链表也可以设表头结点静态链表也可以设表头结点. . 设有变量设有变量s s定义定义: : Slinklist Slinklist s; / s; /* *s s 为一个静态链表为一个静态链表 * */ / 则则s0s0表示头结点表示头结点,s0.cur,s0.cur指示指示第一个元素结点的位置第一个元素结点的位置 si.datasi.data 表示第表示第i i个数据元素的值个数据元素的值 si.cursi.cur 指示指示第第i

5、 i个元素的直接后继个元素的直接后继, ,即第即第i+1i+1个元素的存储位置个元素的存储位置 如图（如图（a) a) 在链表没有使用前，各个结点已经形成一个链，变量在链表没有使用前，各个结点已经形成一个链，变量AVAV指示链表的首地址指示链表的首地址( (头结点头结点) )。由。由AVAV指向的链表称为可利用空间表，指向的链表称为可利用空间表，可用于管理结点的分配和回收。可用于管理结点的分配和回收。012345678-12345678-1datanextheadAVAVAV未用空间创建头结点插入链表插入多个后链表状态(a)(b)(c)(d)30306078258612325501234567

6、812345678-1datanextAV0123456781-1345678-1datanexthead01234567862387-1415datanexthead303060782582122386 带头结点的静态链表操作的 算法逻辑与线性链表相似,不过有以下区别: 1.需要用户自己实现类似于malloc和free函数的操作. 2.线性表中向后移动指针的操作:p=p-next 改为k =si.cur 算法2.14:管理分配给链表的空闲结点 算法2.15:实现结点的分配，即从空白表获取一个结点 算法2.16:实现结点的回收，即将删除的结点链接到空白表 循环链表循环链表(Circular L

7、inked List)是另一种形式的链式存储是另一种形式的链式存储结构。它将单链表中最后一个结点的指针指向链表的头结点，结构。它将单链表中最后一个结点的指针指向链表的头结点，使整个链表头尾相接形成一个环形。这样，使整个链表头尾相接形成一个环形。这样，从链表中任一结从链表中任一结点出发，顺着指针链都可找到表中其它结点点出发，顺着指针链都可找到表中其它结点。循环链表的最。循环链表的最大特点是不增加存储量，只是简单地改变一下最后一个结点大特点是不增加存储量，只是简单地改变一下最后一个结点的指针指向，就可以使操作更加方便灵活。的指针指向，就可以使操作更加方便灵活。2.3.2 循环单链表循环单链表hea

8、d.a1a2aian（a ） 带头结点的空循环链表（b ） 带头结点的循环链表head循环链表结构示意图循环链表结构示意图 带头结点的单循环链表的操作算法和带头结点的单链表带头结点的单循环链表的操作算法和带头结点的单链表的操作算法相似，差别仅在于算法中的判断循环终止的条件的操作算法相似，差别仅在于算法中的判断循环终止的条件不同。循环链表中：不同。循环链表中： 指针指针p指向表尾的条件：指向表尾的条件：p-next=head 表空条件：表空条件：head-next=head 例：例： 求线性表长度求线性表长度Getlen(L)函数、查找运算函数、查找运算locate(L,x)函数、链表元素输出运

9、算函数、链表元素输出运算displist(L)函数中，循环是函数中，循环是否进行的条件由否进行的条件由p!=NULL改为改为p!=L; 此外，还可用尾指针表示循环链表此外，还可用尾指针表示循环链表 。 尾指针尾指针tail指向最后一结点，沿最后一个结点的指针指向最后一结点，沿最后一个结点的指针又可立即找到链表的第一个结点。在实际应用中，使又可立即找到链表的第一个结点。在实际应用中，使用尾指针来代替头指针进行某些操作往往会更简单。用尾指针来代替头指针进行某些操作往往会更简单。【例例1】将两个循环链表首尾相接进行合并，将两个循环链表首尾相接进行合并， La、Lb分别为两个循环链表的分别为两个循环链

10、表的尾指针尾指针，对两个单循环，对两个单循环链表链表La，Lb进行的连接操作，是将进行的连接操作，是将Lb的第一个数据结的第一个数据结点接到点接到La的尾部。的尾部。head指向合并后的链表的指向合并后的链表的头结点头结点。【解】算法思路：【解】算法思路： 在循环链表中若采用尾指针在循环链表中若采用尾指针La，Lb来标识，则时间性来标识，则时间性能将变为能将变为O(1)。其连接过程如图所示。其连接过程如图所示。LbLa(a)连接前p = L a-next;q=Lb-next.a1a2aian.b1b2bibnLaLb.a1a2aian.b1b2bibn(b)连接后L a - next=q-ne

11、xt;Lb-next=p;free(q)headpq图图2-14 两个循环链表首尾相接进行合并两个循环链表首尾相接进行合并 操作如下：操作如下：/*La,Lb为带头结点的循环单链表的尾指针为带头结点的循环单链表的尾指针*/LinkList listMerge(LinkList La,LinkList Lb) LNode *p, *q; p=La-next; /*p指向第一个链表的头结点指向第一个链表的头结点*/ q=Lb-next; /*q指向第二个链表的头结点指向第二个链表的头结点*/ La-next=q-next; /*将链表将链表Lb链接到链接到La的尾部的尾部*/ Lb-next=p;

12、 /*设置链表的尾指针设置链表的尾指针*/ free(q); /*释放多余的头结点释放多余的头结点*/ return Lb; /*返回新链表的尾指针返回新链表的尾指针*/2.3.3 双向链表双向链表 双向链表结点的定义如下：双向链表结点的定义如下： typedef struct Dnode ElemType data; struct DNode *prior; struct DNode *next; Dnode,*DuLinkList; 双向链表是用两个指针表示结点间的逻辑关系。即增加了一个双向链表是用两个指针表示结点间的逻辑关系。即增加了一个指向其直接前驱的指针域，这样形成的链表有两条不同方

13、向的链，指向其直接前驱的指针域，这样形成的链表有两条不同方向的链，前驱和后继，因此称为双链表。前驱和后继，因此称为双链表。 在双链表中，根据已知结点查找其直接前驱结点可以和查找其在双链表中，根据已知结点查找其直接前驱结点可以和查找其直接后继结点一样方便。这里也仅讨论带头结点的双链表。仍假设直接后继结点一样方便。这里也仅讨论带头结点的双链表。仍假设数据元素的类型为数据元素的类型为ElemType。priordatanexta1a2an.(a)空双向链表（b )非 空双向链表headhead带头结点的双向链表带头结点的双向链表 如果指针变量如果指针变量 p 指向了一个结点，则通过指向了一个结点，则

14、通过 p-next 可以直接访问该结点可以直接访问该结点的后继结点，也可以由指针的后继结点，也可以由指针p-prior直接访问它的前驱结点。这种结构极直接访问它的前驱结点。这种结构极大地简化了某些操作。大地简化了某些操作。 在双向链表中也可采用与单链表类似的方法，设置头结点。在双向链表中也可采用与单链表类似的方法，设置头结点。用头指针标识链表的存在。用头指针标识链表的存在。 注意：指针操作序列，操作注意：指针操作序列，操作必须在操作必须在操作之前完成。之前完成。ai-1xs-data=xsaipai-1saip(a)插入前的状态x(b)插入过程关键语句：s -prior=p-prior;s -

15、next=p;p -prior=s;s -prior-next=s;q -next-prior=p;.ai-1aiqai+1ai-1aiqai+1(a)删除前状态( b） 删除过程.关键语句：p -next=q-next;f ree(q)pp 在双向链表中找到删除位置的前一个结点，由在双向链表中找到删除位置的前一个结点，由p指向它，指向它，q指向要删除的指向要删除的结点。删除操作如下：结点。删除操作如下：将将*p的的next域改为指向待删结点域改为指向待删结点*q的后继结点；的后继结点；若若*q不是指向最后的结点，则将不是指向最后的结点，则将*q之后结点的之后结点的prior域指向域指向*p。

16、 注意：在双向链表中进行插入和删除时，对指针的修改需要同时修改注意：在双向链表中进行插入和删除时，对指针的修改需要同时修改结点的前驱指针和后继指针的指向。结点的前驱指针和后继指针的指向。 2.4.1 一元多项式表示一元多项式表示 链式存储结构的链式存储结构的典型应用之一是典型应用之一是在高等数学的在高等数学的多项式方面。本节主要多项式方面。本节主要讨论采用链表结构表示的一元多项式的操作处理。在数学上，一个一讨论采用链表结构表示的一元多项式的操作处理。在数学上，一个一元多项式元多项式Pn(x) 可以表示为可以表示为 ： Pn(x)=a0+a1x+a2x2+anxn (最多有最多有n+1项项) a

17、ixi是多项式的第是多项式的第i项（项（0in）。其中）。其中ai为系数，为系数，x为自变量，为自变量，i为指为指数。多项式中有数。多项式中有n+1个系数，而且是线性排列。个系数，而且是线性排列。 一个多项式由多个一个多项式由多个aixi ( (1im) )项组成，每个多项式项采用以下项组成，每个多项式项采用以下结点存储：结点存储：coefexpnnextcoefexpnnext 其中，其中，coef数据域存放系数数据域存放系数ci； expn数据域存放指数数据域存放指数ei； next域是一个链域，指向下一个结点。域是一个链域，指向下一个结点。由此，一个多项式可以表示成由这些结点链接而成的单

18、链表由此，一个多项式可以表示成由这些结点链接而成的单链表( (假设该单假设该单链表是带头结点的单链表链表是带头结点的单链表) )。 typedef struct node double coef; / /系数为双精度型系数为双精度型 i int expn; / /指数为正整型指数为正整型 struct node *next; /指针域指针域polynode; 在顺序存储结构中，采用基类型为在顺序存储结构中，采用基类型为polynode的数组表示多项式的数组表示多项式中的各项。如中的各项。如pi.coef和和pi.expn分别表示多项式中第分别表示多项式中第i项的系数和项的系数和指数。但多项式中

19、，其中一些项的系数会为指数。但多项式中，其中一些项的系数会为0。如多项式。如多项式A(x)=a0+a1x+a2x2+ a6x6+ a9x9+a15x15 中包括中包括16项，其中只有项，其中只有6项系数项系数不为不为0。顺序存储结构可以使多项式相加算法变得简单。但是，当。顺序存储结构可以使多项式相加算法变得简单。但是，当多项式中存在大量的零系数时，这种方式就会浪费大量的存储空间。多项式中存在大量的零系数时，这种方式就会浪费大量的存储空间。为了有效利用存储空间，可用为了有效利用存储空间，可用有序链表有序链表存储结构表示多项式。存储结构表示多项式。 在链式存储结构中，多项式中每一个非零项构成链表中

20、的一个在链式存储结构中，多项式中每一个非零项构成链表中的一个结点，而对于系数为零的项则不需要表示，因此可以节省存储空间。结点，而对于系数为零的项则不需要表示，因此可以节省存储空间。 2.4.2 一元多项式相加一元多项式相加 假设用单链表表示多项式：假设用单链表表示多项式：A(x)=12+7x+8x10+5x17 ，B(x)=8x+15x7-6x10，头指针，头指针Ah与与Bh分别指向这两个链表，如图分别指向这两个链表，如图2-21所示：所示： 对两个多项式进行相加运算，其结果为对两个多项式进行相加运算，其结果为C(x)= 12+15x+15 x7+2x10+5x17。如图。如图2-22所示。所

21、示。12071810517Ah8115760Bh合并以前的链表合并以前的链表151157210517012Ch合并以后的链表合并以后的链表 对两个一元多项式进行相加操作的运算规则是：假设指针对两个一元多项式进行相加操作的运算规则是：假设指针qa和和qb分别指向多项式分别指向多项式A(x)和和B(x)中当前进行比较的某个结点，中当前进行比较的某个结点，则需比较两个结点数据域的指数项，有三种情况：则需比较两个结点数据域的指数项，有三种情况：(1) 指针指针qa所指结点的指数值指针所指结点的指数值指针qb所指结点的指数值时，则保所指结点的指数值时，则保留留qa指针所指向的结点指针所指向的结点，qa指

22、针后移；指针后移；(2) 指针指针qa所指结点的指数值指针所指结点的指数值指针qb所指结点的指数值时，则将所指结点的指数值时，则将qb指针所指向的结点插入到指针所指向的结点插入到qa所指结点前，所指结点前，qb指针后移；指针后移；(3) 指针指针qa所指结点的指数值指针所指结点的指数值指针qb所指结点的指数值时，将两所指结点的指数值时，将两个结点中的系数相加。若和不为零，则修改个结点中的系数相加。若和不为零，则修改qa所指结点的系数所指结点的系数值，同时释放值，同时释放qb所指结点；反之，从多项式所指结点；反之，从多项式A (x)的链表中删除的链表中删除相应结点，并释放指针相应结点，并释放指针

23、qa和和qb所指结点。所指结点。多项式相加算法多项式相加算法用有序表的合并算法实现：用有序表的合并算法实现：struct polynode *add_poly(struct polynode *Ah,struct polynode *Bh) struct polynode *qa,*qb,*s,*r,*Ch; qa=Ah-next;qb=Bh-next; /qa和和qb分别指向两个链表的第一结点分别指向两个链表的第一结点 r=qa;Ch=Ah; /将链表将链表Ah作为相加后的结果链表作为相加后的结果链表 while(qa!=NULL&qb!=NULL) /两链表均非空两链表均非空 if (qa

24、-exp=qb-exp) /两者指数值相等两者指数值相等 x=qa-coef+qb-coef; if (x!=0) /相加后系数不为零时相加后系数不为零时 qa-coef=x;r-next=qa;r=qa; s=qb+;free(s);qa+; else /相加后系数为零时相加后系数为零时 s=qa+; free(s); s=qb+; free(s); else if (qa-expexp) /多项式多项式Ah的指数值小的指数值小 r-next=qa; r=qa;qa+; else /多项式多项式Bh的指数值小的指数值小 r-next=qb; r=qb;qb+; if (qa=NULL) r-

25、next=qb; else r-next=qa; /链接链接Ah或或Bh中的剩余结点中的剩余结点return (Ch); 本章介绍了线性表的逻辑结构及它的两种存储结构：顺本章介绍了线性表的逻辑结构及它的两种存储结构：顺序表和链表。这两种表各有短长，在实际应用中应根据问题序表和链表。这两种表各有短长，在实际应用中应根据问题的要求和性质来选择使用。的要求和性质来选择使用。通过前面的讨论可知：顺序存储有三个优点：通过前面的讨论可知：顺序存储有三个优点：(1) 方法简单，各种高级语言中都有数组，容易实现；方法简单，各种高级语言中都有数组，容易实现；(2) 不用为表示结点间的逻辑关系而增加额外的存储开销

26、；不用为表示结点间的逻辑关系而增加额外的存储开销；(3) 具有按元素序号随机访问的特点。具有按元素序号随机访问的特点。两大缺点：两大缺点：(1)插入插入/删除操作平均移动大约表中一半的元素删除操作平均移动大约表中一半的元素 (2)(2)需要预先分配足够大的存储空间。若估计过大，容易导需要预先分配足够大的存储空间。若估计过大，容易导致顺序表后部大量闲置；预先分配过小，又会造成溢出。致顺序表后部大量闲置；预先分配过小，又会造成溢出。 顺序表的存储空间是静态分配的，在程序执行前必须明确顺序表的存储空间是静态分配的，在程序执行前必须明确规定它的存储规模。若线性表长度规定它的存储规模。若线性表长度n变化

27、较大，则存储规模很变化较大，则存储规模很难预先正确估计。估计太大将造成空间浪费，估计太小又将使难预先正确估计。估计太大将造成空间浪费，估计太小又将使空间溢出机会增多。所以当对线性表的长度或存储规模难以估空间溢出机会增多。所以当对线性表的长度或存储规模难以估计时，不宜采用顺序存储结构。顺序表的存储密度为计时，不宜采用顺序存储结构。顺序表的存储密度为1 1。 链表不用事先估计存储规模，是动态分配。只要内存空间链表不用事先估计存储规模，是动态分配。只要内存空间尚有空闲，就不会产生溢出。因此，当线性表的长度变化较大，尚有空闲，就不会产生溢出。因此，当线性表的长度变化较大，难以估计其存储规模时，以采用动

28、态链表作为存储结构为好。难以估计其存储规模时，以采用动态链表作为存储结构为好。但链表的存储密度较低。存储密度是指一个结点中数据元素所但链表的存储密度较低。存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比。显然链式存储占的存储单元和整个结点所占的存储单元之比。显然链式存储结构的存储密度是小于结构的存储密度是小于1的。的。 随机存取结构，就是对表中任一结点都可在随机存取结构，就是对表中任一结点都可在O(1)时间内直接取时间内直接取得。若对线性表主要做查找，很少做插入和删除操作时，采用顺得。若对线性表主要做查找，很少做插入和删除操作时，采用顺序存储结构为宜；而在链表中按序号访

29、问的时间性能为序存储结构为宜；而在链表中按序号访问的时间性能为O(n)。所。所以，如果经常做的运算是按序号访问数据元素，显然顺序表优于以，如果经常做的运算是按序号访问数据元素，显然顺序表优于链表。链表。 而在顺序表中做插入、删除操作时，要平均移动表中一半的而在顺序表中做插入、删除操作时，要平均移动表中一半的元素；尤其是当每个结点的信息量较大时，移动结点的时间开销元素；尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观，这一点不应忽视。在链表中的任何位置上进行插入就相当可观，这一点不应忽视。在链表中的任何位置上进行插入和删除，都只需要修改指针。对于频繁进行插入和删除的线性表，和删除，都

30、只需要修改指针。对于频繁进行插入和删除的线性表，宜采用链表做存储结构。若表的插入和删除主要发生在表的首尾宜采用链表做存储结构。若表的插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。两端，则宜采用尾指针表示的单循环链表。一、基础知识题1. 请说明在线性链表中设置头结点的意义。请说明在线性链表中设置头结点的意义。2. 顺序表有哪些优点？请分析在什么情况下使用顺序表较好。顺序表有哪些优点？请分析在什么情况下使用顺序表较好。3. 请分析链式结构的优缺点。请分析链式结构的优缺点。一、思考与练习（1）顺序结构线性表的特点是）顺序结构线性表的特点是_，在顺序表中插入一个元素，平均需要移动在

31、顺序表中插入一个元素，平均需要移动_个元素，移动个元素，移动个数与个数与_有关。但是，在顺序表中进行查找比较有关。但是，在顺序表中进行查找比较方便，可以实现方便，可以实现_查找。查找。（2）在单链表中，逻辑上相邻的元素物理上）在单链表中，逻辑上相邻的元素物理上_，在，在表中插入或删除一个元素只需表中插入或删除一个元素只需_无须移动元素，但是无须移动元素，但是查找链表中的元素都必须从查找链表中的元素都必须从_开始，只能进行开始，只能进行_查查找。找。（3）带头结点的线性链表为空的条件是）带头结点的线性链表为空的条件是_，带头结点的循环链表为空的条件是带头结点的循环链表为空的条件是_。1. 设线性

32、表设线性表A和和B为递增有序的单链表，试编写算法，将二表归为递增有序的单链表，试编写算法，将二表归并为一个递减有序的线性表，并利用原来的结点空间存放新表并为一个递减有序的线性表，并利用原来的结点空间存放新表 Linklist MerageSort(Linklist La,Linklist Lb) 2. 设计一算法，将设计一算法，将带头结点的带头结点的线性链表进行逆置。线性链表进行逆置。 即逻辑关系为即逻辑关系为(a,b,c,d,e) 的表，逆置后变为的表，逆置后变为(e,d,c,b,a) LinkList ReverList(Lnode *Head)status InsertElem(DuLi

33、nkList L,int i, ElemType e) DNode *p=L,*s; int pos=0; /*找待插入结点的位置找待插入结点的位置i，令变量，令变量p指向它指向它*/ while (p & posnext; pos+; if (p=null| posi) return error; /*插入位置插入位置i非法非法*/ /*生成新结点生成新结点,并填充数据并填充数据*/ s=(DNode *)malloc(sizeof(DNode); s-data=e; s-next=p; s-prior=p-prior; /*修改新结点的前驱的修改新结点的前驱的next 域指向域指向s*/ s-prior-next=s; p-prior=s; return ok;