《数据结构c语言》魏刘宏11054126约瑟夫环实验报告

《《数据结构c语言》魏刘宏11054126约瑟夫环实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、杭州电&科牧丈曇计算机学院数据结构课程设计设计题目：约瑟夫环问题专业网络工程班级学号姓名指导教师2012年12月28H一、需求分析1、问题描述：设编号为1,2,n(n>0)个人按顺时针方向围坐一圈，每人持有一个疋整数密码。开始时任意给出一个报数上限m,从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新口1报数；如此下去直到所有人全部出列为止。2、基本要求设计一个程序模拟此过程，给出出列人的编号序列。3、实现提示：可考虑不带头结点的单链表结构，注意空表和非空表的界限。4、测试数据：N

2、=7,七个人的密码依次为3,1,7,2,4,8,4；初始报数上限值m=20«(正确出列顺序为6,1,4,7,2,3,5)二、概要设计链表存储结构的定义：typedefstructLnode{}LNode,*LinkList;UnkListCreatCycleList(intn)创建无头节点的单向循环链表;voidprint(LinkListL)输出琏表；三、详细设计#include#includetypedefintElemType;typedefstructLNode{ElemTypedata;ElemTypeseq;s

3、tructLNode*next;}LNode,*LinkList;LinkListCreatCycleList(intn){〃单向循环链表，无头节点；LinkListLa=(LinkList)malloc(sizeof(LNode));ElemTypea;scanf("%dH,&a);La・>data=a;La・>seq=1;LinkListq=La;for(inti=l;inext=p;scanf(”％d“,&a);p->data=a;p->seq=i+

4、1;p・>next=La;q=p;}returnq;〃指向尾节点，避免对■第一个结点的操作失败;}voidprint(LinkListL){LinkListp=L->next;printf("%d",p->data);p=p・>next;while(p!=L->next)〃适应链表指针指向尾节点的情况{printf("%d",p->data);p=p・>next;}printfC'Xn");}intmain(){printff'约瑟夫环单向循环链表");intm,nj,j;printff"请输入人数:n);scanf(”％d”,&n);printf(“

5、请输入每个人的密码(％d个正整数)：”,n);LinkListL=CreatCycleList(n);LinkListpre=L;//printf(”初始站队为:“);//print(L);printfC'请输入初始报数上限值：H);scanf(”％d“,&m);printf(Hf±i列顺序为：u);j=n;while(j>0){for(i=1;inext;}m=pre->next->data;printf("%d",pre->next->seq);pre->next=pre->next->next;j-；

6、}pnntf("n);return0;}四、调试分析这是我上数据结构课程设计这门课后做的第一个实验，所以开始时1、开始时，我将代表链表的指针指向链表的第一个节点，这样操作第一个节点时会出错；后來，在老师的指点下，将代表指针指向链表的尾节点就成功了。2、本来我将序号和密码存在两个链表中，后来听老师说这样完全没有必耍，纯粹浪费空间，于是就加以改进了。五、用户手册川户点击运行后，依次输入人数n,n个人的密码，初始报数上限m本程序将会计算并输出出队序列。六、测试结果七、验收过程心得体会1、有老师来验收对我们来说是很好的，老师既能督促我们，又能指出我们程序中的错

7、误和不足；2、通过这次实验，我了解到写程序不是一蹴而就的，需要全面思考，反复调试；3、程序并不是功能实现就可以高枕无忧了，还要考虑效率和空间占用。