用循环链表解决约瑟夫环问题

C语⾔⽤循环单链表实现约瑟夫环⽤循环单链表实现约瑟夫环（c语⾔），供⼤家参考，具体内容如下源代码如下，采⽤Dev编译通过，成功运⾏，默认数到三出局。

主函数：main.c⽂件#include <stdio.h>#include "head.h"#include "1.h"int main(){Linklist L;int n;printf("请输⼊约瑟夫环中的⼈数：");scanf("%d",&n);Createlist(L,n);printf("创建的约瑟夫环为：\n");Listtrave(L,n);printf("依次出局的结果为：\n");Solution(L,n);return 0;}head.h⽂件：#include "1.h"#include <stdio.h>#include <stdlib.h>typedef int Elemtype;typedef struct LNode{Elemtype data;struct LNode *next;}LNode,*Linklist;void Createlist(Linklist &L,int n){Linklist p,tail;L = (Linklist)malloc(sizeof(LNode));L->next = L;//先使其循环p = L;p->data = 1;//创建⾸节点之后就先给⾸节点赋值，使得后⾯节点赋值的操作能够循环tail = L;for(int i = 2;i <= n;i++){p = (Linklist)malloc(sizeof(LNode));p->data = i;p->next = L;tail->next = p;tail = p;}printf("已⽣成⼀个长度为%d的约瑟夫环！\n",n);}void Listtrave(Linklist L,int n)//遍历函数{Linklist p;p = L;for(int i = 1;i <= n;i++){printf("%3d",p->data);p = p->next;}printf("\n");}int Solution(Linklist L,int n){Linklist p,s;p = L,s = L;int count = 1;while(L){if(count != 3){count++;p = p->next;//进⾏不等于3时的移位}else{Linklist q;q = p;//⽤q保存p所指的位置，⽅便进⾏节点的删除if(s->next->data == s->data)//当只有⼀个元素的时候{printf("%3d\n",s->data);free(s);return OK;}else//当有两个及两个以上的元素的时候{count = 1;//先将count重置为1printf("%3d",p->data);//再打印出出局的值while(s->next != p){s = s->next;//将s移位到p的前驱节点处}p = p->next;//使p指向⾃⼰的下⼀个节点s->next = p;//进⾏删除free(q);}}}}1.h⽂件：#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2运⾏结果：以上就是本⽂的全部内容，希望对⼤家的学习有所帮助，也希望⼤家多多⽀持。

C语言实现约瑟夫环问题------单向循环链表实现问题描述：有n个人围成一圈进行报数游戏，从第一个人开始报到m的人出圈，接下来有从下一个人开始，。

一次这样往复，直到最后一个人也出圈，求他们的出圈顺序？（例如8个人，凡报3的人出圈，则他们出圈顺序是3 ，6, 1，，5 ，2 ，8，4 ，7）#include<stdio.h>#include<stdlib.h>typedef struct node{int value;struct node *next;}NODE;//*********************建立循环链表(尾插法建立)***********//NODE *createlink(int number){NODE *head=NULL,*p=NULL,*q=NULL;int i=1;head=(struct node*)malloc(sizeof(struct node)); //***建立第一个节点***//head->value=i;p=head;for(i=2;i<=number;i++) //***建立剩下的number-1节点****//{q=(struct node*)malloc(sizeof(struct node));if(q==0) return 0;p->next=q;p=q;p->value=i;}p->next=head;return head;}//*****************建立约瑟夫环********************// void jose(NODE *p,int number,int n){int i,j,g=0;NODE *q=NULL;for(i=1;i<=number;i++){for(j=1;j<n-1;j++){p=p->next;}q=p->next; //***q用来记录要删除的节点*****//p->next=q->next; //****删去q节点******//p=p->next;printf("第%3d个出圈号是：%3d\n",i,q->value);free(q);}printf("\n");// p->next=NULL; 此表达式不能出现在此处，最后一个节点删除后就不存在了}//***********************主函数*************************//int main( ){int number=0;int n=0;printf("请输入总人数number和出拳编号n:\n");scanf("%d",&number);scanf("%d",&n);NODE *head=NULL;head=createlink(number);jose(head,number,n);system("PAUSE");return 1;}。

一问题描述1 题目内容：约瑟夫(Joseph)问题的一种描述是:编号为1,2,..., n的n 个人按顺时针方向围坐一圈, 每人持有一个密码(正整数)。

一开始选任一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。

报m的人出列，将它的密码作为新的m值。

试设计一个程序求出出列顺序。

2 基本要求：利用单项循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

3 测试数据：m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4（正确的出列顺序应为6，1，4，7，2，3，5）。

二需求分析程序运行后，首先要求用户指定初始报数上限值，然后读取个人的密码。

输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。

输出形式：建立一个输出函数，将正确的输出序列三概要设计利用单项循环链表存储结构模拟此过程1 循环链表的抽象数据类型循环链表是单链表的一种变化形式，把单链表的最后一个节点的next指针指向第一个节点，整个链表就形成了一个环。

2 循环链表的基本操作（仅列出用在本程序的）creat(n)操作结果：构造一个长度为n的无头节点的循环链表,并返回指向最后一个节点的指针find(m,s)初始条件：循环链表存在操作结果：找到当前元素（即s）后面第m个元素print(&m,&n,&s)初始条件：循环链表存在操作结果：从s中删除约舍夫问题中下一个被删除的元素，并将此元素显示在屏幕上3 本程序包括4个模块：主程序模块；创建循环链表模块；找节点模块；删节点模块；各模块调用关系如下图所示：4 约舍夫问题的伪码算法void main( ){输入参与的人数；输入第一个密码；创建无头节点的循环链表；输出第一个出列元素；输出剩余出列元素；}四详细设计1 实现概要设计的数据类型typedef struct LNode{int data;int num;struct LNode *next;}LNode,*linklist; //无头节点的循环链表的节点类型2 每个子函数的算法linklist creat(int n){/*构造一个长度为n的无头节点的循环链表,并返回指向最后一个节点的指针*/linklist head,s; //head为头节点标记s为链表中节点int i;s=head=(linklist)malloc(sizeof(LNode)); //创建头节点for(i=1;i<n;i++) //建立循环链表{s->data=i;printf("num%d: ",i);scanf("%d",&(s->num));/*输入第i个人的密码*/while(s->num<=0){/*如果输入的s->num小于等于0,要求重新输入*/ printf("请重新输入\nnum%d: ",i);scanf("%d",&s->num);}s->next=(linklist)malloc(sizeof(LNode)); //开辟下一个节点s=s->next;}s->data=i;printf("num%d: ",i);scanf("%d",&(s->num));s->next=head;return(s);}linklist find(int m,linklist s) //找到当前元素后面第m个元素{int i;for(i=0;i<m-1;i++)s=s->next;return(s); //返回找到元素的指针}void print(into &mint &n,linklist &s){linklist p;s=find(m,s); //找到待删除的元素printf("%d ",s->next->data);/*输出找到的元素*/m=s->next->num;/*将此元素从链表中删除,并释放此节点*/ p=s->next;s->next=s->next->next;free(p);--n; //约舍夫环中节点数少一}3 主程序算法void main( ){/*解决约舍夫问题的主函数*/int n,m; //n为约舍夫环内初始人数m为初始密码printf("type in n :");scanf("%d",&n);/*输入n*/while(n<=0){/*如果输入的n小于等于0,要求重新输入*/printf("please type n in again \ntype in n :");scanf("%d",&n);}printf("type in m :");scanf("%d",&m);/*输入m*/while(m<0){/*如果输入的m小于0,要求重新输入*/printf("please type m in again \ntype in m :");scanf("%d",&m);}linklist s;s=creat(n);/*创建无头节点的循环链表,返回指向最后一个元素的指针*/printf("the sequence is ");print(m,n,s);//输出第一个出列的元素while(n){print(m,n,s);//输出剩余出列的元素}printf("\n");}4 函数调用关系图五调试分析调试过程中出现过如下问题：1 开始编程序时没考虑输入错误的问题，导致输入错误后程序出错2 编程序时删除节点子程序结束条件出错3 对开辟的节点用完后没有释放六使用说明程序运行后按提示输入n和m的值，在输入约舍夫环中每个人的密码，运行即可得到出列顺序七测试结果进入程序后要求输入n的值然后输入m的值再输入每个人的密码最后得到出列顺序八附录（源程序）这里附上两种源程序，本质上相同，只是第一个程序按老师要求写为很多子函数形式，第二个是我已开始编的，一个大函数。

程序源代码：#include <stdio.h>#include <malloc.h>#include<conio.h>#include <stdlib.h>#include<ctime>#define NULL 0typedef struct Node{int m;//密码int n;//序号struct Node *next;}Node,*Linklist;Linklist create(int z) //生成循环单链表并返回,z为总人数{int i,mm;Linklist H,r,s;H=NULL;printf("请按顺序依次为每个人添加密码：");for(i=1;i<=z;i++){printf("\ninput cipher=");scanf("%d",&mm);s=(Linklist)malloc(sizeof(Node));s->n=i;s->m=mm;printf("%d号的密码%d",i,s->m);if(H==NULL)//从链表的第一个节点插入{H=s;r=H;}else//链表的其余节点插入{r->next=s;r=s;//r后移}//for结束r->next=H;/*生成循环单链表*/return H;}void search(Linklist H,int m0,int z)//用循环链表实现报数问题{int count=1;//count为累计报数人数计数器int num=0;//num为标记出列人数计数器Linklist pre,p;p=H;printf("出列的顺序为:");while(num<z){do{count++;pre=p;p=p->next;}while(count<m0);｛pre->next=p->next;printf("%d ",p->n);m0=p->m;free(p);p=pre->next;count=1;num++;}//while结束}void clean(){int system(const char *string);int inquiry;printf("请问需要清除上一次操作记录吗（1.清屏/2.不清屏）...?\n"); scanf("%d",&inquiry);if(inquiry ==1)system("cls");}void text(){int m0,z,i, choose,k=1; //k用来阻止第一次进入程序清屏操作Linklist H;bool chooseFlag=false;while(1){if(k!=1)clean();k++;while(!chooseFlag){printf(" ……………………欢迎进入约瑟夫环问题系统…………………… \n"); printf( "* 1.输入约瑟夫环数据 * \n"); printf(" * 2.什么是约瑟夫环 * \n"); printf(" * 3.退出系统 * \n"); printf("........................................................ \n"); printf("请输入相应的数字进行选择: ");scanf("%d",&choose);for(i=1;i<=4;i++){if(choose==i) { chooseFlag=true; break;}else chooseFlag=false;}if(!chooseFlag) printf("Error Input!\n");} //end while(!chooseFlag)if(choose==1) //if 开始{printf("Input how many people in it:");//z为总人数scanf("%d",&z);if(z<=30){H=create(z);//函数调用printf("\nInput the start code m0=");scanf("%d",&m0);search(H,m0,z);printf("\n\n\n");}else{printf("超过最大输入人数\n");break;}}else if(choose==2){printf("\n约瑟夫环问题：设有n个人，其编号分别为1，2，3，…，n，安装编号顺序顺时针围坐一圈。