数据结构 实习报告 题目：1.2 约瑟夫环 一．需求分析 1.设有编号为 1,2，…，n 的 n（n）0）个人按顺时针方向围坐成一圈。从第一个人开 始顺时针报数，报到 m 的人（m 为正整数），令其出列。然后再从下一个开始，重新从 1 顺 时针报数，如此下去，直至所有人全部出列为止。程序依次输出列人的编号顺序。 2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之 后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和在运算结果显示 在其后。 3.测试数据 M 的初值为 20； N=7,7 个人的密码依次为：3,1,7，2，4,8,4 出列顺序为 6,1,4,7,2,3,5 二．概要设计 本程序包含了四个模块，分别为主函数 main 函数，子函数 outlist，enterpwd， Createlinklist 。 三．详细设计 1.链表存储类型 

typedef struct LNode { int num;//定义人编号变量 int pwd;//定义密码变量 struct LNode *next; }LNode; 2.主函数和其它函数 void main() { int m,n;//m 为报数上限，n 为围圈人数 printf("=============约瑟夫环==============\n"); printf("\n 请输入 m,n:"); scanf("%d %d",&m,&n); if(n<=0 || m<0) { printf("\n\n\t\t 输入出错!最后一次重新输入机会~\n\n\n"); printf("请重新输入 m,n:"); scanf("%d %d",&m,&n); if(n<=0 || m<0) { printf("\n\n\t\t 输入出错!请退出!\n\n"); printf("\n\n\t"); } else { Createlinklist(n);//调用链表函数 enterpwd(n);//调用密码输入函数 printf("\n 围圈人的出列顺序依次是：\t"); outlist(m,n);//调用输出函数 printf("\n\n\t"); } } else { Createlinklist(n);//调用链表函数 enterpwd(n);//调用密码输入函数 printf("\n 出队的人依次是:"); outlist(m,n);//调用输出函数 printf("\n\n\t"); } } //建立循环链表函数，并传递 n int Createlinklist(int n) { 

int i; head=( LNode*)malloc(sizeof(LNode)); if(!head) return Error; p=head; for(i=2;i<=n;i++) { pt= (LNode *)malloc(sizeof (LNode)); if(!pt) return Error; p->next=pt; p=pt; } p->next=head; pt=head; return True; } //建立输入密码函数 int enterpwd(int n) { int i,j; printf("\n 请输入密码:"); for(i=1;i<=n;i++) { scanf("%d",&j); pt->num=i; pt->pwd=j; pt=pt->next; } pt=p; return j; } //建立输出函数 int outlist(int m,int n) { int i; int a; for(i=1;i<=n;i++) { for(a=1;anext; } p=pt->next; m=p->pwd; 

printf(" %d",p->num); pt->next=pt->next->next; free(p); } return 0; } 四．调试分析 1．最先没有对超出范围的 m、n 做相应的处理，使得输入错误后仍然继续运行。 添加了 if 语句判断处理； 2.for 循环中的初始值没取正确，以致运行结果出来以致不正确。改正 i 初始值 为 1； 3． 4.未注意题中要求的 m 值在变化，导致漏泄密码函数。添加了密码函数，切在 主函数中调用了密码函数。 五．用户手册 1.本程序的运行环境为 DOS 操作系统，执行文件是 fanshi4.exe. 2.进入演示程序后即显示文本方式的用户界面： 键入 M,N 值（按回车结束输入），界面显示为： 键入密码后按回车，界面会显示出序顺序，界面显示为： 

六．测试结果 1. 输入 M, N 值：20 7 输入对应密码：3,1,7,2,4,8,4 出列顺序：6,1,4,7,2,3,5 七．附录 源程序文件名清单： stdio.H malloc.H fnshi4.C // 主程序