28 循环链表ADT模板简单应用算法设计:约瑟夫环
问题描述 :
目的:使用C++模板设计循环链表的抽象数据类型(ADT)。并在此基础上,使用循环链表ADT的基本操作,设计并实现单链表的简单算法设计。
内容:(1)请使用模板设计循环链表的抽象数据类型。(由于该环境目前仅支持单文件的编译,故将所有内容都集中在一个源文件内。在实际的设计中,推荐将抽象类及对应的派生类分别放在单独的头文件中。参考网盘中的单链表ADT原型文件,自行设计循环链表的ADT。)
(2)ADT的简单应用:使用该ADT设计并实现循环链表应用场合的一些简单算法设计。
应用2:编号为1,2,...,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。现在给定一个随机数m>0,从编号为1的人开始,按顺时针方向1开始顺序报数,报到m时停止。报m的人出圈,同时留下他的密码作为新的m值,从他在顺时针方向上的下一个人开始,重新从1开始报数,如此下去,直至所有的人全部出列为止。请在使用循环链表ADT的基础上,设计一个算法求出圈的顺序(以编号表示)。限定人数至少为1.
参考函数原型:
template<class ElemType>
void Joseph(CirLinkList<ElemType> &A, int m);
//约瑟夫环专用结点类型
struct node{
int number;
int code;
};
输入说明 :
第一行:人数n
第二行:第一个人所持的密码
第三行:第二个人所持的密码
...
第n+1行:第n个人所持的密码
第n+2行:给定的随机数m
输出说明 :
第一行至第n行:建立的循环链表的遍历结果(一个结点占据1行)
第n+1行:空行
第n+2行:出圈的顺序(编号与编号之间以“->”分隔
输入范例 :
7
3
8
1
22
4
9
15
5
输出范例:
1 3
2 8
3 1
4 22
5 4
6 9
7 15
5->2->6->7->4->3->1
代码:
嗯,嗯嗯