资源描述:
《循环单链表法实现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问题学会了链表存储结构的使用。并对单链表,循环链表存储数据有了较深的体会。