约瑟夫环数据结构课程设计.docx

《约瑟夫环数据结构课程设计.docx》由会员分享，可在线阅读，更多相关《约瑟夫环数据结构课程设计.docx（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、约瑟夫环数据结构课程设计 约瑟夫环问题设计与实现 摘要 约瑟夫问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。改进约瑟夫问题的描述是：编号为1，2，n的n 个人按顺时针方向围坐一圈, 每人有一个密码m（整数），留作其出圈后应报到m后出圈，依次类推，即可求出出列顺序。因此约瑟夫环问题如果采用循环链表则能很好的解决。循环链表的数据结构，就是将一个链表的最后一个节点指针指向第一个结点。出列时，根据密码找到对应的人，打印其编号，将其密码赋值给m后，释放节点，形成新的约瑟夫环，直到所有人出列结束。 关键字：约瑟夫环；循环链表；出列顺序；释放节点； Desi

2、gn and Realization of the Joseph ring ABSTRACT The Joseph problem is the evolution proposed by ancient Rome 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 a

3、round a circle, each with a password of M (integer), keep the ring should be reported after the M ring, and 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 lis

4、t of the points to the first node. Out, according to the code to find the corresponding person, print the number, 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

5、nodes; 目录 1需求分析 (1) 1.1课题内容 (1) 1.2要求 (1) 2概要设计 (1) 3详细设计 (2) 3.1程序中的数据类型 (2) 3.2函数运行过程详解 (3) 4设计和调试分析 (6) 4.1调试中遇到的问题 (6) 4.2经验和体会 (7) 5用户使用说明 (7) 6测试数据和测试结果 (8) 参考文献 (10) 1 需求分析 1.1课题内容： （1）本演示程序中，人数n应为任意的，首先应输入一个值赋给初始报数上限m，程序应能自动保存出列人的序号和将出列的人所持的密码赋给m，再次作为报数上限，如此循环，直至所有人都出列为止。 （2）演示程序以用户和计算机的对话方式

6、执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据（即每个人所持的密码），每个人的序号由程序自动分配。 （3）程序执行的命令包括： （1）构造链表；（2）输入数据；（3）执行报数，储存出列人的序号，删除出列人的信息以及把出列人的密码赋给m；（4）结束。 （4）测试数据 n7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6，则这正确的出列顺序为6，1，4，7，2，3，5。 1.2 要求： （1）源程序要有适当的注释，使程序容易阅读； （2）函数功能要划分好（结构化程序设计）； (3) 可以增加新功能模块； (4) 要提供程序测试方案，程序一定要经得起测试，也要能

7、运行起来， 不能运行的程序是没有价值的。 2 概要设计 该系统采用C语言开发，主要方法是选择合适的程序结构，灵活使用三种程序设计基本结构、函数等编写程序。 21 本程序包含三个模块，对应关系图为： （1）主程序模块； （2）构造链表并输入每个人信息模块； （3）每个人依序出列打印出列顺序并释放结点模块； 2.2 为了实现上述操作，应以单向循环链表为存储结构。 2.3 基本操作： Data_InPut( ) 操作结果：构造链表，初始化每个人的相关信息 Data_OutPut( ) 操作结果：释放指向出列的人的结点，并重新报数 3 详细设计 3.1程序中定义的数据类型 typedef struct

8、 LNode ElemType num; /各人的编号 ElemType data; /各人的密码 struct LNode *next; /指向下一个节点的指针 LNode,*LinkList; 程序中定义了一个节点的结构体，每次新分配一个节点内存，即为新增一个人，data为人的密码，num是人的编号。 3.2 每个函数的过程详解 3.2.1void main()； 函数原型：void main() 函数源程序： void main() LinkList L=NULL; int m,n=30; /m为报数上限，n为人的个数 int i=0; /常用变量 printf(t约瑟夫环问题nn);

9、printf(请输入m的值（要求m30|ndata); /依次输入每个人的密码 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个节点，并录入每个人对应编号，通过scanf函数录入每个人的密码，因为创建了一个节点。并将新创建的节点

10、连到链表尾端，形成一个单链表。最后创建的一个节点是多余的，需要删 除，所以通过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

11、;inext; /指针后移 printf(第%d个出列%dn,i+1,R-num); /输出所找人的编号 b=R-data; /刷新b值，将所找到人的密码赋值给b Q-next=R-next; /将出列人的前一个节点和后一个节点连接形成新环 L=R-next; free(R); /释放已出列结点 函数功能及实现：该函数首先定义了指针变量R，P，Q，L方便对节点的操作。通过for循环以确定所有人都会被出列，在while循环中，b的值最初是给定的报数上限，通过自减操作找到所要出列的那个人，打印其编号，将其密码重新赋值给b，并删除代表该人的节点，并释放该节点，形成一个新的约瑟夫环， 进行下一次循环，

12、最终所有人出列后完成for循环，打印出列顺序，返回大主函数。 4 设计和调试分析 4.1 调试中遇到的问题 （1）在用scanf函数给普通变量输入数据时，在变量名前漏写地址运算符&。 如:scanf(dd, x, y); （2）输入数据时的数据形式与要求不符。 用scanf函数输入数据时，必须注意要与scanf语句中的对应形式匹配。 如：scanf(d,d,&x, &y); 若按以下形式输入数据： 2 4 是不合法。数据2和4之间应当有逗号。 （3）输入、输出时的数据类型与所用格式说明符不匹配。 例如有以下说明语句： int x=1; char y=a; 则运行时执行语句 printf(x=c

13、, y=dn, x, y); 将给出与原意不符的结果：(在TURBO C 2.0 下运行) （4）对于复合语句，忘记加花括号。 例如： i=1; a=0; while (i=10) a+=i; i+; printf(a=dn,a);的上限值是数组定义时元素个数减1。（5）对指针的操作要小心谨慎，比如初始化和赋值等问题值得加以注意。 4.2 经验和体会 通过这次数据结构课程设计，我感受最深的就是对于循环链表的使用，可以 说对循环链表有了比以前更进一步的认识，以前只是一知半解的，如果只给个题目自己根本不能把程序完整地编写出来，所以这次课程设计最大的收获就在于对循环链表有了一定的理解，包括其中的一系

14、列操作，如建立一个循环链表，删除链表中的一个结点，增加一个结点等。 在这次课程设计过程中需要我们一边设计一边探索，这这个过程当中我发现自己在数据结构方面知识掌握不够深入，对一些基本概念不能很好的理解，对一些数据结构不能够熟练的进行上机实现，这是自己比较薄弱的。学好基础知识是理论付诸实践的前提，这样理论和实践才能充分地结合起来。在以后的学习中，我还要努力改正，充分利用上机实验的机会提高自己。在程序的输入的时候，因为自己对键盘的不熟练，代码又很多很繁琐，常常会产生放弃的念头，从中我也感受到只有坚持到底，胜利才会出现。 在调试程序的时候我也有所体会，虽然约瑟夫环问题不是很难，但调试的时候还是会出现很

15、多错误，因此我们不能认为容易就不认真对待。在以后的学习中，要能不断发现问题，提出问题，解决问题，从不足之处出发，在不断学习中提高自己。 5 用户使用说明 （1）根据正确的提示安装软件。 （2）Intel486以上系列、AMD K6 以上系列等PC台式机和便携式电脑都可运行。 (3) 打开该程序系统，根据提示首先输入初始报数上限和约瑟夫环的人数，然后输入各个人的密码，完成输入后，按回车键即可显示约瑟夫环内各人的出列顺序。 6 测试数据和测试结果 （1）进入系统界面 系统提示输入m的值，即报数上限，为测试所给数据，将m的值设为20。（2）输入约瑟夫环的人数 输入人数后，若输入人数大于30则提示输入错误，重新输入，这里为检测所给数据，设定人数为7。 （3）输入7人的密码