循环单链表法实现Josephus问题

《循环单链表法实现Josephus问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、向量法求解Josephus问题智能一班林潇2220101468一．实验题目描述问题可描述如下：设有个人围成一个环，现从第个人开始报数，数到第的人出列，然后从出列的下一个人从新开始报数，数到第的人又出列，如此重复，直至所有人均出列为止。求这些人出列的顺序。二．实验目的熟练掌握线性表的链表实现基本操作。三．实现功能以循环单链表为存储结构，求解问题。四．算法步骤编写一个独立的函数模块求解问题，该函数仅通过参数与外界进行数据交换，不使用其它非局部变量，实现方案应具有良好的健壮性。另编写一个主函数作为驱动，在主函数中处理数据的输入与输出。五．程序结构描述程序主要包括一个驱动功能的主

2、函数，包括要排列数组元素的输入，开始报数的位置，所报数字的输入。还有一个独立函数模块来实现Josephus问题，主函数通过调用该函数来实现元素的出列，并将出列元素按顺序重新存入数组，并将出列元素按顺序输出。六．程序代码#defineN10#include#includetypedefstructLNode{//建立节点类型intmessage;structLNode*next;}LNode,*LinkList;voidJosephus(LinkListL,ints,intm,intn,inte,inta[]);voidmain(){i

3、nti,s,m,e;inta[10];printf("请输入Josephus环的元素");//输入组成Josephus环的元素for(i=0;i<10;i++)scanf("%d",&a[i]);printf("请输入开始报数位置及所报数字");//输入开始报数位置及所报数字scanf("%d%d",&s,&m);LinkListL;//建立单循环连的头结点L=(LinkList)malloc(sizeof(LNode));L->message=a[0];L->next=NULL;Josephus(L,s,m,N,e,a);}voidJosephus(LinkListL,

4、ints,intm,intn,inte,inta[]){LinkListp,q;inti,j;//将组成Josephus环的元素储存到单链中for(i=n-1;i>0;i--){p=(LinkList)malloc(sizeof(LNode));p->message=a[i];p->next=L->next;L->next=p;}LinkListH;H=L;for(i=0;inext;H->next=L;//尾部节点的指针指向头结点p=L;for(i=1;inext;//找到开始报数位置i=1;//利用循环将元素输出wh

5、ile(p->next!=p->next->next){for(j=1;jnext;q=p->next;p->next=q->next;e=q->message;free(q);//释放被输出元素的节点printf("第%d个出列的元素为%d",i,e);p=p->next;i++;}printf("第%d个出列的元素为%d",10,p->message);}七．测试数组及结果测试数组为一个长度为10的整形数组，存储元素为1-10是个整数。开始报数位置为数组的第二个元素，所报数字为3。测试结果截屏如下：八．实验总结与体验本次实验

6、比较成功，通过解决Josephus问题学会了链表存储结构的使用。并对单链表，循环链表存储数据有了较深的体会。