约瑟夫环内含源代码

数据构造课程设计实验学校：江西农业大学班级：软件1115班姓名：朱利斌学号：1976课程：数据构造课程设计指导教师：彭玉莹实验一：约瑟夫问题问题简述：约瑟夫环是一种数学的应用问题：已知n个人（以编号1，2，3...n分别表达）围坐在一张圆桌周边。从编号为k的人开始报数，数到m的那个人出列；他的下一种人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周边的人全部出列。约瑟夫问题是由古罗马出名的史学家Josephus提出的问题演变而来，因此普通称为Josephus问题。改善约瑟夫问题的描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈,每人有一种密码Ki（整数），留作其出圈后应报到Ki后出圈。报数办法采用顺时针报数和逆时针报数交替进行，初始密码可任意拟定。求最后剩余的人的编号。这个就是约瑟夫环问题的实际场景，后来老师规定我们对规定中的每人所持有的密码以及第一次的报数上限值要用随机数产生。因此约瑟夫环问题如果采用双向循环链表则能较好的解决。循环链表的数据构造，就是将一种链表的尾元素指针指向队首元素。p->link=head解决问题的核心环节：先建立一种含有n个链结点，无头结点的循环链表，然后拟定第一种报数人的位置，并不停地从链表中删除链结点，直到链表为空。一、题目内容及规定【问题描述】编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一种密码（正整数）。一开始任选一种正整数作为报数上限值m,从第一种仍开始顺时针方向自1开始次序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一种人开始重新从1报数，如此下去，直到全部人全部出列为止。设计一种程序来求出出列次序。【规定】运用单向循环链表存储构造模拟此过程，按照出列的次序输出各个人的编号。2）

掌握线性表的基本操作，如插入、删除、检索等在链式存储构造上的运算。二、

实验环境（硬/软件规定）：WindowsXP+三、概要设计运用单向循环链表存储构造模拟此过程，由于循环链表最后一种结点的指针域指向头结点，整个链表形成一人环，刚好和题中的“n个人按照顺时针方向围坐一圈，每个人只有一种密码（正整数）”内容规定一致，并且，循环链表中任一结点出发均可找到表中其它结点，运用这一优点可较容易地找出报数的人及下一种报数的人，最后按照出列的次序用一种for语句实现。循环链表的存储构造以下：structJoseph实践约瑟夫问题时的核心是用两个指针把一种移动的，一种指向要删除的节点，另外要注意保存头指针。第一步是建立一种循环的单向链表。第二步是运用指针遍历链表同时计数到第m个时将其删除。此时指针指向不变。其格式以下：voidoutput(structJoseph*head)//输出出列状况{inti,j=1;structJoseph*p1,*p2;p1=p2=head;//p1p2都指向头指针for(i=1;i<m;i++)p1=p1->next;//从第M个人开始报数，因此p1指针依次后移，指向第m个人while(n>0){for(i=1;i<s;i++){p2=p1;p1=p1->next;//开始报数，报到s前p1、p2依次后移}printf("第%d个出列的人是:%d\n",j,p1->num);p2->next=p1->next;p1=p2->next;//此人出列，将p1->next赋给p2->next，将p1所指向的结点删掉n--;//人数减少1j++;//出列人数加1}}2创立单循环链表创立一种空单循环链表，双向循环链表和每个结点涉及两个域:元素域和指针域。形成单循环链表的原理：定义三个指针变量H,r,s,三指针开始全部指向头结点，在插入操作开始后，H不变仍指向头结点，s指针在插入过程中始终指向新插入的节点，而r指针紧随其后，用于将新插入的节点和前一种节点连接起来，最后通过r指向头指针H，来完毕环的操作。核心代码实现以下：if(H==NULL){H=s，r=H;}//从链表的第一种节点插入else{r->next=s，r=s;//r后移}//链表的其它节点插入结束for循环后结成环的操作：r->next=H;/*生成循环单链表*/returnH;3查找并删除节点每当结点计数到某一结点时，将他的前驱结点接到他的后继结点，然后将他的密码值cipher赋给计数变量，再将此结点删除。如此循环下去，直到最后变为空的单循环链表为止。函数通过代码：p=H;pre=p;p=p->next;pre->next=p->next;p=pre->next;来删除现在的那个结点q，通过循环来一次次删除现在的结点，直到链表中剩余最后一种结点。五、程序清单/*运行环境VC*/#include<>#include<>#include<>#defineLENsizeof(structJoseph)structJoseph//定义joseph{intnum;structJoseph*next;};intn,s,m;voidprint(structJoseph*head)//打印链对中的信息{structJoseph*p;//p指针p=head;//将p指向头指针printf("%d个人的代号以下:\n",n);do{printf("%d",p->num);p=p->next;}while(p!=head);//依次输入每个人的代号printf("\n");}voidoutput(structJoseph*head)//输出出列状况{inti,j=1;structJoseph*p1,*p2;p1=p2=head;//p1p2都指向头指针for(i=1;i<m;i++)p1=p1->next;//从第M个人开始报数，因此p1指针依次后移，指向第m个人while(n>0){for(i=1;i<s;i++){p2=p1;p1=p1->next;//开始报数，报到s前p1、p2依次后移}printf("第%d个出列的人是:%d\n",j,p1->num);p2->next=p1->next;p1=p2->next;//此人出列，将p1->next赋给p2->next，将p1所指向的结点删掉n--;//人数减少1j++;//出列人数加1}}structJoseph*create()//建立链队列{inti;structJoseph*head;structJoseph*p1,*p2;printf("请输入总人数(输入0退出程序):\n");scanf("%d",&n);if(n==0)exit(0);//退出for(i=1;i<=n;i++){p1=(structJoseph*)malloc(LEN);p1->num=i;if(i==1)head=p1;elsep2->next=p1;p2=p1;}p2->next=head;//将整个链队构成一种环形print(head);printf("请输入从第几个人开始报数:\n");scanf("%d",&m);printf("数到第几个人出列:\n");scanf("%d",&s);returnhead;}main(){structJoseph*head;while(1){head=create();output(head);system("pause");system("cls");}}六、运行成果七、实验心得在约瑟夫问题中，着重训练的是链表的应用，特别是链表中结点的删除、检索等。由于单向链表等线性表的操作基本思想是一致的，因此通过对单向链表的练习来加深对线性表的理解。在本实验中，需要解决的问题的重点是如何找到要删除的结点。因此，我首先考虑解决这个问题，即应用循环语句来找到满足条件的结点，我选用了if循环语句。然后应用指针实现查找过程。在搞清出这些之后，在建立一种单向链表即形成程序。在通过调试改正某些细节即可。在编辑的过程中，将所学的知