数据结构实验报告-约瑟夫问题求解

教育资料教育资料《计算机软件技术基础》

实验报告I—数据结构实验一、约瑟夫斯问题求解一、问题描述.实验题目：编号1,2,....,n的1个人顺时针围坐一圈，每人持有一个密码（正整数）。开始选择一个正整数作为报数上限m，从第一个人开始顺时针自1报数，报到m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，直至所有人全部出列。.基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号。.测试数据：口=7,7个人的密码依次为：3,1,7,2,4,8,4.m初值为6（正确的出列顺序应为6,1,4,77,2,3）。二、需求分析.本程序所能达到的基本可能：该程序基于循环链表来解决约瑟夫问题。用循环链表来模拟口个人围坐一圈，用链表中的每一个结点代表一个人和他所代表的密码。在输入初始密码后m，对该链表进行遍历，直到第m个结点，令该结点的密码值作为新的密码值，后删除该结点。重复上述过程，直至所有的结点被释放空间出列。.输入输出形式及输入值范围：程序运行后提示用户输入总人数。输入人数口后，程序显示提示信息，提示用户输入第i个人的密码，在输入达到预定次数后自动跳出该循环。程序显示提示信息，提示用户输入初始密码，密码须为正整数且不大于总人数。3．输出形式提示用户输入初始密码，程序执行结束后会输出相应的出列结点的顺序，亦即其编号。用户输入完毕后，程序自动运行输出运行结果。.测试数据要求：测试数据n=7,7个人的密码依次为：3,1,7,2,4,8,4。山初值为6（正确的出列顺序应为6，1，4，7，2，3，5)。三、概要设计为了实现上述功能，应用循环链表来模拟该过程，用结构体来存放其相应的编号和密码信息，因此需要循环链表结构体这个抽象数据类型。1．循环链表结构体抽象数据类型定义：ADTNode{数据对象：D={ai,bi,ci|ai£int,bi£int,ci£(Node*),i=1,2...,n,n三0}:数据关系：R=0基本操作：CreatList(intn) //构建循环单链表；Order(intm,node*l) //输出函数，输出出列顺序并删除链表中的结点；}ADTnode；ADT的C语言形式说明：typedefstructNode{intnum; //结点的数据域，存放编号；intword;//结点的数据域，存放密码；structNode*next; //结点的指针域，存放指向下一结点的指针；}Node；Node*CreatList() //建立循环单项链表；voidOrder(Node*h) //输出出列顺序并删除结点；主程序流程及其模块调用关系:).主程序流程：先提示用户输入相关数据：总人数，运行循环链表结构体模块，输入每个人持有的密码值，创建出新链表，运行输出函数模块，再输入初始密码m值，输出出列序列。(创建循环单链表模块：实现链表的抽象数据类型删除链表结点输出序列模块：实现输出出列顺序)).模块调用关系：四、详细设计1.元素类型、结点类型和结点指针类型：typedefstructNode //定义一个结构体，包含了每个人的序号和密码{intword;intnum;structNode*next;}Node;2、创建单向循环链表类型：Node*CreatList() //尾插法创建一个单向循环链表{Node*p,*s;Node*h; //定义头指针h=(Node*)malloc(sizeof(Node)); //申请动态存储空间p=h;h->next=NULL; //初始化链表printf("第1个人的密码是：")；scanf("%d",&h->word);h->num=1; //给头指针赋值for(i=0;i<n-1;i++){s=(Node*)malloc(sizeof(Node));if(h->next==NULL)h->next=s;else p->next=s;p=s;printf("第％4个人的密码是："，i+2);scanf("%d",&s->word);s->num=i+2;}p->next=h;returnh;}.删除链表结点输出函数模块：voidOrder(Node*h) //输出结果{Node*p;p=h;Node*d;while(p->next!=p){if(m<2){p=p->next;}else{for(i=1;i<m-1;i++) //查找第m个结点{p=p->next;}}d=p->next;m=d->word;printf("%d--",d->num);p->next=d->next; //删除结点p=p->next;free(d);}printf("%d\n",p->num);}.主函数：voidmain(){printf("试验名称：约瑟夫斯问题求解\n");printf("学号：\n");printf("姓名：xx'n");printf("=========================================================\n");time_trawtime1;structtm*timeinfo1;time(&rawtime1);timeinfo1=localtime(&rawtime1); //时间函数；printf("程序运行开始,当前日期和时间:%s",asctime(timeinfo1));printf("请输入总人数：")；scanf("%d",&n);h=CreatList();printf("请输入初始密码：")；scanf("%d",&m);if(m>n){printf("初始密码不得大于总人数，请重新输入。")；scanf("%d",&m);Order(h);}else{Order(h);}time_trawtime2;structtm*timeinfo2;time(&rawtime2);timeinfo2=localtime(&rawtime2);printf("程序运行结束,当前日期和时间:%s",asctime(timeinfo2));while(1);}.函数调用关系：主函数调用Node*CreatList()创建循环单向链表以及调用voidOrder(Node*h)进行删除结点及输出序列功能。输出出列序列输出以后，函数调用结束。五、调试分析

岸号：0313算»10的£史上由于链…用的…是单向……表，而链表中按结点二除后运行开修当前日期和时间：TueNOu0316：30：5岸号：0313算»10的输入数据后界面：

5l\Adrnini^trator\DesLtcp\JF^Si4^KDrbug\TcirigxiniJQ3e,phus.eKei叵1317245l\Adrnini^trator\DesLtcp\JF^Si4^KDrbug\TcirigxiniJQ3e,phus.eKei叵131724S467日皆即皆晋晋甘(生--rrp34.3.3.ripr:rF节7.--SM0055Tfl上竽密密密蜜密空艇^AAAAAA^卷1234567^-ll1qngxin.Josephu工exe 上工作出现了t｛可史.m当程序修止正常二归.谙关闭读程序，3关闭程序4调试程序八、遇到的问题和解决方法：回S31.起初程序编写好后显示0error，回S3■'F:、学习七大二'K•管柏实践\Debug\.Tongxir.Josephu&.exe"试验名称：约瑟夫斯问题求解学号：031350103姓名：佟欣程请第第第第第第第请IG-程pP■:rJrTzrp.rzrpr=rrT=rFTJrr=rp程请第第第第第第第请IG-程pP■:rJrTzrp.rzrpr=rrT=rFTJrr=rp2AyAnL^A5?55-.fl55e取醇恺密密密密密密崎7-舒趾△运-4-行0331724*840331.改正上述错误后虽然可以运行但输出产生了一串随机数。经调试程序发现，出现随机数是因为头指针的数据域没有赋值。增加了对头指针数据域赋值语句后随机数消失。.在调试的开始发现输出顺序有错误，经调试发现是因为查找第m个结点时所用的for循环是从i=1到i<m-1的，但第二个人密码为1，没有考虑m<2的情况，于是输出出错。改正方式是增加一个m<2的特殊情况。经运行，输出成功。九、实验收获和感想：约瑟夫问题是我们学习了软件工程原理与应用这门课后第一次上机编写程序，在以前接触c语言的时候，我们是没有学过链表的，因此，以前也没有编写过循环链表的程序。本学期的软件工程原理与应用开课后，我才真正深入学习和理解了链表结构，通过此次编程对所学知识有了具体的运用，使我对链表结构有了更清晰的了解，从茫然到能正确运用，感觉收获非常大。约瑟夫问题虽说是链表问题中相对来说最简单的一个问题，但我刚开始时却是充满了茫然，编出来的程序处处报错。起初，并没有真正理解建立链表的算法，我单纯仿着课本上的代码照搬上去，不会正确的运用，结果自然是大量的错误。于是我放下急于求成的心态，认真看书，认真查资料，终于成功地写出了这个约瑟夫问题的程序。当它最终0error通过且运行正常时，我的心中充满了激动和满足感，看着自己的作品，很有成就感。编写完整的程序最考验人的耐心和细心，每一个微不足道的小错误都会导致很长时间的排错。这次的计算机实践使我在运用中理解了循环链表这部分的知识，为后面的学习和接下来的计算机实践打好了基础，奠定了基石。十、附录源程序文件清单：#include<stdio.h>#include<malloc.h>#include<time.h>#defineNULL0typedefstructNode //定义一个结构体，包含了每个人的序号和密码{intword;intnum;structNode*next;}Node;inti,n,m;Node*h;Node*CreatList() //尾插法创建一个单向循环链表{Node*p,*s;Node*h; //定义头指针h=(Node*)malloc(sizeof(Node)); //申请动态存储空间p=h;h->next=NULL; //初始化链表printf("第1个人的密码是：");scanf("%d",&h->word);h->num=1; //给头指针赋值for(i=0;i<n-1;i++){s=(Node*)malloc(sizeof(Node));if(h->next==NULL)h->next=s;else p->next=s;p=s;printf("第％4个人的密码是："，i+2);scanf("%d",&s->word);s->num=i+2;}p->next=h;returnh;}voidOrder(Node*h) //输出结果{Node*p;p=h;Node*d;while(p->next!=p){if(m<2){p=p->next;}else{for(i=1;i<m-1;i++) //查找第m个结点{p=p->next;))d=p->next;m=d->word;printf("%d--”,d->num);p->next=d->next;〃删除结点p=p->next;free(d);)printf("%d\n",p->num);)voidmain()(printf("试验名称：约瑟夫斯问题求解\n");printf("学号：\n");printf("姓名：xx'n");printf("=========================================================\n");time_trawtime1;structtm*timeinfo1;time(&rawtime1);timeinfo1=localtime(&rawtime1); //时间函数；printf("程序运行开始，当前日期和时间：%s",asctime(timeinfo1));printf("请输入总人数：")；scanf("%d",&n);h=CreatList();printf(