C语言 数据结构 实验3——约瑟夫问题

《C语言 数据结构 实验3——约瑟夫问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Fly制作版权所有云南大学数学与统计学实验教学中心实验报告课程名称：数据结构与算法学期：20012-2013学年第二学期成绩：指导教师：XXX学生姓名：XXX学生学号：201019100XX实验名称：线性表的应用实验要求：选作实验学时：2学时实验编号：3实验日期：第7-8周完成日期：2012-4-2学院：数学与统计学院专业：信息与计算科学年级：2010级一、实验目的在实验一的基础上，用线性链表解决一个应用问题——约瑟夫问题（Joseph）的求解。二、实验内容[问题描述]：编号为1，2，┄┄，n的n个人，按顺时针方向围坐在一圈，每人持有一个密码（正整数），一开始，任

2、选一个正整数作为报数的上线值m，从第一个人开始，顺时针方向自1开始报数，报到m时停止报数，第m的人出列，并将他的密码作为新的m值，从他开始顺时针方向的下一个人开始重新从1起报数，如此下去，直到所有的人全部出列为止。试设计一个C程序，求出列顺序。三、实验环境WindowsXP程序设计语言C四、实验过程1．实验要求：[基本要求]：利用单循环链表存贮结构摸拟此过程，按照出列的顺序打印出出列序号及各个人的编号。[测试数据]：设n=20，且m的值固定，即每个人的密码一致。[实现提示]：（1）对m的值应从键盘临时输出，程序测试时可临时改变m的值（m=3,m=2）以验证程序的输

3、出结果。（2）可以利用实习1的最后一题的循环链表（为方便，不设头结点）作为本题开始的循环链表。（3）请注意，空表及非空表的判断。[附加要求]：按上述“问题描述”中的要求，即每个人的密码m不同，实现约瑟夫问题(Joseph)的求解。输出时应输出序号、出列人的编号、出列人的密码值。2．实验设计流程图（以下内容请同学认真填写）第6页共6页Fly制作版权所有第6页共6页Fly制作版权所有3．程序设计代码及解释：（必须给出必要的程序注解，以保证可读性）#include#include#defineNULL0typedefstructNo

4、de{intnum;intCipher;structNode*next;}Node,*LinkList;Node*creat(LinkListLA,intn){//构建链表LinkListp1,p2;inti,k=0;p1=p2=(LinkList)malloc(sizeof(Node));printf("PleaseInputtheCipherofperson:");scanf("%d",&p1->Cipher);for(i=n;i>0;--i){k=k+1;if(k==1){p1->num=k;LA=p1;}elsep2->next=p1;p2=p1;if

5、(i-1==0)break;else{p1=(LinkList)malloc(sizeof(Node));p1->num=k+1;scanf("%d",&p1->Cipher);}}p2->next=LA;returnLA;}voidJosephProblem(LinkListL,intn,intm){LinkListp1,p2;intcount=0;intcountPerson=0;p1=L;第6页共6页Fly制作版权所有p2=L;while(p2->next!=L){p2=p1;p1=p1->next;}while(countPerson

6、;if(count==m){printf("%2d%4d",p1->num,p1->Cipher);//打印出列密码，出列序号printf("");m=p1->Cipher;p2->next=p1->next;//删除出列节点p1=p1->next;count=0;//计数器归零countPerson+=1;}else{p2=p1;//p2为前躯，p1=p1->next;//p1转向后继}}}main(){//主函数LinkListLA,head;intn,m;printf("PleaseInputthenumofperson:");scanf("%d",

7、&n);//输入有几个人来参与LA=(LinkList)malloc(sizeof(Node));head=creat(LA,n);//构建链表printf("PleaseInputtherecord:");scanf("%d",&m);//输入初始密码printf("TheresultofJosephProblem:");printf("numCipher");JosephProblem(head,n,m);//解决约瑟夫环的问题system("pause");system("cls");}4．实验（程序运行）结果的粘贴：（请粘贴你的程序运行结果）第

8、6页共6页