第04讲循环链表

1、 一、循环链表一、循环链表 二、双向链表二、双向链表 三、链表的应用三、链表的应用难点难点HaHbpapbqbqa（1）Ha的指数小的指数小（2）Hb的指数小的指数小（3）Ha与与Hb的指数相等的指数相等1）系数相加不为）系数相加不为02）系数相加为）系数相加为01、已知一个单链表，编写一个删除其值为、已知一个单链表，编写一个删除其值为x的的结点的前趋结点的结点的前趋结点的。1)若若x在第一个在第一个Position nextPtr-data=x2)若若x在中间在中间 nextPtr-next-data=x3)若若x不存在不存在 nextPtr-next=NULLheada1a2a3a4tmp

2、PtrnextPtr整个链表形成一个环，从表中任一结整个链表形成一个环，从表中任一结点出发均可找到表中其它结点。点出发均可找到表中其它结点。（1）表中最后一个结点的指针指向第一个结点或）表中最后一个结点的指针指向第一个结点或表头结点（如有表头结点的话）。表头结点（如有表头结点的话）。（2）循环链表的运算与线性链表基本一致。但两）循环链表的运算与线性链表基本一致。但两者判断是否到表尾的条件不同。者判断是否到表尾的条件不同。headhead非空循环链表非空循环链表空循环链表空循环链表rearrear简单循环链表类简单循环链表类注意与单链表算法实现的区别注意与单链表算法实现的区别两个单循环链表（用尾

3、指针表示）的链接示意图两个单循环链表（用尾指针表示）的链接示意图rarbp思考思考: : 如何将其合并如何将其合并? ?p=rb-next; rb-next=ra-next;ra-next=p-next;几个方法的实现几个方法的实现几个方法的实现几个方法的实现几个方法的实现几个方法的实现几个方法的实现几个方法的实现例例2.5 用循环链表求解约瑟夫问题用循环链表求解约瑟夫问题例例2.5 用循环链表求解约瑟夫问题用循环链表求解约瑟夫问题例例2.5 用循环链表求解约瑟夫问题用循环链表求解约瑟夫问题单链表的每个结点再增加一个指向其单链表的每个结点再增加一个指向其前趋的指针域前趋的指针域 back，这样

4、形成的链表有两条不这样形成的链表有两条不同方向的链，称之为双（向）链表。同方向的链，称之为双（向）链表。双链表一般也由头指针双链表一般也由头指针head唯一确定。唯一确定。每一结点均有：每一结点均有： 数据域（数据域（data） 左链域（左链域（back）指向前趋结点）指向前趋结点. 右链域（右链域（next）指向后继。）指向后继。 是一种对称结构（既有前趋，又有后继）。是一种对称结构（既有前趋，又有后继）。 双向链表结点结构双向链表结点结构struct DblNode ElemType data; DblNode * back; DblNode * next; ; 双向链表举例双向链表举例双

5、向链表结点的插入双向链表结点的插入597pq nnewPtrnewPtr-back = nextPtrback = nextPtr-back newPtr-next=nexPtrback newPtr-next=nexPtrn用一条语句实现即：用一条语句实现即：newPtr=new DblNode(e,tmpPtr,nextPtrnewPtr=new DblNode(e,tmpPtr,nextPtr); );nnextPtrnextPtr-back-next = newPtr nextPtr-back=newPtrback-next = newPtr nextPtr-back=newPtrne

6、xtPtrtmpPtrnewPtr双向链表结点的删除双向链表结点的删除 p 597ntmpPtrtmpPtr-backback-next = tmpPtrnext = tmpPtr-nextnextntmpPtrtmpPtr-nextnext-back = tmpPtrback = tmpPtr-backbacktmpPtr在链表结构中保存当前位置和元素个数在链表结构中保存当前位置和元素个数 线性表的三种链式存储结构特点：线性表的三种链式存储结构特点：实现较一致，处实现较一致，处理亦简单，但效率低下。理亦简单，但效率低下。原因：原因：许多应用程序是按顺序处理线性表的中数据许多应用程序是按顺序处

7、理线性表的中数据元素的，也就是处理完一个数据元素后再处理下一元素的，也就是处理完一个数据元素后再处理下一个数据元素，也可能要几次引用同一个数据元素，个数据元素，也可能要几次引用同一个数据元素，比如在访问下一个数据元素之前做比如在访问下一个数据元素之前做GetElem和和SetElem操作，对于这类应用程序，前面的链表实现操作，对于这类应用程序，前面的链表实现效率低下。效率低下。解决：解决：在链表结构中保存当前位置和元素个数。在链表结构中保存当前位置和元素个数。 假设一个单循环链表，其结点含有三个域假设一个单循环链表，其结点含有三个域back、data、next。其中。其中data为数据域；为数

8、据域；back为指针域，它的值为空指针（为指针域，它的值为空指针（NULL）；）；next为为指针域，它指向后继结点。请设计算法，将此指针域，它指向后继结点。请设计算法，将此表改成双向循环链表。表改成双向循环链表。【西安电子科技大学【西安电子科技大学 1999软考软考 五（五（10分）分）】 a b z La a b z Lavoid StoDouble(SimpleLinkList &la) while(La-next-back=NULL) La-next-back=La; La=La-next; 算法中没有设置变量记住单循环链表的起始结点，算法中没有设置变量记住单循环链表的起始结点，至少省

9、去了一个指针变量。当算法结束时，至少省去了一个指针变量。当算法结束时，La恢复到指恢复到指向刚开始操作的结点，这是本算法的优点所在。向刚开始操作的结点，这是本算法的优点所在。haqpa-14 151 7-3 0（1）pa所指结点的指数要减所指结点的指数要减1（2）pa所指结点的系数所指结点的系数=系数系数*指数指数（3）若）若pa所指结点的指数为所指结点的指数为0，则要删除该结点，则要删除该结点void derivative(SimpleCircLinkList &ha) Node *q, *pa; q=ha; pa=ha-next; while( (1) ) if( (2) ) (3) ;

10、delete pa; pa= (4) ; else pa-coef (5) ; pa-exp (6) ; q=(7) ; pa= (8) ; void derivative(SimpleCircLinkList &ha) Node *q, *pa; q=ha; pa=ha-next; while( pa!=ha ) /pa-exp!=-1 if( pa-exp=0 ) q-next=pa-next ; delete pa; pa= q-next ; else pa-coef *=pa-exp ; pa-exp - - ; q=pa ; pa= pa-next ; 一线性表存储在带头结点的双向循

11、环链表中，一线性表存储在带头结点的双向循环链表中，L为头指针。如下算法：为头指针。如下算法：（1）说明该算法的功能。（）说明该算法的功能。（2）在空缺处填写）在空缺处填写相应的语句。相应的语句。 【北京理工大学【北京理工大学 1999 第二部分第二部分 数据结构数据结构 7 （8分）分）】void unknown (BNODETP &L) p=L-next; q=p-next; r=q-next； while (q!=L) while (p!=L) & (p-dataq-data) p=p-back； q-back-next=r；(1) ； q-next=p-next；q-back=p； (2

12、) ；(3) ； q=r；p=q-back； (4) ； void unknown (BNODETP &L) p=L-next; q=p-next; r=q-next； while (q!=L) while (p!=L) & (p-dataq-data) p=p-back； q-back-next=r； r-back=q-back ； q-next=p-next；q-back=p； p-next-back=q ； p-next=q ； q=r；p=q-back； r=r-next； 将双循环链表结点的数据按值从小到大排序。将双循环链表结点的数据按值从小到大排序。设有一头指针为设有一头指针为L的

13、带有表头结点的非循环双向链表，的带有表头结点的非循环双向链表，其每个结点中除有其每个结点中除有back（前驱指针），（前驱指针），data（数据）（数据）和和next（后继指针）域外，还有一个访问频度域（后继指针）域外，还有一个访问频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进在链表被起用前，其值均初始化为零。每当在链表中进行一次行一次Locate(L,x)运算时，令元素值为运算时，令元素值为x的结点中的结点中freq域的值增域的值增1，并使此链表中结点保持按访问频度非增，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相（递减）的顺序排列，同

14、时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的试编写符合上述要求的Locate(L,x)运算的算法，该运运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。算为函数过程，返回找到结点的地址，类型为指针型。【清华大学【清华大学 考研考研 1997 二（二（10分）分） 】查找是否存在查找是否存在x不存在则结束程序不存在则结束程序若存在若存在频度增频度增1将将x结点删除结点删除向前找合适的插入位置向前找合适的插入位置将将x结点插入结点插入分析分析DLinkNode *Locate(DLinkNode &L, ElemType &x) DLinkNode *p=L-next, q; while(p!=NULL & p-data!=x) p=p-next; if(p=NULL) coutfreq+; p-next-back=p-back; p-back-next=p-n