实习报告约瑟夫环

实习报告题目：约瑟夫环班级：网工一班姓名：孙增鹏学号：13155229完成日期：2014.12.6一、需求分析1.用一个循环链表实现n个人按顺时针排成一圈,每个人看作一个节点，每个节点都是一个结构体类型,包含三个域:编号域(num),密码域(code),指向下一个人的指针域(next)。2．程序开始时由用户任意输入人数n及一个正整数作为报数上限值m,一个正整数作为密码最大值，判断所输密码是否在范围内。然后为依次每一个人指定一个密码。3.初始密码为用户外部输入的密码m,从第一个人开始按顺市针方向自1开始报数.,报道m的时停止,报m的人出列,将他的密码作为新的密码值(m),从他在顺针方向的下一个人开始重新从1报数,如此下去,直至所有的人全部出列为止.4．本程序最终结果为n的人的出列顺序5．测试数据:m的初值为20;n=7(即有7个人)7个人的密码依次为:3.1.7.2.4.8.4首先没的值为20,正确的出列顺序应为6.1.4.7.2.3.5二、概要分析1.为实现上述程序功能，需要一个抽象数据类型：单循环链表1.单循环链表的抽象数据类型定义为：ADTLinkList_CL{数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R={R1},R1={ai-1,ai|ai-1,ai∈D,i=2,3,…,n}基本操作：InitList_CL(LinkList&L)操作结果：构造一个空的线性表L。DestroyList_CL(LinkList&L)操作结果：销毁线性表L。ClearList_CL(LinkList&L)初始条件：线性表L已存在。操作结果：将L重置为空表。ListEmpty_CL(LinkListL)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE。ListLength_CL(LinkListL)初始条件：L已存在。操作结果：返回L中数据元素个数。GetElem_CL(LinkListL,inti,ElemType&e)当第i个元素存在时,其值赋给e并返回OK,否则返回ERRORPriorElem_CL(LinkListL,ElemTypecur_e,ElemType&pre_e)初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。NextElem_CL(LinkListL,ElemTypecur_e,ElemType&next_e)初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继，否则操作失败，next_e无定义。ListInsert_CL(LinkList&L,inti,ElemTypee)操作结果：在L的第i个位置之前插入元素eListDelete_CL(LinkList&L,inti,ElemType&e)操作结果：删除L的第i个元素,并由e返回其值ListTraverse_CL(LinkListL,void(*vi)(ElemType))初始条件:L已存在。操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败}ADTLinkList_CL2.算法的基本思想：约瑟夫环问题中的数据是人所在的位置，而这种数据是存在“第一元素、最后元素”，并且存在“唯一的前驱和后继的”，符合线性表的特点。由于需要模拟约瑟夫环的出列问题，可以采用顺序表来实现线性表，完成出列顺序的输出。核心算法主要分为两步：1、确定需要删除的位置，2、设置并删除该位置。已知报数间隔m，我们可以把当前位置加上m获得需要删除的位置，如果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正（即模拟环状计数）。然后把顺序表中的当前指向位置设置为该位置，继而删掉该位置。反复进行上述确定位置和删除位置的操作，直到顺序表为空。3.程序由三个模块组成：（1）主程序模块（2）单循环链表单元模块-----实现循环链表的抽象数据类型（3）节点结构单元模块------定义循环链表的节点结构各模块间调用关系三、详细设计1.源程序代码typedefstructLNode{//节点类型，指针类型intno,data;//no为编号，data为密码LNode*next;}*LinkList,LNode;intmain(){intm,n,i,j;//m为初始报数值，n为游戏人数LinkListL,p,q;InitLink(L);p=L;printf(约瑟夫环\n);printf(请输入初始报数值：);scanf(%d,&m);while(m=0)//用户行为不符合规范时进行纠错{printf(输入值不符合规范，请重新输入初始报数值：);scanf(%d,&m);}printf(请输入参加游戏人数：);scanf(%d,&n);while(n=0)//用户行为不符合规范时进行纠错{printf(输入值不符合规范，请重新输入参加游戏人数：);scanf(%d,&n);}printf(请输入第一个人的密码：);scanf(%d,&L-data);while(L-data=0)//用户行为不符合规范时进行纠错{printf(输入值不符合规范，请重新输入密码：);scanf(%d,&L-data);}for(i=2;i=n;i++){q=(LinkList)malloc(sizeof(LNode));if(!q)exit(overflow);p-next=q;printf(请输入第%d个人的密码：,i);scanf(%d,&q-data);while(q-data=0)//用户行为不符合规范时进行纠错{printf(输入值不符合规范，请重新输入密码：);scanf(%d,&q-data);}q-no=i;p=p-next;}p-next=L;//闭环printf(出列顺序为：);for(i=1;i=n;i++)//执行循环报数出列{LinkDelete(L,m,j);printf(%d,j);}system(pause);return0;}intInitLink(LinkList&L){//创建空链表L=(LinkList)malloc(sizeof(LNode));if(!L)exit(overflow);L-data=0;L-no=1;L-next=L;}intCreatLink(LinkList&L,intn)//创建joseph环，n为参赛人数{inti;LinkListp=L,q;if(!L)returnerror;printf(请输入第1个人的密码:);scanf(%d,&L-data);while(L-data=0)//纠错判断{printf(输入有误，请重新输入：);scanf(%d,&L-data);}for(i=2;i=n;i++){q=(LinkList)malloc(sizeof(LNode));if(!q)exit(overflow);printf(请输入第%d个人的密码：,i);scanf(%d,&q-data);while(q-data=0)//纠错判断{printf(输入有误，请重新输入：);scanf(%d,&q-data);}q-no=i;p-next=q;p=q;}p-next=L;//闭环returnok;}intDelteLink(LinkList&L,intm,intn)//m为初始报数值，n为参赛人数{inti,j;LinkListp=L,q;if(!L||m=0||n=0)returnerror;printf(出列顺序为：);for(i=1;i=n;i++){for(j=1;jm;j++)//p指向出列者p=p-next;printf(%d,p-no);m=p-data;q=p-next;while(q-next!=p)q=q-next;//q指向出列者的前一位，即p的前驱q-next=p-next;free(p);p=q-next;//p指向下一轮的第一人}returnok;}2.函数调用关系图反映了演示程序的层次结构:mainInitLinkCreatLinkLinkDelete四、调试分析编写程序时，指针运用不熟练，导致调试时错误过多，花费了太多时间，后通过对指针相关知识的进一步了解，改正了程序中的错误，正确运行了程序。数据结构是一门比较抽象的课程，但是也是一门最基础的课程学的过程。在现实生活的也非常广泛通过设计该实验让我更加深刻的掌握了有关链表的知识，同时也认识到了自己在平时学习当中的盲点。通过这次实验发现了自己在数据结构这门功课上存在严重的不足。链表中的指针理解不够，运用不够熟练，常常出现一些莫名其妙的问题，调试费时太多。今后一定会多编程，多思索。在以后的学习过程中还需要不断的完善学习，希望能把数据结构这门课学习的更加深入，更加透彻。五、测试结果m初值为20；n=7,7人密码依次为：3,1,7,2,4,8,4出列顺序：6,1,4,7,2,3,5m初值为10；n=5,5人密码依次为：2,3,4,5,1出列顺序：5,1,3,2,4m初值为15；n=4,7人密码依次为：6,4,3,2出列顺序：3,2,1,4