北邮数据结构实验一约瑟夫问题实验报告(递归做法)

学院计算机与信息工程系数据结构课程设计设计题目：约瑟夫环问题专业班级学号姓名指导教师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.调试分析在本次试验调试中很不顺利。

数据结构实验报告题目：约瑟夫环姓名：学号：专业班级：指导教师：课题工作时间：一．需求分析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——约瑟夫环学生姓名：班级：班内序号：学号：日期：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个人。

华北#########学院数据结构实验报告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）问题。

《计算机软件技术基础》实验报告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）。

三、概要设计为了实现上述功能，应用循环链表来模拟该过程，用结构体来存放其相应的编号和密码信息，因此需要循环链表结构体这个抽象数据类型。

1．循环链表结构体抽象数据类型定义：ADT Node{数据对象：D={ai,bi,ci|ai∈int, bi∈int,ci∈(Node*),i =1,2...,n,n ≥0}:数据关系：R=∅基本操作：CreatList(int n) //构建循环单链表；Order(int m,node *l) //输出函数，输出出列顺序并删除链表中的结点；}ADT node；2. ADT的C语言形式说明：typedef struct Node{int num; //结点的数据域，存放编号；int word; //结点的数据域，存放密码；struct Node *next; //结点的指针域，存放指向下一结点的指针；}Node；Node *CreatList( ) //建立循环单项链表；void Order(Node *h) //输出出列顺序并删除结点；3. 主程序流程及其模块调用关系:1）.主程序流程：先提示用户输入相关数据：总人数，运行循环链表结构体模块，输入每个人持有的密码值，创建出新链表，运行输出函数模块，再输入初始密码m值，输出出列序列。

实验报告实验一线性表的基本操作及其应用一、实验目的1、复习C语言程序设计中的知识。

2、熟悉线性表的逻辑结构。

3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。

二、实验内容本次实验提供2个题目，如果实现第一个题目有困难，可做第二个题目题目一：约瑟夫环[问题描述]约瑟夫（Joseph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人可有代表本人的序号。

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

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

试设计一个程序求出出列顺序。

[基本要求]利用单向链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

[测试数据]由学生任意指定。

如：m的初值为5；n的值为7；序号：3，1，7，2，4，8，4；(报告上要求写出多批数据测试结果)[实现提示]程序运行后首先要求用户输入初始报数m，人数n,(设n≤30)。

然后输入各人的序号。

[选作内容]向上述程序中添加在顺序结构上实现的部分实验题目一：约瑟夫环一．需求分析1．利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

2．演示程序以用户和计算机的对话方式执行，即在计算机上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据（滤去输入中的非法字符）和运算结构显示在其后。

3.程序执行的命令包括：1）输入报数上限值；2）输入人数以及所持密码；3）输出出列顺序；4）结束2）测试数据4.由学生任意指定。

如：m的初值为5；n的值为7；序号：3，1，7，2，4，8，4；二．概要设计为实现上述程序功能，需建立单向循环链表以存储此结构。

为此，需要一个抽象数据结构类型。

1.链表结点的抽象数据类型定义为：ADT2.本程序包含三个模块：3）主程序模块；4）循环链表的创建模块——实现创建循环链表；5）出列操作的模块——实现最终的出列操作；各模块之间的调用关系如下：出列操作的模块<——主程序模块——>循环链表的创建模块三.详细设计1.元素类型，结点类型和指针类型struct Lnode{int password;struct Lnode *next;};typedef struct Lnode *LinkList;2. 子函数1，创建循环链表int Creatlist_L(LinkList &head,int n)程序的实现：int Creatlist_L(LinkList &head,int n){//利用引用调用得到头指针head;int i;LinkList p,q;printf("请依次输入各位密码：");for(i=1;i<=n;i++){if(i==1){//申请一个空间，将头指针head和指针p均指向第一个结点；head=p=(LinkList)malloc(sizeof(struct Lnode));if(p==0) return 0; //分配存储空间失败}else{q=(LinkList)malloc(sizeof(struct Lnode));if(q==0) return 0;p->next=q;//通过next将下一个结点和前一个结点连起来;p=q;}scanf("%d",&(p->password));//一次输入对应的密码；}p->next=head;//构成循环链表，并返回链表的头指针return 0;}void DeleteNode(LinkList head,int m,int n){LinkList p,q;int j,i;p=head;for(j=1;j<n;j++){//先出列前n-1个人，并依次释放其结点的空间；for(i=1;i<m;i++,p=p->next);//寻找第m个人；printf("%d ",p->password);p->password=p->next->password;//将后一个结点的数据全部赋值于当前p所指的结点q=p->next;p->next=p->next->next;//p指向其下一个的下个一结点，重新开始寻找；free(q);}printf("%d",p->password);//最后一个人出列，并释放其结点所占空间；free(p);} }scanf("%d",&(p->password));//一次输入对应的密码；}p->next=head;//构成循环链表，并返回链表的头指针return 0;}3.主函数的实现，对两个子函数的调用void main(){int n,m;LinkList List;printf("输入人数:");scanf("%d",&n);printf("输入值m:");scanf("%d",&m);Creatlist_L(List,n);DeleteNode(List,m,n);printf("\n");}4.函数的调用关系图反映了演示程序的层次结构：main——>Creatlist;main——>DeleteNode;四调试分析1.由于对引用调用理解的不透侧，导致刚开始修改了很长时间。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

数据结构实验报告约瑟夫环约瑟夫环是一个经典的问题，涉及到数据结构中的循环链表。

在本次数据结构实验中，我们将学习如何使用循环链表来解决约瑟夫环问题。

约瑟夫环问题最早出现在古代，传说中的犹太历史学家约瑟夫斯·弗拉维奥（Josephus Flavius）在围攻耶路撒冷时，为了避免被罗马人俘虏，与其他39名犹太人躲进一个洞穴中。

他们决定宁愿自杀，也不愿被敌人俘虏。

于是，他们排成一个圆圈，从第一个人开始，每次数到第七个人，就将他杀死。

最后剩下的人将获得自由。

在这个问题中，我们需要实现一个循环链表，其中每个节点表示一个人。

我们可以使用一个整数来表示每个人的编号。

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

接下来，我们需要使用一个循环来模拟每次数到第七个人的过程。

我们可以使用一个指针来指向当前节点，然后将指针移动到下一个节点，直到数到第七个人为止。

一旦数到第七个人，我们就将该节点从链表中删除，并记录下该节点的编号。

然后，我们继续从下一个节点开始数数，直到只剩下一个节点为止。

在实现这个算法时，我们可以使用一个循环链表的数据结构来表示约瑟夫环。

循环链表是一种特殊的链表，其中最后一个节点的指针指向第一个节点。

这样，我们就可以实现循环遍历链表的功能。

在实验中，我们可以使用C语言来实现循环链表和约瑟夫环算法。

首先，我们需要定义一个节点结构体，其中包含一个整数字段用于存储编号，以及一个指针字段用于指向下一个节点。

然后，我们可以实现创建链表、添加节点、删除节点等基本操作。

接下来，我们可以编写一个函数来实现约瑟夫环算法。

该函数接受两个参数，分别是参与游戏的人数和每次数到第几个人。

在函数内部，我们可以创建一个循环链表，并将所有人的编号添加到链表中。

然后，我们可以使用一个循环来模拟每次数到第几个人的过程，直到只剩下一个节点为止。

在每次数到第几个人时，我们可以删除该节点，并记录下其编号。

最后，我们可以返回最后剩下的节点的编号。

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

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

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

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

2. 程序分析2.1 存储结构采用单循环链表实现约瑟夫问题的求解单循环链表存储结构示意图2.2 关键算法分析基本思想：首先，应该确定构造链表时所用的插入方法。

当数到m的那个人就出列，也即删除这个节点，同时建立这个节点的前节点与后节点的联系。

由于是循环计数，所以才采用循环列表方式。

第1页其次还要考虑输入值异常的情况。

之后，就是关于出列节点的逻辑判断。

依次找到待删结点的直接前驱，便于删除结点后修改它的直接后继，如此循环直到最后一个人出列。

关键算法：1.最后一个数据指向头指针，形成循环链表head=new Node; //确定头结点p=head;for(i=1;i<=n-1;i++) //赋初值{p->data=i;p->next=new Node; //为下一个新建内存p=p->next;}p->data=n; //最后一个单独处理p->next=head; //指向头，形成循环链表p=head;2.输入值异常的情况cout<<"请输入环内总人数n:";cin>>n;if (n<1) //考虑n输入错误的情况{cout<<"n值输入错误"<<endl;}cout<<"请输入起始人号码:";cin>>k;if (k<1||k>n) //考虑k输入异常的情况{cout<<"k值输入错误"<<endl;}cout<<"请输入m值:";cin>>m;if (m<1) //考虑m输入异常的情况{cout<<"m值输入错误"<<endl;}3.在约瑟夫环中实现逐个出环并找出最后一个出环的序号while(p!=p->next){for(i=1;i<m-1;i++) //查找q的节点p=p->next;q=p->next;cout<<"第"<<s<<"个出环的人编号是："<<q->data<<endl;p->next=q->next;北京邮电大学信息与通信工程学院p=p->next;delete q; //释放q的空间s++;}cout<<"最后环内留下的人编号是："<<p->data<<endl;delete p;算法步骤：①从第一个结点开始，查找第i-1个元素，设为p指向该结点；②设q指向第i个元素：q = p->next;，输出q元素的数据；③摘链，即将q元素从链表中摘除：p->next = q->next;p=p->next;delete q;3. 程序运行结果1、测试主函数流程：流程图如图所示第3页2、程序运行结果3、输入错误运行结果4. 总结在调试程序过程中，虽然没有编译错误，但是运行结果总是和准确值差1，最后发现是把i=1写成i=0，才造成的错误，改过之后就没有问题了。