(H)实验1 约瑟夫环问题

题目二约瑟夫环问题设编号为1，2，3，……，n 的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。

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

报数。

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

令n 最大值取30。

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

struct node //结点结构{ int number; /* 人的序号人的序号*/ int cipher; /* 密码密码*/ struct node *next; /* 指向下一个节点的指针*/ }; 一、循环链表的结点类型定义/* 单链表的结点类型 */typedefstruct node{int number;int cipher;struct node *next;}list, *linklist;二、循环链表的初始化/* 函数功能:初始化n 个元素的循环链表参数;链表(linklist L)，元素个数（int n ）通过后插法对无头结点的链表初始化。

*/voidinit(linklist&L,int n){int key, i;cout<<"输入第1个人的密码为：";//输入第一个节点的密码。

cin>>key;L= new list;L->number = 1;L->cipher = key;L->next = L;for(i = 2; i<= n; i ++)//输入2—n 的节点密码。

{linklist p = new list;cout<<"输入第"<<i<<"个人的密码为：";cin>>key;p->cipher = key;p->number = i;p->next = L->next; //使用后插法插入。

《数据结构》实验报告班级：姓名：学号：日期：08-10-20题目：约瑟夫环一、上机实验的问题和要求：问题描述：编号为1到n的n个人围成一圈，每人带一个密码c，以m为报数上限。

然后从第一个人开始顺时针自1开始报数，报到m的人出列，将其密码作为新的m值，从他的下一个人开始，同样顺时针自1开始报数，依次循环下去，直到所有的人都出列！要求得到依次出列的那些人的编号序列！基本要求：用C代码实现此活动，要求使用一定的算法进行操作，并最终通过程序运算出最后的结果！二、程序设计的基本思想，原理和算法描述：（包括程序的模块结构，数据结构，输入/输出设计，符号名说明等）基本思想：利用不带头结点单向循环链表模拟该活动，在实现了一切动作之后，运用一定的算法得到最终的结果。

程序的模块结构：定义了相关的结构体之后，主要有以下几大模块：1.建立由头指针指示的有n个结点的不带头结点的单向循环链表crt_CLinkList(H,n);2.寻找、输出、删除H单循环链表的第m个结点locfor(H,m);3.最后通过main函数体处理参数的输入与显示，并调用以上两函数，最终解决问题。

主要数据结构：单链的循环链表，即线性表的链式存储结构。

算法的伪码描述：结构体定义如下：typedef struct Lnode /*定义单链表*/{int number; /*编号*/int cipher; /*密码*/struct Lnode *next; /*指针*/}Lnode,*CLinklist; /*重定向命名*/CLinklist H; /*Ｈ为全局单链表*/算法的实现详见源程序。

输入/输出设计本程序并未采用任何二进制文件出入的方式，这点说明将在最后总结提到。

至于函数的出入口问题，在源程序及注释中将得到详细说明，这里不再赘述。

三、源程序及注释：(说明函数功能、入口及出口参数,其他)#include <stdio.h> /* 头文件*/#include <stdlib.h>#include <alloc.h>typedef struct Lnode /*定义单链表*/{int number; /*编号*/int cipher; /*密码*/struct Lnode *next; /*指针*/}Lnode,*CLinklist; /*重定向命名*/CLinklist H; /*Ｈ为全局单链表*/struct Lnode *crt_CLinkList(CLinklist H,int m) /*创建一个不带头结点的单向循环链表*/{ /*其中，Ｈ为全局单链表，m为链表结点总数*/ int i; /*循环记数用*/struct Lnode *ptr1; /*用于索引*/if((ptr1=(struct Lnode *)malloc(sizeof(struct Lnode)))==NULL) /*一旦动态内存分配失败，报错退出！*/ {perror("malloc");return ptr1;}H=ptr1; /*形成单个结点的单循环链表*/ptr1->next=H;for(i=1;i<m;i++) /*形成m个结点的不带头结点的单循环链表*/ {if((ptr1->next=(struct Lnode *)malloc(sizeof(struct Lnode)))==NULL){perror("malloc");ptr1->next=H;return H;}ptr1=ptr1->next; /*其中Ｈ指头，ptr指尾*/ptr1->next=H;}return H; /*返回成功新建的单链表Ｈ*/}void locfor(CLinklist H,int m) /*寻找输出删除链表Ｈ中的第m个结点*/{ /*H为全局链表，m为要查找删除的结点位置*/ int i; /*循环计数*/struct Lnode *ptr;for(i=1;i<=5;i++) /*考虑图形界面的美观问题*/printf("number\tcipher\t");i=1; /*初始化*/while(H->next!=H) /*只剩单个结点时停止循环，进行最后输出！*/ {if(m==1) /*考虑进行自身删除的情况，即m=1*/{for(ptr=H->next;ptr->next!=H;ptr=ptr->next);/*正因为是自身删除才要费大劲寻找其父结点*/printf("%-6d\t",H->number); /*找到后，先输出*/printf("%-6d\t",H->cipher);m=H->cipher; /*确定下一次寻找的m值*/ptr->next=H->next; *删除结点，即自身结点*/ptr=ptr->next;free(H); /*因为对于链表中的结点，每个之前都分配了内存，所以free是必要的*/H=ptr; /*不同于以下普通结点的删除，自身删除还要还原H*/i=1; /*i重置，以方便下一次的循环操作*/}else if(i==m-1) /*因为从自身开始即为1号，因为m-1,而不是m*/{ptr=H->next; /*结点的删除操作同于上面的情况!*/printf("%-6d\t",ptr->number);printf("%-6d\t",ptr->cipher);m=ptr->cipher;H->next=ptr->next;H=H->next;free(ptr);i=1;}else{H=H->next; /*若未找到，则继续遍历！*/i++;}}printf("%-6d\t",H->number); /*对于单个结点的单循环链表，进行最终的输出操作！*/ printf("%-6d",H->cipher);free(H); /*完成所有任务并释放所有内存占用！*/}void main() /*主函数接口*/{ /*调用所有函数，进行实验模拟，并得出实验结果！*/ int i,j,n=30,m,k;struct Lnode *ptr;randomize(); /*因为下面调用了random函数，故此处的初始化很有必要！*/ printf("Now the experiment will begin.You have two choices!\n");/*数据输入可以电脑随机，也可以自行输入*/printf("If you want to enter the datas all by yourself,please enter 1.\n");/*自行输入（方便检测程序问题）*/ printf("If you want to get the datas by the computer,please enter 0.\n"); /*电脑随机产生数据*/printf("Now your choice:"); /*用户选择*/scanf("%d",&j);while(j!=0&&j!=1) /*考虑程序的完善性，对于误输入的提示并报警！*/ {printf("\nYou enter is unillage!Please try again!\n");printf("Now your choice:"); /*重新输入*/scanf("%d",&j);}H=crt_CLinkList(H,n); /*初始化链表*/if(j==0) /*电脑随机充入数据*/for(i=1;i<=30;i++){H->number=i;H->cipher=rand(); /*随机函数*/H=H->next;}else /*此时选择实验者输入数据！*/{for(i=1;i<=30;i++){H->number=i;printf("Now number %d,please enter the cipher:",i);scanf("%d",&k);H->cipher=k;H=H->next;}}m=rand(); /*默认情况下，m随机产生*/printf("Do you want to enter the number m?Enter 1 to set or others cancel!\n");/*当然，如果想自已输，可以进行覆盖*/scanf("%d",&k);if(k==1) /*自行输入m值*/{printf("Please enter the number m:");scanf("%d",&m);}system("cls"); /*考虑屏幕大小，进行分屏显示*/printf("All followed are your datas!\n"); /*界面友善*/for(i=1;i<=5;i++)printf("number\tcipher\t");for(i=0;i<30;i++) /*显示所有处理前数据*/{printf("%-6d\t",H->number);printf("%-6d\t",H->cipher);H=H->next;}printf("And the number m is :%d\n",m);printf("\nAfter the program,the result is:\n");locfor(H,m); /*对所有数据进行实验处理，直至所有结点处理完！*/ getchar();printf("\nPress any key return!"); /*TC环境下，方便查看结果！*/getchar();}四、用户使用说明与测试运行结果：1．运行程序后，首先弹出界面，截图如右：理性化的选择：如果打1，则所有的cipher均由用户输入，这样方便对特殊数据进行程序测试！如果打0，那么所有的数据均由电脑产生！那如果打其他的呢？考虑到误输入，加了一个循环，以提高程序的健壮性！2．首先自行输入数据进行测试。

约瑟夫环问题实验报告一、实验内容本实验利用单向循环链表模拟约瑟夫环问题（编号为1,2，…，n的n个人按顺时针方向围坐一圈，没人持有一个密码（正整数）。

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

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

M的初值为20，n=7,7个人的密码依次为3,1,7,2,4,8,4，首先m值为6。

二、源程序#include"stdafx.h"#include<iostream>using namespace std;#include<conio.h>//getch();/*write: Han.JH*/static int people_number_count; typedef struct People_Node{int Password_Data,people_number;struct People_Node *next;}People_Node,*People_LinkList;void GreatList(People_LinkList &L){People_Node *s,*r; int flag=1;int Password;L=new People_Node;L->next=NULL;r=L;while(flag==1){cout<<"输入每个人的密码,以回车作间隔,'0'表示结束:";cin>>Password;//输入每个人的密码；if(Password!=0){s=new People_Node;s->Password_Data=Password;people_number_count++; //对人的编号s->people_number=people_number_count;r->next=s;r=s;}else{ r->next=L->next;flag=0;}}}void GetList(People_LinkList &L){People_Node *r;int m,k;int count=0;cout<<"输入报数上限值m:";cin>>m;r=L;cout<<"出列排序:";while(count!=people_number_count){ //则所有人以出列，结束循环for(k=1;k<=m-1;k++){r=r->next;}count++;m=r->next->Password_Data;cout<<"["<<r->next->people_number<<"]";r->next=r->next->next;}}void main(){People_LinkList L;void GreatList(People_LinkList &);void GetList(People_LinkList &);cout<<"++++++++++++约瑟夫环问题+++++++++++"<<endl;GreatList(L);GetList(L);cout<<"[--结束--]"<<endl;getch();}三、调试刚开始调试时出现了无法打开<iostream.h>头文件的错误，经过上网查询，#include<iostream.h>是C语言风格，但是在标准 C 里面,是不用#include <iostream.h>的，而要使用#include <iostream>把#include<iostream.h>改为：#include<iostream>using namespace std;后，问题解决。

实验一：约瑟夫问题问题描述：用数组和链表存储方式实现约瑟夫问题。

约瑟夫问题：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. 通过上机实践,掌握了用高级语言实现算法的基本步骤和方法.（最前面加班级、学号、姓名）。

北京邮电大学电信工程学院数据结构实验报告实验名称：实验一——约瑟夫问题学生姓名： ***班级： 20132111**班内序号： **学号： 201321****日期： 2014年1月4日1．实验要求实验题目：利用循环链表实现约瑟夫问题的求解。

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

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

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

实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法学习指针、模板类、异常处理的使用掌握线性表的操作的实现方法学习使用线性表解决实际问题的能力2. 程序分析2.1 存储结构采用单循环链表实现约瑟夫问题的求解单循环链表示意图2.2关键算法分析1、关键算法首先通过尾插法建立单循环链表，若只有一个人，即只删除该人即可，若多于一人，—则每查到m个人时删除该节点，并将循环链表连接好，共循环n-1次，每次删除均返回被删数值。

2、代码详细分析：1).指针结构、类的声明struct Node //创立节点{int number;Node *next;};class Joseph //建立Joseph类{private:int n;int m;Node *front ; //front头指针public:Joseph(int nn, int mm); //构造函数~Joseph(); //析构函数void Delete(); //删除函数};2）.单循环链表的建立Joseph::Joseph(int nn, int mm) //构造函数，建立循环链表{n=nn;m=mm;Node *p,*rear; //建立两个指针.尾插法，p2始终指向为节点for(int i=1; i<=n; i++){p=new Node;p->number=i;if(i==1) //建立空链表{front=p;rear=p;}else{rear->next=p;rear=p;}}rear->next=front; //尾指向头，循环完成}算法：—①设两个指针p,rear, rear为尾节点，p为新增加的节点②若是空链表，则front=p; rear=p;③否则用尾插法,即p 在rear的后面，将p给rear;rear->next=p; rear=p;④头结点赋给rear的指针域，完成循环循环次数为n, 时间复杂度为O（n）3）. 输入值异常的情况cout<<"请输入环内总人数n:";cin>>n;if (n<1) //考虑n输入错误的情况{cout<<"n值输入错误"<<endl;}cout<<"请输入m值:";cin>>m;if (m<1) //考虑m输入异常的情况{cout<<"m值输入错误"<<endl;}4）.寻找一定间隔的人，并将其删除void Joseph::Delete() //删除人员的函数{Node *p1,*p2,*p;int count; //用来计数p1=front; //头结点给p1if(m==1)cout<<"最后一个人的编号为"<<n<<endl;else{cout<<"每次被删除的人为"<<endl;for(int i=1; i<=n-1; i++) //共删除n-1个人，循环n-1次{count=1;while(count<m){p2=p1; //p2始终为编号为1的那个人p1=p1->next; //p1向后移count++;}cout<<p1->number<<"\t"; //输出被删除的编号p=p1;p2->next=p1->next;p1=p1->next; //p1后移，防止删除后指针悬挂delete p;—}cout<<endl;cout<<"最后一个人的编号为"<<p1->number<<endl;front=p1;} }…………③图1 删除结点示意图算法⑤设p1、p2均指向第一个节点；⑥查找第m个节点，p1=p1—>next; p2始终指向第一个节点⑦摘链，将p指向待删除的p1，即将p1元素从链表中摘除：⑧输出p1的数值⑨释放p元素：delete p;循环次数为m(n-1), 时间复杂度为O（n）5）析构函数Joseph::~Joseph() //析构函数{delete front;front=NULL;}6）主函数void main(){int n,m;cout<<"请输入总人数n=";cin>>n;cout<<"请输入间隔m=";cin>>m;Joseph joseph(n,m);joseph.Delete();}3. 程序运行结果测试主函数流程：开始等待用户输入输入值是否有效是查找删除节点循环次数是否大于n-1次是输出最后一个数值结束流程图示意图1、测试条件：n数量级无限制2、测试结论4. 总结由于是第一次做数据结构的实验，而上学期的C++也因长时间没有碰过而稍显手生，在码程序的过程中遇到了很多问题，但通过翻看教材已基本解决。

实验一：约瑟夫问题求解一、问题描述1、实验题目：约瑟夫（Josephus）问题的一种描述是：编号为1，2，……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

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

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

2、基本要求：试设计一个程序，按出列顺序印出个人编号。

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

ｍ的初值为6，正确的出列顺序应为：6，1，4，7，2，3，5。

二、需求分析１、本程序用来求出含有密码的约瑟夫问题，可以输出所有人的出列顺序。

2 、程序运行后显示提示信息，提示用户输入一圈的人数n，接着输入每个人的密码，最后提示输入初始密码。

3、用户输入完毕后，程序自动输出运算结果。

三、概要设计1、设计思路n个人围成一圈，每个人的手中都有一个密码，这个密码决定了下一次报数的上限。

游戏规则：①给定一个初始密码②循环报数，报到密码值的人要出列，依次类推，直到所有的人都出列本程序要求输入的内容：n个人的密码及初始密码；本程序要求输出的内容：n个人出列的顺序。

2、数据结构为了实现上述功能，可以采用链式存储结构。

采用链式存储结构，定义了一个存储个人信息的结构体，及两个自定义函数，分别用于创建链表和约瑟夫出列操作。

①链表抽象数据类型的定义： #define SLNODE struct slnodeADT SLNODE{数据对象：D={ i a |i a ∈SLNODE, i=1,2,3.... }数据关系：R=φ}ADT SLNODE;②自定义函数:void create_SLnode(SLNODE *p,int n)//创建队列{ 创建链表，为N 个人分配密码 }void Josef(SLNODE *p,int n)//进行约瑟夫操作{输入初始密码m;for(){ 将出列的结点删除，并输出出列序号；}}③本程序的保护模块：结构体模块主程序模块自定义函数模块调用关系：3、程序设计主要算法的流程图：create_SLnode( )算法流程图Josef( )算法流程图四、详细设计1、元素类型、结点的类型及指针#define SLNODE struct slnodeSLNODE//每个结点的结构体{int num;//num代表序号int code;//code代表密码SLNODE *next;};2、自定义函数：void create_SLnode(SLNODE *p,int n)//创建队列，并将其尾指针指向第一个序号{SLNODE *r,*s;s=p;int i,m;cout<<"请给这"<<n<<"个人分配密码："<<endl;for(i=0;i<n;i++){cout<<"请给第"<<i+1<<"个人输入密码："<<endl;cin>>m;r=(SLNODE *)malloc(sizeof(SLNODE));r->code=m;r->num=i+1;r->next=s->next;s->next=r;s=s->next;}p=p->next;s->next=p;}void Josef(SLNODE *p,int n)//进行约瑟夫操作{p=p->next;int m;int i,j;SLNODE *r;cout<<"请输入初始密码："<<endl;cin>>m;cout<<"依次出列的序号为:"<<endl;for(i=0;i<n-1;i++)p=p->next;for(i=0;i<n-2;i++){for(j=0;j<m-1;j++)p=p->next;cout<<(p->next)->num<<endl;m=(p->next)->code;r=p->next;p->next=r->next;}if(m%2==0)cout<<p->num<<endl<<(p->next)->num<<endl;elsecout<<(p->next)->num<<endl<<p->num<<endl;}3、主函数：int main(){SLNODE *p;int n;cout<<"请输入一圈的人数："<<endl;cin>>n;p=(SLNODE *)malloc(sizeof(SLNODE));p->next=NULL;create_SLnode(p,n);Josef(p,n);return 0;}4、函数的调用关系：主函数main()调用自定义函数void create_SLnode(SLNODE *p,int n);/*创建队列*/与void Josef(SLNODE *p,int n);/*进行约瑟夫操作*/。

华北#########学院数据结构实验报告2011～2012学年第二学期级计算机专业班级：学号：姓名：实验一线性表及其应用一、实验题目：线性表及其应用——约瑟夫环二、实验内容：1．设带头结点的单链表ha和hb中结点数据域值按从小到大顺序排列，且各自链表内无重复的结点，要求：（1）建立两个按升序排列的单链表ha和hb。

（2）将单链表ha合并到单链表hb中，且归并后的hb链表内无重复的结点，结点值仍保持从小到大顺序排列。

（3）输出合并后单链表hb中每个结点的数据域值。

代码：实验结果：struct Node{ int data;Node* next; };typedef Node Slink;void create(Slink* h);void show(Slink* h);void merge(Slink* ha,Slink* hb);#include<iostream.h>void main(){cout<<"创建链表ha"<<endl;Slink ha; ha.next =NULL;create(&ha);cout<<"链表ha的节点排列"<<endl;show(&ha);cout<<endl;cout<<"创建链表hb"<<endl;Slink hb; hb.next =NULL;create(&hb);cout<<"链表hb的节点排列"<<endl;show(&hb);cout<<endl;cout<<"合并后链表hb的节点排列"<<endl;merge(&ha,&hb);show(&hb);}void create(Slink* h){if(!h) return;int n=0;//节点总数int j=0;//累计创建结点个数cout<<"请输入创建节点的个数"<<endl;cin>>n;Node* F=h;//F始终指向tou节点Node* pre=h;//pre始终指向要插入位置的前一个节点while(j<n){Node* p=new Node;cout<<"请输入节点的数据"<<endl;cin>>p->data;//链表为空时if(!F->next ){ F->next =p;p->next =NULL;j++;continue;}//链表不空时while(pre->next ){ if(p->data <pre->next ->data ){ p->next =pre->next ;pre->next =p;pre=h;j++;break;}else if (p->data ==pre->next ->data){ cout<<"该值已存在，请重新输入"<<endl;break;}pre=pre->next ;}if(!pre->next ){ pre->next =p;p->next =NULL;j++;}}}void merge(Slink* ha,Slink* hb){ //p遍历ha,q遍历hbNode * p=ha->next ;Node * q=hb->next ;//pw始终指向新生成链表的最后一个结点Node * pw=hb;while(p&&q){ if((p->data)<(q->data)){ pw->next=p;p=p->next;pw=pw->next;continue;}if((p->data)>(q->data)){ pw->next=q;q=q->next;pw=pw->next;continue;}if((p->data)==(q->data)){ pw->next=q;p=p->next;q=q->next;pw=pw->next;continue;}}while(p){ pw->next=p;p=p->next;pw=pw->next;}while(q){ pw->next=q;q=q->next;pw=pw->next;}pw->next=NULL;}void show(Slink* h){Node* p=h->next ;while(p ){ cout<<p->data <<" ";p=p->next ;}cout<<endl;}2．约瑟夫（Joseph）问题。

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

2. 学习使用循环链表解决线性问题。

3. 提高编程能力和算法设计能力。

二、实验原理约瑟夫问题（Josephus Problem）是一个著名的数学问题，也称为约瑟夫环问题。

问题描述为：N个人围成一圈，从第一个人开始按顺时针方向报数，每数到M的人出列，然后从下一个人开始继续报数，直到所有人都出列。

我们需要找到一种方法，计算出每个人出列的顺序。

三、实验内容1. 创建一个循环链表，模拟N个人围成一圈。

2. 编写一个函数，实现报数和出列操作。

3. 输出每个人出列的顺序。

四、实验步骤1. 定义一个循环链表节点结构体，包含编号和指向下一个节点的指针。

2. 创建一个循环链表，包含N个节点，节点的编号依次为1到N。

3. 编写一个函数`kill(int m, int n)`，实现报数和出列操作：- 初始化一个指针指向第一个节点。

- 从第一个节点开始，按照报数上限M进行报数，每数到M的人出列。

- 更新指针，指向下一个节点，继续报数。

- 重复上述步骤，直到所有节点都被删除。

4. 输出每个人出列的顺序。

五、实验代码```c#include <stdio.h>#include <stdlib.h>// 定义循环链表节点结构体typedef struct Node {int number; // 节点编号struct Node next; // 指向下一个节点的指针} Node;// 创建循环链表Node create(int n) {Node head = NULL, tail = NULL, temp = NULL; for (int i = 1; i <= n; i++) {temp = (Node)malloc(sizeof(Node));temp->number = i;temp->next = NULL;if (head == NULL) {head = temp;tail = temp;} else {tail->next = temp;tail = temp;}}tail->next = head; // 形成循环链表return head;}// 输出循环链表void printList(Node head) {Node temp = head;do {printf("%d ", temp->number);temp = temp->next;} while (temp != head);printf("\n");}// 解决约瑟夫问题void josephus(int m, int n) {Node head = create(n);Node temp = head, pre = NULL;for (int i = 1; i <= n; i++) {for (int j = 1; j < m; j++) {pre = temp;temp = temp->next;}printf("%d ", temp->number);pre->next = temp->next; // 删除节点 free(temp);temp = pre->next;}printf("\n");}int main() {int m, n;printf("请输入报数上限M: ");scanf("%d", &m);printf("请输入人数N: ");scanf("%d", &n);printf("初始站队为: ");josephus(m, n);return 0;}```六、实验结果与分析通过运行实验代码，可以得到每个人出列的顺序。

约瑟夫环实验报告约瑟夫环实验报告引言：约瑟夫环是一个经典的数学问题，它源自于古代传说。

根据传说，古代犹太人被罗马人围困在一个洞穴中，他们决定用一种特殊的方式来决定谁将成为首领。

他们站成一个圆圈，从一个人开始，每隔一个人杀掉一个，直到只剩下一个人。

这个问题被称为约瑟夫环问题，它在数学领域引起了广泛的研究和探讨。

实验目的：本实验旨在通过模拟约瑟夫环问题，探讨其数学规律和解法，并分析实验结果的意义和应用。

实验步骤：1. 首先，我们需要确定参与约瑟夫环的人数n和每次报数的间隔m。

在本次实验中，我们选择了n=10和m=3。

2. 接下来，我们将10个人按顺序排成一个圆圈，并给每个人编号，编号从1到10。

3. 实验开始时，从第一个人开始报数，每次报数到m的人将被淘汰出局。

4. 淘汰的人将离开圆圈，下一个人将从淘汰者的下一个人开始报数，继续进行报数和淘汰的过程，直到只剩下一个人为止。

实验结果：通过模拟实验，我们得到了以下结果：- 第一轮淘汰的人依次为：3、6、9、2、7、1、8、5、10。

- 第二轮淘汰的人依次为：4、9、2、8、5、1、7、6。

- 第三轮淘汰的人依次为：9、8、5、1、7、4、6。

- 第四轮淘汰的人依次为：1、7、4、6、9、5。

- 第五轮淘汰的人依次为：7、4、6、9、5。

- 第六轮淘汰的人依次为：4、6、9、5。

- 第七轮淘汰的人依次为：6、9、5。

- 第八轮淘汰的人依次为：9、5。

- 第九轮淘汰的人依次为：5。

结论：通过实验结果的分析，我们可以得出以下结论：1. 在本次实验中，最后幸存的人是编号为5的人。

2. 根据实验结果，我们可以总结出约瑟夫环问题的一般解法。

假设总人数为n，每次报数的间隔为m，最后幸存的人的编号可以通过递归公式f(n,m)=[f(n-1,m)+m]%n得到。

3. 约瑟夫环问题在数学中具有一定的研究价值和应用意义。

它涉及到递归、数论等数学概念和方法，可以帮助我们更好地理解和应用这些数学知识。

数据结构实验报告约瑟夫环约瑟夫环是一个古老而有趣的问题，也是数据结构中一个经典的应用。

它的故事发生在公元前1世纪，当时犹太人正面临罗马的入侵。

为了避免被俘虏，一群犹太士兵决定以一种特殊的方式自杀，而不是被罗马人俘虏。

他们围成一个圈，按照某个规则进行自杀，直到只剩下一个人为止。

这就是著名的约瑟夫环问题。

在这个问题中，我们有n个人，编号从1到n，围成一个圈。

按照一定的规则，从第一个人开始报数，每次报到m的人将被淘汰。

然后，从下一个人开始重新报数，如此循环，直到只剩下一个人为止。

这个问题的解决方法有很多，其中最常见的是使用链表数据结构。

我们可以将每个人表示为一个节点，节点之间通过指针连接，形成一个环形链表。

每次淘汰一个人后，只需要将指针跳过被淘汰的节点，重新连接链表。

为了更好地理解这个问题，我们可以通过一个简单的例子来演示。

假设有10个人，编号从1到10，每次报数到3的人将被淘汰。

首先，我们将这10个人表示为一个环形链表：1->2->3->4->5->6->7->8->9->10->1。

按照规则，第一次报数到3的人是3号，所以我们将3号节点从链表中删除：1->2->4->5->6->7->8->9->10->1。

接下来，从4号节点开始重新报数。

第二次报数到3的人是6号，所以我们再次将6号节点从链表中删除：1->2->4->5->7->8->9->10->1。

以此类推，直到只剩下一个人为止。

通过这个例子，我们可以看到约瑟夫环问题的解决方法非常简单直观。

使用链表数据结构，每次淘汰一个人后，只需要将指针跳过被淘汰的节点，重新连接链表。

这种方法的时间复杂度为O(n*m)，其中n为人数，m为报数的次数。

除了链表，还有其他数据结构可以用来解决约瑟夫环问题。

数据结构实验报告约瑟夫环约瑟夫环是一种经典的数学问题，它源于古代传说中的故事。

根据传说，约瑟夫是一位犹太历史学家，他和他的朋友们被罗马军队包围在一个洞穴里。

为了避免被俘虏，他们决定自杀，但是他们决定以一个特殊的方式来做。

他们围成一个环，从一个人开始，每隔一个人就杀死一个，直到只剩下一个人。

约瑟夫是最后一个幸存者。

这个问题可以用数据结构来解决，其中最常用的方法是使用循环链表。

循环链表是一种特殊的链表，它的最后一个节点指向第一个节点，形成一个环。

在解决约瑟夫环问题时，我们可以使用循环链表来模拟这个环。

首先，我们需要创建一个循环链表，并将所有的人依次添加到链表中。

然后，我们需要设置一个计数器，用来记录当前的位置。

接下来，我们需要遍历链表，每次遍历到计数器所指向的位置时，将该节点从链表中删除，并将计数器加一。

当计数器的值等于要删除的位置时，我们就将该节点删除，并将计数器重置为1。

重复这个过程，直到链表中只剩下一个节点为止。

通过使用循环链表，我们可以很方便地解决约瑟夫环问题。

这种方法的时间复杂度为O(n*m)，其中n表示初始链表的长度，m表示要删除的位置。

由于每次删除一个节点后，链表的长度会减少，所以实际上的时间复杂度会小于O(n*m)。

除了使用循环链表，还可以使用数组来解决约瑟夫环问题。

我们可以创建一个长度为n的数组，然后将所有的人依次添加到数组中。

接下来，我们需要设置一个计数器，用来记录当前的位置。

然后，我们需要遍历数组，每次遍历到计数器所指向的位置时，将该人从数组中删除，并将计数器加一。

当计数器的值等于要删除的位置时，我们就将该人删除，并将计数器重置为1。

重复这个过程，直到数组中只剩下一个人为止。

与循环链表相比，使用数组解决约瑟夫环问题的方法更加简单。

但是，数组的长度是固定的，所以如果要解决的问题规模很大，可能会导致内存的浪费。

此外，数组的删除操作需要移动其他元素，所以时间复杂度较高。

综上所述，约瑟夫环问题是一个经典的数学问题，可以通过使用循环链表或数组来解决。

约瑟夫环实验报告约瑟夫环（Josephus problem）是一个非常经典的数学问题，其得名于公元1世纪的犹太历史学家约塞夫斯（Josephus）。

约瑟夫环问题描述如下：n个人围坐成一个圆圈，从一些人开始依次报数，每报到第m个人，该人就被淘汰出圆圈，然后从下一个人重新开始报数。

直到剩下最后一个人时，即为问题的解。

例如，当n=7，m=3时，最后剩下的是4号人。

本次实验的目的是研究约瑟夫环问题的解决方法，并通过编程实现给定n和m的情况下找到最后的获胜者。

首先，我们需要分析问题的特点。

当n=1时，该问题的解即为最后剩下的人；当n>1时，最后剩下的人可以通过前一轮问题的解（剩下n-1个人的情况下）推导出来。

我们可以将解决该问题的方法分为两种：递归法和迭代法。

一、递归法递归法是通过问题的子问题来解决原问题。

对于约瑟夫环问题来说，递归法的解题思路如下：1.当n=1时，问题的解即为1；2.当n>1时，问题的解为（找到n-1个人时的解+m-1）对n取模，即((f(n-1,m)+m-1)%n)+1二、迭代法迭代法通过循环来解决问题，不断更新当前的解，直到问题得到解决。

对于约瑟夫环问题来说，迭代法的解题思路如下：1.初始化一个长度为n的数组a，a[i]=1表示第i个人还在圆圈中，a[i]=0表示第i个人已经被淘汰出圆圈；2. 从第一个人开始计数，每报数到第m个人，则将该人设为已淘汰，并计数器count加1；3. 重复步骤2，直到count=n-1；4.循环遍历数组a，找到最后剩下的人。

为了更加直观地展示实验结果，我们通过Python编写下述代码：```python#递归法解决约瑟夫环问题def josephus_recursive(n, m):if n == 1:return 1else:return (josephus_recursive(n - 1, m) + m - 1) % n + 1#迭代法解决约瑟夫环问题def josephus_iterative(n, m):a=[1]*ncount = 0i=0while count < n - 1:if a[i] == 1:j=0while j < m:if a[(i + j) % n] == 1:j+=1else:j=0i=(i+1)%na[(i-1)%n]=0count += 1for i in range(n):if a[i] == 1:return i + 1#测试递归法解决约瑟夫环问题print(josephus_recursive(7, 3)) # 输出4 #测试迭代法解决约瑟夫环问题print(josephus_iterative(7, 3)) # 输出4 ```通过以上代码，我们可以得到n=7，m=3时，最后剩下的人是4号人。

约瑟夫环实验报告约瑟夫环实验报告约瑟夫环是一种古老而有趣的数学问题，它源于古代传说中的一个故事。

根据这个故事，约瑟夫是一位犹太人，他和他的朋友们被罗马军队包围在了一个洞穴中。

他们决定宁愿死在洞穴里，也不愿被捕。

于是，他们决定通过一个特殊的方式来决定谁将是第一个自愿去死的人。

约瑟夫提出了一个规则：所有人围成一个圆圈，从某个人开始，每次数到一个固定的数字，该人就会被移除。

然后，继续数下去，直到只剩下一个人。

这个问题被称为约瑟夫环。

为了更好地理解这个问题，我们进行了一次约瑟夫环实验。

我们邀请了十个志愿者参与实验。

首先，我们让他们围成一个圆圈，按照顺时针方向依次编号为1到10。

然后，我们决定每次数到3的人将被移除。

实验开始后不久，我们就发现了一些有趣的现象。

首先，当数到第三个人时，他被移除了。

然后，我们继续数下去，每次数到第三个人，他们也被移除。

但是，当我们数到第九个人时，他并没有被移除。

相反，我们又从第一个人开始数。

这个过程一直持续下去，直到只剩下最后一个人。

通过这个实验，我们发现了约瑟夫环问题的一些规律。

首先，当总人数为奇数时，最后剩下的人的编号总是1。

这是因为每次移除一个人后，剩下的人重新排列，而编号为1的人始终在最后一个位置。

而当总人数为偶数时，最后剩下的人的编号取决于每次数到的数字。

例如，在我们的实验中，当总人数为10时，最后剩下的人的编号是5。

除了这些规律，约瑟夫环问题还有一些有趣的数学性质。

例如，我们可以通过数学推导得出，当总人数为2的幂次方时，最后剩下的人的编号总是1。

这是因为在每次移除一个人后，剩下的人的编号都会向前移动一个位置，而编号为1的人始终在最后一个位置。

通过这次实验，我们不仅更深入地了解了约瑟夫环问题，还发现了一些有趣的数学规律。

这个问题不仅仅是一个数学谜题，它也可以引发我们对数学的思考和探索。

我们相信，通过继续研究约瑟夫环问题，我们可以发现更多有趣的数学性质和规律。

总结起来，约瑟夫环是一个古老而有趣的数学问题，通过实验我们发现了一些规律和性质。

实验1约瑟夫环问题1．需求分析（1）输入的形式和输入值的范围：每一次输入的值为两个正整数，中间用逗号隔开。

若分别设为n,m，则输入格式为：“n,m”。

不对非法输入做处理，即假设输入都是合法的。

（2）输出的形式：输出格式1：在字符界面上输出这n个数的输出序列输出格式2：将这n个数的输出序列写入到文件中（3）程序所能达到的功能：对于输入的约瑟夫环长度n和间隔m，输出约瑟夫环的出列顺序。

（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。

正确：输入：10,3输出：3 6 9 2 7 1 8 5 10 4输入：41,3输出：3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 2634 40 8 17 29 38 11 25 2 22 4 35 16 31错误：输入：10 3输出：6 8 7 1 3 4 2 9 5 102．概要设计（1）抽象数据类型的定义：为实现上述程序的功能，可以用整数存储用户的输入。

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

线性表ADT定义如下：ADT list数据对象：整形数据关系：线性关系，即<ai,ai+1>(0≤a＜n)。

基本操作：bool remove(int &elem)//移除一个元素，被移除的元素赋给elem//如果操作成功，返回true,否则返回falsebool isEmpty()//判断数组的元素是否清空，空返回true,否则返回falsebool setPos(int place)//设置当前元素的位置，设置成功返回true,否则返回falseint getLength()//获取数组的实际长度（2）算法的基本思想：约瑟夫环问题中的数据是人所在的位置，而这种数据是存在“第一元素、最后元素”，并且存在“唯一的前驱和后继的”，符合线性表的特点。

实验报告一题目：约瑟夫环路班级：信息管理与信息系统姓名：王志钢学号：614指导教师：孟繁军完成日期：一．需求分析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={<ai-1,ai> | ai-1, ai ∈D , i=2,……n}基本操作：LinkList EvaluList(int n);执行输入人数时，输入0程序出现了意想不到的错误，所以再重新设计时加入了对空节点的处理2.在链表节点的设计上，最初是仅包含密码和指针，但是后来考虑到链表节点删除时会带来一系列的编号变化，编号难以确定，所以节点设计上又加了一个编号3.在单向链表的赋值操作时，原本是以一个不变的L作为头结点，但是这种赋值方法带来了诸多变量设计的问题，所以将L为节点，赋值完成后，再让L指向头结点六、用户使用说明：题目：约瑟夫环路本程序将利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。