约瑟夫环

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

链表方法：这个就是约瑟夫环问题的实际场景，有一种是要通过输入n,m,k三个正整数，来求出列的序列。这个问题采用的是典型的循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。 p->link=head 手念解决问题的核心步骤：（程序的基本算法） 1.建立一个具有n个链结点，无头结点的循环链表； 2.确定第1个报数人的位置； 3.不断地从链表中删除链结点，直到链表为空。 void JOSEPHUS(int n,int k,int m) //n为总人数，k为第一个开始报数的人，m为出列者喊到的数 { /* p为当前结点 r为辅助结点，指向p的前驱结点 list为头节点*/ LinkList p,r,list/*建立循环链表*/ for(int i=0；i<n；i++) { p=(LinkList)malloc(sizeof(LNode))p->data=iif(list==NULL) list=pelse r->link=pr=p} p->link=list/*使链表循环起来*/ p=list　/*使p指向头节点*/ /*把当前指针移动到第一个报数的人*/ for(i=0i<ki++) { r=p； p=p->link} /*循环地删除队列结点*/ while(p->link!=p) { 毕枯困for(i=0i<m-1i++) { r=pp=p->link败局} r->link=p->linkprintf("被删除的元素：%4d ",p->data)free(p)p=r->link} printf("\n最后被删除的元素是：%4d",P->data)}

这没啥高手的，人称入门题目，也就是说，会做这个基本就可以用C做一些东西了。这是我以前写的，从博客上面搞下来的，你试试看能不能运行，我当时似乎是运行过了的。不过这个不是用链表做的，用数组做的，你结合链表的语法把他改一下就行了，很简单的，就一个结构体而已么，反正基本思路这样就对了。另外对了，当时水平有限还不懂动态分配内存，你去查一下malloc函数的用法，觉得合适可以加进去，你用new命令也可以动态分配内存，具体的可以去看看MSDN，MSDN好东西啊。

#include<stdio.h>

#include<stdlib.h>

void main()

{

int a[100]/*用来放环里的每个人的，人口上限（好像在打魔兽争霸）100，当然可以再改大*/

int n,r,ctor,u/*n是用来循环赋值的，给r个人循环赋1~u，一共r个人，ctor计数器，到了u再重新归1*/

int call(int a[],int real,int u)/*报数函数*/

for(n=0n<=99n++)a[n]=0/*给所有元素赋值为0，这样以后没赋值1~u的就都为0，可以当作不存在*/

printf("/约瑟夫环 JOSEPHUS/\n\n")

printf("输入参与报数的人数\n")

scanf("%d",&r)

printf("输入报数上限\n")

scanf("%d",&u)

ctor=1

for(n=0n<rn++) /*这个循环里给输入的人数都赋值，从1到u，相当于报的数*/

{

*(a+n)=ctor

ctor++

if(ctor>u)ctor=1

}

call(a,r,u)system("pause")/*调用点名函数*/

}

int call(int a[],int real,int u)

{

int n1,i

int *p

p=(a+u-1)

n1=0i=u

for(n1<real-1p++)

{

if(p>(a+real-1))p=a/*如果点名点过了，就接着队伍没有出列的第一个人继续*/

if(*(p)!=0) /*如果扫描的数字不为零，说明这个人还岁毕在队列中，那么看下面*/

{

if(i>u)i=1/*由于是剩下的人继续报数，所以当报到u这个上限时，还是要从新归1*/

if(i==u) /*当到达上限，说明这个人该出列啦，它的位置就填充为0*/

{

*(p)=0n1++/*n1计衡穗算着一共多少人出列，通过n1<real-1,可以留下最后一个人，这是最终目的*/

}

i++

}

}

for(i=0i<reali++) /*从新扫描数组，发现不是0的就输出，到乎拦芹这时候肯定只剩一个数不是0了*/

if(*(a+i)!=0)printf("所剩最后一位原来的呼号是%d\n\n",i+1)

}

写完了

---