约瑟夫问题Word格式.docx
《约瑟夫问题Word格式.docx》由会员分享，可在线阅读，更多相关《约瑟夫问题Word格式.docx（19页珍藏版）》请在冰点文库上搜索。
操作结果：
构造空链表，若成功就初始化每个人的相关信息
解决约瑟夫问题函数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）
操作结果:
输出报数人的序号
（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"
请重新输入总人数n:
scanf（"
}
请输入出列数:
m）;
请输入起始位置:
k）;
head=create（n）;
jose（head,n,m,k）;
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->
}
p->
next=head;
/*将指针指向头节点，构成循环链表*/
returnhead;
（3）输出报数人序号模块
voidjose（linklist*p,intn,intm,intk）
inti,j;
linklist*q=NULL;
for（i=1;
k;
p=p->
next;
for（j=1;
j<
m-1;
j++）
p=p->
q=p->
next=q->
printf（"
第%3d个出列号为:
%3d\n"
i,q->
data）;
free（q）;
（4）函数调用关系图
main（）;
linklist*create（）;
voidjose（）;
3．完整的程序：
（见源文件）.
typedefstruct
elemtypedata[maxsize];
intlength;
}seqlist;
seqlistl;
initlist（l）;
while（n>
scanf（"
createlist（l,n）;
yusefu（l,n,m,k）;
return0;
（2）顺序表初始化模块
l.length=0;
（3）创建顺序表模块
（4）删除数到的人的编号模块
intj;
if（i<
1||i>
l.length）
return;
for（j=i+1;
=l.length;
j++）
{
l.data[j-2]=l.data[j-1];
/*调整数组数据*/
}
l.length--;
（5）输出数到的人的序号模块
inti=k,number=0;
while（l.length>
1）
number++;
if（number==m）
{
%3d"
l.data[i-1]）;
/*输出查找到的数*/
dele（l,i）;
/*删除该数并调整数组数据*/
number=0;
i=i;
if（i>
i=1;
}
else
i=i+1;
i=1;
l.data[0]）;
/*输出最后一个数据*/
（6）函数调用关系图
main（）
initlist（）
createlist（）
yusefu（）
dele（）
四使用说明、测试分析及结果
1．程序使用说明
（1）本程序的运行环境为VC6.0。
（2）进入演示程序后即显示提示信息：
请输入总人数：
请输入出列数：
请输入起始位置：
2．测试结果
当输入n＝8，m＝4，k=2,时，则输出正确的出列顺序为：
51632487。
3．调试中的错误及解决办法。
刚开始做时并未考虑输入人数为0的情况，经改正可以解决。
4．运行界面
五、实验总结
由于本次问题比较简单，所以花了两个小时编写并调试运行成功，在编写中遇到了数据无法输出的问题，经检查是由于链表指针在指向时发生错误，经改正可以顺利使用，顺序表编写时没有遇到问题，通过这次的编写，对于循环链表以及顺序表的创建及使用有了更深的了解和熟悉。
约瑟夫链表
#include<
stdio.h>
malloc.h>
stdlib.h>
#defineLENsizeof（linklist）
//创建循环链表
//解决约瑟夫问题
约瑟夫顺序表
#definemaxsize30
//建立顺序表
inti;
for（i=0;
n;
l.data[i]=i+1;
l.length=n;
//初始化顺序表
//删除数到的人的编号
//对于约瑟夫的求解
升级会员 