线性表的基本操作及其应用
一、实验目的
1、帮助读者复习C++语言程序设计中的知识。 2、熟悉线性表的逻辑结构。
3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。
二、实验内容
约瑟夫环（**） [问题描述]
约瑟夫（Joseph）问题的一种描述是：编号为1,2,…,n的n个人按顺
时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。
[基本要求]
利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的
编号。
[测试数据]
由学生任意指定。
如：m的初值为20；n的值为7；密码：3，1，7，2，4，8，4；
（正确的输出结果应为6，1，4，7，2，3，5）。 (报告上要求写出多批数据测试结果)
[实现提示]
程序运行后首先要求用户输入初始报数上限值m，人数n,(设n≤30)。
然后输入各人的密码。
三、实验前的准备工作
1、掌握线性表的逻辑结构。 2、掌握线性表的链式存储结构。 3、熟练掌握线性表的插入、删除等操作。
四、问题分析
编号为1,2,…,n的n个人按顺时针方向围坐一圈，就需要建立一个单循环链表，由于最后要求输出个人编号，同时还必须记录个人的密码，所以，在建链表时可以用数组存储个人的编号和密码。从第一个人开始按顺时针方向自1开始顺序报数，可以用一个循环来完成，报到m时停止报数。报m的人出列，将他的密码作为新的m值，即达到条件时，将出列人的编号输出，密码赋给m，删除其结点，继续循环，直至所有人出列。
五、算法设计
链表的创建：创建一个链表，用一个for循环，申请结点，将n个人的编号和密码存入链表，最后让尾结点连接到链首，单循环链表就建成了。
出列函数：用一个while循环作为大循环，当p->next!p，即仅剩最后一个人时循环结束。在while循环内，用一个for循环，将链表的指针p指向密码指向的结点，l用来保存p前的结点，以便删除结点p。当结点p指向密码所指的结点时，将p->next给l->next，将p的密码赋给c作为新密码，输出p的编号，释放结点p，将l->next给p，进行新一轮的循环直至剩最后一个结点，即while结束，输出最后一个结点中储存的编号，释放结点空间。至此，已经按出列的顺序印出各人的编号。
六、实验测试数据结果
测试数据如下： m n 密码 结果 -------------------- -------------------- 3，1，7，2，4，8，4 6，1，4，7，2，3，5 2，6，9，5，8，15，4，3，5 8，2，9，6，5，4，1，7，3 7 20 密码 结果 9 8 密码 结果
5 10 密码 结果 11，15，19，5，3 5，3，4，1，2 1，1，1，1，1，1 4，5，6，1，2，3 2，3，6，1 2，1，4，3 6 4 密码 结果 4 2 密码 结果 测试结果如图：
七、总结
对于本次实验，通过问题分析与算法设计，要达到目的也不是很难，主要内容就是单循环链表，但是在写的时候，循环等主程序很快就写得差不多了，但通过验证，结果总是不能达到目的，总是与理论值不一样，经过不断地观察、测试，终于发现了问题所在，有时仅仅是一个变量0和1的问题，就可能导致出错，不过还好，通过我一遍又一遍的计算最终还是弄好了。还是比较成功的。
八、附录
struct node //链表声明 { };
node *input(int n) //用于输入每个人的密码初始化单循环链表 {
int a[2]; //a[0]用于保存每个人的原始号码用于输出结 node *next; //果，a[1]用于保存其密码
}
int m;
node*p=NULL,*l,*head=NULL; for (int i=1;i<=n;i++) { }
p->next=head;
return head; //单循环链表的关键
l=new node; l->a[0]=i;
cout<<\请输入第\个人的密码：\cin>>m; l->a[1]=m; if (i==1)head=l; else p->next=l; p=l;
void visit(node*s,int i) //出列函数 {
node*l,*p; p=s; int c; c=i;
while ((p->next)!=p) {
for (int j=0;j l=p;//l //记录p前的结点，以便删除结点