西安交通大学数据结构上机报告之约瑟夫环问题仿真

《西安交通大学数据结构上机报告之约瑟夫环问题仿真》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1、约瑟夫环问题仿真设编号为1,2,…，n(n>0)个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出一个报数上限m,从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1报数；如此下去直到所有人全部出列为止。(1)问题分析可利用单循环链表解决此问题，建立一个单循环链表，依次录入密码，然后从第一个节点出发，连续略过N-1个结点，将第N个节点从链表中删除，并将第N个结点的密码作为新的m值，接着从下一个结点开始，循环此过程，直至链表为空。(2)数据结构设计此

2、程序实现的方法是建立一个单循环链表，然后对循环链表进行相关操作,模拟整个报数及出列过程。主要为以下三个步骤：1.建立一个具有n个链结点，无头结点的循环链表2.确定第1个报数人的位置3•不断地从链表中删除链结点，直到链表为空首先，建立建立一个单循环链表，将每个人的信息用一个结点存储，包括三个信息，一是他的编号num,二是他持有的密码key,三是指向下一结点的指针。其中编号是一开始按照相邻顺序编号的，密码可以设置，需要输入数值。第一次报数默认为从1号开始报数，需设置报数上限值m,报m的人出列，然后从出列的人后面一个人开始下一轮报数，且报数上限值m变为

3、出列的人持有密码。即笫一次由头指针head开始向后数到笫N-1个结点，删掉第N-1个结点的后继结点，即第N个结点，这时第N-1个结点直接指向第N+1个结点，同时让头指针head也指向第N+1个结点。因为下一轮报数时将从第N+1个结点开始，即还是head指向的结点开始。第二轮报数首先将m值修改为刚刚被删除结点的持有密码，即m=q->key再进行和第一轮报数相同的操作。以后每轮报数如次反复执行，直到所有结点被删除结束。且在此过程中，根据m值的不同，将分别对m二1与m二其他值的情况进行讨论处理。程序主要过程可由以下三个函数实现：1)ERROR()〃判断

4、输入密码是否符合要求.2)structL*creat(intN)//建立动态循环链表(坐成一圈).3)structL^LisDelete(structL*head,intm,intN)//报数为m的退出.（3）算法设计与实现#include#include

5、tN)//建立动态循环链表(坐成一圈).structL*head;structL*pl,*p2;n二0;pl=p2=(structL*)malloc(LEN);printfC请输入第1个人手里的密码:“)；scanf(〃%d〃,&pl->kcy);pl->num=l;head=NULL;while(pl->num<=N){n=n+l;if(n==l)head=pl:elsep2-〉next二pl;p2二pl;pl=(structL*)malloc(LEN);if(n=N){}elseprintf(，z请输入第％d个人手里的密码：〃，n+1);}s

6、canf(〃％d〃,&pl-〉key);pl->num=n+l;}p2->next=head;//尾指针指向头指针.rcturn(head);}structL*LisDelete(structL*head,intm,intN)//报数为m的退出.{structL*p,*q;intj二0,k二0;q二p二head;i二i+1;if(p->next二二head)return(p);if(m=l){while(knext;k=k+l:}printf(〃％i第％(1个人退出.〃，i,q->num);m=q->key;p->nex

7、t=q->next;head二q->next;free(q);}//key二1的处理.else{while(jncxt;p->ncxt=q->ncxt;printf(〃％d第％d个人退出・i,q->num);in二q—〉key;head=p->next;free(q);}//key二其他数的处理.N二N-1;LisDelete(head,m,N);mainOstructL*head;structL*p;printf（〃intm,N;>1^>1^>1^>1^>1^>1^>1^>1^^lzvfx

8、yj、#T^Zr^zt%✓?%#Tx#Tx#Tx✓?%r^yr^Zjx#Tx#T