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

《第 七 讲 单链表、循环链表、双向链表 10 23.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、指向了表的前端。增加一个标记：为简化操作，在循环链表中往往加入表头结点。循环表特点：循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。循环链表示例//简单循环链表类templateclassSimpleCircLinkList{protected://循环链表实现的数据成员:Node*head;//头结点指针//辅助函数Node*GetElemPtr(intposition)const;//返回指向第position个

3、结点的指针voidInit();//初始化线性表public://抽象数据类型方法声明及重载编译系统默认方法声明:SimpleCircLinkList();//无参数的构造函数virtual~SimpleCircLinkList();//析构函数intLength()const;//求线性表长度boolEmpty()const;//判断线性表是否为空voidClear();//将线性表清空voidTraverse(void(*Visit)(constElemType&))const;//遍历线性表StatusCo

4、deGetElem(intposition,ElemType&e)const;//求指定位置的元素StatusCodeSetElem(intposition,constElemType&e);//设置指定位置的元素值StatusCodeDelete(intposition,ElemType&e);//删除元素StatusCodeInsert(intposition,constElemType&e);//插入元素SimpleCircLinkList(constSimpleCircLinkList

5、©);//复制构造函数SimpleCircLinkList&operator=(constSimpleCircLinkList©);//赋值语句重载};用循环链表求解约瑟夫问题约瑟夫问题的提法n个人围成一个圆圈，首先第1个人从1开始一个人一个人顺时针报数,报到第m个人，令其出列。然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其出列，…，如此下去,直到圆圈中只剩一个人为止。此人即为优胜者。例如n=8m=3//文件路径名:s2_5alg.hvoidJ

6、osephus(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,.

7、.,n的循环链表cout<<"出列者:";for(inti=1;ila.Length())position=1;}la.Delete(position--,out);//报数到m的人出列cout<

8、lyLinkedList)双向链表是指在前驱和后继方向都能游历(遍历)的线性链表。双向链表每个结点结构：前驱方向后继方向双向链表通常采用带表头结点的循环链表形式。双向循环链表示例双向链表的实现一、数据结点类模板templatestructDbNode{ElemTypedata;DbNode*back;DbNode