数据结构与算法-线性表3

华中农业大学理学院章英zy@

数据结构与算法

1/29第四讲循环链表本讲知识点：(1)了解循环链表的创建方法(2)掌握双向链表的删除、插入操作

(3)了解链表的相关应用重点：双向链表的操作难点：链表的应用2/29重温约瑟夫环问题，是否可以用链表实现？提出问题la.head3/29数据成员需要变化吗?单链表和循环链表的区别SimpleLinkList<int>la;la.head^la.headSimpleCircLinkList<int>la;4/29一、循环链表之初始化template<classElemType>voidSimpleLinkList<ElemType>::Init()//操作结果：初始化循环链表{ head=newNode<ElemType>;

head->next=head;}5/29约瑟夫环已经形成，如何报数离队？分析问题假设：n=6m=4123456la.head6/29分析问题第一轮 第二轮 4离队2离队12356la.head1356la.head7/29分析问题第三轮 第四轮 1离队3离队356la.head56la.head8/29解决问题 //…… for(inti=1;i<n;i++)

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

la.Delete(position--,out);

cout<<out<<""; } la.GetElem(1,winer);

cout<<winer<<endl;参见文件夹S2_5里的文件alg.h9/29判断指针是否指向最后一个结点的方法？思考：单链表：循环链表：

tmpPtr->next==NULL;

tmpPtr->next==head;10/29二、双向链表

定义：单链表的每个结点再增加一个指向其前趋的指针域back，这样形成的链表有两条不同方向的链，称之为双（向）链表。

结点：DblNode

类：SimpleDblLinkList11/29双向链表结点结构struct

DblNode

{

ElemTypedata;

DblNode<ElemType>*back;

DblNode<ElemType>*next;//……};前驱方向后继方向backdatanext12/29p==p->back->next==p->next->back双向链表举例p13/29双向链表结点的插入 597pq

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

nextPtr->back=newPtrnextPtrtmpPtrnewPtr14/29双向链表结点的删除597tmpPtr->back->next=tmpPtr->nexttmpPtr->next->back=tmpPtr->backtmpPtr××15/29归纳:双向链表和单向链表相比，其优势何在？双向链表可以实现前驱遍历。学会链表，为后续课程打下基础。线段树、平衡树等，在区间统计上有很大的优势。但是对大数据量的修改维护、删除操作，他们也力不从心。要快速的定位元素，最快速的实现方法是数组；要快速的移动大量连续的元素，最快速的实现方法是链表。二者可以统一协调起来，即：块状链表。16/29课堂实战1、假设一个单循环链表，其结点含有三个域back、data、next。其中data为数据域；back为指针域，它的值为空指针（NULL）；next为指针域，它指向后继结点。请设计算法，将此表改成双向循环链表。【西安电子科技大学1999软考五（10分）】17/29∧a∧b∧z∧……分析问题la.head

a

b

z

……la.head18/29voidStoDouble(SimpleCircLinkList<ElemType>&la){Node*p=la.head;do{p->next->back=p;p=p->next;}while(p!=la.head);}解决问题之方法119/29voidStoDouble(SimpleCircLinkList<ElemType>&la){while(la.head->next->back==NULL){

la.head->next->back=la.head;

la.head=la.head->next;}}解决问题之方法220/29课堂实战2、一元稀疏多项式以单循环链表按降幂排列，结点有三个域，系数域coef、指数域exp和指针域next；现对链表求一阶导数，链表ha的头指针为head，头结点的exp域为-1。【南京理工

2000考研（10分）】21/29ha.headqpa-1……41517-30（1）pa所指结点的指数要减1（2）pa所指结点的系数=系数*指数（3）若pa所指结点的指数为0，则要删除该结点分析问题22/29voidderivative(SimpleCircLinkList&ha){Node*q,*pa;q=ha.head;pa=ha.head->next;while((1)){if((2)){(3);deletepa;pa=(4);}else{pa->coef

(5);pa->exp(6);q=(7);pa=(8);}}}程序填空23/29voidderivative(SimpleCircLinkList&ha){Node*q,*pa;q=ha.head;pa=ha.head->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

;}}}参考答案24/29课堂实战3、一线性表存储在带头结点的双向循环链表中，L为头指针。如下算法：（1）说明该算法的功能。（2）在空缺处填写相应的语句。

【北京理工大学（8分）】25/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)；

}}程序填空26/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；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;//r=q->next