大数据结构实验报告材料—约瑟夫问题求解

1、计算机软件技术根底实验报告I数据结构实验一、约瑟夫斯问题求解、问题描述1.实验题目：编号1,2,n的n个人顺时针围坐一圈， 每人持有一个密码正整数。开始选择一个正整数作为报数上限m从第一个人开始顺时针自1报数，报到m的人出列，将他的密码作为新的 m值，从他在顺时针方向下一个人开始重新从1报数，直至所有人全部出列。2. 根本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号。3. 测试数据：n=7,7个人的密码依次为：3,1,7,2,4,8,4.m 初值为6正确的出列顺序应为 6,1,4,77,2,3。、需求分析1.本程序所能达到的根本可能:该程序基于循环链表来解决约瑟夫问题

2、。用循环链表来模拟n个人围坐一圈，用链表中的每一个结点代表一个人和他所代表的密码。在输入初始密码后m对该链表进展遍历，直到第m个结点，令该结点的密码值作为新的密码值，后删除该结点。重复上述过程，直至所有的结点被释放空间出列。2.输入输出形式与输入值 X围:程序运行后提示用户输入总人数。输入人数n后，程序显示提示信息， 提示用户输入第i个人的密码，在输入达到预定次数后自动跳出该循环。程序显示提示信息，提示用户输入 初始密码，密码须为正整数且不大于总人数。3 .输出形式提示用户输入初始密码，程序执行完毕后会输出相应的出列结点的顺序，亦即其编号。 用户输入完毕后，程序自动运行输出运行结果。4.测试数

3、据要求：测试数据n=7, 7个人的密码依次为：3, 1, 7, 2, 4, 8, 4。m初值为6正确的出列 顺序应为 6, 1, 4, 7, 2, 3, 5。三、概要设计为了实现上述功能，应用循环链表来模拟该过程，用结构体来存放其相应的编号和密码 信息，因此需要循环链表结构体这个抽象数据类型。1 循环链表结构体抽象数据类型定义：ADT Node数据对象：D=ai,bi,ci|ai int, bi int,ci (Node*),i =1,2.,n,n> 0:数据关系：R=?根本操作:CreatList(int n)/构建循环单链表;Order(i nt m,node *1)/输出函数，输出

4、出列顺序并删除链表中的结点;ADT n ode ;2. ADT的C语言形式说明:typedef struct Nodeint num; /结点的数据域，存放编号;int word; /结点的数据域，存放密码;struct Node *n ext;/结点的指针域，存放指向下一结点的指针;Node;void Order(Node *h)/输出出列顺序并删除结点;2 / 153. 主程序流程与其模块调用关系 ：1.主程序流程：先提示用户输入相关数据：总人数，运行循环链表结构体模块， 输入每个人持有的密码值，创建出新链表，运行输出函数模块，再输入初始密码m值，输出出列序列。创建循环单链表模块：实现链表

5、的抽象数据类型删除链表结点输出序列模块：实现输出出列顺序2.模块调用关系：四、详细设计1. 元素类型、结点类型和结点指针类型：typedef struct Node /定义一个结构体，包含了每个人的序号和密码int word;int num;struct Node *n ext;Node;2、创建单向循环链表类型：Node *CreatList() /尾插法创建一个单向循环链表Node *h;/定义头指针申请动态存储空间h=(Node*)malloc(sizeof(Node); /p=h;h-> next=NULL;/初始化链表prin tf("第1个人的密码是：")

6、;scan f("%d", &h->word);h-> nu m=1;/给头指针赋值for(i=0;i< n-1;i+)s=(Node*)malloc(sizeof(Node);if(h->n ext=NULL) h->n ext=s;elsep->n ext=s;p=s;printf(" 第 d(人的密码是：”,i+2);scan f("%d", &s->word);s->num=i+2;p_>n ext=h;return h;void Order(Node *h)/输出结

7、果p=h;Node *d;while(p->n ext!=p)if(m<2)p=p->n ext;elsefor(i=1;i<m-1;i+) /p=p->n ext;d=p->n ext;m=d->word;prin tf("%d-",d-> nu m);p->n ext=d->n ext;/查找第m个结点删除结点p=p->n ext;free(d);prin tf("%dn",p-> nu m);void mai n()printf("试验名称：约瑟夫斯问题求解n&quo

8、t;printf("学号：n");printf("某某：xxn”)；prin tf("=： time_t rawtimel;struct tm * timei nfol;time (&rawtimel);time infol = localtime (&rawtimel); /printf ("程序运行开始，当前日期和时间printf("请输入总人数：");sca nf("%d",&n);h=CreatList();prin tf("请输入初始密码：”)；sca nf(&

9、quot;%d",&m);if(m>n)时间函数；%s", asctime(time in fol);prin tf("初始密码不得大于总人数，请重新输入。6 / 15");n");scan f("%d", &m);Order(h);else Order(h);time_t rawtime2;struct tm * timei nfo2;time (&rawtime2);time info2 = localtime (&rawtime2);printf ("程序运行完毕，当前日

10、期和时间：%s", asctime(timeinfo2);while(1);主函数调用 Node *CreatList()创建循环单向链表以与调用void Order(Node *h) 进展删除结点与输出序列功能。输出出列序列输出以后，函数调用完毕。五、调试分析1. 程序中将每个人的编号以与密码信息放在链表节点中的数据域，使密码和序号一一对应。主函数中，只需要调用链表的操作来实现循环单向链表的创建以与删除结点和输出操作。2. 算法的时空分析:由于链表采用的都是单向循环链表，而链表中按结点访问的时间性能0n，n是链表中结点的个数。所以，CreatList 丨以与Order(Node*h

11、丨算法的时间复杂度都是0n。7 / 15$ ri 所有算法的空 间复杂度都悬 I »0 1。« 'F ：学习谀三I计算机妻践Deb ugT ongxinJos ephu 2用餐六、使用说明厂花学号=031350103 姓名：佟欣£1悍主耳Tue Mow 33 16 EG 201!i输入数据后界面: , PAD沏I inmi atviDe»nJo)cphu.eKEk冋砌：厂：LJW町1口输焉箪fe貝肖尹埶簿圉Ml岀3LT-Hcl5 .导並聞停止帀工fE.齢询谥春*关创程序4调试挨序eToTongxinjD5ephus.exe八、遇到的问题和解决方法

12、:1. 起初程序编写好后显示0 error ，但不能正常运行，显示如图W11 TIU 一 I *M81MFr I Rf I Lie Nou 032015Tue Ndu 3 16=31:3& 2015E!-口 TI：二丁厦】尹 j 031350103ui叵1盘:佟欣日 3 17 2 4 0 4-5日co w 6 - w o 当 7 环-3呈to 台A百帀帀无帀吊召赛-e 册蜜密密密密密密罐7-聲 -n- « - T n输-1序e£ 呈青驀幕幕幕幕君蓉主月L惶b " F:学习大三、计算 tf虞践DFbu gT ongxi n.J osep hus, exe&q

13、uot;经再次检查程序发现是判断语句"h->n ext=NULL "写成了" h-> next=NULL ",改正后程序可以运行。2. 改正上述错误后虽然可以运行但输出产生了一串随机数。经调试程序发现，出现随机数是因为头指针的数据域没有赋值。增加了对头指针数据域赋值语句后随机数消失。3. 在调试的开始发现输出顺序有错误，经调试发现是因为查找第 m个结点时所用的for循环是从i=1到i<m-1的，但第二个人密码为 1,没有考虑m<2的情况，于是输出出错。改 正方式是增加一个 m<2的特殊情况。经运行，输出成功。九、实验收获和感

14、想：约瑟夫问题是我们学习了软件工程原理与应用这门课后第一次上机编写程序，在以前接触 c语言的时候，我们是没有学过链表的，因此，以前也没有编写过循环链表的程序。本学期 的软件工程原理与应用开课后，我才真正深入学习和理解了链表结构，通过此次编程对所学知识有了具体的运用，使我对链表结构有了更清晰的了解，从茫然到能正确运用，感觉收获非常大。约瑟夫问题虽说是链表问题中相对来说最简单的一个问题，但我刚开始时却是充满了茫然，编出来的程序处处报错。起初，并没有真正理解建立链表的算法，我单纯仿着课本上的代码照搬上去，不会正确的运用，结果自然是大量的错误。于是我放下急于求成的心态，认真看书，认真查资料，终于成功地

15、写出了这个约瑟夫问题的程序。当它最终0 error通过且运行正常时，我的心中充满了激动和满足感，看着自己的作品，很有成就感。编写完整的程序最考验人的耐心和细心，每一个微不足道的小错误都会导致很长时间的排错。这次的计算机实践使我在运用中理解了循环链表这局部的知识，为后面的学习和接下来的计算机实践打好了根底，奠定了基石。十、附录源程序文件清单：#in clude<stdio.h>#in clude<malloc.h>#in clude <time.h>#defi ne NULL 0/定义一个结构体，包含了每个人的序号和密码typedef struct Nodei

16、nt word;int num;struct Node *n ext;Node;int i,n ,m;Node *h;Node *CreatList()/尾插法创建一个单向循环链表Node *p,*s;Node *h;/定义头指针h=(Node*)malloc(sizeof(Node); / 申请动态存储空间 p=h;h->next=NULL;/初始化链表printf("第1个人的密码是：");scan f("%d",&h->word);h->num=1;/给头指针赋值for(i=0;i< n_1;i+)s=(Node*)

17、malloc(sizeof(Node);if(h->n ext=NULL)h->n ext=s;elsep->n ext=s;P=s;printf("第%d个人的密码是：”,i+2);scan f("%d", &s->word);s->num=i+2;p_>n ext=h;return h;void Order(Node *h)/ 输出结果Node *p;p=h;Node *d;while(p-> next!=p)if(m<2)p=p->n ext;elsefor(i=1;i<m-1;i+)/ 查

18、找第 m 个结点p=p->n ext;d=p->n ext;m=d->word;prin tf("%d-",d-> nu m);p-> next=d-> next;/ 删除结点p=p->n ext;free(d);prin tf("%dn",p-> num);void mai n（）n");n");printf（"试验名称：约瑟夫斯问题求解printf（"学号：n”）;printf（"某某：xxn"）;printf(”time_t rawtimel;struct tm * timei nfol;time (&rawtimel);timeinfol = localtime (&rawtimel);/ 时间函数；printf ("程序运行开始，当前日期和时间：s", asctime(timeinfol);printf("请输入总人数：");scan f("%d", &n);h=CreatList();printf("请输入初始密码：”)；