约瑟夫环实验报告
- 格式：doc
- 大小：99.41 KB
- 文档页数：8
本科学生综合性实验报告
姓名：王慧琳
学号：0144915
专业：管理科学与工程类
班级：信管141
实验项目名称：约瑟夫环
指导老师：李圣宏
开课学期：2015至2016第一学期
完成日期：2015年10月22日
一、需求分析
1、约瑟夫环问题的一种描述是：编号为1，2，...，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。
一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。
报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。
试设计一个程序求出出列顺序。
2、基本要求：利用单向循环链表模拟此过程，按照出列的顺序印出各人的编号。
3、程序执行的命令包括：
1）创建循环链表；2）找到报m数的人，并显示其序号；3）对于出列的人，在循环链表中删除。
4、测试数据：
m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6（正确的出列顺序应为6，1，4，7，2，3，5）。
二、概要设计
1、为显示每个人的序号及密码，对链表中的结点设计应该包含三部分：序号、密码及指针。
如下：
typedef struct LNode
{ int num;//序号
int data;//密码
struct LNode *next;//指针
}LNode,*LinkList;
2、本程序的执行流程为：
对报数上限值m及人数n初始化创建循环链表定位报m数人的前一个人（便于之后的删除），显示出列序号在循环链表中删除出列人
三、详细设计
1、参数类型:
LinkList a1,p,q,L;//a1作为第一个结点
int i,j,k;
2、说明：由于程序不会过于复杂及其他原因，本程序中并未调用子函数，而是全部在主函数中实现
四、调试分析
1、遇到的问题：
开始时，我原本打算编写子函数，用主函数来调用，但是在调试过程中总有一些别的错误干扰，为了节省时间后来我就没有再用子函数，而是全部在主函数中完成。
在创建循环链表时，我没有像书上使用头结点，于是在考虑如何创建链表时，经过好多次的调试和思考，我才慢慢想到要先创建第一个节点来实现。
在实现定位时，一开始我只是照搬书上的函数，根本没有考虑到后续删除结点的问题，于是直
接定位在报m数的结点上，这样是可以显示出列序号，可是程序运行之后结果完全错误。
当时是的确没有考虑到出列的人要删除这回事，于是怎么调试发现都错误，在后来同学的提示下想到要删除，于是推翻前面的想法，发现要定位在报m的人的前一个上。
做删除时遇到了困扰我最多时间的问题，就是删除结点后我居然把删除的结点的下一个结点的序号赋值为删除结点的序号，我一直没发现这个小细节，结果调试中一直显示错误结果，困扰我很久最终才发现并解决。
2、改进之处：
这次的程序没有用到子函数的调用，主要是为了节省时间没想那么多，我想这点可以改进，可以考虑在调用子函数的情况下怎么写这个程序。
3、经验和体会：
首先，细节决定成败是有其合理性的，调试过程最能体会到细节的重要性，一个小细节的错误就会导致程序运行结果出错，所以编程一定要注重细节；其次，我觉得有时候调试过程中遇到问题，而自己不能想明白的时候，可以找老师或者同学请教，站在旁观者的角度或许能更快速地发现问题，进而自己解决问题。
五、测试结果
六、附录
#include <stdio.h>
#include <stdlib.h>
typedef struct LNode
{ int num;//序号
int data;//密码
struct LNode *next;//指针
}LNode,*LinkList;
LinkList a1,p,q,L;//a1作为第一个结点int i,j,k;
void main()
{ int m,n;
printf("请输入m的初始值:");
scanf("%d",&m);
printf("\n请输入人数:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
if(i==1)
{ a1=L=(LinkList)malloc(sizeof(LNode));
a1->num=1;
}
else
{ p=(LinkList)malloc(sizeof(LNode));
p->num=i;
L->next=p;
L=p;
}
printf("\n请输入第%d个人的密码:",i);
scanf("%d",&L->data);
}
L->next=a1;//使表尾指针指向表头，创建循环链表
printf("出列的顺序为:");
for(j=1;j<=n;j++)
{
for(k=1;k<m;k++)
{ L=L->next;
}//找到报m的人的前一个人
m=L->next->data;
printf("%d,",L->next->num);//显示出列人的序号
q=L->next;
L->next=L->next->next;
free(q);//删除出列的人
}
}。
