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

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. 输入输出形式及输入值范围：程序运行后提示用户输入总人数。 输入人数 n 后,程序显示提示信息, 提示用户输入第i 个人的密码,在输入达到预定次数后自动跳出该循环。程序显示提示信息,提示用户输入 初始密码,密码须为正整数且不大于总人数。3 输出形式 提示用户输入初始密码,程序执行结束后会输出相应的出列结点

3、的顺序,亦即其编号。 用户输入完毕后,程序自动运行输出运行结果。4. 测试数据要求：测试数据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=?基本操作：构建循环单链表；/输出函数，输出出列顺序并删除

4、链表中的结点;CreatList(i nt n)/Order( int m,node *1)ADT n ode ;2. ADT的C语言形式说明:typedef struct Nodeint num; /结点的数据域，存放编号;int word; /结点的数据域，存放密码;struct Node *n ext; /结点的指针域，存放指向下一结点的指针;Node;Node *CreatList()void Order(Node *h) /建立循环单项链表;输出出列顺序并删除结点；3. 主程序流程及其模块调用关系1).主程序流程:先提示用户输入相关数据： 总人数，运行循环链表结构体模块， 输入每个人

5、持有的密码 值，创建出新链表，运行输出函数模块，再输入初始密码m值，输出出列序列。(创建循环单链表模块：实现链表的抽象数据类型删除链表结点输出序列模块：实现输出出列顺序)2).模块调用关系：四、详细设计1.元素类型、结点类型和结点指针类型:typedef struct Node /定义一个结构体，包含了每个人的序号和密码int word;int num;struct Node *next;Node; 2、创建单向循环链表类型：Node *CreatList() / 尾插法创建一个单向循环链表 Node *p,*s;Node *h; / 定义头指针 h=(Node*)malloc(sizeof(

6、Node); / 申请动态存储空间 p=h;h-next=NULL; / 初始化链表 printf( 第 1 个人的密码是： ); scanf(%d,&h-word);h-num=1; / 给头指针赋值 for(i=0;inext=NULL) h-next=s; else p-next=s;p=s;printf(”第 d(人的密码是：”,i+2);scanf(%d,&s-word);s-num=i+2; p-next=h;return h;3. 删除链表结点输出函数模块：void Order(Node *h)/输出结果Node *p; p=h;Node *d;while(p-next!=p)i

7、f(mnext;else for(i=1;inext;d=p-next; m=d-word;printf(%d-,d-num);p-next=d-next; / 删除结点 p=p-next;free(d); printf(%dn,p-num);4. 主函数：void main()printf( 试验名称：约瑟夫斯问题求解 n);printf(学号： n);printf(姓名： xxn);printf(=n);time_t rawtime1; struct tm * timeinfo1;time (&rawtime1);timeinfo1 = localtime (&rawtime1); /时间

8、函数；printf ( 程序运行开始 , 当前日期和时间 : %s, asctime(timeinfo1); printf( 请输入总人数： );scanf(%d,&n);h=CreatList();printf( 请输入初始密码： );scanf(%d,&m);if(mn)printf( 初始密码不得大于总人数，请重新输入。 ); scanf(%d,&m);Order(h);elseOrder(h);time_t rawtime2; struct tm * timeinfo2; time (&rawtime2);timeinfo2 = localtime (&rawtime2);printf

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

10、点的个数。所以，reatList()以及 Order(Node*h )算法的时间复杂度都是0(n)。节:学习伏三、计算机ScSDebugTongxrn J ose phusnexe*. I 回聖H名称；约瑟夫斯问题求解佟欣输入数据后界面:C:U5er5AdministratorDesldop17KDebugTcngxinJo5eplius,exei，?S5U 5马刃刃刃当nTTtTP吊 rTR-rnJTEJtrTJlr-Jt7-rT7-OT 匕心 . L IE3 17 2 4 8 4口回 Sg i Tongxin.Josephus,exe 止工作出现了f 可猛.导匙程字呀止正當工件”滴关題程

11、序a专矢诩程序回 却才I f 一“ ” n * F:学习试三计算机实跨Qpbu gT n gxi nJos e phu 5rexe试验名称|约瑟夫斯冋题求解学号：031350103姓名；佟欣密密密密密密密部？直- -Tn -A aaaza/az-4囱玉 程请第第第第第第第请A程坯日 3 17 2 4 8 4-5日co 亠勺 -亠川 亠冃 . 4- * 2 1 3 ; 3 亠冃 _0 当乎曰B習晋沓晉晉疋勺一当t * :乌1马|-:|7牛咼牛帀2Jy AQA zy zw znH znH 5- TflM - tH e 少發呂孑孑屋屋官皆-迭-3 ffTue Hou 032815Tue Nov 03

12、 16：31：3& 2815数是因为头指针的数据域没有赋值。增加了对头指针数据域赋值语句后随机数消失。3. 在调试的开始发现输出顺序有错误，经调试发现是因为查找第m个结点时所用的for循环是从i=1到im-1的，但第二个人密码为 1,没有考虑m2的情况，于是输出出错。改 正方式是增加一个 m2的特殊情况。经运行，输出成功。九、实验收获和感想：约瑟夫问题是我们学习了软件工程原理与应用这门课后第一次上机编写程序,在以前接触 c 语言的时候,我们是没有学过链表的,因此, 以前也没有编写过循环链表的程序。 本学 期的软件工程原理与应用开课后, 我才真正深入学习和理解了链表结构, 通过此次编程对所 学知

13、识有了具体的运用, 使我对链表结构有了更清晰的了解, 从茫然到能正确运用, 感觉收 获非常大。 约瑟夫问题虽说是链表问题中相对来说最简单的一个问题,但我刚开始时却是充满了茫然, 编出来的程序处处报错。 起初,并没有真正理解建立链表的算法,我单纯仿着课 本上的代码照搬上去, 不会正确的运用, 结果自然是大量的错误。 于是我放下急于求成的心 态,认真看书,认真查资料,终于成功地写出了这个约瑟夫问题的程序。当它最终0 error通过且运行正常时, 我的心中充满了激动和满足感,看着自己的作品, 很有成就感。编写完 整的程序最考验人的耐心和细心, 每一个微不足道的小错误都会导致很长时间的排错。 这次 的

14、计算机实践使我在运用中理解了循环链表这部分的知识,为后面的学习和接下来的计算机实践打好了基础,奠定了基石。十、附录源程序文件清单：#include#include#include #define NULL 0定义一个结构体,包含了每个人的序号和密码typedef struct Node / int word;int num;struct Node *next;Node;int i,n,m;Node *h;Node *CreatList() / 尾插法创建一个单向循环链表Node *p,*s;申请动态存储空间Node *h; / 定义头指针 h=(Node*)malloc(sizeof(Node

15、); /p=h;h-next=NULL; / 初始化链表 printf( 第 1 个人的密码是： ); scanf(%d,&h-word);h-num=1; / 给头指针赋值 for(i=0;inext=NULL) h-next=s; else p-next=s;p=s;printf(”第 d(人的密码是：”,i+2);scanf(%d,&s-word);s-num=i+2;p-next=h;return h;void Order(Node *h)/Node *p;p=h;Node *d;while(p-next!=p)if(mnext; elsefor(i=1;inext;输出结果查找第m个

16、结点d=p-next; m=d-word; printf(%d-,d-num);删除结点p-next=d-next; / p=p-next; free(d);printf(%dn,p-num);void main()printf( 试验名称：约瑟夫斯问题求解 n); printf(学号： n);printf(姓名： xxn);printf(=n);time_t rawtime1;struct tm * timeinfo1;time (&rawtime1);timeinfo1 = localtime (&rawtime1); /时间函数；printf ( 程序运行开始 ,当前日期和时间 : %s, asctime(timeinfo1);printf( 请输入总人数： );scanf(%d,&n);h=CreatLis