2009级数据结构实验报告
实验名称： 实验线性表实现约瑟夫问题求解 学生姓名： 桂柯易 班 级： 2009211120 班内序号： 07 学 号： 09210580
日 期： 2010年10月31日
1.实验要求
【实验目的】
1． 熟悉C++语言的基本编程方法,掌握集成编译环境的调试方法； 2． 学习指针、模板类、异常处理的使用； 3． 掌握线性表的操作实现方法； 4． 培养使用线性表解决实际问题的能力。
【实验内容】
利用循环链表实现约瑟夫问题的求解。
约瑟夫问题如下：已知n个人（n>=1）围坐一圆桌周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m的那个人出列。他的下一个人又从1开始报数，数到m的那个人又出列。依此规则重复下去，直到所有人全部出列。请问最后一个出列的人的编号。
2.程序分析
2.1 存储结构
存储结构：循环链表
1 first 2 3 …n
2.2 关键算法分析
【设计思想】
首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环本身具有循环性质，考虑采用循环链表，为了统一对表中任意节点的操作，循环链表不带头结点。循环链表的结点定义为如下结构类型：
struct Node {
int number; Node *next; };
其次，建立一个不带头结点的循环链表并由头指针first指示。 最后，设计约瑟夫环问题的算法。 【伪代码】
1、 工作指针first，r，s，p，q初始化 2、 输入人数（n）和报数（m） 3、 循环n次，用尾插法创建链表 Node *q;
for(int i=1;i<=n;i++) {
Node *p; p=new Node; p->number=i; p->next=NULL; if(i==1) L=q=p; else {
q->next=p; q=q->next; } }
q->next=L;
if(L!=NULL){return(L);} 4、输入报数的起始人号数k;
5、Node *q = new Node;计数器初始化i=1;
6、循环n次删除结点并报出位置（其中第一个人后移k个） 当i 移动指针m-2次p=p->next; 删除p结点的后一结点q q=p->next; p->next=q->next; *L = p->next; 报出位置后Delete q; 计数器i++; 【复杂度】 for(int i=1;i<=n;i++) { Node *p; p=new Node; p->number=i; p->next=NULL; if(i==1) L=q=p; else { q->next=p; q=q->next; } 时间复杂度：O（n） if(i==1) i+=LengthList(*L); Node *p; p=*L; int j=0; while(j p->next=p->next->next; *L = p->next; return(q); 时间复杂度：O（n2） 算法的空间复杂度：O（n2） 2.3 其他 程序源代码： #include int number;//编号 Node *next; }; Node *CreateList(Node *L,int &n,int &m);//建立约瑟夫环函数 void Joseph(Node *L,int n,int m);//输出每次出列号数函数 Node *DeleteList(Node **L,int i,Node *q);//寻找每次出列人的号数 int LengthList(Node *L);//计算环上所有人数函数