第4课-循环链表及应用

本课内容一、链表的其它几种形式：静态链表（理解）循环链表（掌握）双向链表（掌握插入/删除算法）二、链表的应用（了解）一元高次多项式的存储集合类型的实现

有些高级程序设计语言中没有指针类型，但为了实现链表结构，应用其优点，可以通过定义一个结构体数组实现类似于“链表”的存储结构。该数组中的每个元素类似与线性表的“结点”，只是将结点中的指针改为下标，用于指出后继在数组中的序号（相对位置），从而形成静态链表结构。由于它是利用数组定义的，数组的长度在编译时就确定，因此在整个运算过程中链表存储空间的大小不会发生变化，故称这种结构为静态链表。

2.3.1静态链表静态链表的类型定义

#defineMaxSize1000/*链表的最大长度*//*定义存储数据元素的“结点”类型——Snode*/

typedef

struct

{ElemTypedata;/*存储数据元素的值*/

intcur;/*存储元素直接后继的下标*/}Snode;

/*定义静态链表类型SlinkList—结构体数组类型*/

typedef

Snode

SlinkList[MaxSize];

理解：静态链表中的用于存储每个数据元素的结点也有数据域data和指向下个元素存储位置的域cur，不过这里的cur是个下标,是相对数组第一个元素的偏移,属于相对地址.但是所起的作用与线性链表中的指针next相同，因此称为静态指针。为了简化链表操作算法,静态链表也可以设表头结点.

设有变量s定义:

Slinklists;/*s为一个静态链表*/

则s[0]表示头结点,s[0].cur指示第一个元素结点的位置

s[i].data

表示第i个数据元素的值

s[i].cur

指示第i个元素的直接后继,即第i+1个元素的存储位置

如图（a)在链表没有使用前，各个结点已经形成一个链，变量AV指示链表的首地址(头结点)。由AV指向的链表称为可利用空间表，可用于管理结点的分配和回收。∧∧∧∧∧∧带头结点的静态链表操作的算法逻辑与线性链表相似,不过有以下区别:1.需要用户自己实现类似于malloc和free函数的操作.2.线性表中向后移动指针的操作:p=p->next

改为k=s[i].cur算法2.14:管理分配给链表的空闲结点算法2.15:实现结点的分配，即从空白表获取一个结点算法2.16:实现结点的回收，即将删除的结点链接到空白表静态链表的操作实现算法2.14将链表空间初始化为一个空白链表

/*将数组space的各分量链成一空白链表，space[0].cur为头指针*/

voidInitSpaceSL(SLinkListspace)

{

inti;

for(inti=0;i<MAXSIZE-1;++i)

space[i].cur=i+1;

/*置链表结束标志,cur为0表示尾结点*/

space[MAXSIZE-1].cur=0;

}

算法2.15——malloc函数

/*若备用空间链表非空，则返回分配的结点下标，否则返回0

int

Malloc_SL(SLinkListspace)

{

inti=space[0].cur;/*获取空白链表第一个结点的下标*/

if(i>0)/*备用空间不为空*/

space[0].cur=space[i].cur;/*从表中摘下第一个结点*/

returni;

}

算法2.16——将下标为k的空闲结点回收到备用链表

voidFree_SL(SLinkListspace,intk)

{

space[k].cur=space[0].cur;/*链接到头结点后*/

space[0].cur=k;

}

循环链表(CircularLinkedList)是另一种形式的链式存储结构。它将单链表中最后一个结点的指针指向链表的头结点，使整个链表头尾相接形成一个环形。这样，从链表中任一结点出发，顺着指针链都可找到表中其它结点。循环链表的最大特点是不增加存储量，只是简单地改变一下最后一个结点的指针指向，就可以使操作更加方便灵活。2.3.2循环单链表循环链表结构示意图带头结点的单循环链表的操作算法和带头结点的单链表的操作算法相似，差别仅在于算法中的判断循环终止的条件不同。循环链表中：

指针p指向表尾的条件：p->next=head

表空条件：head->next=head

例：求线性表长度Getlen(L)函数、查找运算locate(L,x)函数、链表元素输出运算displist(L)函数中，循环是否进行的条件由p!=NULL改为p!=L;

此外，还可用尾指针表示循环链表。尾指针tail指向最后一结点，沿最后一个结点的指针又可立即找到链表的第一个结点。在实际应用中，使用尾指针来代替头指针进行某些操作往往会更简单。【例1】将两个循环链表首尾相接进行合并，

La、Lb分别为两个循环链表的尾指针，对两个单循环链表La，Lb进行的连接操作，是将Lb的第一个数据结点接到La的尾部。head指向合并后的链表的头结点。【解】算法思路：在循环链表中若采用尾指针La，Lb来标识，则时间性能将变为O(1)。其连接过程如图所示。图2-14两个循环链表首尾相接进行合并

操作如下：/*La,Lb为带头结点的循环单链表的尾指针*/LinkList

listMerge(LinkList

La,LinkListLb){

LNode*p,*q;p=La->next;

/*p指向第一个链表的头结点*/q=Lb->next;

/*q指向第二个链表的头结点*/La->next=q->next;

/*将链表Lb链接到La的尾部*/Lb->next=p;

/*设置链表的尾指针*/free(q);/*释放多余的头结点*/returnLb;

/*返回新链表的尾指针*/}2.3.3双向链表

双向链表结点的定义如下：

typedef

struct

Dnode{

ElemTypedata;

struct

DNode*prior;

struct

DNode*next;}Dnode,*DuLinkList;双向链表是用两个指针表示结点间的逻辑关系。即增加了一个指向其直接前驱的指针域，这样形成的链表有两条不同方向的链，前驱和后继，因此称为双链表。在双链表中，根据已知结点查找其直接前驱结点可以和查找其直接后继结点一样方便。这里也仅讨论带头结点的双链表。仍假设数据元素的类型为ElemType。双向链表结点示意图带头结点的双向链表如果指针变量p指向了一个结点，则通过p->next可以直接访问该结点的后继结点，也可以由指针p->prior直接访问它的前驱结点。这种结构极大地简化了某些操作。

在双向链表中也可采用与单链表类似的方法，设置头结点。用头指针标识链表的存在。双向链表的插入过程如图表示：

注意：指针操作序列，操作①必须在操作③之前完成。在双向链表中找到删除位置的前一个结点，由p指向它，q指向要删除的结点。删除操作如下：①将*p的next域改为指向待删结点*q的后继结点；②若*q不是指向最后的结点，则将*q之后结点的prior域指向*p。

注意：在双向链表中进行插入和删除时，对指针的修改需要同时修改结点的前驱指针和后继指针的指向。

双向链表的删除过程：

2.4线性表的应用

——

一元多项式表示及计算2.4.1一元多项式表示链式存储结构的典型应用之一是在高等数学的多项式方面。本节主要讨论采用链表结构表示的一元多项式的操作处理。在数学上，一个一元多项式Pn(x)可以表示为：

Pn(x)=a0+a1x+a2x2+…+anxn

(最多有n+1项)

aixi是多项式的第i项（0≤i≤n）。其中ai为系数，x为自变量，i为指数。多项式中有n+1个系数，而且是线性排列。一个多项式由多个aixi(1≤i≤m)项组成，每个多项式项采用以下结点存储：

其中，coef数据域存放系数ci；

expn数据域存放指数ei；

next域是一个链域，指向下一个结点。由此，一个多项式可以表示成由这些结点链接而成的单链表(假设该单链表是带头结点的单链表)。

typedef

structnode{doublecoef;//系数为双精度型

int

expn;//指数为正整型

structnode*next;//指针域}polynode;

在顺序存储结构中，采用基类型为polynode的数组表示多项式中的各项。如p[i].coef和p[i].expn分别表示多项式中第i项的系数和指数。但多项式中，其中一些项的系数会为0。如多项式A(x)=a0+a1x+a2x2+a6x6+a9x9+a15x15

中包括16项，其中只有6项系数不为0。顺序存储结构可以使多项式相加算法变得简单。但是，当多项式中存在大量的零系数时，这种方式就会浪费大量的存储空间。为了有效利用存储空间，可用有序链表存储结构表示多项式。在链式存储结构中，多项式中每一个非零项构成链表中的一个结点，而对于系数为零的项则不需要表示，因此可以节省存储空间。

2.4.2一元多项式相加

假设用单链表表示多项式：A(x)=12+7x+8x10+5x17，B(x)=8x+15x7-6x10，头指针Ah与Bh分别指向这两个链表，如图2-21所示：对两个多项式进行相加运算，其结果为C(x)=12+15x+15x7+2x10+5x17。如图2-22所示。合并以前的链表合并以后的链表对两个一元多项式进行相加操作的运算规则是：假设指针qa和qb分别指向多项式A(x)和B(x)中当前进行比较的某个结点，则需比较两个结点数据域的指数项，有三种情况：(1)指针qa所指结点的指数值＜指针qb所指结点的指数值时，则保留qa指针所指向的结点，qa指针后移；(2)指针qa所指结点的指数值＞指针qb所指结点的指数值时，则将qb指针所指向的结点插入到qa所指结点前，qb指针后移；(3)指针qa所指结点的指数值＝指针qb所指结点的指数值时，将两个结点中的系数相加。若和不为零，则修改qa所指结点的系数值，同时释放qb所指结点；反之，从多项式A(x)的链表中删除相应结点，并释放指针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->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);}

}

elseif(qa->exp<qb->exp)//多项式Ah的指数值小

{r->next=qa;r=qa;qa++;}else//多项式Bh的指数值小

{r->next=qb;r=qb;qb++;}}if(qa==NULL)r->next=qb;elser->next=qa; //链接Ah或Bh中的剩余结点return(Ch);}

2.5小结：顺序表和链表的比较本章介绍了线性表的逻辑结构及它的两种存储结构：顺序表和链表。这两种表各有短长，在实际应用中应根据问题的要求和性质来选择使用。通过前面的讨论可知：顺序存储有三个优点：(1)方法简单，各种高级语言中都有数组，容易实现；(2)不用为表示结点间的逻辑关系而增加额外的存储开销；(3)具有按元素序号随机访问的特点。两大缺点：(1)插入/删除操作平均移动大约表中一半的元素(2)需要预先分配足够大的存储空间。若估计过大，容易导致顺序表后部大量闲置；预先分配过小，又会造成溢出。1．基于空间的考虑顺序表的存储空间是静态分配的，在程序执行前必须明确规定它的存储规模。若线性表长度n变化较大，则存储规模很难预先正确估计。估计太大将造成空间浪费，估计太小又将使空间溢出机会增多。所以当对线性表的长度或存储规模难以估计时，不宜采用顺序存储结构。顺序表的存储密度为1。链表不用事先估计存储规模，是动态分配。只要内存空间尚有空闲，就不会产生溢出。因此，当线性表的长度变化较大，难以估计其存储规模时，以采用动态链表作为存储结构为好。但链表的存储密度较低。存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比。显然链式存储结构的存储密度是小于1的。2．基于时间的考虑

随机存取结构，就是对表中任一结点都可在O(1)时间内直接取得。若对线性表主要做查找，很少做插入和删除操作时，采用顺序存储结构为宜；而在链表中按序号访问的时间性能为O(n)。所以，如果经常做的运算是按序号访问数据元素，显然顺序表优于链表。而在顺序表中做插入、删除操作时，要平均移动表中一半的元素；尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观，这一点不应忽视。在链表中的任何位置上进行插入和删除，都只需要修改指针。对于频繁进行插入和删除的线性表，宜采用链表做存储结构。若表的插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。3．基于环境的考虑顺序表容易实现，任何高级语言中都有数组类型；链表的操作是基于指针的，其使用受语言环境的限制，这也是用户应该考虑的因素之一。两种存储结构各有特点。选择哪种结构根据实际使用的主要因素决定。通常“较稳定”的线性表选择顺序存储结构；而插入/删除频繁“动态性“较强的线性表宜选择链式存储结构。一、基础知识题1.请说明在线性链表中设置头结点的意义。2.顺序表有哪些优点？请分析在什么情况下使用顺序表较好。3.请分析链式结构的优缺点。一、思考与练习（1）顺序结构线性表的特点是__________________________，在顺序表中插入一个元素，平均需要移动________个元素，移动个数与_______________有关。但是，在顺序表中进行查找比较方便，可以实现________查找。（2）在单链表中，逻辑上相邻的元素物理上____________，在表中插入