约瑟夫环的C语言实现与应用

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运⾏结果：以上就是本⽂的全部内容，希望对⼤家的学习有所帮助，也希望⼤家多多⽀持。

目录1．需求分析说明1.Joseph环的总体功能要求2. 各功能模块的功能描述3. 需要测试的数据2．概要设计说明1. 程序流程图2. 模块调用图3．详细设计说明1. 主函数模块2. 节点数据结构体定义模块3．单向循环链表创建模块4．结点删除模块5．输入子模块4．调试分析5．用户使用说明6．课程设计总结7．测试结果8．参考书目一、需求分析说明1. Joseph环的总体功能要求：Joseph环的总体目标：在Microsoft Visual C++ 6.0 的开发环境下，利用所学C语言和数据结构的相关知识，编写约瑟夫环（Joseph）问题的程序，要求如下：编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。

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

报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。

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

利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。

其中的功能主要分为四项：（1）界面友好，易与操作。

（2）要求使用单向循环链表模拟过程（3）输入报数上限值m和人数上限n，密码值，均限定为正整数，输入的形式为一个以“回车符”为结束标志的正整数。

（4）演示程序以人机对话的形式进行，提供用户从键盘输入，Joseph 约瑟夫环的必要数据，并显示出列顺序2. 各功能模块的功能描述：（1）主函数模块本模块的主要功能是初始化图形界面，调用各模块，实现软件功能。

（2）节点数据结构体定义模块本模块的主要功能是进行数据对象及数据关系的创建（3）单向循环链表创建模块本模块的主要功能是用一个循环链表表示joseph环，结构中有两个成员，其一为指向下一个人的指针，已构成joseph环的链，其二为该人的标记。

（4）结点删除模块本模块的主要功能是将结点的下一结点复制到该结点后后将其释放（5）输入子模块本模块的主要功能是进行光标定位，输出提示文字，并对用户输入数据进行处理。

《数据结构》课程设计报告课程名称：《数据结构》课程设计课程设计题目：约瑟夫环姓名：张光栋院系：计算机学院专业：网络工程年级：2013级学号：13055532指导教师：张纪林一、需求分析1.以单项循环链表存储结构模拟约瑟夫环问题。

即编号为1、2、3…、n的n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

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

报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。

按出列顺序印出各人的编号。

2.演示程序以用户与计算机的对话方式执行，用户输入相应的数据，输出结果显示在其后。

3.测试数据：(1)n=55个人的密码依次为：2,4,2,6,2；首先m值为2（正确的输出顺序为：2 1 4 3 5）(2)n=77个人的密码依次为：2,4,1,4,3,2,3首先m值为5（正确的输出顺序为：5 1 3 4 6 2 7）二、概要设计为实现上述程序功能，可利用单向循环链表存储结构模拟此过程。

1.单向循环链表的抽象数据类型定义为：ADT CircularList{数据对象：D={ai|ai∈LNode,i=1,2,…,n,n≥0}数据关系：R1={<ai-1,ai>|ai-1∈D,i=2,…,n}基本操作：Status LisCreate_L(LinkList &L,int I,ElemType &e)操作结果：在不带头结点的单链表L中，创建第i个元素，并用e赋值}2.本程序中包括的两个基本模块：1)主程序模块：Void main(){初始化；do{接受命令；处理命令；}while(“命令”=”退出”)}2)循环链表模块：实现循环链表的抽象数据结构三、详细设计1.结点类型typedef struct ListNode{int mi;int n;struct ListNode *next;}ListNode,*LinkList;2.用循环链表存储约瑟夫环，没有头结点，基本操作函数如下：void CreateList(LinkList&L, int n){LinkList s;int i;L=(LinkList)malloc(sizeof(ListNode));L->n=1;L->next=L;for(i=2;i<=n;i++){s=(LinkList)malloc(sizeof(ListNode));s->next=L->next;L->next=s;s->n=i;L=L->next;}}void Delete(LinkList L, int m){int i;LinkList p,q;p=L;while(p->next!=p){for(i=1;i<m;i++)p=p->next;q=p->next;m=q->mi;printf("%d ",q->n);p->next=q->next;free(q);}printf("%d ",p->n);free(p);}3.主函数：int main(){int n,i,m;LinkList L,p;printf("请输入人数:");scanf("%d",&n);CreateList(L,n);printf("请输入密令\n");p=L->next;for(i=1;i<=n;i++){printf("请输入第%d条密令\n",i);scanf("%d",&p->mi);p=p->next;}printf("请输入初始密令\n");scanf("%d",&m);printf("输出为\n");Delete(L, m);return 0;}四、调试分析1.第一次写时，没有区分出只剩下的一个的情况，导致最终输出出现错误。

题1. 统计字母的使用频率一、题目：统计字母的使用频率二、目的与要求1．目的：通过编写程序统计字母的使用频率，培养学生综合利用C语言进行程序设计的能力，熟悉字符串的操作方法，加强函数的运用，提高软件系统分析能力和程序文档建立、归纳总结的能力。

2．基本要求：1）要求用C语言编程，在Visual C++环境下调试完成；2）要求按照程序功能分成几个功能模块来实现，各个功能模块分别使用函数来完成；3）要求应用本课所讲授的程序设计语言知识来解决问题三、设计方法和基本原理1．课题功能描述本程序的功能，就是要统计英文字母的使用频率。

2．问题详细描述为统计英文字母的使用频率，输入一个不包括空格的由英文字母组成的字符串，长度不超过200个字符。

统计26个英文字母的使用频率，不区分大小写。

最后按使用频率从大到小输出字母（小写字母）和使用频率（出现的次数）。

3．问题的解决方案按照程序要求，本程序应采用模块化设计方法,设计几个功能模块。

例如（仅供参考）：l 将字符串中的大写字母转换为小写字母l 统计输入的字符串中字母的使用频率l 按使用频率从大到小进行排序主函数中控制输入、函数调用和输出。

四、主要技术问题的描述根据三的分析，主要问题在于：1) 为统计字母的使用频率，定义一个长度为26的int数组存放所统计的各个字母的使用频率。

2) 在统计字母的使用频率时，不要使用if语句或switch语句，利用字母的ASCII码与数组元素下标之间的关系来求得。

3) 按使用频率从大到小进行排序时，建议使用指针数组更为方便。

五、创新要求实现程序功能后，可进行创新设计：1) 使用多文件，即主函数和各个函数分别存放在不同的.c文件中，在头文件中进行函数原型声明。

2) 读入一篇英文文档，并对其进行字母频率分析。

题2.指示灯控制问题描述：N盏灯排成一排，从1到N按顺序依次编号。

有N个人也从1到N依次编号。

第一个人（1号）将灯全部关闭。

第二个人（2号）将凡是2和2的倍数的灯打开。

实验一：约瑟夫问题问题描述：用数组和链表存储方式实现约瑟夫问题。

约瑟夫问题：n个人围成一个圆圈，首先第1个人从1开始一个人一个人顺时针报数，报到第m个人，令其出列。

然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其出列，…，如此下去，直到圆圈中只剩一个人为止。

此人即为优胜者。

基本要求：用顺序存储和链式存储方式实现。

试验报告内容：1．问题描述：设有n个人围坐在圆桌周围，现从某个位置m（1≤m≤n）上的人开始报数，报数到k 的人就站出来。

下一个人，即原来的第k+1个位置上的人，又从1开始报数，再报数到k的人站出来。

依此重复下去，直到全部的人都站出来为止。

2. 算法描述：可以先建一个单向循环链表；而整个“约瑟夫环”问题的过程，最终是把这个链表删空为止。

但在删时不能顺着删，而是按该问题的方案来删。

3.源程序#include <stdio.h>#include <stdlib.h>#define MAX_NODE_NUM 100#define TRUE 1U#define FALSE 0Utypedef struct NodeType{int id; /* 编号 */int cipher; /* 密码 */struct NodeType *next;} NodeType;/* 创建单向循环链表 */static void CreaList(NodeType **, const int);/* 运行 "约瑟夫环 "问题 */static void StatGame(NodeType **, int);/* 打印循环链表 */static void PrntList(const NodeType *);/* 得到一个结点 */static NodeType *GetNode(const int, const int);/* 测试链表是否为空, 空为TRUE，非空为FALSE */static unsigned EmptyList(const NodeType *);int main(void){int n, m;NodeType *pHead = NULL;while (1){printf( "请输入人数n（最多%d个）: ", MAX_NODE_NUM); scanf( "%d ", &n);printf( "和初始密码m: ");scanf( "%d ", &m);if (n > MAX_NODE_NUM){printf( "人数太多，请重新输入！\n ");continue;}elsebreak;}CreaList(&pHead, n);printf( "\n------------ 循环链表原始打印 -------------\n "); PrntList(pHead);printf( "\n-------------- 出队情况打印 ---------------\n "); StatGame(&pHead, m);printf( "\n\ "约瑟夫环\ "问题完成!\n ");return 0;}static void CreaList(NodeType **ppHead, const int n){int i, iCipher;NodeType *pNew, *pCur;for (i = 1; i <= n; i++){printf( "输入第%d个人的密码: ", i);scanf( "%d ", &iCipher);pNew = GetNode(i, iCipher);if (*ppHead == NULL){*ppHead = pCur = pNew;pCur-> next = *ppHead;}else{pNew-> next = pCur-> next;pCur-> next = pNew;pCur = pNew;}}printf( "完成单向循环链表的创建!\n ");}static void StatGame(NodeType **ppHead, int iCipher){int iCounter, iFlag = 1;NodeType *pPrv, *pCur, *pDel;pPrv = pCur = *ppHead;/* 将pPrv初始为指向尾结点，为删除作好准备 */while (pPrv-> next != *ppHead)pPrv = pPrv-> next;while (iFlag) /* 开始搞了! */{/* 这里是记数，无非是移动iCipher-1趟指针! */for (iCounter = 1; iCounter < iCipher; iCounter++) {pPrv = pCur;pCur = pCur-> next;}if (pPrv == pCur) /* 是否为最后一个结点了 */iFlag = 0;pDel = pCur; /* 删除pCur指向的结点，即有人出列 */pPrv-> next = pCur-> next;pCur = pCur-> next;iCipher = pDel-> cipher;printf( "第%d个人出列, 密码: %d\n ",pDel-> id, /* 这个编号标识出列的顺序 */pDel-> cipher);free(pDel);}*ppHead = NULL; /* 没人了！为了安全就给个空值 */}static void PrntList(const NodeType *pHead){const NodeType *pCur = pHead;if (EmptyList(pHead))return;do{printf( "第%d个人, 密码: %d\n ", pCur-> id,pCur-> cipher); pCur = pCur-> next;} while (pCur != pHead);}static NodeType *GetNode(const int iId, const int iCipher){NodeType *pNew;pNew = (NodeType *)malloc(sizeof(NodeType));if (!pNew){printf( "Error, the memory is not enough!\n ");exit(-1);}pNew-> id = iId;pNew-> cipher = iCipher;pNew-> next = NULL;return pNew;}static unsigned EmptyList(const NodeType *pHead){if (!pHead){printf( "The list is empty!\n ");return TRUE;}return FALSE;}4.实验测试数据（要求有多组）：第一组测试结果人数n为7, 初始密码m为20第1个人, 密码: 3第2个人, 密码: 1第3个人, 密码: 7第4个人, 密码: 2第5个人, 密码: 4第6个人, 密码: 8第7个人, 密码: 4-------------- 出队情况打印 ---------------第6个人出列, 密码: 8第1个人出列, 密码: 3第4个人出列, 密码: 2第7个人出列, 密码: 4第2个人出列, 密码: 1第3个人出列, 密码: 7第5个人出列, 密码: 4第二组测试结果人数n为8, 初始密码m为15第1个人, 密码: 5第2个人, 密码: 4第3个人, 密码: 3第4个人, 密码: 2第5个人, 密码: 9第6个人, 密码: 1第7个人, 密码: 7第8个人, 密码: 8-------------- 出队情况打印 ---------------第7个人出列, 密码: 7第6个人出列, 密码: 1第8个人出列, 密码: 8第3个人出列, 密码: 3第1个人出列, 密码: 5第4个人出列, 密码: 2第2个人出列, 密码: 4第5个人出列, 密码: 95.总结：1. 通过本次上机实践,对链表存储结构有了更深的理解和把握.2. 通过本次上机实践,应用链表的知识解决和分析问题的能力有了新的提高.3. 通过上机实践,掌握了用高级语言实现算法的基本步骤和方法.（最前面加班级、学号、姓名）。

#include"stdio.h"#include"stdlib.h"#include"malloc.h"#include"conio.h"#define ERROR 1#define OK 0typedef int ElemType;typedef int Status;typedef struct LNode{ElemType code;ElemType number;struct LNode *next;}LNode,*LinkList;Status CreateLink_L(LinkList &L,int n){struct LNode *p,*q;int i;if(n<=0)return ERROR;printf("请输入个人的密码：");L = (LinkList)malloc(sizeof(LNode));L -> next = NULL;L -> number=1;scanf("%d",&L->code);p=L;q=L;for(i = 2;i <= n;++i){L = (LinkList)malloc(sizeof (LNode));L -> next = NULL;L -> number = i;scanf("%d",&L->code);q-> next=L;q = L;}L->next=p;//首尾链接,L指向最后一个人return OK;Status ListDelete_L(LinkList &L,int n,int k,ElemType &code,ElemType &number) {int i;LinkList p=NULL;if(L->next==L) //{p=L;L=NULL;}else{k=(k-1+n)%n;//该移动的次数for(i=1;i<=k;i++) L=L->next;//点到出列的前一个人p=L->next;//该出列的人L->next=p->next;}code=p->code;number=p->number;free(p);return OK;}Status Josephus_L(LinkList &L,int n){ElemType code=0;ElemType number=0;int m;if(L==NULL)return ERROR;printf("请输入m的初值：");scanf("%d",&m);printf("先后出列的人是：");while(L!=NULL){ListDelete_L(L,n--,m,code,number);m=code;printf("%d ",number);}printf("\n");return OK;}int main()LinkList L=NULL;int n;int m;printf("请输入人数：");while(!scanf("%d",&n)||n<=0){printf("请输入一个正整数：");fflush(stdin);}if(!CreateLink_L(L,n)) // 判断链表是否创建成功Josephus_L(L,n);elseprintf("创建链表失败");printf("按任意键结束程序");getch();return 0;}。

C语言约瑟夫环问题编号为1，2，3，…，n 的n 个人围坐一圈，任选一个正整数m 作为报数上限值，从第一个人开始按顺时针方向报数，报数到m 时停止，报数为m 的人出列。

从出列人的顺时针方向的下一个人开始又从1 重新报数，如此下去，直到所有人都全部出列为止。

算法思想每个人的编号存放在一个数组a 中，主函数中决定人数的个数以及报数的上限值m，设计一个函数实现对应的操作。

函数的形参有整型数组a、整数n 和m，n 用来接收传递的人数，m 用来接收报数上限，函数的返回值为空；函数体中输出出列人的顺序。

函数中利用循环访问数组中n 个元素，每次访问元素，设定内循环连续访问m 个元素，元素访问的下标为k，访问到第m 个元素时，如果元素不是0，此时输出元素a[k]，再设定a[k] 为0，继续访问后面的元素。

主函数中设定数组a，从键盘输入n 和m，利用循环产生n 的位置序号存放到数组a 中，调用函数实现相应的操作。

程序代码1.#include<stdio.h>2.#define N 1003.int josef(int a[],int n,int m)4.{5.int i,j,k=0;6.for(i=0;i<n;i++)7.{8. j=1;9.while(j<m)10.{11.while(a[k]==0)12. k=(k+1)%n;13. j++;14. k=(k+1)%n;15.}16.while(a[k]==0)17. k=(k+1)%n;18.printf("%d ",a[k]);19. a[k]=0;20.}21.return0;22.}23.24.int main()25.{26.int a[100];27.int i,j,m,n;28.printf("input n and m：");29.scanf("%d%d",&n,&m);30.for(i=0;i<n;i++)31. a[i]=i+1;32.printf("\n output：\n");33.josef(a,n,m);34.printf("\n");35.return0;36.}调试运行结果15 个人围坐在一起，报数上限为4 时的出列顺序如下所示：100 个人围坐在一起，报数上限为9 时的出列顺序如下所示：。