约瑟夫环问题可惜设计

《约瑟夫环问题可惜设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、山东科技大学学生课程设计1.设计1约瑟夫环问题一、需求分析1、利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号，只适用于一个案例。具体目标包括：（1）实现单循环链表的初始化；（2）理解约瑟夫环的定义，用循环找到每次报数人的序号；（3）从单循环链表中删除节点，并判断链表空与非空的临界条件。2、构造一个含有n个元素的单向循环链表3、程序中，先输入总人数PN与初始密码SN，再输入输入n个正整数，作为这n个人的密码，接下来初始密码m。4、测试数据PN=5SN=2，N个人的密码依次=14648。出列为：21354。二、概要设计1、函

2、数功能在main函数中实现voidmain(void){intPN,SN,i;LinkListL;printf("请输入总人数PN,和出示密码SN：");第46页山东科技大学学生课程设计scanf("%d%d",&PN,&SN);inta[N];a[0]=SN;//将a[0]保存为初始密码printf("请输入%d个人各自所持的密码:",PN);for(i=1;i

3、eldata(&L,PN,a);}2、程序包括两部分（1）结点类型（2）main函数实现约瑟夫环三、详细设计1、结点类型typedefstructNode{intdata;//将这一圈人按从1~PN贴上序号structNode*next;}Node,*LinkList;LinkListhead;第46页山东科技大学学生课程设计2、构建一个单循环链表算法voidCreatLinkList(LinkList*L,intPN){Node*p,*q;inti;(*L)=(LinkList)malloc(sizeof(Node));p=(*L);p

4、->data=1;for(i=2;i<=PN;i++){q=(LinkList)malloc(sizeof(Node));q->data=i;p->next=q;p=q;}p->next=(*L);}流程图：第46页山东科技大学学生课程设计结束p->next=headp=qP->next=p2head=qi==1q指向申请空间i<=np指向申请空间2、程序主模块实现算法从头结点开始，根据报数上限找到下一个出列人的序号，并读出该人的密码作为新的报数上限，从此节点的下一个节点开始进行新的查找。取每次将要删除的人的密码，用于下次报数的上限.通过

5、指针依次删除出列人相应的节点，直到该链表中无节点，退出循环。四、运行结果及分析1.调试分析第46页山东科技大学学生课程设计（1）进入程序后按提示输入程序初始数据回车后即可得到结果，输出结果表示依次出列人的序号，程序结束。若输入过程中输入有误，程序直接结束。算法时间复杂度正比于2n加上所有人的密码和。（2）结果分析：对一般数据与边界数据能输出正确结果；对错误数据能做出合适的反应。2.测试结果输入值不符合条件是：第46页山东科技大学学生课程设计五、总结1.本程序比较简单，只有一个main函数，功能在main函数中实现，程序有待优化。本次实验主

6、要考察了对单循环链表的应用。2.调试过程中，由于指针使用不当多次出现错误，对指针的设计还需要熟练掌握。通过本次实验设计，巩固了演循环链表的知识。附：主要源代码#include#include#defineN100typedefstructNode{intdata;//将这一圈人按从1~PN贴上序号structNode*next;}Node,*LinkList;voidCreatLinkList(LinkList*L,intPN){Node*p,*q;inti;(*L)=(LinkList)malloc

7、(sizeof(Node));p=(*L);p->data=1;for(i=2;i<=PN;i++){第46页山东科技大学学生课程设计q=(LinkList)malloc(sizeof(Node));q->data=i;p->next=q;p=q;}p->next=(*L);}voiddeldata(LinkList*L,intPN,inta[]){Node*p,*q;intk;intj=1;inti=0;//取每次将要删除的人的密码，用于下次报数的上限p=(*L);for(;PN>=1;PN--){k=1;while(k!=a[i]){

8、p=p->next;k++;}printf("第%d个出列的人的序号是%d，其密码是%d.",j,第46页山东科技大学学生课程设计p->data,a[j]);j++;i=p->data;p