下载文档原格式
一、实验目的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。
一问题描述1 题目内容：约瑟夫(Joseph)问题的一种描述是:编号为1,2,..., n的n 个人按顺时针方向围坐一圈, 每人持有一个密码(正整数)。
一开始选任一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。
报m的人出列，将它的密码作为新的m值。
试设计一个程序求出出列顺序。
2 基本要求：利用单项循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。
3 测试数据：m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4（正确的出列顺序应为6，1，4，7，2，3，5）。
二需求分析程序运行后，首先要求用户指定初始报数上限值，然后读取个人的密码。
输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。
输出形式：建立一个输出函数，将正确的输出序列三概要设计利用单项循环链表存储结构模拟此过程1 循环链表的抽象数据类型循环链表是单链表的一种变化形式，把单链表的最后一个节点的next指针指向第一个节点，整个链表就形成了一个环。
2 循环链表的基本操作（仅列出用在本程序的）creat(n)操作结果：构造一个长度为n的无头节点的循环链表,并返回指向最后一个节点的指针find(m,s)初始条件：循环链表存在操作结果：找到当前元素（即s）后面第m个元素print(&m,&n,&s)初始条件：循环链表存在操作结果：从s中删除约舍夫问题中下一个被删除的元素，并将此元素显示在屏幕上3 本程序包括4个模块：主程序模块；创建循环链表模块；找节点模块；删节点模块；各模块调用关系如下图所示：4 约舍夫问题的伪码算法void main( ){输入参与的人数；输入第一个密码；创建无头节点的循环链表；输出第一个出列元素；输出剩余出列元素；}四详细设计1 实现概要设计的数据类型typedef struct LNode{int data;int num;struct LNode *next;}LNode,*linklist; //无头节点的循环链表的节点类型2 每个子函数的算法linklist creat(int n){/*构造一个长度为n的无头节点的循环链表,并返回指向最后一个节点的指针*/linklist head,s; //head为头节点标记s为链表中节点int i;s=head=(linklist)malloc(sizeof(LNode)); //创建头节点for(i=1;i<n;i++) //建立循环链表{s->data=i;printf("num%d: ",i);scanf("%d",&(s->num));/*输入第i个人的密码*/while(s->num<=0){/*如果输入的s->num小于等于0,要求重新输入*/ printf("请重新输入\nnum%d: ",i);scanf("%d",&s->num);}s->next=(linklist)malloc(sizeof(LNode)); //开辟下一个节点s=s->next;}s->data=i;printf("num%d: ",i);scanf("%d",&(s->num));s->next=head;return(s);}linklist find(int m,linklist s) //找到当前元素后面第m个元素{int i;for(i=0;i<m-1;i++)s=s->next;return(s); //返回找到元素的指针}void print(into &mint &n,linklist &s){linklist p;s=find(m,s); //找到待删除的元素printf("%d ",s->next->data);/*输出找到的元素*/m=s->next->num;/*将此元素从链表中删除,并释放此节点*/ p=s->next;s->next=s->next->next;free(p);--n; //约舍夫环中节点数少一}3 主程序算法void main( ){/*解决约舍夫问题的主函数*/int n,m; //n为约舍夫环内初始人数m为初始密码printf("type in n :");scanf("%d",&n);/*输入n*/while(n<=0){/*如果输入的n小于等于0,要求重新输入*/printf("please type n in again \ntype in n :");scanf("%d",&n);}printf("type in m :");scanf("%d",&m);/*输入m*/while(m<0){/*如果输入的m小于0,要求重新输入*/printf("please type m in again \ntype in m :");scanf("%d",&m);}linklist s;s=creat(n);/*创建无头节点的循环链表,返回指向最后一个元素的指针*/printf("the sequence is ");print(m,n,s);//输出第一个出列的元素while(n){print(m,n,s);//输出剩余出列的元素}printf("\n");}4 函数调用关系图五调试分析调试过程中出现过如下问题：1 开始编程序时没考虑输入错误的问题，导致输入错误后程序出错2 编程序时删除节点子程序结束条件出错3 对开辟的节点用完后没有释放六使用说明程序运行后按提示输入n和m的值，在输入约舍夫环中每个人的密码，运行即可得到出列顺序七测试结果进入程序后要求输入n的值然后输入m的值再输入每个人的密码最后得到出列顺序八附录（源程序）这里附上两种源程序，本质上相同，只是第一个程序按老师要求写为很多子函数形式，第二个是我已开始编的，一个大函数。
“约瑟夫”问题及若⼲变种“约瑟夫”问题及若⼲变种例1、约瑟夫问题(Josephus)[问题描述]M只猴⼦要选⼤王，选举办法如下：所有猴⼦按1…M编号围坐⼀圈，从第1号开始按顺序1，2，…，N报数，凡报到N的猴⼦退出到圈外，再从下⼀个猴⼦开始继续1~ N报数，如此循环，直到圈内只剩下⼀只猴⼦时，这只猴⼦就是⼤王。
M和N由键盘输⼊，1≤N,M≤10000，打印出最后剩下的那只猴⼦的编号。
例如，输⼊8 3，输出：7。
[问题分析1]这个例题是由古罗马著名史学家Josephus提出的问题演变⽽来的，所以通常称为Josephus(约瑟夫)问题。
在确定程序设计⽅法之前⾸先来考虑如何组织数据，由于要记录m只猴⼦的状态，可利⽤含m个元素的数组monkey来实现。
利⽤元素下标代表猴⼦的编号，元素的值表⽰猴⼦的状态，⽤monkey[k]=1表⽰第k只猴⼦仍在圈中，monkey[k]=0则表⽰第k只猴⼦已经出圈。
程序采⽤模拟选举过程的⽅法，设变量count表⽰计数器，开始报数前将count置为0，设变量current表⽰当前报数的猴⼦编号，初始时也置为0，设变量out记录出圈猴⼦数，初始时也置为0。
每次报数都把monkey[current]的值加到count上，这样做的好处是直接避开了已出圈的猴⼦（因为它们对应的monkey[current]值为0），当count=n时，就对当前报数的猴⼦作出圈处理，即：monkey[current]：=0，count：=0，out：=out+1。
然后继续往下报数，直到圈中只剩⼀只猴⼦为⽌（即out=m-1）。
参考程序如下：program josephus1a {模拟法，⽤数组下标表⽰猴⼦的编号}const maxm=10000;var m,n,count,current,out,i:integer;monkey:array [1..maxm] of integer;beginwrite('Input m,n:');readln(m,n);for i:=1 to m do monkey[i]:=1;out:=0; count:=0; current:=0;while out<m-1 dobeginwhile count<n dobeginif current<m then current:=current+1 else current:=1;count:=count+monkey[current];end;monkey[current]:=0; out:=out+1; count:=0end;for i:=1 to m doif monkey[i]=1 then writeln('The monkey king is no.',i);readlnend.[运⾏结果]下划线表⽰输⼊Input m，n:8 3The monkey king is no.7 {时间：0秒}Input m，n:10000 1987The monkey king is no.8544 {时间：3秒}[反思] 时间复杂度很⼤O(M*N)，对于极限数据会超时。
#include <iostream.h>#include <stdlib.h>struct Member//定义结构体{int number;int password;Member *next;};class Joseph{public:Member *frist;//头指针int size;Joseph(void);~Joseph(void);int Size(void) const;//返回长度Member *Index(int i);//定位void Create(int i);//构造循环单链表int Delete(int i);//删除结点并返回number的值};Joseph::Joseph(){//frist=new Member;Member *p=new Member;frist=p;size=0;}Member *Joseph::Index(int i){if(i==0)return frist;Member *p=frist->next;int j=1;while(j<i){p=p->next;j++;}return p;}int Joseph::Size(void)const{return size;}void Joseph::Create(int i){for(int j=1;j<=i;j++){Member *p=Index(j-1);Member *q=new Member;q->number=j;p->next=q;size++;};//Member *p=Index(i);//p->next=frist;}Joseph::~Joseph(void){Member *p,*q;p=frist;while(size!=0){q=p;p=p->next;delete q;size--;}size=0;frist=NULL;}int Joseph::Delete(int i){Member *s,*p=Index(i-1);s=p->next;p->next=p->next->next;int x=s->number;cout<<x<<" ";int y=s->password;delete s;size--;return y;}void main(void){Joseph jos;int i;cout<<"Please input number of people :"<<endl;cin>>i;jos.Create(i);int frist;//设初始值cout<<"Please input the frist number :"<<endl;cin>>frist;for(int k=1;k<=i;k++)//用循环输入每个人的密码{cout<<"please input No."<<k<<"`s password:"<<endl;Member *b=jos.Index(k);cin>>b->password;}cout<<"The final is :"<<endl;int l=frist%i;if (l==0) l=i;for(int b=i-1;b>0;b--){frist=jos.Delete(l);l=(frist+l-1)%b;int e=jos.Size();if(l==0)l=e;}jos.Delete(l);cout<<endl;}。
实验一：约瑟夫问题问题描述：用数组和链表存储方式实现约瑟夫问题。
约瑟夫问题：n个人围成一个圆圈，首先第1个人从1开始一个人一个人顺时针报数，报到第m个人，令其出列。
然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其出列，…，如此下去，直到圆圈中只剩一个人为止。
此人即为优胜者。
基本要求：用顺序存储和链式存储方式实现。
试验报告内容：1．问题描述：设有n个人围坐在圆桌周围，现从某个位置m（1≤m≤n）上的人开始报数，报数到k 的人就站出来。
下一个人，即原来的第k+1个位置上的人，又从1开始报数，再报数到k的人站出来。
依此重复下去，直到全部的人都站出来为止。
2. 算法描述：可以先建一个单向循环链表；而整个“约瑟夫环”问题的过程，最终是把这个链表删空为止。
但在删时不能顺着删，而是按该问题的方案来删。
3.源程序#include <stdio.h>#include <stdlib.h>#define MAX_NODE_NUM 100#define TRUE 1U#define FALSE 0Utypedef struct NodeType{int id; /* 编号 */int cipher; /* 密码 */struct NodeType *next;} NodeType;/* 创建单向循环链表 */static void CreaList(NodeType **, const int);/* 运行 "约瑟夫环 "问题 */static void StatGame(NodeType **, int);/* 打印循环链表 */static void PrntList(const NodeType *);/* 得到一个结点 */static NodeType *GetNode(const int, const int);/* 测试链表是否为空, 空为TRUE，非空为FALSE */static unsigned EmptyList(const NodeType *);int main(void){int n, m;NodeType *pHead = NULL;while (1){printf( "请输入人数n（最多%d个）: ", MAX_NODE_NUM); scanf( "%d ", &n);printf( "和初始密码m: ");scanf( "%d ", &m);if (n > MAX_NODE_NUM){printf( "人数太多，请重新输入！\n ");continue;}elsebreak;}CreaList(&pHead, n);printf( "\n------------ 循环链表原始打印 -------------\n "); PrntList(pHead);printf( "\n-------------- 出队情况打印 ---------------\n "); StatGame(&pHead, m);printf( "\n\ "约瑟夫环\ "问题完成!\n ");return 0;}static void CreaList(NodeType **ppHead, const int n){int i, iCipher;NodeType *pNew, *pCur;for (i = 1; i <= n; i++){printf( "输入第%d个人的密码: ", i);scanf( "%d ", &iCipher);pNew = GetNode(i, iCipher);if (*ppHead == NULL){*ppHead = pCur = pNew;pCur-> next = *ppHead;}else{pNew-> next = pCur-> next;pCur-> next = pNew;pCur = pNew;}}printf( "完成单向循环链表的创建!\n ");}static void StatGame(NodeType **ppHead, int iCipher){int iCounter, iFlag = 1;NodeType *pPrv, *pCur, *pDel;pPrv = pCur = *ppHead;/* 将pPrv初始为指向尾结点，为删除作好准备 */while (pPrv-> next != *ppHead)pPrv = pPrv-> next;while (iFlag) /* 开始搞了! */{/* 这里是记数，无非是移动iCipher-1趟指针! */for (iCounter = 1; iCounter < iCipher; iCounter++) {pPrv = pCur;pCur = pCur-> next;}if (pPrv == pCur) /* 是否为最后一个结点了 */iFlag = 0;pDel = pCur; /* 删除pCur指向的结点，即有人出列 */pPrv-> next = pCur-> next;pCur = pCur-> next;iCipher = pDel-> cipher;printf( "第%d个人出列, 密码: %d\n ",pDel-> id, /* 这个编号标识出列的顺序 */pDel-> cipher);free(pDel);}*ppHead = NULL; /* 没人了！为了安全就给个空值 */}static void PrntList(const NodeType *pHead){const NodeType *pCur = pHead;if (EmptyList(pHead))return;do{printf( "第%d个人, 密码: %d\n ", pCur-> id,pCur-> cipher); pCur = pCur-> next;} while (pCur != pHead);}static NodeType *GetNode(const int iId, const int iCipher){NodeType *pNew;pNew = (NodeType *)malloc(sizeof(NodeType));if (!pNew){printf( "Error, the memory is not enough!\n ");exit(-1);}pNew-> id = iId;pNew-> cipher = iCipher;pNew-> next = NULL;return pNew;}static unsigned EmptyList(const NodeType *pHead){if (!pHead){printf( "The list is empty!\n ");return TRUE;}return FALSE;}4.实验测试数据（要求有多组）：第一组测试结果人数n为7, 初始密码m为20第1个人, 密码: 3第2个人, 密码: 1第3个人, 密码: 7第4个人, 密码: 2第5个人, 密码: 4第6个人, 密码: 8第7个人, 密码: 4-------------- 出队情况打印 ---------------第6个人出列, 密码: 8第1个人出列, 密码: 3第4个人出列, 密码: 2第7个人出列, 密码: 4第2个人出列, 密码: 1第3个人出列, 密码: 7第5个人出列, 密码: 4第二组测试结果人数n为8, 初始密码m为15第1个人, 密码: 5第2个人, 密码: 4第3个人, 密码: 3第4个人, 密码: 2第5个人, 密码: 9第6个人, 密码: 1第7个人, 密码: 7第8个人, 密码: 8-------------- 出队情况打印 ---------------第7个人出列, 密码: 7第6个人出列, 密码: 1第8个人出列, 密码: 8第3个人出列, 密码: 3第1个人出列, 密码: 5第4个人出列, 密码: 2第2个人出列, 密码: 4第5个人出列, 密码: 95.总结：1. 通过本次上机实践,对链表存储结构有了更深的理解和把握.2. 通过本次上机实践,应用链表的知识解决和分析问题的能力有了新的提高.3. 通过上机实践,掌握了用高级语言实现算法的基本步骤和方法.（最前面加班级、学号、姓名）。
约瑟夫环数据结构实验报告约瑟夫环数据结构实验报告引言约瑟夫环是一种经典的数学问题，它涉及到一个有趣的数据结构。
本次实验旨在通过实现约瑟夫环数据结构，深入理解该问题，并探索其在实际应用中的潜力。
本报告将介绍实验的设计和实现过程，并分析实验结果。
实验设计在本次实验中，我们选择使用链表来实现约瑟夫环数据结构。
链表是一种非常灵活的数据结构，适合用于解决约瑟夫环问题。
我们设计了一个Josephus类，其中包含了创建环、添加元素、删除元素等操作。
实验实现1. 创建环在Josephus类中，我们首先需要创建一个循环链表。
我们使用一个头节点来表示环的起始位置。
在创建环的过程中，我们可以选择指定环的长度和起始位置。
2. 添加元素在创建环之后，我们可以通过添加元素来向约瑟夫环中插入数据。
我们可以选择在环的任意位置插入元素，并且可以动态地调整环的长度。
3. 删除元素根据约瑟夫环的规则，每次删除一个元素后，下一个元素将成为新的起始位置。
我们可以通过删除元素的操作来模拟约瑟夫环的运行过程。
在删除元素时，我们需要考虑环的长度和当前位置。
实验结果通过实验，我们得出了以下结论：1. 约瑟夫环数据结构可以有效地模拟约瑟夫环问题。
通过创建环、添加元素和删除元素的操作，我们可以模拟出约瑟夫环的运行过程，并得到最后剩下的元素。
2. 约瑟夫环数据结构具有一定的应用潜力。
除了解决约瑟夫环问题，该数据结构还可以用于其他类似的问题，如任务调度、进程管理等。
3. 约瑟夫环数据结构的时间复杂度较低。
由于约瑟夫环的特殊性质，我们可以通过简单的链表操作来实现该数据结构，使得其时间复杂度较低。
结论本次实验通过实现约瑟夫环数据结构，深入理解了该问题，并探索了其在实际应用中的潜力。
通过创建环、添加元素和删除元素的操作，我们可以模拟出约瑟夫环的运行过程，并得到最后剩下的元素。
约瑟夫环数据结构具有一定的应用潜力，并且具有较低的时间复杂度。
通过本次实验，我们对数据结构的设计和实现有了更深入的理解，并为将来的研究和应用奠定了基础。
C语言的循环链表和约瑟夫环C语言的循环链表和约瑟夫环约瑟夫问题）是一个数学的应用问题，对于学习C语言四非常挺有帮助的，下面是店铺为大家搜集整理出来的有关于C语言的循环链表和约瑟夫环，一起了解下吧!循环链表的实现单链表只有向后结点，当单链表的尾链表不指向NULL，而是指向头结点时候，形成了一个环，成为单循环链表，简称循环链表。
当它是空表，向后结点就只想了自己，这也是它与单链表的主要差异，判断node->next是否等于head。
代码实现分为四部分：1. 初始化2. 插入3. 删除4. 定位寻找代码实现：1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1void ListInit(Node *pNode){int item;Node *temp,*target;cout<<"输入0完成初始化"<<endl; cin="">>item;if(!item)return ;if(!(pNode)){ //当空表的时候，head==NULLpNode = new Node ;if(!(pNode))exit(0);//未成功申请pNode->data = item;pNode->next = pNode;}else{//for(target = pNode;target->next!=pNode;target = target->next);4 15 16 17 18 19 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 3 0 3 1 3 2 3 3 3 4 3 5 3temp = new Node;if(!(temp))exit(0);temp->data = item;temp->next = pNode;target->next = temp;}}}void ListInsert(Node *pNode,int i){ //参数是首节点和插入位置Node *temp;Node *target;int item;cout<<"输入您要插入的值:"<<endl; cin="">>item;if(i==1){temp = new Node;if(!temp)exit(0);temp->data = item;for(target=pNode;target->next != pNode;target = target->next);temp->next = pNode;target->next = temp;pNode = temp;}else{target = pNode;for (int j=1;j<i-1;++j) target="target-">next;temp = new Node;if(!temp)exit(0);temp->data = item;temp->next = target->next;target->next = temp;}}void ListDelete(Node *pNode,int i){Node *target,*temp;if(i==1){for(target=pNode;target->next!=pNode;target=target ->next);temp = pNode;//保存一下要删除的首节点 ,一会便于释放6 37 38 39 4 0 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 5 0 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5pNode = pNode->next;target->next = pNode;temp;}else{target = pNode;for(int j=1;j<i-1;++j) target="target-">next;temp = target->next;//要释放的nodetarget->next = target->next->next;temp;}}int ListSearch(Node *pNode,int elem){ //查询并返回结点所在的位置Node *target;int i=1;for(target = pNode;target->data!=elem && target->next!= pNode;++i)target = target->next;if(target->next == pNode && target->data!=elem)return 0;else return i;}</i-1;++j)></i-1;++j)></endl;></endl;>5 96 0 6 1 6 2 6 3 6 4 6 5 6 6 67 68 69 7 0 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 8约瑟夫问题约瑟夫环(约瑟夫问题)是一个数学的'应用问题：已知n个人(以编号1，2，3…n分别表示)围坐在一张圆桌周围。
约瑟夫环上机实验报告1. 概述约瑟夫环问题是一个经典的数学问题，该问题是以约瑟夫·弗拉维奥(Josephus Flavius)命名的，故称为约瑟夫环。
问题的具体描述如下：在编号为1到n的n 个人围成一个圆圈，从第一个人开始报数，报到m的人出列，然后从出列的下一个开始重新从1到m报数，再次报到m的人再次出列，如此循环下去，直到所有的人都出列为止。
本次实验旨在使用程序实现约瑟夫环的模拟，并观察对于不同的参数n和m，最后剩余的人的编号特点。
2. 实验设计2.1 算法设计本实验中采用循环链表来模拟约瑟夫环，首先构建一个含有n个结点的循环链表，每个结点表示一个人，每个结点的数据域存储该人的编号。
然后根据报数规则，依次遍历链表，当报数为m时，删除对应的结点。
直到链表中仅剩一个结点为止。
2.2 程序实现pythonclass ListNode:def __init__(self, val=0):self.val = valself.next = Nonedef josephus(n, m):if n == 0:return -1构建循环链表dummy = ListNode(-1)cur = dummyfor i in range(1, n + 1):node = ListNode(i)cur.next = nodecur = cur.nextcur.next = dummy.next模拟游戏过程count = 0while cur.next != cur:count += 1if count == m:cur.next = cur.next.nextcount = 0else:cur = cur.nextreturn cur.val3. 实验结果为了观察不同参数n和m对最后剩余的人的编号的影响，我们进行了多组实验。
结果如下：n m 最后剩余的人的编号5 2 310 3 415 4 1420 5 6从实验结果可以看出，最后剩余的人的编号与参数m有关，而与参数n无关。
Josephus设计报告班级：10信息与计算科学学号：姓名：一. 需求分析：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。
首先创建一个空链表，初始化链表，构造出一个只有头结点的空链表，建立好一个约瑟夫环。
1. 输入的形式和输入值的范围本程序中，输入报数上限值m和人数上限l，密码，均限定为正整数，输入的形式为一个以“回车符”为结束标志的正整数。
2. 输出的形式从屏幕显示出列顺序。
3. 程序功能提供用户从键盘输入，Josephus约瑟夫环的必要数据，并显示出列顺序。
二、概要设计以单向循环链表实现该结构。
1. 抽象数据类型的定义为：ADT LNode{数据对象：D={ai | ai∈CharSet，i= 1，2，…，n，n≥0}数据关系：R1={< ai-1 ，ai > | ai ∈D，I=2，…，n} 三．源程序：#include<stdio.h>#include<stdlib.h>typedef struct Node{int key;//每个人持有的密码int num;//这个人的编号struct Node *next;//指向下一个节点}Node,*Link;void InitList(Link &L) //创建一个空的链表{L=(Node *)malloc(sizeof(Node));if(!L) exit(1);L->key=0;L->num=0;L->next=L;}void Creater(int n,Link &L) //初始化链表{Link p,q;q=L;for(int i=1;i<=n;i++){p=(Node *)malloc(sizeof(Node));if(!p) exit(1);printf("the key_%d is:",i);scanf("%d",&p->key);L->next=p;L=p;}L->next=q->next;free(q);}void main(){Link L,p,q;int n,x;L=NULL;InitList(L);//构造出一个只有头结点的空链表printf("please input the totle number of people:"); scanf("%d",&n);//总共的人数nprintf("the start key is:");scanf("%d",&x);//初始密码为xCreater(n,L);//建立好一个约瑟夫环p=L;for(int i=1;i<=n;i++){for(int j=1;j<x;j++)q=p->next;x=q->key;printf("%d ",q->num);p->next=q->next;free(q);}}四、测试数据：m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4 输出：6 7 4 1 5 3 2。
约瑟夫问题【问题描述】约瑟夫问题的一种描述是：编号为1，2，3···n个人按顺时针方向围坐一圈，每人持有一个密码（正整数），一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止，试设计一个程序求出出列顺序。
【基本要求】应用单向循环链表作为约瑟夫环的存储结构，基于其基本操作模拟实现出环过程，按照出环的顺序输出各人的编号【测试数据】n=7个人，n的初值为20，1-7个人的密码分别是：3，4，7，2，4，8，4，则正确出列顺序（每个人编号）为：6，1，4，7，2，3，5。
【数据结构c++实现代码】#include<iostream>#include<malloc.h>using namespace std;struct node{int no; //代表编号结点的数据int code;//代表密码结点的数据node *next;//代表后一个结点的地址};int main(){int m,n,i,j;node *p,*q,*first;cout<<"请输入m的初始值m:";cin>>m;cout<<"请输入人数n:";cin>>n;for(i=1;i<=n;i++){if(i==1){first=p=(node*)malloc(sizeof(node));if(p==0)return 0;}else{q=(node*)malloc(sizeof(node));if(q==0)return 0;p->next=q;p=q;}cout<<"请输入第"<<i<<" 个人的密码: ";cin>>(p->code);p->no=i;}p->next=first; //让表尾指向表头形成循环链表p=first;cout<<"出列顺序为: ";for (j=1;j<=n;j++){for(i=1;i<m;i++,p=p->next);m=p->code;cout<<p->no<<" ";p->no=p->next->no;p->code=p->next->code;q=p->next;p->next=p->next->next;free(q);}cout<<endl;return 0;}。
数据结构实验报告约瑟夫环约瑟夫环是一个经典的问题，涉及到数据结构中的循环链表。
在本次数据结构实验中，我们将学习如何使用循环链表来解决约瑟夫环问题。
约瑟夫环问题最早出现在古代，传说中的犹太历史学家约瑟夫斯·弗拉维奥（Josephus Flavius）在围攻耶路撒冷时，为了避免被罗马人俘虏，与其他39名犹太人躲进一个洞穴中。
他们决定宁愿自杀，也不愿被敌人俘虏。
于是，他们排成一个圆圈，从第一个人开始，每次数到第七个人，就将他杀死。
最后剩下的人将获得自由。
在这个问题中，我们需要实现一个循环链表，其中每个节点表示一个人。
我们可以使用一个整数来表示每个人的编号。
首先，我们需要创建一个循环链表，并将所有人的编号依次添加到链表中。
接下来，我们需要使用一个循环来模拟每次数到第七个人的过程。
我们可以使用一个指针来指向当前节点，然后将指针移动到下一个节点，直到数到第七个人为止。
一旦数到第七个人，我们就将该节点从链表中删除，并记录下该节点的编号。
然后，我们继续从下一个节点开始数数，直到只剩下一个节点为止。
在实现这个算法时，我们可以使用一个循环链表的数据结构来表示约瑟夫环。
循环链表是一种特殊的链表，其中最后一个节点的指针指向第一个节点。
这样，我们就可以实现循环遍历链表的功能。
在实验中，我们可以使用C语言来实现循环链表和约瑟夫环算法。
首先，我们需要定义一个节点结构体，其中包含一个整数字段用于存储编号，以及一个指针字段用于指向下一个节点。
然后，我们可以实现创建链表、添加节点、删除节点等基本操作。
接下来，我们可以编写一个函数来实现约瑟夫环算法。
该函数接受两个参数，分别是参与游戏的人数和每次数到第几个人。
在函数内部，我们可以创建一个循环链表，并将所有人的编号添加到链表中。
然后，我们可以使用一个循环来模拟每次数到第几个人的过程，直到只剩下一个节点为止。
在每次数到第几个人时，我们可以删除该节点，并记录下其编号。
最后，我们可以返回最后剩下的节点的编号。
约瑟夫环问题的两种解法（详解）约瑟夫环问题的两种解法（详解）题⽬：Josephus有过的故事：39 个犹太⼈与Josephus及他的朋友躲到⼀个洞中，39个犹太⼈决定宁愿死也不要被敌⼈抓。
于是决定了⾃杀⽅式，41个⼈排成⼀个圆圈，由第1个⼈开始报数，每报数到第3⼈该⼈就必须⾃杀。
然后下⼀个重新报数，直到所有⼈都⾃杀⾝亡为⽌。
然⽽Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与⾃⼰安排在第16个与第31个位置，于是逃过了这场死亡游戏。
对于这个题⽬⼤概两种解法：⼀、使⽤循环链表模拟全过程⼆、公式法我们假设这41个⼈编号是从0开始，从1开始报数，第3个⼈⾃杀。
1、最开始我们有这么多⼈：[ 0 1 2 3 4 5 ... 37 38 39 40 ]2、第⼀次⾃杀，则是(3-1)%41=2 这个⼈⾃杀，则剩下：[ 0 1 3 4 5 ... 37 38 39 40 ]3、然后就是从编号为3%41=3的⼈开始从1报数，那么3号就相当于头，既然是头为什么不把它置为0，这样从它开始就⼜是与第1,2步⼀样的步骤了，只是⼈数少了⼀个，这样不就是递归了就可以得到递归公式。
想法有了就开始做：4、把第2步中剩下的⼈编号减去3映射为：[ -3 -2 0 1 2 ... 34 35 36 37 ]5、出现负数了，这样不利于我们计算，既然是环形，37后⾯报数的应该是-3，-2，那么把他们加上⼀个总数（相当于加上360度，得到的还是它）[ 38 39 0 1 2 3 ... 34 35 36 37 ]6、这样就是⼀个总数为40个⼈，报数到3杀⼀个⼈的游戏。
这次⾃杀的是第5步中的(3-1)%40=2号，但是我们想要的是第2步中的编号（也就是最初的编号）那最初的是多少？对应回去是5；这个5是如何得到的呢？是（2+3)%41得到的。
⼤家可以把第5步中所有元素对应到第2步都是正确的。
7、接下来是[ 35 36 37 38 0 1 2... 31 32 33 34 ]⾃杀的是(3-1)%39=2，先对应到第5步中是(2+3)%40=5，对应到第2步是(5+3)%41=8。
循环队列之约瑟夫环问题约瑟夫问题 约瑟夫环（约瑟夫问题）是⼀个数学的应⽤问题：已知n个⼈（以编号1，2，3...n分别表⽰）围坐在⼀张圆桌周围。
从编号为k的⼈开始报数，数到m的那个⼈出列；他的下⼀个⼈⼜从1开始报数，数到m的那个⼈⼜出列；依此规律重复下去，直到圆桌周围的⼈全部出列。
通常解决这类问题时我们把编号从0~n-1，最后结果+1即为原问题的解。
循环队列求解（链式）#include<stdio.h>#include<stdlib.h>//循环队列//typedef int ElemType;typedef struct QueueNode{int data;struct QueueNode *next;}QueueNode;typedef struct Queue{QueueNode *front;QueueNode *rear;}Queue;void InitQueue(Queue *q){q->front=q->rear=NULL;}void EnQueue(Queue *q , int value){QueueNode *temp=(QueueNode*)malloc(sizeof(QueueNode));temp->data=value;if(q->rear==NULL){temp->next=temp;q->rear=q->front=temp;}else{temp->next=q->rear->next;q->rear->next=temp;q->rear=temp;}}//enter a element from the tailvoid DeQueue(Queue *q, int *value){QueueNode *temp=(QueueNode*)malloc(sizeof(QueueNode)); if(q->rear==NULL){return;}// It's nullelse if(q->rear->next==q->rear){*value=q->front->data;free(q->rear);q->rear=q->front=NULL;}//It just has one nodeelse{*value=q->front->data;temp=q->front;q->front=temp->next;q->rear->next=q->front;}//more one nodefree(temp);}//delete a element from the headint main(){Queue *q=(Queue*)malloc(sizeof(Queue));int i,m,n,count,temp;printf("请输⼊⼈数n和循环要报的数m（两数之间留个空格）\n"); scanf("%d%d",&n,&m);for(i=1;i<=n;i++)EnQueue(q,i);printf("出圈序列：\n");while(q->front){ count=1;while(count<m){q->front=q->front->next;q->rear=q->rear->next;count++;}count=1;DeQueue(q,&temp);printf("%d ",temp);}putchar('\n');}简单解法#include <stdio.h>int josephus(int n, int m) {if(n == 1) {return0;}else {return (josephus(n-1, m) + m) % n;}}int main() {int n, m;while (scanf("%d", &n) == 1) {if (!n) {break;}scanf("%d", &m);int result = josephus(n, m);printf("%d\n", result+1);}return0;}。
约瑟夫问题实验报告（文章一）：约瑟夫问题数据结构实验报告中南民族大学管理学院学生实验报告实验项目: 约瑟夫问题课程名称：数据结构年级：专业：信息管理与信息系统指导教师：实验地点：管理学院综合实验室完成日期：小组成员：学年度第（一）、实验目的（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 报数，如此下去，直至所有人全部出列为止。
试设计一个程序求出出列顺序。
基本要求是利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。
题目：约瑟夫（Joseph）问题的一种描述是：编号为1，2，......，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。
一开始任选一个整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。
报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个开始重新从1报数，如此下去，直至年有人全部出列为止。
试设计一个程序求出出列顺序。
班级：姓名：学号：完成日期：一、需求分析1．本演示程序中，利用单向循环链表存储结构存储约瑟夫环数据（即n个人的编号和密码）。
2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示"提示信息"之后，由用户在键盘上输入演示程序中需要输入的数据，运算结果显示在其后。
3．程序执行的命令包括：1)构造单向循环链表；2）4．测试数据m 的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6（正确的出列顺序为6，1，4，7，2，1，3，5）。
二、概要设计1．单向循环链表的抽象数据类型定义为：ADT List｛数据对象：D=｛ai | ai∈正整数，I=1，2，......，n,n≥0｝数据关系：R1=｛< ai-1，ai > |，ai-1，ai∈D,I=1，2，......，n｝基本操作：Init List(&L)操作结果：构造一个空的线性表L。
List Insert(&L,i,e)初始条件：线性表L已存在，1≤i≤List Length(L)+1.操作结果：在L中第i个位置之前插入新的数据无素e，L长度加1。
List Delete(&L,i,&e)初始条件：线性表L存在非空，1≤i≤List Length(L).操作结果：删除L的第i个元素，并用e返回其值，L长度减1。
2．程序包含四个模块：1）主程序模块：三详细设计typedef struct LNode{int password; //密码int No; //序号struct LNode *next; //下一成员指针}member; //成员结构体typedef int status;#define OVERFLOW -2#define OK 1#define ERROR 0#include <stdio.h>#include <stdlib.h>status CreateList_Circle(member **,int);status DeleteNode(member **);status main(){int n,m;member *head=NULL,*p=NULL; //头指针即首成员地址，遍历指针p printf ("Please enter number of people:\n");scanf ("%d",&n); //总成员数while (n<=0){printf ("n must be positive, please enter again:\n");scanf ("%d",&n);}if(!CreateList_Circle(&head,n)) //创建循环链表，返回头指针head return OVERFLOW;printf ("Please enter initial m:\n");scanf ("%d",&m); //初始mwhile (m<=0){printf ("m must be positive, please enter again:\n");scanf ("%d",&m);}printf ("\nThe order is:\n");p=head;while (n>=2) //寻找出列成员{int i;m=(m%n==0)?n:m%n; //化简m值for (i=1;i<m;i++)p=p->next; //p指向出列成员printf ("%d\n",p->No); //输出出列成员序号m=p->password; //修改mDeleteNode(&p); //删除链表中的出列成员n--; //成员数自减}printf ("%d\n",p->No); //输出最后一个成员序号return OK;}status CreateList_Circle(member **p_head,int n){//此算法创建一个无头结点的循环链表，结点数n,*p_head返回链表头指针即首结点地址int i;member *tail,*p;*p_head=(member *)malloc(sizeof(member));if (!(*p_head)) return OVERFLOW;(*p_head)->No=1; //储存成员一序号printf ("Please enter password of No. 1:\n");scanf ("%d",&(*p_head)->password); //储存成员一密码tail=*p_head;tail->next=NULL;for (i=2;i<n+1;i++){p=(member *)malloc(sizeof(member));if (!p) return OVERFLOW;p->No=i; //储存成员序号printf ("Please enter password of No. %d:\n",i);scanf("%d",&(p->password)); //储存成员密码tail->next=p;tail=p;}tail->next=*p_head;return OK;}status DeleteNode(member **pp){//此算法删除链表中的结点*pp,操作实质是将*pp下一结点复制到*pp后将其free member *temp;(*pp)->password=((*pp)->next)->password;(*pp)->No=((*pp)->next)->No;temp=(*pp)->next;(*pp)->next=(*pp)->next->next;free(temp);return OK;}四、调试分析程序的编写和调试基本正常。
//假设n个人围坐在圆桌周围，现在从第s个开始报数，数到m的那个人出局，下一个开始重新报数，如此反复，知道所有的人都出局为止。
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
typedef struct cirlist{
int data;
struct cirlist *next;
}CirNode, *Cirlist;
Cirlist CreateList_L(Cirlist L, int n)//正序输出链表；
{
Cirlist p = NULL, s;
L = (Cirlist)malloc(sizeof(CirNode));
L->next = L;//建立头结点；
s = L;//用一个中间变量承接L，保持L的地址不变；
printf("输入链表的值：\n");
for (int i = 0; i < n; i++)//尾插法
{
p = (Cirlist)malloc(sizeof(CirNode));
scanf("%d", &p->data);
s->next = p;
s = p;
}
p->next = L;
return L;//如果不用s中间变量，利用尾插法L的地址是变化的；
}
void jopus(Cirlist L, int n, int s, int m)
{
Cirlist p = L->next, q = L;
int i, j;
for (i = 1; i < s; i++)
{
p = p->next;
}
for (i = 0; i < n; i++)
{
for (j = 1; j < m; j++)
{
q = p;
p = p->next;
if (p == L)
{
q = p;
p = p->next;
}
}
printf("%-3d", p->data);
q->next = p->next;
free(p);
p = q->next;
if (p == L)
{
q = p;
p = p->next;
}
}
}
void Show_L(Cirlist L)
{
Cirlist p;
p = L->next;
while (p != L)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
void main()
{
Cirlist L = NULL;
int n, s, m;
printf("你想创建循环链表的长度：");
scanf("%d", &n);
L = CreateList_L(L, n);
printf("你创建的链表为;\n");
Show_L(L);
printf("输入你开始的位置以及相隔几个数字：");
scanf("%d%d", &s, &m);
jopus(L, n, s, m);
system("pause");
}。
