数据结构实验报告
实验名称：实验一——约瑟夫问题
学生姓名： ***
班级： 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值输入错误"<}
cout<<"请输入m值:";
cin>>m;
if (m<1) //考虑m输入异常的情况{
cout<<"m值输入错误"<}
4）.寻找一定间隔的人，并将其删除
void Joseph::Delete() //删除人员的函数
{
Node *p1,*p2,*p;
int count; //用来计数
p1=front; //头结点给p1
if(m==1)
cout<<"最后一个人的编号为"<else
{cout<<"每次被删除的人为"<for(int i=1; i<=n-1; i++) //共删除n-1个人，循环n-1次
{
count=1;
while(count{
p2=p1; //p2始终为编号为1的那个人
p1=p1->next; //p1向后移
count++;
}
cout<number<<"\t"; //输出被删除的编号
p=p1;
p2->next=p1->next;
p1=p1->next; //p1后移，防止删除后指针悬挂
delete p;
}
cout<cout<<"最后一个人的编号为"<number<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. 程序运行结果
测试主函数流程：
