数据结构实验报告 约瑟夫环问题

约瑟夫问题实验报告背景约瑟夫问题（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个数输出到屏幕上三．详细设计首先，设计实现约瑟夫环问题的存储结构。

2009级数据结构实验报告实验名称：实验线性表实现约瑟夫问题求解学生姓名：桂柯易班级：2009211120班内序号：07学号：09210580日期：2010年10月31日1.实验要求【实验目的】1．熟悉C++语言的基本编程方法,掌握集成编译环境的调试方法；2．学习指针、模板类、异常处理的使用；3．掌握线性表的操作实现方法；4．培养使用线性表解决实际问题的能力。

【实验内容】利用循环链表实现约瑟夫问题的求解。

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

从序号为1的人开始报数，顺时针数到m的那个人出列。

他的下一个人又从1开始报数，数到m 的那个人又出列。

依此规则重复下去，直到所有人全部出列。

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

2.程序分析2.1 存储结构存储结构：循环链表2.2 关键算法分析【设计思想】首先，设计实现约瑟夫环问题的存储结构。

由于约瑟夫环本身具有循环性质，考虑采用循环链表，为了统一对表中任意节点的操作，循环链表不带头结点。

循环链表的结点定义为如下结构类型：struct Node{int number;Node *next;};其次，建立一个不带头结点的循环链表并由头指针first指示。

最后，设计约瑟夫环问题的算法。

【伪代码】1、工作指针first，r，s，p，q初始化2、输入人数（n）和报数（m）3、循环n次，用尾插法创建链表Node *q;for(int i=1;i<=n;i++){Node *p;p=new Node;p->number=i;p->next=NULL;if(i==1) L=q=p;else{q->next=p;q=q->next;}}q->next=L;if(L!=NULL){return(L);}4、输入报数的起始人号数k;5、Node *q = new Node;计数器初始化i=1;6、循环n次删除结点并报出位置（其中第一个人后移k个）当i<n时移动指针m-2次p=p->next;删除p结点的后一结点qq=p->next;p->next=q->next;*L = p->next;报出位置后Delete q;计数器i++;【复杂度】for(int i=1;i<=n;i++){Node *p;p=new Node;p->number=i;p->next=NULL;if(i==1) L=q=p;else{q->next=p;q=q->next;}时间复杂度：O（n）if(i==1) i+=LengthList(*L);Node *p;p=*L;int j=0;while(j<i-2) {p=p->next;j++;}q = p->next;p->next=p->next->next;*L = p->next;return(q);时间复杂度：O（n2）算法的空间复杂度：O（n2）2.3 其他程序源代码：#include<iostream>using namespace std;struct Node//循环节点的定义{int number;//编号Node *next;};Node *CreateList(Node *L,int &n,int &m);//建立约瑟夫环函数void Joseph(Node *L,int n,int m);//输出每次出列号数函数Node *DeleteList(Node **L,int i,Node *q);//寻找每次出列人的号数int LengthList(Node *L);//计算环上所有人数函数void main()//主函数{Node *L;L=NULL;//初始化尾指针int n, m;cout<<"请输入人数N：";cin>>n;//环的长度if(n<1){cout<<"请输入正整数!";}//人数异常处理else{cout<<"请输入所报数M：";cin>>m;if(m<1){cout<<"请输入正整数!";}//号数异常处理else{L=CreateList(L,n,m);//重新给尾指针赋值Joseph(L,n,m);}}system("pause");}Node *CreateList(Node *L,int &n,int &m)//建立一个约瑟夫环（尾插法）{Node *q;for(int i=1;i<=n;i++){Node *p;p=new Node;p->number=i;p->next=NULL;if(i==1) L=q=p;//工作指针的初始化else{q->next=p;q=q->next;}}q->next=L;if(L!=NULL){return(L);}//返回尾指针else cout<<"尾指针异常!"<<endl;//尾指针异常处理}void Joseph(Node *L,int n,int m)//输出每次出列的人{int k;cout<<"请输入第一个报数人：";cin>>k;if(k<1||k>n){cout<<"请输入1-"<<n<<"之间的数"<<endl;} else{cout<<"\n出列顺序:\n";for(int i=1;i<n;i++){Node *q = new Node;if(i==1) q=DeleteList(&L,k+m-1,q);//第一个出列人的号数else q=DeleteList(&L,m,q);cout<<"号数："<<q->number<<endl;delete q;//释放出列人的存储空间}cout<<"最后一个出列号数是："<<L->number<<endl;;//输出最后出列人的号数}}Node *DeleteList(Node **L,int i,Node *q) //寻找每次出列的人{if(i==1) i+=LengthList(*L);//顺序依次出列情况的处理方式Node *p;p=*L;int j=0;while(j<i-2) {p=p->next;j++;}q = p->next;p->next=p->next->next;*L = p->next;return(q);}int LengthList(Node *L)//计算环上的人数{if(L){cout<<"尾指针错误!"<<endl;}//异常处理else{int i=1;Node *p=L->next;while(p!=L){i++;p=p->next;}return(i);}}3.程序运行结果1.测试主函数流程：2.测试条件：如上图所示，人数为20人，所报数为6，第一个报数的人是1号。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

《数据结构》课程设计报告课程名称: 《数据结构》课程设计课程设计题目: 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, 2, 3,…，n的n个人按顺时针方向围坐一圈，每人手持一个密码（正整数）。

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

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

试设计程序实现之。

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

[ 实验提示] 程序运行后首先要求用户指定初始报数上限值。

然后读取各人的密码。

设n<=30 。

程序执行后,要求用户在计算机终端上显示“提示信息”后,用键盘输入“提示信息”中规定的命令,以“回车符”为结束标志。

相应的输入数据和运算结果显示在其后。

二、设计目的1. 达到熟练掌握C++ 语言的基本知识和技能；2. 能够利用所学的基本知识和技能,解决简单的面向对象程序设计问题。

3. 把课本上的知识应用到实际生活中,达到学以致用的目的。

三、系统分析与设计（确定程序功能模块）1、为实现上述程序的功能,应以有序链表表示集合。

基本操作：InitList(&L)操作结果：构造一个空的有序表L。

DestroyList(&L)初始条件：有序表L 已存在。

操作结果：销毁有序表L。

ListEmpty(L)初始条件：有序表L 已存在。

操作结果：若L为空表，则返回TRUE，否则返回FALSE。

ListLength(L)初始条件：有序表L 已存在。

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

GetElem(L,i)初始条件：有序表L已存在，并且K i< ListLength(L)。

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

LocatePos(L,e)初始条件：有序表L已存在，e和有序表中元素同类型的值。

操作结果：若L中存在和e相同的元素，则返回位置；否则返回0。

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

它的故事发生在公元前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为报数的次数。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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