数据结构课程设计报告
题目：约瑟夫环实验
班级：
成员：
指导教师：
完成日期：
目录：
实习报告要求 (2)
约瑟夫环实验描述 (3)
课程设计报告正文 (4)
一．需求分析 (4)
二．概要设计 (4)
三．详细设计 (6)
1．各模块关键代码及算法的解释： (6)
2．函数的调用关系图 (8)
四．调试分析 (11)
五．用户使用说明 (12)
六．测试结果 (13)
七．小结 (3)
八．附录，带注释的源程序 (4)
实习报告要求
实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下七个内容：
1. 需求分析
以无歧义的陈述说明程序设计的任务，强调的是程序要做什么?明确规定:
(1) 输入的形式和输入值的范围；
(2) 输出的形式；
(3) 程序所能达到的功能；
(4) 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。
2. 概要设计
说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。
3. 详细设计
实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为:按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；画出函数的调用关系图。
4. 调试分析
内容包括：
(1)调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；
(2)算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想；
(3)经验和体会等。
5. 用户使用说明
说明如何使用你编写的程序，详细列出每一步的操作步骤。
6. 测试结果
列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。
7. 附录
带注释的源程序。可以只列出程序文件名的清单。
实习报告的各种文档资料，如：上述中的前三部分要在程序开发的过程中逐渐充实形成，而不是最后补写(当然也可以应该最后用实验报告纸誉清或打印)。
约瑟夫环实验描述
【问题描述】
约瑟夫(Joseph) 问题的一种描述是：编号为1，2，… ，n的n个人按顺时针方向围坐一圈，每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。
【基本要求】
利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。
【测试数据】
m的初值为20；n=7，7 个人的密码依次为：3，1，7，2，4，8，4，首先m值为6( 正确的出列顺序应为6，1，4，7，2，3，5) 。
【实现提示】
程序运行后，首先要求用户指定初始报数上限值，然后读取各人的密码。可设n≤30。此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。
【选作内容】
向上述程序中添加在顺序结构上实现的部分。
课程设计报告正文
一．需求分析
1．输入的形式和输入值的范围
本程序中，输入人数n(n小于等于30)和初始密码m（m大于等于1），然后给每个人输入所持有的密码key，均限定为正整数。用单循环链表模拟约瑟夫环，从队头开始从1报数，报到m的人出列，再把此人的密码赋给m，继续下一轮的报数，直到所有的人出列。结果出来后再选择输入一数字，输入1继续新一轮的游戏，输入0结束，退出此游戏。演示程序以用户和计算机对话方式进行，根据提示信息由用户从键盘输入数据，输入的形式为一个以“回车符”为结束标志的正整数。
2．输出的形式
在计算机终端上显示提示信息之后，有用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在其后。运行后输出的结果是约瑟夫环的相关信息和经过报数后出队的人的序列号及相关信息。
程序执行的命令包括：（1）输入人数和初始密码（2）输入所有人的密码（3）显示输入的所有人的编号及相应的密码（4）输出出列密码及编号（5）结束即：（1）构造单循环链表；（2）输出循环链表的信息；（3）按照出列的顺序输出各人的编号
3．程序功能
提供用户从键盘输入，Joseph约瑟夫环的必要数据，并从屏幕显示出列顺序。
4．测试数据
（1）n=7 ,m=20（常规数据）, 7个人的密码依次为3，1，7，2，4，8，4，正确的输出序列为6，1，4，7，2，3，5.
（2）n=5，m=6（常规数据），5个人的密码依次为2，5，4，6，7，正确的输出序列为1,3,4,2,5。
（3）n=31, m=3（错误数据），“这个人数太大了，请重新输入”。
（4）n=0, m=3（错误数据），“这个约瑟夫环里没有人！”。
（5）n=1, m=4,（边缘数据），正确的输出序列为1。
（6）n=3, m=1,（边缘数据），正确的输出序列为1，3，2。
第一组为常规数据，中间两组为错误数据，后面两组为边缘数据。
5．设计思路及方案
用单循环链表来模拟约瑟夫环，结点信息包括编号、密码、指向下一个结点的指针，用三大主要的函数来实现功能，包括创建链表的函数、输出链表信息的函数、删除结点也就是出队的函数、主函数等函数。
二．概要设计
1．抽象数据类型的定义
为实现上述功能，应以有序单向循环链表表示约瑟夫环。为此，需要有一个抽象数据类型。该抽象数据类型的定义为：
ADT LinkList
{
数据对象：D={ ai | ai ∈termset,i=1,2,……n,n>=0}，
termset中每个元素包含编号，密码，和一个指向下一节点的指针
数据关系：R1={
基本操作：
LinkList EvaluList(int n);//对单向循环链表进行尾插入赋值
int size(LinkList L);//求链表的节点个数
Status ScanList(LinkList L);//遍历单向循环链表
Status Joseph(LinkList &L,int m);//约瑟夫环的实现
}
此抽象数据类型中的一些常量如下：#define TRUE 1
#define FALSE 0
#define OK 1
typedef int Status;
typedef double ElemType;
单向循环链表中节点的定义如下所示：
typedef struct LNode
{
int number;
int data;
struct LNode *next;
}LNode, *LinkList;
2．主程序的流程
void main()
{
初始化；
输入数据；
执行功能；
显示结果；
}
3．模块的设计及介绍
（1）主程序模块
Void main（）{
初始化；
do {
接受命令；
处理命令；
}while（“命令”=“退出”）；
}
（2）创建链表模块
Static void creatlist（行参）{
初始化；
For{
接受命令；
处理命令 }
}
（3）输出链表信息模块
static void PrntList(参数){
定义变量并初始化；
输出命令；
}
（4）删除结点也就是出队模块
static void StatGame(参数){
定义变量并初始化；
While{
开始报数；
输出结果；}}
4．各程序模块之间的层次(调用)关系。
本程序包含以下模块：
（1）主程序模块：
（2）各功能模块——实现顺序表的各项功能。
各模块的调用关系：
主程序
↓
各功能模块
三．详细设计
1．各模块关键代码及算法的解释：
（1）主函数模块代码
circularlist pHead=NULL;
int main(void)
{ int n, m， iflag=1
while(iflag=1){
printf("请输入总人数n=");
scanf("%d",&n);
printf("\n再请输入初始报数上限m="); scanf("%d",&m)；
CreatList(&pHead,n);
printf("\n输出所有人的信息如下:\n");
PrntList(pHead);
printf("\n按照出列顺序输出每个人的编号:\n");
StatGame(&pHead, m);
printf("\n约瑟夫环的游戏完成!\n");
printf("输入1开始建环做游戏，输入0退出该游戏，请选
择!");scanf("%d",&i);
} return 0;
}
程序解释：该主函数用一个循环语句，来执行其它的函数的功能。从键盘输入总人数和初始的报数上限，再调用创建链表的函数建环，后输出单循环链表的信息，再调用StatGame（）函数，报到上限的那个结点从表中删除既出队，然后再选择输入一个数确定是否继续游戏，输入1继续，输入0退出。
（2）创建单循环链表函数模块代码
static void CreatList(circularlist * ppHead, const int n)
{
int i,ikey;
Node *pNew, *pCur;
for(i=1;i<=n;i++)
{
printf("请输入第%d个人所持有的密码:",i);
scanf("%d", &ikey);
pNew=GetNode(i,ikey);
if(*ppHead==NULL)
{
*ppHead=pCur=pNew; pCur->next=*ppHead;
}
else
{
pNew->next=pCur->next; pCur->next=pNew; pCur=pNew; }
}
程序解释：用一个for循环来给链表的每个结点分配空间，并从键盘输入每人所持有的密码，如果头结点的值为空，使其指向新生成的一个结点，新结点的next 指针指向头结点，如果不是，则当前结点的next的值赋给新结点的next，然后
当前结点的next值指向新结点，再当前结点的指针指向新结点，实现链表的建立。
（3）删除结点函数代码
static void StatGame(circularlist * ppHead, int ikey)
{
int iCounter, iFlag=1;
Node *pPrv, *pCur, *pDel;
pPrv=pCur=*ppHead;
while(iFlag) ! */
{
for(iCounter=1;iCounter<=ikey;iCounter++)
{
pPrv=pCur; pCur=pCur->next;
}
if(pPrv==pCur) iFlag=0;
pDel=pCur; Prv->next=pCur->next;
pCur=pCur->next;
ikey=pDel->key;
printf("第 %d个人出列, 所持有密码是: %d\n", pDel->id,pDel->key);
free(pDel);
}
ppHead=NULL;
}
程序解释：设立一个标签，值为1执行循环语句，值为0跳出循环。循环语句里的for循环实现报数功能，也就是结点移动的功能，移动ikey个结点，再删除第ikey个结点，并把该结点的密码值赋给ikey，再从该结点的下一个结点移动，重复上面的过程，结点全都删除后使标签的值为0，结束while循环，游戏结束。
2
2.2创建单循环链表函数流程图
2.3删除结点函数（出队函数）程序流程图
2.4
四．调试分析
1.调试过程中遇到的问题及解决方法及对设计与实现的回顾讨论和分析
程序的编写和调试基本正常。遇到的问题有：指针的指向的边界问题。当执行输入人数时，输入0程序出现了意想不到的错误，所以再重新设计时加入了对空节点的处理。在链表节点的设计上，最初是仅包含密码和指针，但是后来考虑到链表节点删除时会带来一系列的编号变化，编号难以确定，所以节点设计上又加了一个编号。在单向链表的赋值操作时，原本是以一个不变的L作为头结点，但是这种赋值方法带来了诸多变量设计的问题，所以将L为节点，赋值完成后，再让L指向头结点。程序原本是没有求节点个数的函数，但是在约瑟夫环的实现函数中，节点的个数时时影响着结果的判断，所以加入了该函数。
2.算法的时空分析
在空间复杂度方面第一种算法可以增加一存储出列序列的数据组，需要辅助空间，而且与问题的规模Maxsize有关。第二种算法也可直接对约瑟夫环进行求解，结果仍然存储在环中，好处是没有增加额外的空间。在时间复杂度方面，第一种算法可以从中可以看到，报数m的时间极短,问题在出列时,由于用顺序表做删除操作,平均移动大约表中一半的元素,影响效率.但是,两者都存在二重循环,
算法中语句重复执行次数的数量级没有发生变化,即时间复杂度O相同。与这两种算法不同的是，动态链表实现的算法中，不需要预先分配足够大的存储空间，没有太大的辅助空间的要求，远小于问题规模Maxsize，即绝小于第一种算法的辅助空间，而接近第二种算法。另外，删除结点操作极其方便，比第二种算法移动元素的少。不过，三者时间复杂度O均相同。对同一问题，可以有不同的算法。但仍可以进一步优化。例如时间问题，密码可采用对剩余节点取余来减少遍历次数。
3.经验和体会
通过这次的课程设计的综合训练，培养分析和编程等实际动手能力，系统掌握数据结构这门课程的主要内容，我们对数据结构有了更深的理解。与以往不同的是我们自己选定一个研究问题，对其进行详尽的分析思考，最终解决。我们选择的课程设计的内容是用单循环链表模拟约瑟夫环游戏，循环链表是一种首尾相接链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活，约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例，了解单链表和单循环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。
在此期间遇到了很多困难。如：当程序大体完成时，却又在调试过程中发现出列次序总是错误的，才想到第一次指向时应该让变化的指针指向尾节点，这样可以减少当密码为1时程序的设计量。
此次课程设计收获相当多，我们不仅对VC软件更加熟悉，而且学会了能运用所学知识分析和解决一些实际问题。了解并初步掌握设计、实现较大程序的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。本实验采用数据抽象的与模块化程序设计方法。思路清晰，实现时调试顺利，各模块具有很好的可重用性，得到了一次良好的程序设计训练。同时在和队友的不断完善中，许多困难都得到了解决，从这点我们也认识到团队中合作的重要性。相信我们以后会做得更优秀。
五．用户使用说明
1．如何使用你编写的程序
首先根据提示输入初始密码和人数，再输入每个人的密码。最后输入1或0，选择继续或结束。
2．每一步的操作步骤
示例：进入演示程序后即显示文本方式的用户界面;
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@"
@ 欢迎您进入'约瑟夫环'运行界面 @"
@ 请按照提示执行程序 @"
@ @"
@ 设计者:姜密王轶广鲍玉凤@"
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
先请输入人数n(n小于等于30)和初始密码m(m大于等于1)，再请输入每个人的密码。显示出出列顺序。最后输入1，继续测试。输入0，结束。
如：请输入人数n(n小于等于30)7
和初始密人数：20
输入1个人的密码：3
输入2个人的密码：1
输入3个人的密码：7
输入4个人的密码：2
输入5个人的密码：4
输入6个人的密码：8
输入7个人的密码：4
后会出现7个人的密码为：3 1 7 2 4 8 4 和出列顺序6 1 4 7 2 3 5。
输入1之后的界面：继续测试数据
输入0之后的界面：结束
六．测试结果
1．程序调试，正确
2．点击运行，进入“约瑟夫环”运行初界面
3.输入总人数之后的界面
4．输入初始密码后的界面：
5.输入所有人所持有的密码后的界面（继续新一轮的游戏，结束后的界面）输入所规定范围内的数值。（第一组，常规数据）
6.输入1之后的界面：
7.输入0之后的界面：
8．第二次测试，输入所规定范围内的数值（第二组，常规数据）。运行结果如下：
9．当输入的人数值超过范围时，系统会输出“这个人数太大了，请重新输入”，（第三组，错误数据）运行如下：
10．当输入的人数为0时，系统会输出“这个约瑟夫环里没有人”。（第四组，错误数据）程序运行的界面如下：
11．当输入的人数为1时（第五组，边缘数据）运行界面如下：
12．当输入的密码为1时（第六组，边缘数值），运行界面如下：
七．小结
通过一周的课程设计之后，培养了我们选用参考书，查阅手册及文献资料的能力，培养独立思考，深入研究，分析问题、解决问题的能力，提高综合运用本课程所学知识的能力，还对设计的基本过程的设计方法、步骤、思路、有一定的了解与认识，并对存储结构，比如线形表、链表、循环链表、树、图等存储结构，特别是对单循环链表理解的更深。也使我认识到《数据结构》这门课程是计算机程序设计的重要理论技术基础，在我们计算机专业的学习中占据着十分重要的地位。同时也使我知道，要学好这门课程，仅学习书本上的知识是不够的，还要有较强的实践能力。因为我们学习知识就是为了实践。而只有多实践，多编写程序，才能更好的理解与掌握书本上的东西。
本次课程设计的主题是用单循环链表来模拟约瑟夫环游戏，由于刚开始对循环链表的理解不够，也没理请约瑟夫环的基本思路，做起来有点难，但通过反复的修改，最终还是能够理解。
我学到了很多的东西，通过实际编译系统的分析设计、编程调试，也掌握了一些工程设计方法。现在也能够按要求编写课程设计报告书，能正确阐述设计和实验结果，正确绘制程序框图。课程设计是把我们所学的理论知识进行系统的总结并应用于实践的良好机会，有利于加强我们用知识理论来分析实际问题的能力，进而加强了我们对知识认识的实践度，巩固了我们的理论知识，深化了对知识的认识，并为走向社会打下一个良好的基础。
在这次课程设计中我遇到许多问题和麻烦。比如，表建成之后，不能输出表
中南民族大学管理学院学生实验报告 实验项目: 约瑟夫问题 课程名称：数据结构 年级： 专业：信息管理与信息系统 指导教师： 实验地点：管理学院综合实验室 完成日期： 小组成员： 2012 学年至2013 学年度第1 学期
一、实验目的 （1）掌握线性表表示和实现； （2）学会定义抽象数据类型； （3）学会分析问题，设计适当的解决方案； 二、实验内容 【问题描述】：编号为1,2,…,n的n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自 1 开始顺序报数，报到m 时停止报数。报m 的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1 报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 【基本要求】：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 【测试数据】：m 的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。 三、实验步骤 （一）需求分析 对于这个程序来说，首先要确定构造链表时所用的插入方法。当数到m 时一个人就出列，也即删除这个节点，同时建立这个节点的前节点与后节点的联系。由于是循环计数，所以才采用循环列表这个线性表方式。 程序存储结构利用单循环链表存储结构存储约瑟夫数据（即n个人的编码等），模拟约瑟夫的显示过程，按照出列的顺序显示个人的标号。编号为1,2,…,n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值 m，从第一个人开始按顺时针方向自1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。基本要求是利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 程序执行的命令（1）构造单向循环链表。 （2）按照出列的顺序引出各个人的标号。 测试数据 m 的初值为 20；密码：3，1，7，2，4，8，4（正确的结果应为 6，1，4，7，2，3，5） （1）、插入：在把元素插入到循环链表中时，由于是采用的头插法，所以我保留了front头结点。在每加入一个节点时，都会直接连接在front后面，从而保证一开始就赋值的rear尾节点不用修改。 伪代码阐释如下：
课程实验报告 题目：2016.4.6 学生姓名：黄玲 学生学号：201408070105 专业班级：智能1401 指导老师：骆嘉伟 完成日期：2016.4.6
一．需求分析 1.本实验基本要求是用数组来实现线性表，再基于线性表的基本操作（插入、删除、修改等）来实现约瑟夫问题 2.由键盘输入总人数n和出列报数m 3.在DOS界面上显示依次出圈的人的编号和最后一个留下的人,在当前文件夹里生成一个文本文件，里面是相同的输出。 4.测试数据： 输入： 10，3 输出： 3 6 9 2 7 1 8 5 10 4//DOS 3 6 9 2 7 1 8 5 10 4//TXT 二．概要设计 §抽象数据类型 为实现上述程序的逻辑功能，应以整数存储用户的输入 用线性表实现，线性表定义如下： ADT LISt 数据对象：整数 基本操作： AList(100);//构建一个最大人数为100的顺序表（数组）来存储人 Next();//指向下一个人 moveStart();//回到第一个人继续数数 Length();//查看圈里还剩多少人 currPos();//查看当前数到人的编号 getValue();//查看当前编号的人是否还在圈内 §程序的流程 以书上的代码案例为参考，编写线性表的ADT在继承线性表的基础上编写顺序表（数组）的类文件编写主函数，创建类的对象，完成程序 三．详细设计 §物理数据类型 将大小为n的数组赋好值，其值为他本身的编号，即数组下标。 §程序思路的具体步骤实现 设一个标志点，在数组中移动，同时报数，当报到m时，当前人的值变为0，出圈，然后继续移动，重新数。当数到值为0的人时自动跳过（已出圈），当数
一．需求分析 1.约瑟夫环（Joseph）问题的一种描述是：编号为1，2……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。 2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，有用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在其后。 3.程序执行的命令包括： 1）输入初始密码和人数2）输入所有人的密码3）显示输入的所有人的编号及相应的密码4）输出出列密码及编号5）结束 4.测试数据 (1)m=20, n=7, 7个人的密码依次为3，1，7，2，4，8，4 (2)m=20,n=1 (3)m=20,n=0 前面一组为常规数据，后面两组为边缘数据 二、概要设计 为实现上述功能，应以有序单向循环链表表示约瑟夫环。为此，需要有一个抽象数据类型。该抽象数据类型的定义为： ADT LinkList { 数据对象：D={ ai | ai ∈termset,i=1,2,……n,n>=0}， termset中每个元素包含编号，密码，和一个指向下一节点的指针数据关系：R1={
《数据结构》 课程设计报告 课程名称：《数据结构》课程设计课程设计题目：joseph环 姓名： 院系：计算机学院 专业： 年级： 学号： 指导教师： 2011年12月18日
目录 1 课程设计的目的 (2) 2 需求分析 (2) 3 课程设计报告内容 (3) 1、概要设计 (3) 2、详细设计 (3) 3、调试分析 (x) 4、用户手册 (x) 5、测试结果 (6) 6、程序清单 (7) 4 小结 (10) 1、课程设计的目的 （1）熟练使用C++编写程序，解决实际问题； （2）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； （3）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； （4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 2、需求分析 1、问题描述： 编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 2、要求： 利用不带表头结点的单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。 3、测试数据： m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？ 输出形式：建立一个输出函数，将正确的输出序列
3、课程设计报告内容 概要设计： 在理解了题目后，我先想到的是我们所学的单链表，利用单链表先建立循环链表进行存贮，建立完循环链表后，我将所要编写的函数分为了两块，一块是经过学过的单链表改编的循环链表的基本操作函数，还有一块是运行约瑟夫环的函数。 详细设计： 我先建立一个结构体，与单链表一样，只是多了一个存密码的code域 struct LinkNode { int data; /删除的是尾结点时（不知道为什么我写程序里总是编译出现错误）{ q->next=head; //重新链接 delete a; len--; return out; } else { q->next=a->next; delete a; len--; return out; } } } } 5、测试结果：
《数据结构》课程实验 实验报告 题目：Joseph问题求解算法的设计与实现专业：计算机科学与技术 班级： 姓名： 学号： 完成日期：
一、试验内容 约瑟夫（Joseph）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 二、试验目的 掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。 三、流程图 输入总人数n 创建并初始化 n个结点 输入第一个报 的数key n==0 报数过程 输出出列者 的编号及密 码 结束 n--
四、源程序代码 //Joseph问题求解算法的设计与实现 #include
《计算机软件技术基础》实验报告 I —数据结构 实验一、约瑟夫斯问题求解 一、问题描述 1.实验题目：编号 1,2,....,n的n个人顺时针围坐一圈，每人持有一个密码（正整数）。 开始选择一个正整数作为报数上限m，从第一个人开始顺时针自 1 报数，报到m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从 1 报数，直至所有人全部出列。 2. 基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号。 3. 测试数据： n=7,7 个人的密码依次为：3,1,7,2,4,8, 4.m初值为6（正确的出列顺序 应为 6,1,4,77,2,3）。 二、需求分析 1. 本程序所能达到的基本可能： 该程序基于循环链表来解决约瑟夫问题。用循环链表来模拟n 个人围坐一圈，用链表 中的每一个结点代表一个人和他所代表的密码。在输入初始密码后m，对该链表进行遍历，直到第 m个结点，令该结点的密码值作为新的密码值，后删除该结点。重复上述过程，直至所有的结点被释放空间出列。 2. 输入输出形式及输入值范围： 程序运行后提示用户输入总人数。输入人数 n 后，程序显示提示信息，提示用户输入第 i个人的密码，在输入达到预定次数后自动跳出该循环。程序显示提示信息，提示用户输入 初始密码，密码须为正整数且不大于总人数。 3．输出形式 提示用户输入初始密码，程序执行结束后会输出相应的出列结点的顺序，亦即其编号。 用户输入完毕后，程序自动运行输出运行结果。 4.测试数据要求： 测试数据 n=7，7 个人的密码依次为：3， 1， 7， 2， 4， 8， 4。 m初值为 6（正确的出列 顺序应为6， 1， 4，7， 2， 3， 5）。 三、概要设计 为了实现上述功能，应用循环链表来模拟该过程，用结构体来存放其相应的编号和密码
4：课程设计报告书附件 《数据结构》课程设计报告 环Joseph）约瑟夫（ 第七组别组组长成组员成绩教师指导 计算机科学与技术系 日11月6年2014． 摘要 约瑟夫环问题是典型的线性表的应用实例，其开发主要包括后台数据库的建立和维护以及前端应用程序的开发两个方面。对于前者要求建立起数据一致性和完整性强、数据安全性好的库。而对于后者则要求应用程序功能完备，易使用等特点。经过分析，我们使用MICROSOFT公司的Microsoft Visual C++6.0开发工具，利用其提供的各种面向对象的开发工具，尤其是数据窗口这一能方便而简洁操作数据库的智能化对象，首先在短时间内建立系统原型，然后，对初始原型系统进行需求迭代，不断修正和改进，直到形成用户满意的可行系统。 关键词：单循环链表；c 语言；约瑟夫环；
序言 数据结构是研究数据元素之间的逻辑关系的一门课程，以及数据元素及其关系在计算机中的存储表示和对这些数据所施加的运算。该课程设计的目的是通过课程设计的综合训练，培养分析和编程等实际动手能力，系统掌握数据结构这门课程的主要内容。 本次课程设计的内容是用单循环链表模拟约瑟夫环问题，循环链表是一种首尾相接链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活，约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例，了解单链表和单循环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。 通过该课程设计，能运用所学知识，能上机解决一些实际问题，了解并初步掌握设计、实现较大程序的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。 章节安排 1........................... 摘要、序言.... 一、问题描述 1、课程设计目的.................. (4) 2、课程设计任务.................. (4) 二、设计过程 1、设计思想（数据结构）.................. . (4) 2、设计表示（函数说明）.................. . (5) 3、详细设计（主要算法）.................. . (6) 4、用户手册（使用说明）.................. . (6) 三、测试报告
基础成绩：82分《数据结构》课程实验 实验报告 题目：Joseph问题求解算法的设计与实现 专业：网络工程 班级：网络102 姓名：张晨曦 学号： 102534 完成日期：2012/6/20 一、试验内容
- 约瑟夫（Joseph）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 二、试验目的 掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。 三、流程图 struct list {
- int num,code; struct list *next; }; void main() { printf("Joseph问题求解算法的设计与实现\n \n"); int i,j,m=1; int key; // 密码. int n; //人数. list *p,*s,*head; head=(list *)malloc(sizeof(list)); //为头结点分配空间. p=head; //使指针指向头节点 printf("输入人的总个数:"); scanf("%d",&n); for(i=1;i<=n;i++) { printf("第%d个人的密码:\n",i); scanf("%d",&key); s=p; p=(list *)malloc(sizeof(list)); //创建新的结点. s->next=p; p->num=i; p->code=key; } p->next=head->next; p=head; head=head->next; free(p); //释放头结点. p=head; printf("\n\n输入初始值:\n"); scanf("%d",&key); printf("\n出列顺序为:\n"); do { j=1; p=head; while(j
《数据结构与算法设计》约瑟夫环实验报告 ——实验一 专业:物联网工程 班级:物联网1班 学号: 姓名:刘沛航
一、实验目的 1、熟悉VC环境,学习使用C语言利用链表的存储结构解决实际的问题。 2、在编程、上机调试的过程中,加深对线性链表这种数据结构的基本概念理解。 3、锻炼较强的思维与动手能力与更加了解编程思想与编程技巧。 二、实验内容 1、采用单向环表实现约瑟夫环。 请按以下要求编程实现: ①从键盘输入整数m,通过create函数生成一个具有m个结点的 单向环表。环表中的结点编号依次为1,2,……,m。 ②从键盘输入整数s(1<=s<=m)与n,从环表的第s个结点开始计 数为1,当计数到第n个结点时,输出该第n结点对应的编号, 将该结点从环表中消除,从输出结点的下一个结点开始重新计 数到n,这样,不断进行计数,不断进行输出,直到输出了这个环 表的全部结点为止。 例如,m=10,s=3,n=4。则输出序列为:6,10,4,9,5,2,1,3,8,7。 三、程序设计 1、概要设计 为了解决约瑟夫环的问题,我们可以建立单向环表来存储每个人的信息(该人的编号以及其下一个人的编号),及结点,人后通
过查找每个结点,完成相应的操作来解决约瑟夫问题。 （1） 抽象数据类型定义 ADT Joh{ 数据对象:D={|,1,2,,,0}i i a a ElemSet i n n ∈=≥ 数据关系:R1=11{,|,,1,2,,}i i i i a a a a D i n --<>∈= 基本操作: create(&J, n) 操作结果:构造一个有n 个结点的单向环表J 。 show(J) 初始条件:单向环表J 已存在。 操作结果:按顺序在屏幕上输出J 的数据元素。 calculate( J,s,n) 初始条件:单向环表J 已存在,s>0,n>0,s<环表结点 数。 操作结果:返回约瑟夫环的计算结果。 }ADT Joh (2)宏定义 #define NULL 0 #define OK 1 #define ERROR -1 (3)主程序流程
数据结构实验报告 题目：约瑟夫环 姓名： 学号： 专业班级： 指导教师： 课题工作时间：
一．需求分析 1.约瑟夫环（Joseph）问题的一种描述是：设有编号1,2,3。。。n(n>0)的N个人围成一个圈，每个人持有一个密码（正整数）。开始时从第k（1<=k<=n）个人按顺时针方向自1开始顺序报数，报到m（m为第K个人的密码）的人出圈，再以这个人顺时针方向上的下一个人的密码为m，并开始重新从1报数。如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，有用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在其后。 3.测试数据 (1)m=20, n=7, 结果依次为为3，1，7，2，4，8，4 (2)m=20,n=1 (3)m=20,n=0 前面一组为常规数据，后面两组为边缘数据 二、概要设计 本程序是多文件程序，构成的函数有 int main() 主函数，输出出队序列 int initsuiji() 随机数产生初始化 int suiji(int x,int y) 随机数产生函数 int InitList(SqList &L) 初始化顺序表 int ListInsert(SqList &L,int i,ElemType e) 在顺序表中插入元素 int ListDelete(SqList &L,int i,ElemType &e) 删除顺序表中的元素 int shunxu(int number) 顺序存储算法 JosephuNode *Creat_Node(int numbers) 创建单循环链表 void Josephu(JosephuNode *head,int Password) 添加元素信息 int lianbiao(int number) 链表算法 其中，void main()是最主要的函数，分别执行两种算法，并在执行的同时按照出列顺序输出元素信息（编号，密码），并在结尾输出两种算法执行所用的时间长短。 三、详细设计 头文件 #include
《数据结构》课程设计报告书 设计题目：约瑟夫环 专业： 班级： 姓名： 指导教师： 完成日期：
目录 一、问题描述 (1) 二、基本要求 (1) 三、测试数据 (1) 四、算法思想 (2) 五、模块划分 (3) 六、数据结构 (4) 七、源程序 (4) 八、界面设计 (6) 九、运行与测试 (6) 十、总结 (8) 十一、思考与感悟 (9)
课程设计设计报告书 一、问题描述 约瑟夫问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。改进约瑟夫问题的描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈, 每人有一个密码（整数），留作其出圈后应报到后出圈。报数方法采用顺时针报数和逆时针报数交替进行，初始密码可任意确定。求最后剩下的人的编号。这个就是约瑟夫环问题的实际场景，后来老师要求我们对要求中的每人所持有的密码以及第一次的报数上限值要用随机数产生。因此约瑟夫环问题如果采用双向循环链表则能很好的解决。循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。p->link=head解决问题的核心步骤：先建立一个具有n个链结点，无头结点的循环链表，然后确定第一个报数人的位置，并不断地从链表中删除链结点，直到链表为空。 二、基本要求 (1)输入的形式和输入值的范围：输入的形式是以数字的形式输入，输入范围为-2147483648～2147483648 (2)输出的形式：字符串形式输出 (3)程序所能达到的功能：达到符合约瑟夫环要求的响应功能。 三、测试数据 进入程序，显示“1.开始游戏0.退出游戏”输入非0数进入游戏，输入0退出游戏。 进入游戏后显示“输入总人数”，输入大于0的整数；若输入错误，则光标处清空，重新输入。 后提示“输入开始人的序号”；范围是大于零，小于总人数的整数，若输入错误，则光标处清空，重新输入。 后提示“输入间隔数字”，范围是任意正整数；若输入错误，则光标处清空，重新输入。 按回车键，显示结果，并重新询问“1.开始游戏0.退出游戏”。
题目：编制一个程序模拟约瑟夫问题 一﹑需求分析 1. 本程序将模拟约瑟夫问题，求出出列的编号，并在每次出列后显示此时的顺序，本程序采用循环链表作为存储结构，无带头结点。 2. 输入可以是文件输入或标准输入，链表长度size>0，各个结点所带的密码值secret>0,第一次的报数m>0，若m<1，将提示更正。 3. 本程序在输入完毕后将先输出刚输入的内容,再提供报数后，开始进行运算,每出列一次将显示出列者和出列后链表顺序。 4. 测试数据：长度7，密码：3,1,7,2,4,8,4，报数初值6；长度-1，密码：3,2,5,6,4；长度5，密码：3,2,5,0,4; 长度5，密码：3,2,5,6,4，报数初值-1,4。 二﹑概要设计 采用循环链表表示约瑟夫环 1. 循环链表的抽象定义： ADT CycList{ 数据对象:D={i a ,i b |i a ,i b ∈ I ,i=1,2,…3,n>0} 数据关系:R={|i a ,i b ∈D,I=1,2…3} 基本操作: CreatList(&L,&in) 初始条件：输入流有效，输入的值合法，申请空间成功 操作结果：构造一个非空的循环链表 PrintList(const L) 初始条件：循环链表L 已存在 操作结果：输出L Fun(&L,Secret) 初始条件：循环链表L 已存在 操作结果：得到出列顺序 } 2. 本程序包含两个模块： 1) 主程序模块 2) 循环链表模块
三﹑详细设计 #include
《约瑟夫环》实验报告 专业：网络工程班级 学号姓名 一、问题描述： 约瑟夫问题的一种描述是：编号为1，2，……，n点的n个人按顺时针方向围坐一个圈，每人持有一个密码。一开始选一个正整数作为报数上限值m，从第一个人开始从顺时针方向自1开始报数，报到m时停止。报到m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始从新从1报数，如此下去，直达所有人出列。 基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各人的编号。 测试数据：m的初始值为20；n=7，7个人的密码依次是3，1，7，2，4，8，4，首先m的值为6（正确的出列顺序为6，1，4，7，2，3，5） 二、程序设计的基本思想，原理和算法描述： 采用结构体定义单链表，格式为：struct Lnode {int number; int password; struct Lnode*next; }Lnode,*p,*q,*head; 其中number是人的排列序号，password是各人所持有的密码值，next是节点指针。Lnode是节点变量，p、q是节点，head是头指针。 程序的代码：定义变量n，i,m,j 输入人的数量n If n<=0或n>30 重新输入n值 当0
附件4：课程设计报告书 《数据结构》 课程设计报告 约瑟夫（Joseph）环 组别第七组 组长 组成员 成绩 指导教师 计算机科学与技术系 2014年6月11日
摘要 约瑟夫环问题是典型的线性表的应用实例，其开发主要包括后台数据库的建立和维护以及前端应用程序的开发两个方面。对于前者要求建立起数据一致性和完整性强、数据安全性好的库。而对于后者则要求应用程序功能完备，易使用等特点。 经过分析，我们使用MICROSOFT公司的Microsoft Visual C++6.0开发工具，利用其提供的各种面向对象的开发工具，尤其是数据窗口这一能方便而简洁操作数据库的智能化对象，首先在短时间内建立系统原型，然后，对初始原型系统进行需求迭代，不断修正和改进，直到形成用户满意的可行系统。 关键词：单循环链表；c语言；约瑟夫环； 序言 数据结构是研究数据元素之间的逻辑关系的一门课程，以及数据元素及其关系在计算机中的存储表示和对这些数据所施加的运算。该课程设计的目的是通过课程设计的综合训练，培养分析和编程等实际动手能力，系统掌握数据结构这门课程的主要内容。 本次课程设计的内容是用单循环链表模拟约瑟夫环问题，循环链表是一种首尾相接链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活，约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例，了解单链表和单循环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。 通过该课程设计，能运用所学知识，能上机解决一些实际问题，了解并初步掌握设计、实现较大程序的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。
实验报告 实验课名称：数据结构实验一 实验名称：约瑟夫环问题 时间 班级000 学号000 姓名神刀公 子 1.问题描述 约瑟夫环问题 （1）问题描述 设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。 （2）基本要求 建立模型，确定存储结构。 对任意n个人，密码为m，实现约瑟夫环问题。 出圈的顺序可以依次输出，也可以用一个数组存储。 （3）思考： 采用顺序存储结构如何实现约瑟夫环问题？ 如果每个人持有的密码不同，应如何实现约瑟夫环问题？ 2.数据结构设计 由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型：struct Node { int data; //数据域 Node *next; //next指针指向下一个结点 }; 3.算法设计 问题要求建立模型，确定存储结构，之后对任意n个人，密码为m，实现约瑟夫环问题，出圈的顺序可以依次输出，也可以用一个数组存储。
设计流程图如图1.1所示。 开始 输出提示语 输入所需参数 创建链表，计算，得出结果 输出结果 结束 图1.1 设计流程图 （1）创建循环链表 由于内容的要求以及问题的方便，用循环链表作为本次实验的抽象数据类型。申请一个结点作为第一个结点，之后调用creat_list函数将后续结点一次插入链接，构造为循环链表。 NODE *link(int number) { NODE *head=NULL,*p=NULL,*q=NULL; int i=1; head=(struct node*)malloc(sizeof(struct node)); head->value=i; p=head; for(i=2; i<=number; i++)
约瑟夫环的三种实现方法的实验报告 公选题：约瑟夫环（使用一维数组、一维结构体数组、循环链表三种方法完成）一，实验目的 1、学会通过对问题的分析，设计一种合理的数据结构，并进行定义及操作的实现。 2、掌握利用一维数组，结构体，还有循环链表的各种操作来进行具体的实际应用。 3、加强程序设计的能力。 二，实验内容 什么是约瑟夫环？ 约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。 举例如下； n = 9, k = 1, m = 5 【解答】 出局人的顺序为5, 1, 7, 4, 3, 6, 9, 2, 8。 三，怎么用程序来实现这个实际场景？ 要实现这个场景有多种语言（C，C++，JA V A语言，C#），每一种语言在实现的过程中各有不同，在实现上复杂程度也不同。针对自己目前的水平以及查阅相关资料，做了如下的一些解决方案。 四，三种解决方法（） 1，使用一维数组： #include
{ int x; printf("请输入第%d个元素的值：\n",i+1); scanf("%d",&x); a[i]=x; i++; } printf("所有元素信息如下：\n"); for(int j=0;j
实验一线性表的基本操作及其应用 一、实验目的 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、主要思想： 首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环本身具有循环性质，考虑采用循环链表，为了统一对表中任意节点的操作，循环链表不带头结点。循环链表的结点定义为如下结构类型：
typedef struct LNode { int num,pwd; //num存储人的序号，pwd存储人的密码 struct LNode *next; }; 其次，建立一个不带头结点的循环链表并由头指针Head指示。 最后，设计约瑟夫环问题的算法。 2、本程序包含四个模块 1）主函数 void main() { int m,n;//分别为报数上限和人数 printf("\n参数m,n传递报数上限和人数.\n\n请输入m和n：\n"); scanf("%d %d",&m,&n); creatLinkList(n);//带哦用创建链表函数 enterPwd(n);//调用输入密码函数 printf("\n出列的人依次是：\n"); outList(m,n); } 2）创建链表函数creatLinkList()——根据用户输入的人数创建人数相等数量结点的循环链表。 3）输入密码函数enterPwd()——根据用户输入的密码，存入相应结点的数据域pwd； 4）输出出列人的序号函数outList(m,n) 3、核心算法 根据用户输入的报数上限以及人数，在一个循环里面循环和人数相等的次数。这个循环里面还有一个小的循环用于找到每次出列的结点，小循环找到了出列结点的上一个结点。然后记下这个结点，接着去除要出列结点的数据域里的pwd，然后free （）这个结点。开始找下一个出列的结点。 for(i=1;i<=n;i++) //搜索循环链表 { for(a=1;a
实验报告 课程名称：数据结构班级：实验成绩： 实验名称：顺序表和链表的应用学号：批阅教师签字： 实验编号：实验一姓名：实验日期： 指导教师：组号：实验时间： 一、实验目的 （1）掌握线性表的基本操作（插入、删除、查找）以及线性表合并等运算在顺序存储结构、链式存储结构上的实现。重点掌握链式存储结构实现的各种操作。 （2）掌握线性表的链式存储结构的应用。 二、实验内容与实验步骤 （1）实验内容： 实现约瑟夫环，约瑟夫环（Joseph）问题的一种描述是：编号为1、2、3……n的n个人按照顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按照顺时针的方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。设计一个程序求出出列顺序。 （2）抽象数据类型和设计的函数描述，说明解决设想。 首先定义一个链表，用其中的data项存储每个人的编号，用password项存储每个人所持有的密码，并且声明一个指针。之后使用CreatList_CL函数来创建一个循环链表，在其中的data和password中存入编号和密码，最后使最后一个节点的next指向L，使其能够形成循环队列。定义了函数Display来显示链表当中的内容，以确定存储的数据没有错误。定义了函数Delete_L来实现约瑟夫环中依次删除的功能，依次比较，如果某个人所持的密码和m值相等，则删除这个结点，并且输出此时该结点的编号和密码，实现出列的功能。 （3）简短明确地写出实验所采用的存储结构，并加以说明。 该实验我主要采用的是线性表的链式存储结构，首先定义了链表的结构，其中包括data 项和password项，分别存储每个人的编号和所持密码，还声明了指向下一个结点的指针，该指针可以连接各个结点，并且将最后一个结点的指针指向第一个结点使之成为一个循环链表。 三、实验环境 操作系统：Windows 7 调试软件名称：VC++ 版本号：6.0 上机地点：综合楼311 四、实验过程与分析 （1）主要的函数或操作内部的主要算法，分析这个算法的时、空复杂度，并说明设计的巧
数据结构上机实验报告 02090401 12 雒文杰题目：约瑟夫环问题 一．问题描述 设有n个人围做一圈，现从某个人开始报数，数到m的人出列，接着从出列的下一个人开始重新报数，数到m的人又出列，如此下去，直到所有人都出列为止。试设计确定他们的出列次序序列的程序。 二．基本要求 运用循环单链表解决约瑟夫环问题。 三．算法说明 本程序采用循环单链表的算法来解决约瑟夫环问题：建立一个循环单链表，按顺序查找指定结点，找到后删除，最后打印删除的编号序列。 四．源程序清单 #include {new_node=(clink)malloc(sizeof(cnode)); if(!new_node) return NULL; new_node->data=array[i]; new_node->order=i+1; new_node->next=NULL; before->next=new_node; before=new_node; } new_node->next=head; return head; } void main() {clink head,ptr; int find,j,i,a,list[n]; printf("Please input 'm'\n"); for(i=0;i
相关主题
文本预览