《约瑟夫环数据结构课程设计.docx》由会员分享，可在线阅读，更多相关《约瑟夫环数据结构课程设计.docx（18页珍藏版）》请在金锄头文库上搜索。
1、 约瑟夫环问题设计与实现 CHANGSHA UNIVERSITY OF SCIENCE & TECHNOLOGY 课程设计（论文）题目： 约瑟夫环 学生姓名：江元学 号：201153100121班 级: 信息与计算科学11-01班所在院部: 数学与计算科学学院指导教师：龚红仿 2013 年 6 月约瑟夫环学生姓名：江元学 号：201153100121班 级：信计11-01班指导教师：龚红仿 完成日期: 2013年6月27日约瑟夫环问题设计与实现摘要约瑟夫问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。改进约瑟夫问题的描述是：编号为1，2，n的n个
2、人按顺时针方向围坐一圈, 每人有一个密码m（整数），留作其出圈后应报到m后出圈，依次类推，即可求出出列顺序。因此约瑟夫环问题如果采用循环链表则能很好的解决。循环链表的数据结构，就是将一个链表的最后一个节点指针指向第一个结点。出列时，根据密码找到对应的人，打印其编号，将其密码赋值给m后，释放节点，形成新的约瑟夫环，直到所有人出列结束。关键字：约瑟夫环；循环链表；出列顺序；释放节点；Design and Realization of the Joseph ringABSTRACTThe Joseph problem is the evolution proposed by ancient Rome
3、 famous historian Josephus and come, so often referred to as the Josephus problem. Improvement of Joseph problem description is: No. 1, 2,. N, n individuals according to a clockwise direction around a circle, each with a password of M (integer), keep the ring should be reported after the M ring, and
4、 so on, we can calculate the column order. So Joseph circle if using circular linked list can be very good solution. Circulation list data structure, is the last of a node is a pointer to a list of the points to the first node. Out, according to the code to find the corresponding person, print the n
5、umber, the password is assigned to m, release the node, the formation of Joseph ring, until all the people out of the end.Keywords:Joseph ring; circular linked list; the column order release nodes;目录1需求分析11.1课题内容11.2要求12概要设计13详细设计23.1程序中的数据类型23.2函数运行过程详解34设计和调试分析64.1 调试中遇到的问题64.2 经验和体会75用户使用说明76测试数据
6、和测试结果8参考文献101 需求分析1.1课题内容：（1）本演示程序中，人数n应为任意的，首先应输入一个值赋给初始报数上限m，程序应能自动保存出列人的序号和将出列的人所持的密码赋给m，再次作为报数上限，如此循环，直至所有人都出列为止。（2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据（即每个人所持的密码），每个人的序号由程序自动分配。（3）程序执行的命令包括：（1）构造链表；（2）输入数据；（3）执行报数，储存出列人的序号，删除出列人的信息以及把出列人的密码赋给m；（4）结束。（4）测试数据n7，7个人的密码依次为：3，1，7，2，4，
7、8，4，首先m值为6，则这正确的出列顺序为6，1，4，7，2，3，5。1.2 要求：（1）源程序要有适当的注释，使程序容易阅读；（2）函数功能要划分好（结构化程序设计）；(3) 可以增加新功能模块；(4) 要提供程序测试方案，程序一定要经得起测试，也要能运行起来，不能运行的程序是没有价值的。 2 概要设计 该系统采用C语言开发，主要方法是选择合适的程序结构，灵活使用三种程序设计基本结构、函数等编写程序。21 本程序包含三个模块，对应关系图为：（1） 主程序模块；（2） 构造链表并输入每个人信息模块；（3） 每个人依序出列打印出列顺序并释放结点模块；调用函数Data_InPut创建链表并输入每个
8、人的编号和密码调用函数Data_OutPut按特定的顺序让每个人出列，并释放已出列的节点结束开始执行主函数的内容，开始程序2.2 为了实现上述操作，应以单向循环链表为存储结构。数据next数据next数据next数据next2.3 基本操作：Data_InPut( )操作结果：构造链表，初始化每个人的相关信息Data_OutPut( )操作结果：释放指向出列的人的结点，并重新报数3 详细设计3.1程序中定义的数据类型typedef struct LNodeElemType num;/各人的编号ElemType data;/各人的密码struct LNode *next;/指向下一个节点的指针L
9、Node,*LinkList;程序中定义了一个节点的结构体，每次新分配一个节点内存，即为新增一个人，data为人的密码，num是人的编号。3.2 每个函数的过程详解3.2.1 void main()；函数原型：void main()函数源程序：void main()LinkList L=NULL;int m,n=30;/m为报数上限，n为人的个数int i=0;/常用变量printf(t约瑟夫环问题nn);printf(请输入m的值（要求m30|n0)/人数异常处理printf(请输入小于30的正整数：);scanf(%d,&n);printf(n);/换行/调用数据录入函数Data_InPu
10、t(L,n);/调用数据输出函数Data_OutPut(L,n,m);函数功能及实现：此为主函数，先输入m和n的值，即确定初始上限m和人数n，并对人数进行防出错处理，之后调用函数Data_InPut(L,n)对n个人编号和输入对应密码，再调用函数Data_OutPut(L,n,m)按照要求对各个人依次出列，打印相关信息到屏幕上。3.2.2 LinkList Data_InPut(LinkList &L,int k); 函数原型：LinkList Data_InPut(LinkList &L,int k);函数源程序：LinkList Data_InPut(LinkList &L,int k)L
11、inkList R,P,Q;L=(LinkList)malloc(sizeof(LNode);/创建一个节点R=L;for(int i=0;idata);/依次输入每个人的密码R-num=i+1;/输入每个人的编号P=(LinkList)malloc(sizeof(LNode);/创建新节点P-next=NULL;Q=R;R-next=P;/连接新的节点R=P;free(P);/释放无用结点Q-next=L;return (L);/返回循环链表函数功能及实现：先定义结构体指针变量R，P，Q，L，创建一个新节点赋值给指针L，并将L赋值给R，通过for循环再创建n个节点，并录入每个人对应编号，通过
12、scanf函数录入每个人的密码，因为创建了一个节点。并将新创建的节点连到链表尾端，形成一个单链表。最后创建的一个节点是多余的，需要删除，所以通过free函数释放最后一个节点。之后将单链表的尾指针指向第一个节点，形成一个单循链表。最后通过return函数返回循环链表，继续执行主函数。3.2.3 void Data_OutPut(LinkList &L,int k,int b)；函数原型：void Data_OutPut(LinkList &L,int k,int b)；函数原程序：void Data_OutPut(LinkList &L,int k,int b)printf(n出列顺序为:n);LinkList R,P,Q;for(int i=0;inext;/指针后移printf(第%d个出列%dn,i+1,R-num);/输出所找人的编号b=R-data;/刷新b值，将所找到人的密码赋值给bQ-next=R-next;/将出列人
