1、数据结构 课程设计 二 班级： 06 计本（ 1） 姓名：魏建平 学号： 20060724035 题目： 严慰敏习题实习一的第二题，约瑟夫环问题：约瑟夫问题的一种描述是：编号为 1，2， n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个整数作为报数上限值 m,从第一个人开始顺时针自 1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开始重新从 1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。 一、 需求分析 1、 利用 单向循环链表存储结构模拟此过程，按照出列的顺序一次打印
2、出每个人的编号。 2、 程序运行后，首先要求用户指定初始 报数上限值，然后读取各人的密码。可设 n30.此题所用的循环链表中不需要“头结点”，应注意空表和非空表的界限。 3、 程序执行的命令：提示用户选择相应操作以及输入相应的人数、每个人的密码和 m值。 4、 测试数据： m 的初值为 20； n =7， 7 个人的密码依次是： 3， 1， 7， 2， 4， 8， 4，出列的顺序为 6， 1， 4， 7， 2， 3， 5。 二、 概要设计 1、 单向循环表的抽象数据类型定义 typedef struct CLNode ElemType data; ElemType i; struct CLNo
3、de *next; CLNode, *CLinkList; 2、 Void main() do 接受命令（ 提示用户 选择功能） ； 接受命令（ 提示 用户输入参数） ； 输入结果； while(“命令” =”退出” ) 3、本程序只有两个模块，调用简单： 三、 详细设 计 1、循环链表结构： typedef struct CLNode ElemType data; ElemType i; struct CLNode *next; CLNode, *CLinkLis 2、初始化循环链表函数： void init_CLinkList(CLinkList *l) (*l)=(CLinkList)m
4、alloc(sizeof(struct CLNode); (*l)-data=-1; (*l)-i = 0; (*l)-next=(*l); 3、清空循环链表函数： void clear_CLinkList(CLinkList l) CLNode *p,*useless; p=l-next; l-next=l; while(p!=l) useless=p; p=p-next; free(useless); 4、创建约瑟夫环表函数： void crt_CLinkList(CLinkList l) int num,n; int j; CLNode *p,*r; clear_CLinkList(l)
5、; r = l; j = 1; printf(“n 输入游戏人数： “); scanf(“%d“, while(j data=num; p-i = j; r-next=p; r=p; j+; r-next=l; 5、显示表中元素函数： void disp_CLinkList(CLinkList l) int row=1; CLNode *p; p = l-next; printf(“n“); while(p!=l) if(row=7) row=1; printf(“n“); printf(“%5d:%-5d|“,p-i,p-data); row+; p=p-next; 6、销毁循环链表函数：
6、void release_CLinkList(CLinkList l)/ clear_CLinkList(l); free(l); 7、元素出圈函数： void game(CLinkList l) int m,k=0; CLNode *p,*pre,*u; p=l; printf(“n 输入 m： “); scanf(“%d“, printf(“n%40snn“,“游戏开始 “); while(p-next!=p) pre=p; p=p-next; if(p=l) pre=p; p=p-next; k+; if(k=m) printf(“%d “,p-i); m=p-data; pre-nex
7、t=p-next; u=p; free(u); p=pre; k=0; printf(“nn%40s“,“游戏结束 “); void exitgame() printf(“nn%40s“,“再见 !“); 8、主函数 ： void main() int select; CLinkList list; init_CLinkList( do printf(“%s%15s%15s%15s%15s“,“nnnnnn“, “1:创建 “, “2:显示 “, “3:游戏 “, “4:退出 “); printf(“nn%33c“, ); select=getche(); switch(select) cas
8、e 1: crt_CLinkList(list); disp_CLinkList(list); break; case 2: disp_CLinkList(list); break; case 3: game(list); break; case 4: exitgame(); break; default: printf(“nWrong select ! Try again. “); /*switch*/ while(select!=4); release_CLinkList(list); getch(); 四、 调试分析 1、 程序使用的是单向循环链表存储结构，所以在指针的使用上容易出现问题，刚开始调试时，就出现 了这个问题，程序老提示内存错误。 2、 由于题目本来就不是很难，所以也没有其它的什么严重的调试问题。 五、 用户手册 1、 本程序的运行环境为 DOS 操作环境，文件名为 Matrix.exe; 2、 本例演示程序简单明了，按菜单提示操作即可。 六、 测试结果
