线性表的基本操作及其应用 约瑟夫环

本文格式为Word版，下载可任意编辑——线性表的基本操作及其应用约瑟夫环

线性表的基本操作及其应用

一、试验目的

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终止，输出最终一个结点中储存的编号，释放结点空间。至此，已经按出列的顺序印出各人的编号。

六、试验测试数据结果

测试数据如下：mn密码结果3，1，7，2，4，8，46，1，4，7，2，3，52，6，9，5，8，15，4，3，58，2，9，6，5，4，1，7，3720密码结果98密码结果

510密码结果11，15，19，5，35，3，4，1，21，1，1，1，1，14，5，6，1，2，32，3，6，12，1，4，364密码结果42密码结果测试结果如图：

七、总结

对于本次试验，通过问题分析与算法设计，要达到目的也不是很难，主要内容就是单循环链表，但是在写的时候，循环等主程序很快就写得差不多了，但通过验证，结果总是不能达到目的，总是与理论值不一样，经过不断地观测、测试，终究发现了问题所在，有时仅仅是一个变量0和1的问题，就可能导致出错，不过还好，通过我一遍又一遍的计算最终还是弄好了。还是比较成功的。

八、附录

structnode//链表声明{};

node*input(intn)//用于输入每个人的密码初始化单循环链表{

inta[2];//a[0]用于保存每个人的原始号码用于输出结node*next;//果，a[1]用于保存其密码

}

intm;

node*p=NULL,*l,*head=NULL;for(inti=1;inext=head;

returnhead;//单循环链表的关键

l=newnode;l->a[0]=i;

cout>m;l->a[1]=m;if(i==1)head=l;elsep->next=l;p=l;

voidvisit(node*s,inti)