约瑟夫问题实验报告

1、约瑟夫问题实验报告篇一：约瑟夫问题数据结构实验报告 中南民族大学管理学院 学生实验报告 实验项目: 约瑟夫问题 课程名称： 数据结构 年级： 专业：信息管理与信息系统 指导教师：实验地点：管理学院综合实验室 完成日期： 小组成员： 学年度第一、实验目的 （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

2、时一个人就出列，也即删除这个节点，同时建立这个节点的前节点与后节点 的联系。由于是循环计数，所以才采用循环列表这个线性表方式。 程序存储结构 利用单循环链表存储结构存储约瑟夫数据（即n个人的编 码等），模拟约瑟夫的显示过程，按照出列的顺序显示个人的标号。编号为 1,2,?,n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。 一开始任选一个正整数作为报数上限值 m，从第一个人开始按顺时针方向自 1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新 的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去， 直至所有人全部出列为止。试设计一个程序求出出列顺序。基本要求是利用 单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 程序执行的命令（1）构造单向循环链表。 （2）按照出列的顺序引出各个人的标号。 测试数据 m 的初值为 20；密码：3，1，7，2，4，8，4（正确的结果 应为 6，1，4，7，2，3，5） （1）、插入：在把元素插入到循环链表中时，由于是采用的头插法，所以我 保留了front头结点。在每加入一个节点时，

3、都会直接连接在front后面， 从而保证一开始就赋值的rear尾节点不用修改。 伪代码阐释如下： 1)、在堆中建立新节点：NodeT *s=new NodeT;2)、将ai写入到新节点的数据域：s-data=ai; 3)、修改新节点的指针域：s-next=front-next; 4)、修改头结点的指针域，将新节点加入到链表中：front-next=s; 时间复杂度为：1； (2)、删除：首先通过p指针查找到所要删除的节点的前一个节点，继而通 过q=p-next简单地删除掉。假设所要查找的为第i个元素。 伪代码阐释如下： 1）、在堆中建立新节点p,通过循环查找到i-1，将此节点的地址赋给p。 2）、设q指向第i个节点：若p=rear，则q=front-next; 否则，q=p-next; 3)、摘链，即将q从链表中摘除：若q=rear，则p-next=front-next；否 则，则p-next=q-next. 4)、保存q元素的数据：x=q-data； 5）、释放q元素：delete q； 时间复杂度为：1； （3）、约瑟夫问题的基本思想：在这个循环查找问题中，通过循环链表实现 了循环

4、查找到节点。一个关键部分就是删除节点后进行链表的链接，从而保 证链表的循环性。在查找方面上，我利用了一个for循环来计数所查找过的 节点。其中查找的时间复杂度也为1； （二）概要设计 测试主函数流程： 流程图如下： 否（三）详细设计 #includeiostream using namespace std; const int d=50000; struct Node int data; struct Node*next; /声明next指针 ;class Clinklist public: Clinklist(int a,int n); void Josef(int m,int n); private: Node *rear; /声明rear和front指针 Node *front; int n; ; Clinklist:Clinklist(int a,int n) rear=new Node; front=new Node; front-next=rear;/构造空单链表 rear-next=front; rear-data=an-1; for(int i=n-2;i=0;i-)

5、Node*s=new Node; /循环插入元素来建立链表s-data=ai; s-next=front-next; front-next=s; void Clinklist:Josef(int m,int n) Node* p=front; int j=0; while(front-next!=front) int i=0; while(i!=m-1) /实现第m-1个节点的查找 if(p=rear) p=front-next; else p=p-next; i+;篇二：约瑟夫环问题 实验报告 数学与计算机学院 约瑟夫环问题 实验报告 年级 10级 学号 2021434062 姓名 成绩 专业 电气信息（计算机类）实验地点 主楼402 指导教师 史青宣 实验项目 约瑟夫环问题 实验日期 2021年12月26日 一、实验目的 本实验的目的是进一步理解线性表的逻辑结构和存储结构，进一步提高使用理 论知识指导解决实际问题的能力。 二、实验问题描述 设编号为1，2，n的n个人围坐一圈，约定编号为k（1kn）的人从1 开始报数，数到m的那个人出列，他的下一位又从1开始报数，数到m的那个人 又出

6、列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。 三、实验步骤 1、实验问题分析 由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人 仍要是围成一个圆圈，可以使用循环表；由于退出圆圈的工作对应着表中结点的 删除操作，对于这种删除操作频繁的情况，应该选用效率较高的链表结构；为了 程序指针每一次都指向一个具体的代表一个人的结点而不需要进行判断，链表不 带表头结点。所以，对于所有人围成的圆圈所对对应的数据结构采用一个不带头 结点的循环链表来描述。设头指针为p，并根据具体情况移动 可以采用数据类型定义： Typedef struct node int number; struct node *next; Lnode,*Linklist; 为了记录退出的人的先后顺序，采用一个顺序表进行存储，程序结束后再 输入依次退出的人的编号顺序。由于只记录各个结点的number值就可以，所以 定义一个整型一维数组。如“int quiteN;”N为一个根据实际问题定义的一 个足够大的整数。 2、功能（函数）设计 根据上述分析，该算法可以由3个功能函数实现。Main（）用做数据的输入和

7、函数的调用，Init()做链表的初始化工作，使用Josephus()做删除结点和保存 输出顺序的工作，OutRing()完成序列的输出工作。 1.建立单循环链表函数 LinkList InitRingList(int n)； 2.产生Josephus顺序函数 void Josephus(LinkList L,int n,int k,int m,int quitN) 3.输出顺序表void Print(int n,int quitN) 四、实验结果（程序）及分析 1.实验的的源代码： / 约瑟夫环问题.cpp : Defines the entry point for the console application. / /#include stdafx.h #includeiostream.h #define N 34 typedef struct Node int data; struct Node *next; Lnode,*LinkList; LinkList InitRingList(int n)/尾插法建立单循环链表 Lnode *L,*r,*s; L=new Lnode; /不带头结点 r=L; for(int i=1;in;i+) s=new Lnode; r-data=i; r-next=s; r=s; r-data=n; r-next=L; /链表首尾相连 L=r; /L指向循环链表的尾结点 return L; void Josephus(LinkList L,int n,int k,int m,int quitN) int i,j; Lnode *p,*q; p=L; for(int r=1;rm;r+)p=p-next; for(i=0;in;i+) for(j=1;j=k-1;j+) p=p-next; q=p-next; p-next=q-next; quiti=q-data; delete q; void Print(int n,int quitN) int i; for(i=0;in;i+)

《约瑟夫问题实验报告》由会员re****.1分享，可在线阅读，更多相关《约瑟夫问题实验报告》请在金锄头文库上搜索。