欢迎来到天天文库
浏览记录
ID:55036041
大小:31.50 KB
页数:3页
时间:2020-04-26
《数据结构-约瑟夫问题-代码实例.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、一、问题描述:约瑟夫问题的一种描述是:编号为1,2,……,n点的n个人按顺时针方向围坐一个圈,每人持有一个密码。一开始选一个正整数作为报数上限值m,从第一个人开始从顺时针方向自1开始报数,报到m时停止。报到m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始从新从1报数,如此下去,直达所有人出列。基本要求:利用单向循环链表存储结构模拟此过程,按照出列的顺序输出各人的编号。测试数据:m的初始值为20;n=7,7个人的密码依次是3,1,7,2,4,8,4,首先m的值为6(正确的出列顺序为6,1,4,7,2,
2、3,5)二、程序设计的基本思想,原理和算法描述:采用结构体定义单链表,格式为:structLnode{intnumber;intpassword;structLnode*next;}Lnode,*p,*q,*head;其中number是人的排列序号,password是各人所持有的密码值,next是节点指针。Lnode是节点变量,p、q是节点,head是头指针。程序的代码:定义变量n,i,m,j输入人的数量nIfn<=0或n>30重新输入n值当0password尾指针指向头指
3、针,形成循环链表输入初始报数上限值m当1<=j<=n时循环找出报m的节点p输出报m节点的编号p->number将p->password赋给m值删除此节点结束三、源程序及注释:#include#includestructLnode/*定义链表*/{intnumber;intpassword;structLnode*next;}Lnode,*p,*q,*head;intmain(void){intn;/*n个人*/inti;intm;/*初始报数上限值*/intj;printf("
4、tt用单向循环链表测试约瑟夫环问题----刘辉学号::");printf("请测试人的数量:");/*输入测试人的数量*/scanf("%d",&n);loop:if(n<=0
5、
6、n>30)/*检验n是否满足要求,如不满足重新输入n值*/{printf("niserorr!");printf("pleaseenterthenumberofpeopleagainn:");scanf("%d",&n);gotoloop;}for(i=1;i<=n;i++)/*建立单链表*/{if(i==1){hea
7、d=p=(structLnode*)malloc(sizeof(structLnode));}else{q=(structLnode*)malloc(sizeof(structLnode));p->next=q;p=q;}printf("pleaseenterthe%dpeople'spassword:",i);/*输入每个人所持有的密码值*/scanf("%d",&(p->password));p->number=i;}p->next=head;/*形成循环链表*/p=head;printf("pleaseenter
8、thenumberm:");scanf("%d",&m);printf("Thepasswordis:");for(j=1;j<=n;j++)/*输出各人的编号*/{for(i=1;inext);m=p->password;printf("%d",p->number);p->number=p->next->number;/*删除报m的节点*/p->password=p->next->password;q=p->next;p->next=p->next->next;free(q);}print
9、f("");}四、运行输出结果:测试的数据:n为5,m的初值为7,密码:1、2、3、4、5,正确的结果应为:2、4、5、1、3。
此文档下载收益归作者所有