约瑟夫环-数据结构报告源代码(源码).doc

实习报告题目:约瑟夫环班级：08052712 姓名: 傅宁捷 学号: 08052210 完成日期: 2010.1.4一、 需求分析1. 本演示程序中，编号为1，2，n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，如此下去，直到所有人全部出列为止。2. 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据（即总人数，m的值，每个人所持的密码），运算结果显示在其后。3. 程序执行的命令包括：（1）构造链表；（2）输入数据；（3）执行报数，储存出列人的序号，删除出列人的信息以及把出列人的密码赋给m；（4）结束。4. 测试数据：m的初始值为20；n7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6，则这正确的出列顺序为6，1，4，7，2，3，5。二、 概要设计为了实现上述操作，应以单向循环链表为存储结构。为此，需要1个抽象数据类型：线性表。1. 线性表的抽象数据类型为：ADT List 数据对象：D=ai|aiElemSet,i=1,2,，n,n0 数据关系：R1=|ai-1,aiD,i=2,3,n 基本操作： InitList( &L) 操作结果：构造一个空的线性表L。ADT List2. 本程序包括三个模块:1） 主程序模块：void main（）初始化；输入数据；函数调用；2） 构造链表并输入每个人信息的模块 -实现线性表的抽象数据类型；3） 运行模块-模拟约瑟夫环依次出列；各模块之间调用关系如下：主程序模块 构造链表并输入每个人信息的模块 运行模块三、 详细设计1. 结点类型和指针类型 typedef struct Node int num; int password; struct Node *next;LNode,*LinkList;/ 结点类型,指针类型Status MakeNode（LinkList &p，Elem Type e）/分配由p指向的数据元素为e、后继为“空”的特点，并返回TRUE，/若分配失败，则返回FALSEP=(LinkType)malloc（sizeof（NodeType）；If（！p）return FALSE；p-data=e；p-next=null；return TRUE；viod Free Node（Link Type &p）/释放p所指结点2. 主函数和其他函数int main()/主函数LinkList L = NULL; LinkList s ,r; int n,i,j,m; /初始化 printf(请输入人数nn); scanf(%d,&n); printf(请输入mn); scanf(%d,&m);printf(请依次输入每个人的密码n); /输入数据 CreatList(L,s,r,n); /创建链表 run(L,n,m); /模拟约瑟夫环并输出 return 0; / mainvoid CreatList(LinkList &L,LinkList &s,LinkList &r,int n)/创建链表int i=1;s=(LNode*)malloc(sizeof(LNode); /分配空间 scanf(%d,&s-password);/输入密码 s-num = i;/序号为i if(L=NULL) L=s; else r-next=s; r=s; /为下次连接做准备 for(i=2;ipassword); s-num = i; r-next=s; /连接到下个结点 r=s; /为下次连接做准备 r-next = L; /闭合 L = r; / void CreatListvoid run(LinkList &L,int n,int m) /模拟约瑟夫环并输出LinkList s,r;int i,j;for( i = 0; i n; i +) for( j = 1;j next; /报数 s = L-next; r = s-next; printf(%dn,s-num); /输出序号 m = s-password; L-next = r; free(s);/删除结点 /run3. 函数的调用关系图反映了演示程序的层次结构:main CreatList run Make Node Free Node四、 调试分析1. 刚开始由于使用头结点,使得程序不符合要求。2. 在写程序时忽略了一些变量参数的标识“&”,使调试程序费时不少。今后应重视确定参数的变量和赋值属性的区分和标识。3. 本程序模块划分比较简单且容易看懂，但头指针赋空不太合理。4. 本实习作业采用数据抽象的设计方法，将程序划分为3个层次，使得设计时思路清晰，实现调试顺利五、 用户手册1. 本