约瑟夫问题.docx
《约瑟夫问题.docx》由会员分享，可在线阅读，更多相关《约瑟夫问题.docx（19页珍藏版）》请在冰点文库上搜索。
约瑟夫问题
《数据结构》实验报告
◎实验题目:
约瑟夫环问题
◎实验目的：
有效掌握循环链表和顺序表的使用，对于两种结构有更深层次的理解。
◎实验内容：
设有N个人围坐一圈，先从某个人开始报数，数到M的人出列，接着从出列的下一个人开始重新报数，数到M的人出列，如此下去，直到所有人都出列为止。
试设计确定他们的出列次序序列的程序。
分别用单向循环链表和顺序表作为存储结构模拟整个过程。
一、需求分析
1．本演示程序中，人数n应为任意的小于等于30的整数，首先应输入一个值赋给初始报数m以及起始位置k，从第k个人开始，程序中会将数到m的人的序号输出，再从输出的人的下一个人开始，再将数到m的人的序号输出，如此循环，直至所有人都出列为止。
2．程序的输出为数到m的人的序号。
3．程序执行的命令包括：
单向循环链表：
（1）创建循环链表
（2）输入总人数、报号数、起始位置的数据（3）执行报数，输出出列人的序号，再进行下一次循环（4）直到所有人都输出结束
顺序表：
（1）创建顺序表
（2）输入总人数、报号数、起始位置的数据（3）执行报数，输出出列人的序号，再进行下一次循环（4）直到所有人都输出结束
4．测试数据
（1）n＝8，m=4,k=2，8人的序号依次为：
12345678，则出列次序为51632487。
二概要设计
单向循环链表：
为了实现上述操作，应以单向循环链表为存储结构。
本程序中创建链表函数linklist*create（intn）
操作结果：
构造空链表，若成功就初始化每个人的相关信息
解决约瑟夫问题函数voidjose（linklist*p,intn,intm,intk）两个子函数
初始条件：
线性链表存在
操作结果：
输出报数人序号，释放指向出列的人的结点，并重新报数。
本程序的主程序包括
（1）主程序模块
（2）链表初始化模块
（3）输出报数人序号模块
各程序模块之间的层次（调用）关系
顺序表：
为了实现上述操作，应以顺序表为存储结构。
创建顺序表函数：
voidcreatelist（seqlist&l,intn）
操作结果：
构造空顺序表，若成功就初始化每个人的相关信息
初始化顺序表函数：
voidinitlist（seqlist&l）
操作结果：
使顺序表初始化
删除数到的人的编号函数：
voiddele（seqlist&l,inti）
操作结果：
将数到的人从顺序表中删除
解决约瑟夫问题函数：
voidyusefu（seqlistl,intn,intm,intk）
操作结果:
输出报数人的序号
本程序的主程序包括
（1）主程序模块
（2）顺序表初始化模块
（3）创建顺序表模块
（4）输出报数人序号模块
（5）删除数到的人的编号模块
各程序模块之间的层次（调用）关系
三详细设计
单向循环链表：
1．元素类型，结点类型和指针类型：
typedefintelemtype;
typedefstructlnode
{
elemtypedata;
structlnode*next;
}linklist;
linklist*p,*q,*head;
2．每个模块的分析：
（1）主程序模块：
intmain（）
{
intk,n=0,m=0;
linklist*head=NULL;
printf（"请输入总人数n:
\n"）;
scanf（"%d",&n）;
while（n>30||n==0）/*设定输入条件*/
{
printf（"错误\n"）;
printf（"请重新输入总人数n:
\n"）;
scanf（"%d",&n）;
}
printf（"请输入出列数:
\n"）;
scanf（"%d",&m）;
printf（"请输入起始位置:
\n"）;
scanf（"%d",&k）;
head=create（n）;
jose（head,n,m,k）;
getchar（）;
getchar（）;
return1;
}
（2）链表初始化模块；
linklist*create（intn）
{
linklist*p,*q,*head;
q=NULL;
head=NULL;
inti=1;
head=（linklist*）malloc（sizeof（linklist））;/*创建头节点*/
head->data=i;
p=head;
for（i=2;i<=n;i++）
{
q=（linklist*）malloc（sizeof（linklist））;
if（q==0）return0;
p->next=q;/*给链表赋值*/
p=q;
p->data=i;
}
p->next=head;/*将指针指向头节点，构成循环链表*/
returnhead;
}
（3）输出报数人序号模块
voidjose（linklist*p,intn,intm,intk）
{
inti,j;
linklist*q=NULL;
for（i=1;i{
p=p->next;
}
for（i=1;i<=n;i++）
{
for（j=1;j{
p=p->next;
}
q=p->next;
p->next=q->next;
p=p->next;
printf（"第%3d个出列号为:
%3d\n",i,q->data）;
free（q）;
}
printf（"\n"）;
}
（4）函数调用关系图
main（）;
linklist*create（）;
voidjose（）;
3．完整的程序：
（见源文件）.
顺序表：
1．元素类型，结点类型和指针类型：
typedefintelemtype;
typedefstruct
{
elemtypedata[maxsize];
intlength;
}seqlist;
2．每个模块的分析：
（1）主程序模块：
intmain（）
{
intk,n=0,m=0;
seqlistl;
initlist（l）;
printf（"请输入总人数n:
\n"）;
scanf（"%d",&n）;
while（n>30||n==0）/*设定输入条件*/
{
printf（"错误\n"）;
printf（"请重新输入总人数n:
\n"）;
scanf（"%d",&n）;
}
printf（"请输入出列数:
\n"）;
scanf（"%d",&m）;
printf（"请输入起始位置:
\n"）;
scanf（"%d",&k）;
createlist（l,n）;
yusefu（l,n,m,k）;
getchar（）;
getchar（）;
return0;
}
（2）顺序表初始化模块
voidinitlist（seqlist&l）
{
l.length=0;
}
（3）创建顺序表模块
voidinitlist（seqlist&l）
{
l.length=0;
}
（4）删除数到的人的编号模块
voiddele（seqlist&l,inti）
{
intj;
if（i<1||i>l.length）
return;
for（j=i+1;j<=l.length;j++）
{
l.data[j-2]=l.data[j-1];/*调整数组数据*/
}
l.length--;
}
（5）输出数到的人的序号模块
voidyusefu（seqlistl,intn,intm,intk）
{
inti=k,number=0;
while（l.length>1）
{
number++;
if（number==m）
{
printf（"%3d",l.data[i-1]）;/*输出查找到的数*/
dele（l,i）;/*删除该数并调整数组数据*/
number=0;
i=i;
if（i>l.length）
i=1;
}
else
{
i=i+1;
if（i>l.length）
i=1;
}
}
printf（"%3d\n",l.data[0]）;/*输出最后一个数据*/
}
（6）函数调用关系图
main（）
initlist（）
createlist（）
yusefu（）
dele（）
3．完整的程序：
（见源文件）.
四使用说明、测试分析及结果
单向循环链表：
1．程序使用说明
（1）本程序的运行环境为VC6.0。
（2）进入演示程序后即显示提示信息：
请输入总人数：
请输入出列数：
请输入起始位置：
2．测试结果
当输入n＝8，m＝4，k=2,时，则输出正确的出列顺序为：
51632487。
3．调试中的错误及解决办法。
刚开始做时并未考虑输入人数为0的情况，经改正可以解决。
4．运行界面
顺序表：
1．程序使用说明
（1）本程序的运行环境为VC6.0。
（2）进入演示程序后即显示提示信息：
请输入总人数：
请输入出列数：
请输入起始位置：
2．测试结果
当输入n＝8，m＝4，k=2,时，则输出正确的出列顺序为：
51632487。
3．调试中的错误及解决办法。
刚开始做时并未考虑输入人数为0的情况，经改正可以解决。
4．运行界面
五、实验总结
由于本次问题比较简单，所以花了两个小时编写并调试运行成功，在编写中遇到了数据无法输出的问题，经检查是由于链表指针在指向时发生错误，经改正可以顺利使用，顺序表编写时没有遇到问题，通过这次的编写，对于循环链表以及顺序表的创建及使用有了更深的了解和熟悉。
约瑟夫链表
#include
#include
#include
#defineLENsizeof（linklist）
typedefintelemtype;
typedefstructlnode
{
elemtypedata;
structlnode*next;
}linklist;
//创建循环链表
linklist*create（intn）
{
linklist*p,*q,*head;
q=NULL;
head=NULL;
inti=1;
head=（linklist*）malloc（sizeof（linklist））;/*创建头节点*/
head->data=i;
p=head;
for（i=2;i<=n;i++）
{
q=（linklist*）malloc（sizeof（linklist））;
if（q==0）return0;
p->next=q;/*给链表赋值*/
p=q;
p->data=i;
}
p->next=head;/*将指针指向头节点，构成循环链表*/
returnhead;
}
//解决约瑟夫问题
voidjose（linklist*p,intn,intm,intk）
{
inti,j;
linklist*q=NULL;
for（i=1;i{
p=p->next;
}
for（i=1;i<=n;i++）
{
for（j=1;j{
p=p->next;
}
q=p->next;
p->next=q->next;
p=p->next;
printf（"第%3d个出列号为:
%3d\n",i,q->data）;
free（q）;
}
printf（"\n"）;
}
intmain（）
{
intk,n=0,m=0;
linklist*head=NULL;
printf（"请输入总人数n:
\n"）;
scanf（"%d",&n）;
while（n>30||n==0）/*设定输入条件*/
{
printf（"错误\n"）;
printf（"请重新输入总人数n:
\n"）;
scanf（"%d",&n）;
}
printf（"请输入出列数:
\n"）;
scanf（"%d",&m）;
printf（"请输入起始位置:
\n"）;
scanf（"%d",&k）;
head=create（n）;
jose（head,n,m,k）;
getchar（）;
getchar（）;
return1;
}
约瑟夫顺序表
#include
#include
#definemaxsize30
typedefintelemtype;
typedefstruct
{
elemtypedata[maxsize];
intlength;
}seqlist;
//建立顺序表
voidcreatelist（seqlist&l,intn）
{
inti;
for（i=0;il.data[i]=i+1;
l.length=n;
}
//初始化顺序表
voidinitlist（seqlist&l）
{
l.length=0;
}
//删除数到的人的编号
voiddele（seqlist&l,inti）
{
intj;
if（i<1||i>l.length）
return;
for（j=i+1;j<=l.length;j++）
{
l.data[j-2]=l.data[j-1];/*调整数组数据*/
}
l.length--;
}
//对于约瑟夫的求解
voidyusefu（seqlistl,intn,intm,intk）
{
inti=k,number=0;
while（l.length>1）
{
number++;
if（number==m）
{
printf（"%3d",l.data[i-1]）;/*输出查找到的数*/
dele（l,i）;/*删除该数并调整数组数据*/
number=0;
i=i;
if（i>l.length）
i=1;
}
else
{
i=i+1;
if（i>l.length）
i=1;
}
}
printf（"%3d\n",l.data[0]）;/*输出最后一个数据*/
}
intmain（）
{
intk,n=0,m=0;
seqlistl;
initlist（l）;
printf（"请输入总人数n:
\n"）;
scanf（"%d",&n）;
while（n>30||n==0）/*设定输入条件*/
{
printf（"错误\n"）;
printf（"请重新输入总人数n:
\n"）;
scanf（"%d",&n）;
}
printf（"请输入出列数:
\n"）;
scanf（"%d",&m）;
printf（"请输入起始位置:
\n"）;
scanf（"%d",&k）;
createlist（l,n）;
yusefu（l,n,m,k）;
getchar（）;
getchar（）;
return0;
}
升级会员 