程序员经验分享-hwhale

C语言数据结构篇——约瑟夫环的实现

2023-10-27

作者名：Demo不是emo 

主页面链接：主页传送门
创作初心：对于计算机的学习者来说，初期的学习无疑是最迷茫和难以坚持的，中后期主要是经验和能力的提高，我也刚接触计算机1年，也在不断的探索，在CSDN写博客主要是为了分享自己的学习历程，学习方法，总结的经验等等，希望能帮助到大家
座右铭：不要让时代的悲哀成为你的悲哀
专研方向：网络安全，数据结构

每日emo：唯一有效的安慰方式，就是你在我身边
————————————————

 

大一新生自学中，有不完善的地方希望大家见谅，有什么好的改进想法欢迎提出来一起交流，感谢大家的阅读。 

目录

什么是约瑟夫环

约瑟夫环的实现方式

循环链表的构建

循环链表在约瑟夫问题上的应用 

完整代码 

什么是约瑟夫环

约瑟夫环是循环链表的一个典型应用，其描述如下：m个人围成一圈，从任意一个人开始，按顺时针顺序使所有人依次从1开始报数，报到n的人出列，然后使n之后的人接着从1开始报数，再次使报到n的人出列，不断重复此操作，并输出出局的先后顺序，直到最后只剩下一个人，如下示意图所示

假设8个人围成一圈，依次编号1到8，按从小到大顺序报数，报到3的人出局，流程如下

第一轮：从1到3，三号选手出局；

第二轮：4号选手从1开始报数，6号选手报到3，则6号选手出局；

第三轮：7号选手从1开始报数，1号选手报到3，则1号选手出局

第四轮：2号选手从1开始报数，5号选手报到3，则5号选手出局

第五轮：7号选手从1开始报数，2号选手报到3，则2号选手出局

第六轮：4号选手从1开始报数，8号选手报到3，则8号选手出局

第七轮：4号选手从1开始报数，此时只剩下4号和7号，所以4号报到3，4号出局，只剩7号

约瑟夫环的实现方式

一：数组链接方式实现；

二：数组标志位实现

三：循环链表实现（重点）；

因为我是学习循环链表的时候接触的约瑟夫环，所以本文只用第三种方式实现——循环链表实现，当然，循环链表实现约瑟夫环也有很多种写法，下面仅仅是我个人的观点，有不完善的地方还请见谅，下面让我们进入正文。

循环链表的构建

因为本文主要讲述的是用循环链表实现约瑟夫环，所以循环链表的创建就一带而过了，对循环链表不太熟悉的小伙伴也可以参考一下我的上一篇博客，里面对循环链表有比较清楚的讲解，点此链接可以直接进入：C语言数据结构篇——单循环链表的创建，插入，节点删除，打印等操作_Grande joie的博客-CSDN博客下面直接附上为大家封装好的函数

头结点和数据节点结构体的定义如下

typedef struct header//头结点
{
    int length;
    struct node* next;
}head;
typedef struct node//数据节点
{
    int val;
    struct node* next;
}node;

1， head* listcreat(）//循环链表的创建

head* listcreat()
{
    head* p;
    p=(head*)malloc(sizeof(head));
    p->next=NULL;
    p->length=0;
    return p;
}

2， void listinsert(head* p,int pos,int x)//循环链表数据节点的插入

void listinsert(head* p,int pos,int x)
{
    if(p==NULL||pos<0||pos>p->length)
    {
        printf("listinsert():error\n");
        return;
    }
    node* temp=(node*)malloc(sizeof(node));
    temp->val=x;
    node* pcur=p->next;//指向第一个数据节点
    node* plast=p->next;//指向最后一个数据节点
    while(pcur!=NULL&&plast->next!=pcur)//使plast指向最后一个节点
    {
        plast=plast->next;
    }
    if(p->length==0)//判断循环链表为空的情况
    {
        p->next=temp;
        temp->next=temp;
    }
    else if(pos==0)//头插
    {
        plast->next=temp;
        temp->next=pcur;
        p->next=temp;
    }
    else if(pos==p->length)//尾插
    {
        plast->next=temp;
        temp->next=pcur;
    }
    else
    {
        node* pval=p->next;//pval用来指向要插入位置的数据节点
        for(int i=1;i<pos;i++)
        {
            pval=pval->next;
        }
        temp->next=pval->next;
        pval->next=temp;
    }
    p->length++;
    return;
}

void listdelete(head* p,int x)//循环链表数据节点的删除 

void listdelete(head* p,int x)
{
    node* temp;//temp指向要删除的节点
    temp=p->next;
    for(int i=0;i<p->length;i++)
    {
        if(temp->val==x)
        {
            break;
        }
        temp=temp->next;
    }
     if(temp->val!=x)
    {
        printf("listdelete():error\n");
        return;
    }
    node* pcur=p->next;//pcur指向第一个节点
    node* plast=p->next;//plast用来指向最后一个节点
    while(plast->next!=pcur)
    {
        plast=plast->next;
    }
    if(p->length==1)//只有一个元素时
    {
        p->next=NULL;
    }
    else if(temp==pcur)//删除的是第一个节点
    {
        p->next=pcur->next;
        plast->next=pcur->next;
    }
    else if(temp==plast)//删除的是最后一个节点
    {
        node* pre=p->next;//指向倒数第二个节点
        while(pre->next!=plast)
        {
            pre=pre->next;
        }
        pre->next=pcur;
    }
    else
    {
        node* pre=p->next;
        while(pre->next!=temp)//使pre指向temp的前一个元素
        {
            pre=pre->next;
        }
        pre->next=temp->next;
    }
    p->length--;
}

void listprint(head* p)//循环链表的遍历打印（输出） 

void listprint(head* p)
{
    if(p==NULL||p->length==0)
    {
        printf("listprint():error");
        return;
    }
    node* temp=p->next;
    for(int i=0;i<p->length;i++)
    {
        printf("%d ",temp->val);
        temp=temp->next;
    }
    printf("\n");
    return;
}

有了这些封装函数，一个基础的循环链表就可以构建啦

循环链表在约瑟夫问题上的应用  

int main()
{
    head* p;定义循环链表头结点
    p=listcreat();
    printf("题意：m个人围成一圈，报到n的人退出，直到只留下一个\n");
    printf("请输入约瑟夫环的总人数m\n");
    int m,n;
    scanf("%d",&m);
    printf("请输入被踢出的报数n\n");
    scanf("%d",&n);
    for(int i=m;i>0;i--)//围圈操作（即按要求构建循环链表）
    {
        listinsert(p,0,i);
    }
    printf("输出初始循环链表\n");
    listprint(p);
    node* temp=p->next;//定义指向循环链表第一个数据节点的指针，方便报数
    int count=1;//因为此时temp已经指向第一个人了，所以报数从1开始，多看几遍也许好理解一点
    printf("被踢顺序\n");
    while(temp->next!=temp)//剩下一个数时结束循环
    {
        if(count==n)//如果报数等于需要出局的数
        {
            node* pre=p->next;//用于保留位置使temp不至于丢失
            while(pre->next!=temp)//遍历到指向temp的前一个节点
            {
                pre=pre->next;
            }
            printf("%d ",temp->val);
            listdelete(p,temp->val);//出局操作（即删除该数据节点）
            //此时如果没有前面定义的pre，那么temp就没有任何指向了，而有了pre，出局后就可以用                            
            temp代表pre的指向，temp就不会丢失指向
            temp=pre;
            count=0;//因为temp指向了出局的前一个人，下一个人报数从一开始，所以报数先归0
            continue;//出局时就不执行遍历和报数操作
        }
        count++;
        temp=temp->next;
    }
    printf("\n");
    printf("链表中最后被剩下的是：\n");
    listprint(p);
}

完整代码  

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct header
{
    int length;
    struct node* next;
}head;
typedef struct node
{
    int val;
    struct node* next;
}node;
head* listcreat()
{
    head* p;
    p=(head*)malloc(sizeof(head));
    p->next=NULL;
    p->length=0;
    return p;
}
void listinsert(head* p,int pos,int x)
{
    if(p==NULL||pos<0||pos>p->length)
    {
        printf("listinsert():error\n");
        return;
    }
    node* temp=(node*)malloc(sizeof(node));
    temp->val=x;
    node* pcur=p->next;//指向第一个数据节点
    node* plast=p->next;//指向最后一个数据节点
    while(pcur!=NULL&&plast->next!=pcur)//使plast指向最后一个节点
    {
        plast=plast->next;
    }
    if(p->length==0)//判断循环链表为空的情况
    {
        p->next=temp;
        temp->next=temp;
    }
    else if(pos==0)//头插
    {
        plast->next=temp;
        temp->next=pcur;
        p->next=temp;
    }
    else if(pos==p->length)//尾插
    {
        plast->next=temp;
        temp->next=pcur;
    }
    else
    {
        node* pval=p->next;//pval用来指向要插入位置的数据节点
        for(int i=1;i<pos;i++)
        {
            pval=pval->next;
        }
        temp->next=pval->next;
        pval->next=temp;
    }
    p->length++;
    return;
}
void listdelete(head* p,int x)
{
    node* temp;//temp指向要删除的节点
    temp=p->next;
    for(int i=0;i<p->length;i++)
    {
        if(temp->val==x)
        {
            break;
        }
        temp=temp->next;
    }
    node* pcur=p->next;//pcur指向第一个节点
    node* plast=p->next;//plast用来指向最后一个节点
    while(plast->next!=pcur)
    {
        plast=plast->next;
    }
    if(temp->val!=x)
    {
        printf("listprintf():error\n");
        return;
    }
    if(p->length==1)//只有一个元素时
    {
        p->next=NULL;
    }
    else if(temp==pcur)//删除的是第一个节点
    {
        p->next=pcur->next;
        plast->next=pcur->next;
    }
    else if(temp==plast)//删除的是最后一个节点
    {
        node* pre=p->next;//指向倒数第二个节点
        while(pre->next!=plast)
        {
            pre=pre->next;
        }
        pre->next=pcur;
    }
    else
    {
        node* pre=p->next;
        while(pre->next!=temp)//使pre指向temp的前一个元素
        {
            pre=pre->next;
        }
        pre->next=temp->next;
    }
    p->length--;
}
void listprint(head* p)
{
    if(p==NULL||p->length==0)
    {
        printf("listprint():error");
        return;
    }
    node* temp=p->next;
    for(int i=0;i<p->length;i++)
    {
        printf("%d ",temp->val);
        temp=temp->next;
    }
    printf("\n");
    return;
}
int main()
{
    head* p;
    p=listcreat();
    printf("题意：m个人围成一圈，报到n的人退出，直到只留下一个\n");
    printf("请输入约瑟夫环的总人数m\n");
    int m,n;
    scanf("%d",&m);
    printf("请输入被踢出的报数n\n");
    scanf("%d",&n);
    for(int i=m;i>0;i--)
    {
        listinsert(p,0,i);
    }
    printf("输出初始循环链表\n");
    listprint(p);
    node* temp=p->next;
    int count=1;
    printf("被踢顺序\n");
    while(temp->next!=temp)//剩下一个数时结束循环
    {
        if(count==n)
        {
            node* pre=p->next;
            while(pre->next!=temp)//指向temp的前一个节点
            {
                pre=pre->next;
            }
            printf("%d ",temp->val);
            listdelete(p,temp->val);
            temp=pre;
            count=0;
            continue;
        }
        count++;
        temp=temp->next;
    }
    printf("\n");
    printf("链表中最后被剩下的是：\n");
    listprint(p);
}

循环链表在约瑟夫环上的应用就完整的写出来了，随便写点数据运行一下就是下面这个效果啦

 题意：m个人围成一圈，报到n的人退出，直到只留下一个
请输入约瑟夫环的总人数m
8
请输入被踢出的报数n
3
输出初始循环链表
1 2 3 4 5 6 7 8
被踢顺序
3 6 1 5 2 8 4
链表中最后被剩下的是：
7

大家如果有疑问可以随时私信，都会回复大家。  

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

C语言数据结构篇

数据结构

链表

C语言数据结构篇——约瑟夫环的实现 的相关文章

随机推荐

  • phpstudy+phpstorm+navicat环境配置

    phpstudy phpstorm navicat环境配置 这篇文章对我帮助很大 附上链接 https blog csdn net u012861467 article details 54692236 本文章着重记录学习过程如果对你有帮助

  • 看雪学习笔记-[原创]EXP编写学习 之 栈溢出（一）

    看雪学习笔记 原创 EXP编写学习 之 栈溢出 一 https www exploit db com exploits 10619 usr bin python coding UTF 8 char x41 27000 Fileptr ope

  • VMware Workstation搭建Centos7虚拟机详细步骤

    直接按照图文步骤进行操作即可 目录 1 新建虚拟机 2 典型安装 3 稍后安装操作系统 4 版本选择CentOS 7 64位 5 设置虚拟机的名称和位置 6 设置磁盘大小 7 虚拟机向导任务完成 8 虚拟机设置 9 开启虚拟机 10 正式安

  • Python——文件搜索工具

    功能 通过输入一个目标路径和关键字 检索路径下所有文件和子文件中是否有包含关键字的文件 实现 由于需要遍历路径的子文件 因此使用os walk可以递归遍历操作系统的所有文件 具体代码如下 for dirpath dirnames filen

  • 第一章 函数 极限 连续

    第一章 函数 极限 连续 第一节 函数 一 函数的概念及常见函数 1 函数概念 函数的两个基本要素 对应关系 定义域 判断两函数相等 从函数的两基本要素入手 即两函数的对应关系 表达式 定义域相同 对 于 任 意 x D 变 量 x 按 照

  • 时序分解

    时序分解 MATLAB实现MVMD多元变分模态分解信号分量可视化 目录 时序分解 MATLAB实现MVMD多元变分模态分解信号分量可视化 效果一览 基本介绍 程序设计 参考资料 效果一览 基本介绍 MVMD多元变分模态分解 可直接替换Exc

  • Spring应用上下文配置：xml配置

    前言 之前的章节我们讲解了Spring的两种启动方式 分别是web xml方式 java编程方式 如同我们讲过的那样 启动Spring 实际上是启动一个容器 创建一组应用上下文 既然需要创建应用上下文 就必须配置应用上下文 指导应用上下文如

  • 网络知识-02 物理层

    文章目录 1 物理层概念 1 1 主要功能 1 2 主要特性 1 3 传输方式 1 3 1 串行传输 1 3 1 1 同步通信 比特流 报文同步 1 3 1 2 异步传输 字符同步 1 3 2 并行传输 2 数据通信 2 1 源系统 2 2

  • 《Attention is all you need》源码解析+算法详解

    Attention is all you need 源码解析 最近学习Transformer模型的时候 并且好好读了一下Google的 Attention is all you need 论文 论文地址如下 Attention is All

  • 一文详解MySQL的锁机制

    一 表级锁 行级锁 页级锁 数据库锁定机制简单来说 就是数据库为了保证数据的一致性 而使各种共享资源在被并发访问变得有序所设计的一种规则 MySQL数据库由于其自身架构的特点 存在多种数据存储引擎 每种存储引擎的锁定机制都是为各自所面对的特

  • 蓝桥杯历年赛题解析 (C/C++) B 组

    写在前面 以下网盘密码均为1111 文章目录 第十二届蓝桥杯省赛C C B组真题 PDF下载 真题解析 第十二届蓝桥杯省赛C C B组真题 PDF下载 PDF下载 点我 真题解析 真题解析 点我 注 如果您通过阅读本文解决了问题 恳请您留下

  • 应用层 —— 域名系统（DNS）

    一 域名系统 DNS 域名系统 DNS 是因特网使用的命名系统 用来把便于人们记忆的具有特定含义的主机名 如www cskaoyan com 转换为便于机器处理的 IP 地址 从概念上可将DNS分为3部分 层次域名空间 域名服务器和解析器

  • Unity中实现倒计时

    Unity中使用Coroutine 协程 实现倒计时功能 核心代码 do currentMinute minute do while pause yield return null second if OnCountDowning null

  • quota exceeded

    From MailDeliverySystem

  • 解析失败:com.alibaba.fastjson.JSONException: syntax error, expect {, actual string, p

    jsonString jsonString replace replace replace 什么情况 加了转义的 导致解析失败了 这就是报错的原因 把所有的 替换为空 让后将 替换为 即可

  • TCP/IP 标志位 SYN ACK RST UTG PSH FIN

    三次握手 发送端发送一个SYN 1 ACK 0标志的数据包给接收端 请求进行连接 这是第一次握手 接收端收到请求并且允许连接的话 就会发送一个 SYN 1 ACK 1标志的数据包给发送端 告诉它 可以通讯了 并且让发送端发送一个确认数据包

  • 多道程序系统的作业调度模拟程序——先来先服务

    2 编写并调度一个多道程序系统的作业调度模拟程序 作业调度算法 采用基于先来先服务的调度算法 对于多道程序系统 要假定系统中具有的各种资源及数量 调度作业时必须考虑到每个作业的资源要求 本程序中 我设定CPU最大可运行资源数为10 时间片为

  • Hive中rank()、row_number()函数的用法

    1 函数说明 rank 排序相同时会重复 总数不会变 dense rank 排序相同时会重复 总数会减少 row number 会根据顺序计算 2 操作案例 2 1 数据准备 孙悟空 语文 87 孙悟空 数学 95 孙悟空 英语 68 唐僧

  • [附源码]Python计算机毕业设计红色景点自驾游网站管理系统Django（程序+LW）

    该项目含有源码 文档 程序 数据库 配套开发软件 软件安装教程 项目运行 环境配置 Pychram社区版 python3 7 7 Mysql5 7 HBuilderX list pip Navicat11 Django nodejs 项目技

  • C语言数据结构篇——约瑟夫环的实现

    作者名 Demo不是emo 主页面链接 主页传送门创作初心 对于计算机的学习者来说 初期的学习无疑是最迷茫和难以坚持的 中后期主要是经验和能力的提高 我也刚接触计算机1年 也在不断的探索 在CSDN写博客主要是为了分享自己的学习历程 学习方

热门标签