实验六 约瑟夫环的实现

一、实验目的1. 理解并掌握约瑟夫环问题的基本概念和解决方法。

2. 熟悉链表数据结构及其操作，提高编程能力。

3. 通过实验加深对数据结构和算法的理解，提高解决实际问题的能力。

二、实验原理约瑟夫环问题是一个经典的数学问题，描述了N个人围成一圈，从某个人开始报数，报到M的人出列，然后从下一个人开始重新报数，如此循环，直到所有人都出列为止。

本实验通过实现单向循环链表来模拟这个过程。

三、实验内容1. 单向循环链表实现：- 定义单向循环链表的节点结构体，包含数据域和指针域。

- 实现创建单向循环链表的函数，从键盘输入N和M，生成包含N个节点的单向循环链表。

- 实现遍历单向循环链表的函数，用于输出链表中的节点信息。

2. 约瑟夫环报数：- 实现报数函数，从链表的第一个人开始报数，报到M的人出列。

- 实现删除节点的函数，将出列的人从链表中删除。

- 实现重新开始报数的函数，从下一个人开始重新报数。

3. 输出结果：- 实现输出出列顺序的函数，将出列的人的编号按顺序输出。

四、实验步骤1. 定义单向循环链表的节点结构体：```ctypedef struct Node {int data; // 数据域struct Node next; // 指针域} Node;```2. 实现创建单向循环链表的函数：```cNode createList(int n) {Node head = NULL;Node tail = NULL;Node tmp = NULL;for (int i = 1; i <= n; i++) {tmp = (Node)malloc(sizeof(Node)); tmp->data = i;tmp->next = NULL;if (head == NULL) {head = tmp;tail = tmp;} else {tail->next = tmp;tail = tmp;}}tail->next = head; // 形成循环链表return tail; // 返回尾节点}```3. 实现遍历单向循环链表的函数：```cvoid printList(Node tail) {Node p = tail->next; // 从头节点开始遍历while (p != tail) {printf("%d ", p->data);p = p->next;}printf("\n");}```4. 实现报数函数：```cvoid josephus(int n, int m) {Node tail = createList(n); // 创建单向循环链表Node p = tail->next; // 从头节点开始报数Node q = NULL; // 记录出列节点的前一个节点 for (int i = 1; i <= n; i++) {for (int j = 1; j < m; j++) {q = p;p = p->next;}q->next = p->next; // 删除出列节点printf("%d ", p->data); // 输出出列节点编号free(p); // 释放出列节点内存p = q->next; // 从下一个人开始报数}printf("\n");}```5. 实现输出出列顺序的函数：```cvoid printOutSequence(int n, int m) {printf("出列顺序为：\n");josephus(n, m);}```五、实验结果与分析1. 实验结果：- 当N=7，M=3时，出列顺序为：6 1 4 7 2 3 5。

基础成绩：82分《数据结构》课程实验实验报告题目：Joseph问题求解算法的设计与实现专业：网络工程班级：网络102姓名：***学号： ******完成日期：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<key){s=p;p=p->next;//使P指向下一结点j++;} //报数过程.i=p->num;key=p->code;printf("%d\n",i);s->next=p->next;-head=p->next; //重新定义head,下次循环的开始结点.free(p);// 释放已出列的结点.n--; //人数减一.}while(n>0);int x;printf(“输入0退出：”);scanf(“%d”,&x);for(;;){if(x==o)break;}}五、调试过程调试过程中,曾出现过缺少分号、括号之类的错误,还出现过运算顺序颠倒，致使运算出现了错误，在经过仔细的检查并且向人请教,终于得出了正确结果.六、结果分析输入人数：7 输入密码：3 1 7 2 4 8 4 初值：6排序结果：6 1 4 7 2 3 5。

《数据结构》课程设计报告课程名称：《数据结构》课程设计课程设计题目：约瑟夫环姓名：张光栋院系：计算机学院专业：网络工程年级：2013级学号：13055532指导教师：张纪林一、需求分析1.以单项循环链表存储结构模拟约瑟夫环问题。

即编号为1、2、3…、n的n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。

报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。

按出列顺序印出各人的编号。

2.演示程序以用户与计算机的对话方式执行，用户输入相应的数据，输出结果显示在其后。

3.测试数据：(1)n=55个人的密码依次为：2,4,2,6,2；首先m值为2（正确的输出顺序为：2 1 4 3 5）(2)n=77个人的密码依次为：2,4,1,4,3,2,3首先m值为5（正确的输出顺序为：5 1 3 4 6 2 7）二、概要设计为实现上述程序功能，可利用单向循环链表存储结构模拟此过程。

1.单向循环链表的抽象数据类型定义为：ADT CircularList{数据对象：D={ai|ai∈LNode,i=1,2,…,n,n≥0}数据关系：R1={<ai-1,ai>|ai-1∈D,i=2,…,n}基本操作：Status LisCreate_L(LinkList &L,int I,ElemType &e)操作结果：在不带头结点的单链表L中，创建第i个元素，并用e赋值}2.本程序中包括的两个基本模块：1)主程序模块：Void main(){初始化；do{接受命令；处理命令；}while(“命令”=”退出”)}2)循环链表模块：实现循环链表的抽象数据结构三、详细设计1.结点类型typedef struct ListNode{int mi;int n;struct ListNode *next;}ListNode,*LinkList;2.用循环链表存储约瑟夫环，没有头结点，基本操作函数如下：void CreateList(LinkList&L, int n){LinkList s;int i;L=(LinkList)malloc(sizeof(ListNode));L->n=1;L->next=L;for(i=2;i<=n;i++){s=(LinkList)malloc(sizeof(ListNode));s->next=L->next;L->next=s;s->n=i;L=L->next;}}void Delete(LinkList L, int m){int i;LinkList p,q;p=L;while(p->next!=p){for(i=1;i<m;i++)p=p->next;q=p->next;m=q->mi;printf("%d ",q->n);p->next=q->next;free(q);}printf("%d ",p->n);free(p);}3.主函数：int main(){int n,i,m;LinkList L,p;printf("请输入人数:");scanf("%d",&n);CreateList(L,n);printf("请输入密令\n");p=L->next;for(i=1;i<=n;i++){printf("请输入第%d条密令\n",i);scanf("%d",&p->mi);p=p->next;}printf("请输入初始密令\n");scanf("%d",&m);printf("输出为\n");Delete(L, m);return 0;}四、调试分析1.第一次写时，没有区分出只剩下的一个的情况，导致最终输出出现错误。

约瑟夫问题实验报告背景约瑟夫问题（Josephus Problem）据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。

然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

原题：用户输入M,N值，N个人围成一个环，从0号人开始数,数到M,那个人就退出游戏，直到最后一个人求最后一个剩下的人是几号？问题描述设编号为1-n的n(n>0)个人按顺时针方向围成一圈．首先第1个人从1开始顺时针报数．报m的人(m 为正整数)．令其出列。

然后再从他的下一个人开始，重新从1顺时针报数，报m的人，再令其出列。

如此下去，直到圈中所有人出列为止。

求出列编号序列。

一.需求分析：(1)基本要求需要基于线性表的基本操作来实现约瑟夫问题需要利用循环链表来实现线性表（2）输入输出格式输入格式：n，m(n,m均为正整数，)输出格式1：在字符界面上输出这n个数的输出序列(3)测试用例（举例）输入：8，4输出：4 8 5 2 1 3 7 6二．概要设计（1）抽象数据类型：数据对象：n个整数数据关系：除第一个和最后一个n外，其余每个整数都有两个元素与该元素相邻。

基本操作：查找，初始化，删除，创建链表循环链表的存储结构:（2）.算法的基本思想循环链表基本思想：先把n个整数存入循环链表中，设置第m个数出列，从第一个开始查找，找到第m个时，输出第m个数，并删掉第m个节点，再从下一个数开始查找,重复上一步骤，直到链表为空，结束。

（3）.程序的流程程序由三个模块组成：1.输入模块：完成两个正整数的输入，存入变量n和m中2.处理模块：找到第m个数3.输出模块：按找到的顺序把n个数输出到屏幕上三．详细设计首先，设计实现约瑟夫环问题的存储结构。

浙江大学城市学院实验报告课程名称数据结构基础实验项目名称实验六约瑟夫环的实现学生姓名专业班级学号实验成绩指导老师（签名）日期一.实验目的和要求1、学会通过对问题的分析，设计一种合理的数据结构，并进行定义及操作的实现。

2、掌握利用线性表的各种操作来进行具体的实际应用。

3、加强程序设计的能力。

二.实验内容1、编写程序，模拟约瑟夫环（josephus）问题：n个人（编号为1，2，3，……，n (n>0) ）按顺时针方向围坐一圈，每人持有一个正整数密码。

开始时任意给出两个值：一个为首先报数的人的编号i (0<i<=n)，另一个为起始报数上限值m。

接着从编号为i的人开始按顺时针方向自1起顺序报数，报到m时停止报数，且报到m的人出列，并将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1报数，……，如此下去，直到所有人全部出列为止。

要求设计一个程序模拟此过程，给出出列人的编号序列。

基本要求:（1）人数n、每人的正整数密码、首次报数人编号i、初始报数上限值m均由键盘输入。

（2）参照线性表的抽象数据类型定义，设计本实验的抽象数据类型。

（3）根据你设计的抽象数据类型，分别用顺序存储结构和链式存储结构实现约瑟夫环问题。

并请分别将顺序存储结构的程序存放在文件test6_Seq.h（基本操作函数）、test6_Seq.cpp（主函数）中，链式存储结构的程序存放在文件test6_Link.h（基本操作函数）、test6_Link.cpp（主函数）中。

（4）设计测试数据，并调试程序，直到正确运行。

2、填写实验报告，实验报告文件取名为report6.doc。

3、上传实验报告文件report6.doc及源程序文件test6_Seq.h、test6_Seq.cpp、test6_Link.h、test6_Link.cpp到Ftp服务器（ftp://10.61.14.240:5000 ）自己的文件夹下。

同时上交一份书面的实验报告。

数据结构实验报告题目：约瑟夫环姓名：学号：专业班级：指导教师：课题工作时间：一．需求分析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()是最主要的函数，分别执行两种算法，并在执行的同时按照出列顺序输出元素信息（编号，密码），并在结尾输出两种算法执行所用的时间长短。

一、实验题目：约瑟夫环问题。

二、实验内容：设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。

开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m 的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。

如此下去，直到所有人全部出列为止。

令n最大值取30。

要求设计一个程序模拟此过程，求出出列编号序列。

实现：用一个不带头结点的单向循环链表表示上述约瑟夫环，结点结构可定义为：typedef struct node{ Array int pos;//位置int code;//密码struct node *next;}JosephNode,* JosephList;;三、程序源代码：# include <stdio.h># include <stdlib.h># define ERROR 0# define OK 1Typedef struct node{int pos,code;struct node *next;}JosephNode,* JosephList;int InitList_Joseph(JosephList &h,int n)//初始Joseph环。

//为什么就&h,而不是h??{ JosephNode *newp,*p;h=NULL;for(int i=1;i<=n;i++){ newp=(JosephList)malloc(sizeof(JosephNode));if(!newp)return ERROR;newp->pos=i;printf("Please input the %dth one's code\n ",i);scanf("%d",&newp->code);if(h==NULL){h=newp;p=newp;}else{p->next=newp;p=newp;}}p->next=h;return OK;}int length(JosephList &h)//求Joseph环的长度。

约瑟夫环数据结构实验报告约瑟夫环数据结构实验报告引言约瑟夫环是一种经典的数学问题，它涉及到一个有趣的数据结构。

本次实验旨在通过实现约瑟夫环数据结构，深入理解该问题，并探索其在实际应用中的潜力。

本报告将介绍实验的设计和实现过程，并分析实验结果。

实验设计在本次实验中，我们选择使用链表来实现约瑟夫环数据结构。

链表是一种非常灵活的数据结构，适合用于解决约瑟夫环问题。

我们设计了一个Josephus类，其中包含了创建环、添加元素、删除元素等操作。

实验实现1. 创建环在Josephus类中，我们首先需要创建一个循环链表。

我们使用一个头节点来表示环的起始位置。

在创建环的过程中，我们可以选择指定环的长度和起始位置。

2. 添加元素在创建环之后，我们可以通过添加元素来向约瑟夫环中插入数据。

我们可以选择在环的任意位置插入元素，并且可以动态地调整环的长度。

3. 删除元素根据约瑟夫环的规则，每次删除一个元素后，下一个元素将成为新的起始位置。

我们可以通过删除元素的操作来模拟约瑟夫环的运行过程。

在删除元素时，我们需要考虑环的长度和当前位置。

实验结果通过实验，我们得出了以下结论：1. 约瑟夫环数据结构可以有效地模拟约瑟夫环问题。

通过创建环、添加元素和删除元素的操作，我们可以模拟出约瑟夫环的运行过程，并得到最后剩下的元素。

2. 约瑟夫环数据结构具有一定的应用潜力。

除了解决约瑟夫环问题，该数据结构还可以用于其他类似的问题，如任务调度、进程管理等。

3. 约瑟夫环数据结构的时间复杂度较低。

由于约瑟夫环的特殊性质，我们可以通过简单的链表操作来实现该数据结构，使得其时间复杂度较低。

结论本次实验通过实现约瑟夫环数据结构，深入理解了该问题，并探索了其在实际应用中的潜力。

通过创建环、添加元素和删除元素的操作，我们可以模拟出约瑟夫环的运行过程，并得到最后剩下的元素。

约瑟夫环数据结构具有一定的应用潜力，并且具有较低的时间复杂度。

通过本次实验，我们对数据结构的设计和实现有了更深入的理解，并为将来的研究和应用奠定了基础。

实验报告：约瑟夫环一．需求分析1．本实验中，要求模拟N个持有密码的人在一种出序规则下的出序情况，每人有一个密码，并且N人在顺时针方向编号为1，2……N，在给予一个初始密码时要求将出序的人的序号打印出以摸拟该过程。

2．程序以计算机提示的方式出现，在显示提示信息后由用户从键盘上输入相应的信息。

3．测试数据M初值为20，N=7，7人的密码依次为：3，1，7，2，4，8，4，输入后正确的输出顺序为6，1，4，7，2，3，5。

二．概要设计为实现上述模拟功能，应以循环链表表示被编号的人。

为此，仅需要一个数据类型：循环链表。

1．循环链表的抽象数据类型定义为：ADT linkpeople{数据对象:D={a i|a i∈elepeople, i=1,2,3……,n}数据关系：R1={<a i-1,a i>|a i-1,a i∈D，i=1,2,……n}基本操作：creatcircle(&L)初始条件：L不存在。

操作结果：构造一个环形链表。

Workcircle(&L)初始条件：环形链表已存在。

操作结果：按所给规则处理链表，并释放退出循环的结点。

}ADT Linkpeople2.本程序包含三个模块：（1）主程序模块：int main(){读入初始值；构造链表；处理链表；}（2）创立链表模块——创立环形链表。

（3）处理链表模块——处理链表。

各模块之间的调用关系如下：创立模块处理模块三．详细设计1．元素结点类型typedef struct people{int number;int code;struct people *next;}elepeople,*linkpeople;2．模块设计linkpeople creatcircle(linkpeople p,int n){int i;linkpeople k,q,r;printf("please enter code \n");q=p;k=p;for(i=1;i<=n;i++){ if(i==n){k->next=q;k->number=n;scanf("%d",&k->code);}//处理最末的输入数据else{ scanf("%d",&k->code);k->number=i;r=(linkpeople)malloc(sizeof(elepeople));k->next=r;k=k->next;} //依此处理输入数据}return k;//返回最后结点指针}//creatcirclevoid workcircle(linkpeople q,int m){int c;linkpeople p,r;p=q;printf("the sequence of outpeople\n");while(p!=p->next){for(c=1;c<=m-1;c++)p=p->next;//找到处理结点前一个指针printf("%d ",p->next->number);m=p->next->code;r=p->next;p->next=p->next->next;free(r);}printf("%d ",p->number);free(p);//处理最后结点}//workcircle3．主函数int main(){int m;int n;linkpeople s;linkpeople p;printf("please enter the first code and sum of people\n");scanf("%d %d",&m,&n);p=(linkpeople)malloc(sizeof(elepeople));s=creatcircle(p,n);workcircle(s,m);return 0;}//main4．函数调用关系creatcircle workcircle四．调试分析1．在creatcircle的操作中，对其参数的传值问题未认真推敲，导致运行有误，以后应该注意。