约瑟夫环课程设计实验报告【约瑟夫环数据结构实验报告】
数据结构实验报告
实习1 线性表及其应用
题目：编制一个演示约瑟夫环的程序
班级：1403011班 姓名：付尧 学号：[1**********] 完成日期：2015.10.25
一．需求分析
1．本程序中，人数n为任意整数，首先输入一个报数上限值整数m，程序应能自动将出列的人所持的密码赋给m，再次作为报数上限，如此循环，直至所有人都出列为止。
2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据（即每个人所持的密码），每个人的序号由程序自动分配。
3．程序执行的命令包括：
（1）构造线性表；（2）输入数据；（3）执行报数，删除出列人的信息以及把出列人的密码赋给m；（4）结束。
4．测试数据
（1）m初值为20，n＝7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6，则正确的出列顺序为6，1，4，7，2，3，5。
二．概要设计
为了实现程序上述功能，应以单向循环链表为存储结构。
1. 基本操作：
void createList()
操作结果：构造单向循环链表，初始化每个人的密码并分配序号。
void Josephus()
初始条件：链表存在。
操作结果：删除出列人的节点并重新报数。
2． 本程序包含三个模块：
（1）主程序模块；
（2）构造链表并输入信息模块；
（3）执行约瑟夫环函数模块；
三．详细设计
1.元素类型，结点类型和指针类型：
struct node{
int num;
int code;
struct node *next;
};
typedef struct node NODE;
NODE *head,*tail;
int m,n;
2．每个模块的分析：
（1）主程序模块：
int main(){
createList();
Josephus(head,m);
return 0;
}
（2）构造链表模块：
void createList(){
//申请头结点空间
//生成头结点
printf("请输入m和n\n");
//读取m，n
printf("请输入每个人的密码\n");
//创建节点并写入密码分配相应序号。
//形成循环链表
}
（3）约瑟夫环函数模块：
void Josephus(NODE *p,int m){
NODE *q;
int count=0; //报数计数器
q=tail; //q为尾结点
p=p->next; //p为第一个数据
while (p->next!=p){
count++; //当循环链表所剩元素大于1时
if (count==m){
//输出当前出列者的序号
//更新m为出列者的密码
//删除p节点
//令p指向下一个数据结点
count=0;
}
else {
//维护p和q到下一个结点
}
}
//打印最后剩下的人的序号
}
四．调试分析
（1）设计过程中对函数结束的条件感到疑惑，经过考虑，采取 p==p->next来判断，非常简捷方便
。
（2）算法的时间复杂度为n^2，空间复杂度为n，时间复杂度偏高，如果遇到数据过多可能会变得很慢。可以将m转化为m除以当前人数的余数，可以减少时间复杂度。
（3）这道题第一眼看觉得十分复杂，但编写中就会发现并不难。调试过程中我对链表的建立和插入删除操作更加熟练，也加深了对算法的认识。
五．用户使用说明
（1）本程序的运行环境为VS2010。
（2）进入演示程序后即显示提示信息：
请输入m和n：
输入m和n
请输入每个人的密码：
输入密码
输入完毕后就进行报数操作：
六．测试结果
当输入m＝20，n＝7，每个人所持密码一次为：3，1，7，2，4，8，4时，则输出正确的出列顺序为：6，1，4，7，2，3，5。
七．附录
#include
#include
struct node{
//建立链表数据类型
int num;
int code;
struct node *next;
};
typedef struct node NODE; //定义NODE为链表数据类型
NODE *head,*tail; //声明头指针，尾指针
int m,n;
void createList(){
//建立链表函数
NODE *p,*q;
int i;
p=new NODE; //申请头结点空间
p->next=NULL;
head=p; //生成头结点
printf("请输入m和n\n");
scanf("%d %d",&m,&n);//读取m，n
printf("请输入每个人的密码\n");
for (i=1;i
q=new NODE; //申请结点空间
q->num=i; //为节点排序
scanf("%d",&q->code); //记录该节点密码
p->next=q; //插入节点P
p=q;
}
tail=p; //保存尾指针
tail->next=head->next; //形成循环链表
}
void Josephus(NODE *p,int m){
//约瑟夫函数
NODE *q;
int count=0; //报数计数器
q=tail; //q为尾结点
p=p->next; //p为第一个数据
while (p->next!=p){
count++; //当循环链表所剩元素大于1时
if (count==m){
printf("%d ",p->num); //输出当前出列者的序号
m=p->code; //更新m为出列者的密码
q->next=p->next; //删除p节点
delete(p);
p=q->next; //令p指向下一个数据结点
count=0;
}
else {
q=p;
p=p->next;
}
}
printf("%d ",p->num); //打印最后剩下的人的序号
}
int main(){
createList();
Josephus(head,m);
return 0;
}