第 七 讲 单链表、循环链表、双向链表 10 23.ppt

1、循环链表、双向链表,时间：201310-23,劝学语,玩物丧志，玩人丧德。尚书读书须用意，一字值千金。弟子规,只要有了积极主动的态度，没有什么目标是不能达到的。李开复,第七次上课内容,1、循环链表P392、双向链表P433、线性表的应用P55,本节课学习目标,1、循环表的定义2、双向表的定义3、线性表的应用,数据的逻辑结构可归结为以下四类,线性结构,树形结构,图状结构,集合结构,第2章线性表,循环链表(CircularList),循环链表是单链表的变形唯一一个区别：循环链表最后一个结点的next指针不为0(NULL)，而是指向了表的前端。增加一个标记：为简化操作，在循环链表中往往加入表头结点。

2、循环表特点：循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。,循环链表示例,/简单循环链表类templateclassSimpleCircLinkListprotected:/循环链表实现的数据成员:Node*head;/头结点指针/辅助函数Node*GetElemPtr(intposition)const;/返回指向第position个结点的指针voidInit();/初始化线性表,public:/抽象数据类型方法声明及重载编译系统默认方法声明:SimpleCircLinkList();/无参数的构造函数virtualSimpleCircLinkList();/析

3、构函数intLength()const;/求线性表长度boolEmpty()const;/判断线性表是否为空voidClear();/将线性表清空voidTraverse(void(*Visit)(constElemType/设置指定位置的元素值,StatusCodeDelete(intposition,ElemType,用循环链表求解约瑟夫问题,约瑟夫问题的提法n个人围成一个圆圈，首先第1个人从1开始一个人一个人顺时针报数,报到第m个人，令其出列。然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其出列，如此下去,直到圆圈中只剩一个人为止。此人即为优胜者。例如n=8m=3,/文件路径名

4、:s2_5alg.hvoidJosephus(intn,intm)/操作结果:n个人围成一个圆圈，首先第1个人从1开始一/个人一个人顺时针报数,报到第m个人，令其出列。/然后再从下一个人开始，从1顺时针报数报到第m/个人，再令其出列，如此下去,直到圆圈中只/剩一个人为止。此人即为优胜者SimpleCircLinkListla;/定义空循环链表intposition=0;/报数到的人在链表中序号intout,winer;for(intk=1;k=n;k+)la.Insert(k,k);/建立数据域为1,2,.,n的循环链表,coutla.Length()position=1;la.Delete(

5、position-,out);/报数到m的人出列coutout;la.GetElem(1,winer);/剩下的一个人为优胜者coutendl优胜者:winerpos)curPose=0;curPtr=head;For(;curPosnext;returncurPtr;,在计算机中，可以用一个线性表来表示:P=(p0,p1,，pn),多项的链表表示一元多项式,但是对于形如S(x)=1+3x100002x20000的多项式，上述表示方法是否合适？,一般情况下的一元稀疏多项式可写成Pn(x)=p1xe1+p2xe2+pmxem其中：pi是指数为ei的项的非零系数，0e1e2em=n,可以下列线性表

6、表示：（p1,e1）,(p2,e2),(pm,em)）,P999(x)=7x3-2x12-8x999,例如:,可用线性表(7,3),(-2,12),(-8,999)表示,/多项式类classPolynomialprotected:/多项式实现的数据成员:LinkListpolyList;/多项式组成的线性表public:/抽象数据类型方法声明:Polynomial();/无参构造函数Polynomial();/析构函数intLength()const;/求多项式的项数,boolIsZero()const;/判断多项式是否为0voidSetZero();/将多项式置为0voidDisplay();/显示多项式voidInsItem(