资源描述：
《同济CC软件基础数据结构3》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、本文由_MR_L_L贡献ppt文档可能在WAP端浏览体验不佳。建议您优先选择TXT,或下载源文件到木机杳看。二.循环链表将单链表最后一个结点的link字段指向第一个结点就构成将单链表最后一个结点的link字段指向第一个结点就构成link了循环链表(circularlist),一般的单链表只能访问某结循环链表(list),-般的单链表只能访问某结),点后面的结点，点后面的结点，而循环链表从任一结点出发都可以访问所有的结点•如下所示：结点.如下所示：alfirstai-laian对于环链表：对于环链表：？最后一个结点的link值不再是NULL,而是表头指针first.最后一个结点的link
2、值不再是NULL,而是表头指针first.最后一个结点的link值不再是NULL,而是表头指针?可通过检查current-*link==first来判断当前指针可通过检查current^current是否指向最后结点是否指向最后结点；current是否指向最后结点；循环链表的应用举例循环链表的应用举例约瑟夫问题约瑟夫问题问题描述：旅行社要从n个旅客屮选出一名旅客，问题描述：旅行社要从n个旅客屮选出一名旅客，为其提供免费环球旅行服务.旅行社安排这些旅客围成一个圆圈，从免费环球旅行服务.旅行社安排这些旅客围成一个圆圈，小于n的数中随意抽出一个数m作为报数值。游戏进行时，小于n的数屮随意抽出
3、一个数m,作为报数值。游戏进行时，从第一个人开始按顺时针方向自1开始顺序报数，报到m从第一个人开始按顺时针方向自1开始顺序报数，报到m吋停止报数，报m的人被淘汰出列，然后从他顺吋针方向上的下止报数，的人被淘汰出列，一个人开始重新报数，如此卞去，直到圆圈中只剩下一个人，一个人开始重新报数，如此下去，直到圆圈中只剩下一个人，这个戢后的幸运者就是游戏的胜利者，这个最示的幸运者就是游戏的胜利者，将得到免费旅行的奖励。例如，若n二8,呼3,则岀列顺序将为3,6,1,5,2,8,例如,n=8,m=3,则出列顺序将为34,最初编号为7的旅客将赢得环球旅游的机会。最初编号为7的旅客将赢得环球旅游的机会
4、。例如n=8m=3程序处理步骤：程序处理步骤：1、建立环链。建立环链。通过voidi)函数将值为函数将值为i通过voidadd(inti)函数将值为i的数据不断加到环链的尾部.尾部.2、选择获胜者.选择获胜者.通过void函数在含冇n通过voidjosph(intn,intm)函数在含有n个结点的环链屮从表头开始按步长m顺时针删除n个结点.链屮从表头开始按步长m顺时针删除nT个结点.具体步骤如门具体步骤如下：(1)当前工作指针指向表头结点。(1)当前工作指针指向表头结点。current=hcad当询工作指针指向表头结点(2)当询指针向后移动m(2)当前指针向后移动m-1次当前指针向后移
5、动move()函数其功能：函数，voidmove()函数，其功能:移动current指针到下一结点并保存其原值到前驷指移动current指针到下一结点并保存其原值到前驱指current针(3)current指向的结点出列并删除.(3)current指向的结点岀列并删除.指向的结点出列并删除getdata()函数获取出列结点的数据函数获取出列结点的数据，intgetdata()函数获取出列结点的数据，del()函数将其指向结点从环链屮删除函数将其指向结点从环链小删除.voiddel()1^1数将其指向结点从环链小删除.(4)重复执行⑵⑶步共n(4)重复执行(2)(3)步共n-1次•最终c
6、urrent指向获胜者.重复执行⑵(3)步共最终current指向获胜者.current指向获胜者根据分析，坏链类设计如下：根据分析，坏链类设计如2classnode//定义结点类{friendclassCirlist;//环链表类为其友元类intdata;node細ext;public:node(intvalue){data=value;next=NULL;}};classCirlist//定义环链表类{node*head,*tail,^current,*pr;public:Cirlist(){head二tail二NULL;}voidadd(intn);//向表尾添加一结点voidm
7、ove();//I作指针后移一位voiddel();//删除当前指针指向的结点intgetdataO;//获取当前结点的数据voidprint();voidjosph(intm,intn);//选获胜者};current代表当前工作指针current代表当前工作指针pr代表其前驱指针pr代表其前驱指针成员函数的实现：成员函数的实现：voidCirlist::add(inti){node*newnode;newnode=newnode(i);if
