数据结构课程设计报告约瑟夫环完整版

学院计算机与信息工程系数据结构课程设计设计题目：约瑟夫环问题专业班级学号姓名指导教师2010年12月20日约瑟夫环一.实验目的：本实验是设计一个可以解决约瑟夫环问题的程序。

此程序要求利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号。

二.实验环境：VC2008.三.试验步骤：1.问题分析和任务定义本实验要求设计一个程序解决约瑟夫环问题，且要利用单向循环链表存储结构模拟此过程。

这就要求我们必须用链表结构而不能用像数组等其它结构。

首先输入的数据必须是整型且是整数，同样输出的也必须是整型且整数；其次也要备好测试数据（包括合法的输入数据和非法形式输入的数据）以此来检查程序是否符合要求；最后2.数据类型和系统设计链表存储结构的定义：typedef struct Node{}SeqList链表的建立：SeqList * Creat(int num){}链表的输出：void OutQueue(SeqList * tail, int num, int code){}3.详细设计：#include <stdio.h>#include <stdlib.h>typedef struct Node{int num;int code;struct Node * next;}SeqList;SeqList * Creat(int);void OutQueue(SeqList *, int , int );int main(){int n,m,i;printf( " 姓名：徐正杰学号：090502201：\n");printf("Input The Number of People, Frist Code:");{int num = 0,code = 0;scanf("%d%d",&num, &code);{SeqList * tail = NULL;tail=Creat(num);OutQueue(tail, num, code);}}return 0;}SeqList * Creat(int num){getchar();SeqList * tail = NULL;tail=(SeqList *)malloc(sizeof(SeqList));{int i = 1, code = 0;printf("Input Num.%d Code:", i);scanf("%d", &code);tail->num = i;tail->code = code;tail->next = tail;{SeqList * p = NULL;for(i = 2; i <= num; ++i){p = (SeqList *)malloc(sizeof(SeqList));if(p){printf("Input Num.%d Code:", i);scanf("%d", &code);p->num = i;p->code = code;p->next = tail->next;tail->next = p;tail = p;}else{perror("Out of menroy!");getchar();exit(1);}}}}return(tail);}void OutQueue(SeqList * tail, int num, int code) {printf("Out of Queue:");{SeqList * p;while(tail - tail->next){code=(code-1)%num+1;{int i;for(i = 1; i < code; ++i){tail = tail->next;}}p = tail->next;printf("%d,", p->num);tail->next = p->next;code = p->code;free(p);p = NULL;--num;}}printf("%d.",tail->num);free(tail);tail = NULL;}4.调试分析在本次试验调试中很不顺利。

*******************实践教学*******************兰州理工大学软件职业技术学院2011年春季学期算法与数据结构课程设计题目：约瑟夫环专业班级：姓名：学号：指导教师：成绩：摘要约瑟夫环问题是典型的线性表的应用实例，其开发主要包括后台数据库的建立和维护以及前端应用程序的开发两个方面。

对于前者要求建立起数据一致性和完整性强、数据安全性好的库。

而对于后者则要求应用程序功能完备，易使用等特点。

经过分析，我们使用MICROSOFT公司的Microsoft Visual C++6.0开发工具，利用其提供的各种面向对象的开发工具，尤其是数据窗口这一能方便而简洁操纵数据库的智能化对象，首先在短时间内建立系统应用原型，然后，对初始原型系统进行需求迭代，不断修正和改进，直到形成用户满意的可行系统。

关键词：单循环链表；c语言；约瑟夫环；序言数据结构是研究数据元素之间的逻辑关系的一门课程，以及数据元素及其关系在计算机中的存储表示和对这些数据所施加的运算。

该课程设计的目的是通过课程设计的综合训练，培养分析和编程等实际动手能力，系统掌握数据结构这门课程的主要内容。

本次课程设计的内容是用单循环链表模拟约瑟夫环问题，循环链表是一种首尾相接链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活，约瑟夫环问题就是用单循环链表处理的一个实际应用。

通过这个设计实例，了解单链表和单循环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。

通过该课程设计，能运用所学知识，能上机解决一些实际问题，了解并初步掌握设计、实现较大程序的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。

目录摘要0序言1目录2正文3一、问题描述3二、逻辑设计5三、详细设计7四、程序代码16五、程序调试与测试16设计总结18参考文献19致谢20附录20正文一、问题描述约瑟夫环问题描述的是：设编号为1，2，…，n的n （n>0）个人按顺时针方向围坐一圈，每个人持有一正整数密码。

数据结构上机实验报告1、需求分析1：用一个循环链表实现n个人按顺时针排成一圈,每个人看作一个节点,每个节点都是一个结构体类型,包含三个域: 序号域(data), 密码域(key),指向下一个人的指针域(next).2：程序开始时由用户任意输入人数n及一个正整数作为报数上限值m,一个正整数作为密码最大值，判断所输密码是否在范围内。

然后为依次每一个人指定一个密码3：初始密码为用户外部输入的密码m, 从第一个人开始按顺市针方向自1开始报数.,报道m的时停止,报m的人出列,将他的密码作为新的密码值(m), 从他在顺针方向的下一个人开始重新从1报数,如此下去,直至所有的人全部出列为止.4：本程序最终结果为n 的人的出列顺序5：测试数据: m的初值为1; n =5(即有5个人)57个人的密码依次为:1，2，3,4，5.首先没的值为1,正确的出列顺序应为1，2，4，3，5。

2概要分析（1）抽象数据类型的定义：为实现上述程序的功能，可以用整数存储用户的输入。

并将用户输入的值存储于线性表中。

算法的基本思想：约瑟夫环问题中的数据是人所在的位置，而这种数据是存在“第一元素、最后元素”，并且存在“唯一的前驱和后继的”，符合线性表的特点。

由于需要模拟约瑟夫环的出列问题，可以采用顺序表来实现线性表，完成出列顺序的输出。

核心算法主要分为两步：1、确定需要删除的位置，2、设置并删除该位置。

已知报数间隔m，我们可以把当前位置加上m获得需要删除的位置，如果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正（即模拟环状计数）。

然后把顺序表中的当前指向位置设置为该位置，继而删掉该位置。

反复进行上述确定位置和删除位置的操作，直到顺序表为空。

（2）主程序的流程：程序由三个模块组成：（1）输入模块：无提示语句，直接输入总人数n和报数次数m，中间用逗号隔开。

（2）构造链表并输入每个人信息模块：（3）主要处理出列的函数：分别在DOS下和文件中，按移除元素的顺序依次显示其位置。

合肥学院计算机科学与技术系课程设计报告2009～2010学年第二学期课程数据结构与算法课程设计名称joseph环学生姓名朱玉庭学号0804012029专业班级08计本(2)指导教师王昆仑、张贯虹2010 年06月08号一、问题分析和任务定义：约瑟夫环是一个数学游戏，根据游戏内容的描述，能够很容易的看出，游戏中的玩家顺时针围坐一圈，能够很容易的发现，这跟本课上的单循环链表非常相似，所以可以通过单循环链表存储结构模拟此过程，当游戏中的玩家出列时，可以通过删除单循环链表中的结点来实现。

二、数据结构的选择和概要设计：选择带为指针的单循环链表来解决这个问题，先建立一个空链表，然后根据人数生成具有相应结点的单循环链表，知道密码后，通过循环来找到对应的结点，然后将该结点的编号输出，改变密码，最后删除结点，以此类推，知道编码全部输完，即可得到结果序列。

三、详细设计和编码：本题目是通过单循环链表存储结构来模拟此过程的，首先要先明确该单循环链表中结点的结构类型，定义如下：typedef struct Node{int key; //每个人持有的密码int num; //这个人的编号struct Node *next; //指向下一个结点}Link;当生成单循环链表时，就需要用到课本上创建单循环链表的有关内容了，可以先通过子函数Link *InitList()建立一个空链表，返回指针L，然后将返回的指针代入子函数Link *Creater(Link *L,int n)的形参中，对循环链表进行初始化，并且也返回一个指针，然后再将这个返回的指针代入到输出函数void Output(Link *L,int n,int m)的形参中，要想根据题目要求完成序列的输出，需要通过两个for循环来实现，第一个循环for(i=1;i<=n;i++) ，因为一个用n个人，所以结果要输出n个编号，这个循环每循环一次输出一个编号即printf("%d ",q->num)，并将该编号下的密码赋值给m 即m=q->key，当循环完毕时正好将编号全部输出，第二个循环for(j=1;j<m;j++) p=p->next; q=p->next; 用以找到相应的结点，并用指针q指向它，当完成了编号的输出和密码的赋值后，删除q指向的结点，将两个循环适当结合，即可输出正确的结果序列，其中的人数n和初始密码在主函数中确定。

《数据结构与算法设计》约瑟夫环实验报告——实验一专业：物联网工程班级：物联网1班学号：15180118姓名：刘沛航一、实验目的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 ∈=≥K数据关系：R1=11{,|,,1,2,,}i i i i a a a a D i n --<>∈=K基本操作：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）主程序流程（4）程序分为下述模块：1）主函数模块——执行输入调用其他的功能函数2）创建环表模块——创建单向环表3）计算处理模块——计算出要出列的标号并输出4）显示模块——输出建立好的环表调用关系如下：2、详细设计(1)数据类型设计typedef int ElemType; //元素类型typedef struct {ElemType data;struct Joh *next;}Joh, *LinkList,*p; //结点类型，指针类型(2)操作算法Status create(LinkList &J,int n){//创建一个有n个结点的单向环表if(n<=0)return ERROR; //n<0错误J=(LinkList)malloc(sizeof(J));J->data=1;J->next=J;//建立第一个结点for(int i=n;i>1;--i){p=(LinkList)malloc(sizeof(J));p->data=i;p->next=J->next;J->next=p;//插入到表头}return OK;}//createvoid show(LinkList J){//主要的操作函数//顺序输出环表J的结点p=J;printf("%d ",p->data);p=p->next;while(p!=J){ //循环终止条件printf("%d ",p->data);p=p->next;}}//showvoid calculate(LinkList J,int s,int n){p=J;Joh *head=p; //声明结点while(p->data!=s){p=p->next;head=p;}//寻找起始结点while(p->next!=p){ //终止条件for(int i=0;i<n-1;i++){head=p; //保存前置节点p=p->next;}printf("%d ",p->data);head->next=p->next; //删除已输出结点p=head->next;}if(n!=1)printf("%d\n",p->data);elseprintf("\n");}//calculate(3)主函数代码int main(){//主函数Joh *J;int m,s,n;printf("The num of node is:");scanf("%d",&m);create(J,m); //创建单向环表Jshow(J); //输出J的数据printf("\n");printf("The first node which you want is:");scanf("%d",&s);printf("The internal which you want is:");scanf("%d",&n);calculate(J,s,n); //计算并输出结果return 0;}//main四、程序调试分析1、细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。

北邮数据结构实验-约瑟夫环数据结构实验报告实验名称：实验1——约瑟夫环学生姓名：班级：班内序号：学号：日期：1．实验要求实验目的：通过利用循环链表实现约瑟夫问题的求解进行实现，掌握如下内容：1.熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法2.学习指针、模板类、异常处理的使用3.掌握线性表的操作的实现方法4.学习使用线性表解决实际问题的能力实验内容：利用循环链表实现约瑟夫问题的求解。

约瑟夫问题如下：已知n个人（n>=1）围坐一圆桌周围，从1开始顺序编号。

从序号为1的人开始报数，顺时针数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规则重复下去，直到所有人全部出列。

请问最后一个出列的人的编号。

2. 程序分析2.1 存储结构首先构建结点的结构体，包括结点的编号number和指向后继元素的指针*next。

然后构建循环链表储存每一个结点。

2.2 关键算法分析1、关键算法：插入：用尾插法构建循环链表，建立一个尾指针r用来保存最后一个结点的地址，插入每一个节点后，r指向新插入的结点。

用for循环来给每一个结点的number赋值。

插入的步骤：1.建立新指针s；2.在for循环中给s赋值；3.将r指针指向s；4.修改尾指针r=s5.在全部结点插入后，将终端结点指向第一个指针，r->next=front->next。

约瑟夫环算法实现：1.因为每次循环都有一个人出列，最后只剩一个人，因此要进行n-1次循环，用for循环实现。

2.同时定义一个指针p=front->next，每次循环front和p均后移m-1个，使p指向每次循环的第m个人，front指向第m-1个人。

并输出出列的人的number，即p->number。

3.让front->next=p->next，删除p。

4.继续进行循环2、代码详细分析：约瑟夫环算法步骤：①定义一个指针p=front->next，每次循环front和p均后移m-1个，使p指向每次循环的第m个人，front指向第m-1个人。

数据结构课程设计报告设计课题：约瑟夫问题院系：计算机科学与技术学院专业班级：计算机网络技术1102 班学生姓名：张利学号： 1 1 0 8 0 4 0 2 1 1指导教师：王昱哲目录1. 需求剖析 . (3)1.1 问题描绘 (3)1.2功能剖析 (4)2. 纲要设计 . (5)3. 详尽设计 . (6)4. 调试与操作说明 ........... 1 错误 ! 不决义书签。

总结 . (16)一．需求剖析1.1 问题描绘瑟夫描绘的是：号1，2，⋯， n 的 n（n>0）个人按方向坐一圈，每一个人拥有一正整数密。

开始一个正整数作数上限m，从第一个人开始方向自 1 起序数，到 m停止数， m的人出圈，将他的密作新的 m，从他在方向上的下一个人起从头从 1数。

这样下去，直到所有人都出圈止。

令n 最大 100。

要求一个程序模此程，求出出圈的号序列。

以下剖析：这是第一个人，他的密码是“ 1”，个他输一个 m 值，假如 m=3,则从他开始向下走3个213这就是第二步的地点，这时他的密码作为新的m 值，即 m=4,同时获得的第一个密码为4；4 号出去处下走4，到9 这儿；（这这一步完了剩余的为：041,2,3,5,6 ，， 7,8,9,0，）95867这就是第三步的地点，这时他的密码作为新的m值，即m=9 ，同时获得的第二个密码为9；9 号出去处下走9，到 0 这儿；持续走就行了（这儿节余的就是： 1 ， 2， 3， 5，6,7,8,0）图 1 约瑟夫环问图解第三步：约瑟夫环原理演示图第二次， 1 号出列1234567 3172484第四步：第三次，第一步：给第一个人第二部：第一次停下的地点，此赋初始密码为： 20则4 号出列时 6 号出列，并将他的值作为新从它开始向下走20的 m 值，即：新的 m=8；从 7次，到 6 号地点好开始持续向下走8 次，到 1 号最后排序后的密码序列：的地点（本图只演示前两步）8324174 6147235图 2约瑟夫环原理演示图1.2 功能剖析约瑟夫环问题是一个古老的数学识题，本次课题要求用程序语言的方式解决数学识题。

课程设计报告课程设计名称：数据结构课程设计课程设计题目：约瑟夫环院（系）：专业：班级：学号：姓名：指导教师：目录1 课程设计介绍 (1)1.1课程设计内容 (1)1.2课程设计要求 (1)2 课程设计原理 (2)2.1课设题目粗略分析 (2)2.2原理图介绍 (2)2.2.1 功能模块图（如图2.1） (2)2.2.2 流程图分析 (3)3 数据结构分析 (5)3.1存储结构 (5)3.2算法描述 (5)4 调试与分析 (6)4.1调试过程 (6)4.2程序执行过程 (6)参考文献 (8)附录（关键部分程序清单） (9)1 课程设计介绍1.1 课程设计内容编号为1,2，……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。

使用单循环链表作为存储结构分析：由题意可以将每个人看做链表上的一个节点，每个人持有的密码即为每个节点所存储的数据；相邻的人之间存在连结关系，即链表的两个相邻节点之间由指针来进行关联；最后一个人和第一个人也存在连结关系，即链表的末尾节点和头结点相连构成了单循环链表存储结构。

执行报数过程可以看做一个单独指针依次指向每一个节点，有人出列即删除掉链表中相应的节点。

1.2 课程设计要求1.参考相应的资料，独立完成课程设计任务。

2.交规范课程设计报告和软件代码。

2课程设计原理2.1 课设题目粗略分析根据课设题目要求，程序应该分为两大部分：1、单循环链表储存结构的建立：建立所需的单循环链表数据存储结构，对每个节点输入所需的密码、序号数据并通过指针连接成单循环链表。

2、实现约瑟夫环数据出列顺序的算法：依照题目要求按照报数上限对节点进行查找和删除操作，按顺序输出出列的节点序号，依照每次出列的节点存储的密码修改报数上限循环操作直到全部节点出列完毕程序运行结束。

《数据结构》课程设计报告课程名称：《数据结构》课程设计课程设计题目：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; //顺序int code; //密码LinkNode *next;};建立一个类LinkList ,包含的函数：LinkList(); //构造函数void Creat(const int ); //创建循环链表int Delete(LinkNode* ); //删除报到数的结点int Joseph(int ); // 约瑟夫环私有成员是LinkNode* head; //指向第一个结点的指针LinkNode* elem; // 同上int len; //长度我定义了一个elem指针是为了约瑟夫环里运行方便，elem只在约瑟夫环这个函数里用到，其他函数没有特别大的用处。

课程设计报告一、需求分析1、本演示程序中，利用单向循环链表存储结构模拟约瑟夫问题的进行。

程序运行后，首先要求用户指定初始报数上限值，然后读取个人的密码。

可设n≤30。

此题所用的循环链表中不需要“头结点”，因此在程序设计中应注意空表和非空表的界限。

2、演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令：相应的输入数据和运算结果显示在其后。

3、程序执行的命令包括：1）构造约瑟夫环；2）执行约瑟夫环，并输出出列人的序号以及相应的密码；3）结束。

4、测试数据1）m的初始值为20；2）n=7，7个人的密码依次为：3、1、7、2、4、8、4。

3）首先m值为6，正确的出列顺序应为6、1、4、7、2、3、5。

二、概要设计为实现上述程序功能，应以单向循环链表表示约瑟夫环。

为此，需要两个抽象数据类型：单向循环链表和约瑟夫环。

1）、单向循环链表的抽象数据类型定义为：ADT List{数据对象：D={ai｜ai∈Elemset,i=1,2,…,n,n≥0}数据关系：R1={＜a(i-1),ai＞｜a(i-1),ai∈D,i=2,…n}基本操作：InitList(&L)操作结果：构造一个空的链表L。

DestroyList(&L)初始条件：线性表L已存在。

操作结果：销毁线性表L。

ListLength(L)初始条件：线性表L已存在。

操作结果：返回L中数据元素个数。

GetElem(L,i,&e)初始条件：线性表L已存在，1≤i≤ListLength(L)。

操作结果：用e返回L中第i个数据元素的值。

ListInsert(&L,I,e)初始条件：线性表L已存在，1≤i≤ListLength(L)+1。

操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。

ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1≤i≤ListLength(L)。

数据结构课程设计报告（约瑟夫问题）问题描述约瑟夫问题:编号为1-n的n个人围坐圆桌旁,从任一指定编号为k的人开始报数,报数为m的人离开圆桌,下一个人接着从n开始报数, 报数为m的人又离开圆桌,依此重复,直至所有人离开圆桌.编一程序,输出离开圆桌的人的编号序列.设计思想首先采单循环链表建立整个约瑟夫环，手动输入总人数(既链表的长度)、每个人的所持下一轮报数出对值和初始报数值。

node->num为人的编号，node->为此人所持的下一轮报数值。

建立单循环链表后，通过初始报数值找到出列的人，输出node->num的值，然后将该结点中的data值作为下一轮的报数值。

重复以上过程直至所有的人都出列，则程序结束。

主要算法do{k=1;while(k!=m)//当k=m时，结束第一轮报数{p1=p1->next;k++;}//报数中将指针指向下一位p2=p1->next;p1->next=p2->next;//把报数为m的人的结点从链表中删除printf("编号为%d的人出列，他的key%d作为新的m值/n",p2->num,p2->data);//m=p2->data;//报数为m的人的密码作为下一轮新的m值free(p2);//释放报m的人的结点}while(p1->next!=p1);//当p1->指向自己时，报数结束的值加一，当k=m时，此时p1指向人出列，p2指向该结点的上一结点，k为计数器，指针每移动一次，k让上一结点的next指向该结点的下一结点，然后删除该结点。

P1指向该结点下一结点，令k=1，再开始下一轮报数。

等到所有人出列后，循环结束。

for(i=1;i<=n;i++){printf("请输入%d号同学的key",i);scanf("%d",&j);//输入学生所带有的密码p1->next =(listnode*)malloc(sizeof(listnode));//建立一个空间p1=p1->next ;p1->data=j;p1->num=i;//对结点的num和data成员赋值p1->next=head->next; }定义指针p1,然后建立一个新结点并将p1->next指向他，再将地址赋给p1，最后将head->next赋给p1->next,构成了循环单链表，然后让所有人键入链表并给num和data成员赋值。

华北科技学院课程设计说明书班级: 姓名:____设计题目: 约瑟夫环设计时间:____2011-2-28 至__2011-3-11指导教师:评语:_________________________________ _________________________________________ _________________________________________ _________________________________________ _________________________________________ 评阅成绩:＿＿＿＿评阅教师:＿＿＿＿＿一、设计题目与要求设计题目：约瑟夫环问题描述：编号为1，2… n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。

基本要求：1、利用单循环链表作为存储结构模拟此过程；2、键盘输入总人数、初始报数上限值m及各人密码；3、显示游戏中队形及各人密码变化过程；4、按照出列顺序输出各人的编号。

二、概要设计实验设计思路：1．以无头结点的单循环链表为存储结构模拟此过程。

2．键盘录入各各同学所持密码，存储在一维数组a[]中。

3．单循环链表初始化时，将密码和编号存入结构体中。

4．进行单链表删除操作，直到链表为空，输出的编号存入数组b[]中5．依次输出b[]中的元素。

程序结构：本程序是单文件程序，构成的函数有LinkedList LinkedListInit(int n,int a[]) 初始化循环单链表void LinkedListTraverse(LinkedList L) 遍历单链表void Play(LinkedList L,int m,int b[],int n) 单循环链表的删除void main() 主函数，输出出队序列其中，void Play()是最主要的函数，初始化单链表后，开始执行该函数，指针按给定的密码值m依次后移m次删除定位后的结点，输出编号，同时获得新的m 值，继续循环，直到该链表为空。