《数据结构课程设计》约瑟夫环实习报告

《《数据结构课程设计》约瑟夫环实习报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实习报告一约瑟夫环班级:08052311姓名:钱子霞学号:08051103一、需求分析实习要求是利用单向循环链表储存结构模拟约瑟夫问题的过程，按照出列顺序印出各人的编号。从这个实习要求可以看出要实现约瑟夫环模拟过程,我们需要建立一个循环链表，建完链表后需要一个函数模拟实现该过程,输岀岀列序列。二、概要设计1.写一个函数根据题目要求建立一个循环链表CreatList_L(LinkList&L,intn)初始条疋头指针L已存在，人数n己输入操作结果:建成没有头结点的循环链表L,L的头结点为最后一个申请空间的节点。2.

2、写一个函数输岀查看建成后的链表Show(LinkList&L,intn)初始条件：循环链表L已存在，人数n已输入操作结果：输岀链表L3.写一个函数来模拟约瑟夫问题的过程Joseph(LinkList&L,intn’intm)初始条件：循环链表L已存在，人数n已输入，第一个密码m已输入操作结果：输岀约瑟夫模拟过程的岀列顺序三、详细设计1.voidCreatList_L(LinkList&L,intn){〃构造和初始化循环链表L=(LinkList)malloc(sizeof(LNode));printfC*请按顺序

3、输入n个人的密码:”)；L->next=L;//当只有一个节点吋，该节点指向自己，形成循环链表。L・>num=l;seanf("%d&L->data);LinkListp,q;q=L；for(inti=2;i<二n;i++){p=(LinkList)malloc(sizeof(LNode));scanf(n%d",&p->data);p・>num=i;p・>next=q・>next;q_>next=p;q=p;}L=p；}代码思路：这个函数的功能是建立循环链表，建立过程是通过在先建立一个单节点的循环链表即L->n

4、ext=L;然后中请个节点依次插入已有的循环链表中。最后将第n个节点的地址赋给链表头指针。即最后一行L=p;这样的设计是为了下面移动删除节点。具体在后面会讲到。2・voidShow(LinkList&L,intn){printfC*建成的循环链表为：“)LinkListp=L;inti=0;while(inum);p=p->next;}printfC'Xn");}代码思路：这个函数就是输出一个链表，比较简单，主要是为了调试用的。3.voidJoseph(LinkLis

5、t&L,intn’intm){intcode,manLeft;LinkListp=L,q;inti,j；manLeft=n;code=m%manLeft;讦(code==0)code=manLeft;printf("tB列顺序如下所示：");while(manLeft>l){j=0;while(jnext;j++；}code=p->data%(manLeft・l);if(!code)code=manLeft-1;printf("%d",p->num);q・>next=p・>ne

6、xt;free(p);P=q；manLeft-;printf("%d舄p・>num);printfCXn**);代码思路:每次通过前一个出列的人的密码去查找下一个将出列的人。这里的处理不是每次就找到要岀列的节点，而是找到要出列的节点的前驱，这个是为了删除后通过该前驱与出列节点后继相连就可以重新建成循环链表。因为每次都是要找到前驱，所以将每次删除的节点的前驱赋给链表头指针比较方便，那样处理的话，每次移动的次数跟密码上的数值一样。代码优化:这个代码里的优化就是移动的次数不等于取出的密码的数值，而是每次都是密码对剩余的

7、人数取模，因为实际的移动就是取模后的值，而其他的移动只是一次次在循环链表中循环数数而已。这样的话就可以提高出列效率四、测试结果如下图:C".•E:目己专业学习住傷夫环・exe・输入人数於5输入m初值汉请按顺序输入口个人的密码汉2345建成的循环链表为：12345出列顺序如下所示：12435输入人数口汐输入m初值：20请按顺序输入口个人的密码：31建成的循环链表为：12345出列顺序如下所示：61472