第04讲循环链表

EssentialofLectureFour：一、循环链表二、双向链表三、链表的应用第四讲循环链表难点1HaHbpapbqbqa上一讲例题回顾:（1）Ha的指数小（2）Hb的指数小（3）Ha与Hb的指数相等1）系数相加不为02）系数相加为02上一讲作业回顾:1、已知一个单链表，编写一个删除其值为x的结点的前趋结点的程序。1)若x在第一个PositionnextPtr->data==x2)若x在中间nextPtr->next->data==x3)若x不存在nextPtr->next==NULLheada1a2a3a4……tmpPtrnextPtr3定义：整个链表形成一个环，从表中任一结点出发均可找到表中其它结点。特点：（1）表中最后一个结点的指针指向第一个结点或表头结点（如有表头结点的话）。（2）循环链表的运算与线性链表基本一致。但两者判断是否到表尾的条件不同。一、循环链表CircularLinkedList

4headhead非空循环链表空循环链表rearrear5template<classElemType>classSimpleCircLinkList

{protected://循环链表实现的数据成员: Node<ElemType>*head; //头结点指针//辅助函数

Node<ElemType>*GetElemPtr(intposition)const;

//返回指向第position个结点的指针

voidInit(); //初始化线性表简单循环链表类注意与单链表算法实现的区别6public://抽象数据类型方法声明及重载编译系统默认方法声明:

SimpleCircLinkList(); //无参数的构造函数

virtual~SimpleCircLinkList(); //析构函数

intLength()const; //求线性表长度

boolEmpty()const; //判断线性表是否为空

voidClear(); //将线性表清空

voidTraverse(void(*Visit)(const

ElemType&)) const; //遍历线性表

StatusCode

GetElem(intposition,ElemType&e) const; //求指定位置的元素

StatusCode

SetElem(intposition,constElemType &e); //设置指定位置的元素值7

StatusCode

Delete(intposition,ElemType&e);

//删除元素

StatusCode

Insert(intposition,constElemType&e);

//插入元素

SimpleCircLinkList(const

SimpleCircLinkList<ElemType>©);

//复制构造函数

SimpleCircLinkList<ElemType>&operator=(const

SimpleCircLinkList<ElemType>©);

//赋值语句重载};8两个单循环链表（用尾指针表示）的链接示意图rarbp①②③思考:如何将其合并?p=rb->next;rb->next=ra->next;ra->next=p->next;9template<classElemType>Node<ElemType>*SimpleCircLinkList<ElemType>::GetElemPtr(intposition)const//操作结果：返回指向第position个结点的指针{ if(position==0) { //头结点的序号为0 returnhead; } Node<ElemType>*tmpPtr=head->next;//用tmpPtr遍历线性表以查找第position个结点

int

curPosition=1; //tmpPtr所指结点的位置几个方法的实现10

while(tmpPtr!=head&&curPosition<position) //顺指针向后查找，直到tmpPtr指向第position个结点

{

tmpPtr=tmpPtr->next;

curPosition++; } if(tmpPtr!=head&&curPosition==position) { //查找成功

returntmpPtr; } else { //查找失败

returnNULL; }}几个方法的实现11template<classElemType>int

SimpleCircLinkList<ElemType>::Length()const//操作结果：返回线性表元素个数{

intcount=0; //计数器

for(Node<ElemType>*tmpPtr=head->next;tmpPtr!=head;tmpPtr=tmpPtr->next) { //用tmpPtr依次指向每个元素

count++; //对线性表的每个元素进行计数

} returncount;}几个方法的实现12template<classElemType>bool

SimpleCircLinkList<ElemType>::Empty()const//操作结果：如线性表为空，则返回true，否则返回false{ returnhead->next==head;}几个方法的实现13例2.5用循环链表求解约瑟夫问题14voidJosephus(intn,intm){

SimpleCircLinkList<int>la; //定义空循环链表

intposition=0; //报数到的人在链表中序号

intout,winer;

for(intk=1;k<=n;k++)

la.Insert(k,k); //建立数据域为1,2,..,n的循环链表

cout<<"出列者:";例2.5用循环链表求解约瑟夫问题15

for(inti=1;i<n;i++)//循环n-1次，让n-1个个出列

{ for(intj=1;j<=m;j++) //从1报数到m { position++; if(position>la.Length()) position=1; }

la.Delete(position--,out); //报数到m的人出列

cout<<out<<""; }

la.GetElem(1,winer);//剩下的一个人为优胜者

cout<<endl<<"优胜者:"<<winer<<endl;}例2.5用循环链表求解约瑟夫问题16定义：单链表的每个结点再增加一个指向其前趋的指针域back，这样形成的链表有两条不同方向的链，称之为双（向）链表。二、双向链表DoubleLinkedList

特点：双链表一般也由头指针head唯一确定。每一结点均有：数据域（data）

左链域（back）指向前趋结点.

右链域（next）指向后继。是一种对称结构（既有前趋，又有后继）。17前驱方向后继方向backdatanext双向链表结点结构struct

DblNode

{

ElemTypedata;

DblNode<ElemType>*back;

DblNode<ElemType>*next;……};18p==p->back->next==p->next->back双向链表举例p19双向链表结点的插入 597pq

①③④②newPtr->back=nextPtr->backnewPtr->next=nexPtr用一条语句实现即：newPtr=newDblNode<ElemType>(e,tmpPtr,nextPtr);nextPtr->back->next=newPtr

nextPtr->back=newPtrnextPtrtmpPtrnewPtr20双向链表结点的删除597tmpPtr->back->next=tmpPtr->nexttmpPtr->next->back=tmpPtr->backtmpPtr21在链表结构中保存当前位置和元素个数线性表的三种链式存储结构特点：实现较一致，处理亦简单，但效率低下。原因：许多应用程序是按顺序处理线性表的中数据元素的，也就是处理完一个数据元素后再处理下一个数据元素，也可能要几次引用同一个数据元素，比如在访问下一个数据元素之前做GetElem和SetElem操作，对于这类应用程序，前面的链表实现效率低下。解决：在链表结构中保存当前位置和元素个数。22三、链表的应用1、假设一个单循环链表，其结点含有三个域back、data、next。其中data为数据域；back为指针域，它的值为空指针（NULL）；next为指针域，它指向后继结点。请设计算法，将此表改成双向循环链表。【西安电子科技大学1999软考五（10分）】23∧a∧b∧z∧……La

a

b

z

……La24voidStoDouble(SimpleLinkList<ElemType>&la){

while(La->next->back==NULL){La->next->back=La;La=La->next;}}算法中没有设置变量记住单循环链表的起始结点，至少省去了一个指针变量。当算法结束时，La恢复到指向刚开始操作的结点，这是本算法的优点所在。252、一元稀疏多项式以单循环链表按降幂排列，结点有三个域，系数域coef、指数域exp和指针域next；现对链表求一阶导数，链表的头指针为ha，头结点的exp域为-1。【南京理工

2000（10分）】haqpa-1……41517-30（1）pa所指结点的指数要减1（2）pa所指结点的系数=系数*指数（3）若pa所指结点的指数为0，则要删除该结点26voidderivative(SimpleCircLinkList&ha){Node<ElemType>*q,*pa;q=ha;pa=ha->next;while((1)){if((2)){(3);deletepa;pa=(4);}else{pa->coef

(5);pa->exp(6);q=(7);pa=(8);}}}272、参考答案voidderivative(SimpleCircLinkList&ha){Node<ElemType>*q,*pa;q=ha;pa=ha->next;while(pa!=ha)//pa->exp!=-1{if(pa->exp==0){q->next=pa->next;deletepa;

pa=q->next;}else{pa->coef

*=pa->exp

;pa->exp

--

;q=pa;pa=

pa->next

;}}}283、一线性表存储在带头结点的双向循环链表中，L为头指针。如下算法：（1）说明该算法的功能。（2）在空缺处填写相应的语句。

【北京理工大学1999第二部分数据结构[7]（8分）】29voidunknown(BNODETP&L){…p=L->next;q=p->next;r=q->next；

while(q!=L){while(p!=L)&&(p->data>q->data)p=p->back；

q->back->next=r；(1)；

q->next=p->next；q->back=p；

(2)；(3)；

q=r；p=q->back；

(4)；

}}30voidunknown(BNODETP&L){…p=L->next;q=p->next;r=q->next；

while(q!=L){while(p!=L)&&(p->data>q->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；

}}3、将双循环链表结点的数据按值从小到大排序。314、设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有back（前驱指针），data（数据）和next（后继指针）域外，还有一个访问频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次Locate(L,x)运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。【清华大学考研

1