实习报告1（约瑟夫环）
课程设计报告
课程名称： 《数据结构》课程设计
课程设计题目： 约瑟夫环 姓 名：
院系： 专 业： 年 级： 学 号： 指导教师：
倪哲 计算机学院 软件工程 大三 08052319 赵葆华
实习报告1（约瑟夫环）
一、需求分析
1． 本演示程序中，利用单向循环链表存储结构存储约瑟夫环数据（即n个人的
编号和密码），模拟约瑟夫环的显示过程，按照出列的顺序印出各人的编号。 2． 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示\"提示信
息\"之后，由用户在键盘上输入演示程序中需要输入的数据，以“回车符”为结束标志。相应的输入数据和运算结果显示在其后。 3． 程序执行的命令包括：
1)构造单向循环链表；2） 按照出列的顺序印出各人的编号。 4． 测试数据
m 的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6（正确的出列顺序为6，1，4，7，2，1，3，5）。 二、概要设计
1．单向循环链表的抽象数据类型定义为： ADT List｛
数据对象：D=｛ai | ai∈正整数，I=1，2，......，n,n≥0｝
数据关系：R1=｛< ai-1，ai > |，ai-1，ai∈D,I=1，2，......，n｝ 基本操作： Init List(&L)
操作结果：构造一个空的线性表L。 List Insert(&L,i,e)
初始条件：线性表L已存在，1≤i≤List Length(L)+1.
操作结果：在L中第i个位置之前插入新的数据无素e，L长度加1。 List Delete(&L,i,&e)
初始条件：线性表L存在非空，1≤i≤List Length(L).
操作结果：删除L的第i个元素，并用e返回其值，L长度减1。 2． 程序包含三个模块： 1）主程序模块： Void main（）{
初始化； do {
接受命令； 处理命令； }while（“命令”=“退出”）； }
2）有序表单元模块——实现有序表的抽象数据类型。 3）输出函数模块——有序表的输出 三、详细设计
1、 元素类型，结点类型和指针类型。
typedef struct LNode //定义结构体
实习报告1（约瑟夫环）
{
int number; //number用来存储人的序号， int password; //password用来存储人的密码
struct LNode *next; };
lnode,*linklist; //定义结点 2、创建循环链表函数及创建输入密码函数
void In(int n,LinkList &La) {
LinkList Lb,Lc; int pw,i=1;
printf(\"请输入密码：\"); scanf(\"%d\
La=(LinkList)malloc(sizeof(LNode)); La->number=i; La->password=pw; La->next=La; Lb=La; Lc=La;
for(i=2;i<=n;i++) {
scanf(\"%d/n\
Lb=(LinkList)malloc(sizeof(LNode)); Lb->number=i; Lb->password=pw; Lc->next=Lb; Lc=Lb;
Lb->next=La; } }
创建输出函数
void Out(int n,int m,LinkList &La) {
LinkList Lb,Lc; int i,j; Lb=La; Lc=La;
实习报告1（约瑟夫环）
for(i=1;inext;printf(\"正确的出列顺序应为:\"); for(i=1;i<=n;i++) {
for(j=1;jnext; Lc=Lb->next;Lb->next=Lc->next;
printf(\"%d\\ m=Lc->password; free(Lc); } }
main主函数
void main() {
LinkList La; int n,m;
printf(\"请输入密码的初值:\"); scanf(\"%d\
printf(\"请输入人数：\"); scanf(\"%d\In(n,La); Out(n,m,La); }
四、调试分析
1、由于对循环链表的理解不够，在几次课上的讲解以及作业的练习之后，
开始慢慢了解，也慢慢可以理清约瑟夫环的基本思路 2、忽视字母大小写，以及变量名的定义
3、经常弄混链表中的指针，将其所指位置混淆，以致在头结点的问题上徘
徊多时，今后应注意这方面的问题。
4、本实习作业采用数据抽象的程序设计方法，将程序分为三个层次：主函
数，创建循环链表函数及输入密码函数，输出链表函数，使得设计时思路清晰，实现时调试顺利，各模块具有较好的可重用性。
5、在不同系统上的测试成功，表明程序具有一定的通用性，可避免因系统
的问题导致的调试问题的出现。
6、因为要求用单向链表实现，因而实现起来比较麻烦，很多人第一感觉是
可以应用数组，也比较简单，起初用过数组做法，可以从中体会问题的
实习报告1（约瑟夫环）
主要思想。
五、用户手册
1、 本程序运行环境为WindowsXP Professional以及Windows Vista。 2、 可以直接执行.exe文件，进入演示程序后即显示文本方式的用户界面，并带有提示信息。
3、 输入报数上m及人数n后，再输入各人的密码。 4、 执行相应运算和显示结果。 六、测试结果
1、运行程序后，初界面：
2、输入密码的初值后：
3、输入总人数后
4、输入各人的密码后，最后的运行结果
