约瑟夫环问题

约瑟夫环问题 《数据结构》实验一 实验内容: 约瑟夫环问题 学号:20095101249 姓名: 程方洁 一、上机实验的问题和要求(需求分析): [ 题目 ] 设有n个人围坐一圈，现从某个人开始报数，数到m的人出列，接着从出列的下一个人开始重新报数，数到m的人又出列，如此下去，直到所有人都出列为止。试设计一个程序求出出列顺序。要求利用单向循环链存储结构模拟此过程，按照出列的顺序打印出各人的编号。n=8,m=3 二、程序设计的基本思想，原理和算法描述: 用不带头结点的循环链表解决该问题，设有n个人围坐在一起，现从某个人开始报数，数到m的人出列，接着从下一个人开始报数，数到m的人又出列，如此下去，直到所有的人全部出列。输出出队列的人的序号。 三、调试和运行程序过程中产生的问题及采取的: 调试的时候没有正确定义各个参数的类型和正确书写输出函数。 四、源程序及注释 [ 源程序 ] 源程序:1.cpp #include #include #define NULL 0 typedef struct LNode{ int data; struct LNode *next; }LNode, *LinkList; void main( ) { //不带头结点的循环链表解决约瑟夫环问题. //设有n个人围坐一圈，现从某个人开始报数，数到m的人出列， //接着从出列的下一个人开始重新报数，数到m的人又出列，如此下去， //直到所有人都出列为止。求最后一个出队列的人的序号。 int N,k,i; LinkList L,p; printf("Please input the Number and the order:\n"); scanf("%d,%d",&N,&k);//N代表总人数,k代表出列号. L=(LinkList)malloc(sizeof(LNode)); L->data=1; L->next=L;//首先生成第一个结点 for(i=N;i>1;i--) { p=(LinkList)malloc(sizeof(LNode)); p->data=i; p->next=L->next; L->next=p; }//建立循链表 p=L; while(p->next!=p) { for(i=1;i!=k-1;i++) p=p->next; printf("%d ",p->next->data); p->next=p->next->next; p=p->next; } printf("\n"); printf("The last one is:%d\n",p->data); } 五、运行结果 输入环中元素的个数为: 8 运行结果:1 2 3 4 5 6 7 8 删除元素的位置为:3 运行结果为: 3 6 1 5 2 8 4 7