篇一：约瑟夫问题数据结构实验报告
中南民族大学管理学院
学生实验报告
实验项目: 约瑟夫问题
课程名称： 数据结构
年级：
专业：信息管理与信息系统
指导教师：实验地点：管理学院综合实验室
完成日期：
小组成员：
学年度第
一、实验目的
（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 报数，如此下去，
直至所有人全部出列为止。试设计一个程序求出出列顺序。基本要求是利用
单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。
程序执行的命令（1）构造单向循环链表。
（2）按照出列的顺序引出各个人的标号。
测试数据 m 的初值为 20；密码：3，1，7，2，4，8，4（正确的结果
应为 6，1，4，7，2，3，5）
（1）、插入：在把元素插入到循环链表中时，由于是采用的头插法，所以我
保留了front头结点。在每加入一个节点时，都会直接连接在front后面，
从而保证一开始就赋值的rear尾节点不用修改。
伪代码阐释如下：
1)、在堆中建立新节点：Node<T> *s=new Node<T>;
2)、将a[i]写入到新节点的数据域：s->data=a[i];
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）、约瑟夫问题的基本思想：在这个循环查找问题中，通过循环链表实现
了循环查找到节点。一个关键部分就是删除节点后进行链表的链接，从而保
证链表的循环性。在查找方面上，我利用了一个for循环来计数所查找过的
节点。其中查找的时间复杂度也为1；
（二）概要设计
测试主函数流程：
流程图如下：
否
（三）详细设计
#include<iostream>
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=a[n-1];
for(int i=n-2;i>=0;i--)
{
Node*s=new Node; //循环插入元素来建立链表s->data=a[i];
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级 学号 2010434062 姓名 成绩
专业 电气信息（计算机类）实验地点 主楼402 指导教师 史青宣 实验项目 约瑟夫环问题 实验日期 2011年12月26日
一、实验目的
本实验的目的是进一步理解线性表的逻辑结构和存储结构，进一步提高使用理
论知识指导解决实际问题的能力。
二、实验问题描述
设编号为1，2，···，n的n个人围坐一圈，约定编号为k（1≤k≤n）的人从1
开始报数，数到m的那个人出列，他的下一位又从1开始报数，数到m的那个人
又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
三、实验步骤
1、实验问题分析
①由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人
仍要是围成一个圆圈，可以使用循环表；由于退出圆圈的工作对应着表中结点的
删除操作，对于这种删除操作频繁的情况，应该选用效率较高的链表结构；为了
程序指针每一次都指向一个具体的代表一个人的结点而不需要进行判断，链表不
带表头结点。所以，对于所有人围成的圆圈所对对应的数据结构采用一个不带头
结点的循环链表来描述。设头指针为p，并根据具体情况移动
可以采用数据类型定义：
Typedef struct node
{
int number;
struct node *next;
}Lnode,*Linklist;
②为了记录退出的人的先后顺序，采用一个顺序表进行存储，程序结束后再
输入依次退出的人的编号顺序。由于只记录各个结点的number值就可以，所以
定义一个整型一维数组。如“int quite[N];”N为一个根据实际问题定义的一
个足够大的整数。
2、功能（函数）设计
根据上述分析，该算法可以由3个功能函数实现。Main（）用做数据的输入和
函数的调用，Init()做链表的初始化工作，使用Josephus()做删除结点和保存
输出顺序的工作，OutRing()完成序列的输出工作。
1.建立单循环链表函数 LinkList InitRingList(int n)；
2.产生Josephus顺序函数 void Josephus(LinkList L,int n,int k,int
m,int quit[N])
3.输出顺序表void Print(int n,int quit[N])
四、实验结果（程序）及分析
1.实验的的源代码：
// 约瑟夫环问题.cpp : Defines the entry point for the console application.
//
//#include "stdafx.h"
#include"iostream.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;i<n;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 quit[N])
{
int i,j;
Lnode *p,*q;
p=L;
for(int r=1;r<m;r++)
p=p->next;
for(i=0;i<n;i++)
{
for(j=1;j<=k-1;j++)
p=p->next;
q=p->next;
p->next=q->next;
quit[i]=q->data;
delete q;
}
}
void Print(int n,int quit[N])
{
int i;
for(i=0;i<n;i++)
cout<<quit[i]<<" ";
cout<<endl;
}
int main(int argc, char* argv[])
{
LinkList L;
int n;
int k;
int m;
cout<<"请输入围坐一圈的人数n的值:"<<endl;
cin>>n;
L=InitRingList(n);
int quit[N];
cout<<"约定从编号为m的值开始数，请输入m的值:"<<endl;
cin>>m;
while(m>n||m<1)
{
cout<<"输入错误，请重新输入："<<endl;
cin>>m;
}
cout<<"要求数到k的人出列，请输入k的值:"<<endl;
cin>>k;
cout<<"顺序为:";
Josephus(L,n,k,m,quit);
Print(n,quit);
return 0;
}
2.测试数据
A．当n的初始值为7，k的值为5，m的值为1时，正确的出列顺序为：5、3、2、4、7、1、6，经程序运行测试，结果如下：
可知程序运行正确。
B．程序的容错性测试，当输入m的值不符合问题约定时，应有错误提示给用户，指导用户正确输入，并做出相应处理，保证程序运行。测试如下：
3.测试中出现的问题
A．在此次编写中一个for循环出现的位置发生了错误，但程序仍可运行，可是这样运行出来的数据的顺序会发生错误，解决此类问题的方法是多运行几次，而且应该有这样一个概念运行出来和调试没有错误不一定代表没有了错误。
篇三：实验一约瑟夫问题实验报告
数据结构实验报告
实验名称： 实验一 ——约瑟夫问题
学生姓名： ***
班 级： 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;//头结点给p1
if(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. 程序运行结果
测试主函数流程：
流程图示意图
1、 测试条件：n数量级无限制
2、 测试结论
《约瑟夫问题实验报告》
由：免费论文网互联网用户整理提供,链接地址：
http://m.csmayi.cn/show/119477.html
转载请保留,谢谢!
- 上一篇：换届邀请函
- 下一篇：空军双学活动心得体会文章