数据结构—约瑟夫环问题(C语言版)

这篇具有很好参考价值的文章主要介绍了数据结构—约瑟夫环问题(C语言版)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

首先什么是约瑟夫环

约瑟夫环实现方式

一、创建结构体变量

二、初始化链表

三、构建循环链表

四、删除链表

 五、完整代码及注释讲解

首先什么是约瑟夫环

约瑟夫环循环链表中的一个经典问题;题目描述:n 个人围成一圈,从第一个人开始报数,数到 m 的人出列,再由下一个人重新从 1 开始报数,数到 m 的人再出圈,依次类推,直到所有的人都出圈;

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

数据结构—约瑟夫环问题(C语言版)

约瑟夫环实现方式

我个人倾向于循环链表;

一、创建结构体变量

typedef struct Node{
    int data;  //数据域
    struct Node* next;  //指针域
}Node;

二、初始化链表

Node* Create(){
	 Node* head;
     head = (Node*)malloc(sizeof(Node));
     if (head == NULL) {
         exit(1);
     }
     head->next = NULL;
     return head;
}

三、构建循环链表

数据结构—约瑟夫环问题(C语言版)

 创建一个临时结点tail,将头结点head赋予tail,插入新结点p,让tailnext指向pp的next指向head的下一个结点即结点p;同时让tail移到p的位置,为下个结点插入做准备;这样一个循环链表就初步完成了;

代码块

Node* Push(Node* head,Node* tail,int 1){
    p->data=i;
    tail->next =p;
    p->next = head->next;
    tail = p;
    return head;
}

数据结构—约瑟夫环问题(C语言版)

 数据结构—约瑟夫环问题(C语言版)

 最重要的一件事,每次插入新结点后,要将tail移动到新结点位置!

四、删除链表

数据结构—约瑟夫环问题(C语言版)

 

void Print(Node* head){
    Node* q=head;
    q->next = p->next;
    printf("%d ", p->data);
    free(p);
    p = q->next;
}

 五、完整代码及注释讲解

#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
    int data;
    struct Node* next;
}Node;
//创建结构体变量
Node* Create(){
	 Node* head;
     head = (Node*)malloc(sizeof(Node));
     if (head == NULL) {
         exit(1);
     }
     head->next = NULL;
     return head;
}
int main()
{
     int n, m,i;
     Node * tail, * p, * q;
     Node* head=Create();
     scanf("%d %d", &n, &m);  //输入n个人围一圈及报数m的人出局
//判断如果插入的数据为0或者以报数0为出局,则结束操作
     if (n == 0 || m == 0) {
         return 0;
     }
     else {
         tail = head;  //开始没有数据,故尾结点tail与头结点重合
         for ( i = 0; i < n; i++) {
             p = (Node*)malloc(sizeof(Node));  //插入新结点需,先申请动态内存
             if (p == NULL) {        //判断动态内存是否申请成功
                 printf("申请失败!");
                 exit(1);
             }
             p->data = i+1; //以下4步为插入新结点及数据的操作,具体分析请看上面构建循环链表
             tail->next =p;
             p->next = head->next;
             tail = p;
         }
     }
     p =head->next;  //插入完数据后,将最后一个结点的临时结点移到第一个数据处
     q =tail;   //然后临时结点到尾结点处
     i = 1;
     while (p != q) {      //首尾结点是否重合,重合则表示只剩一个数据,结束循环
         if (i == m) {     //对报数m的人进行出局操作
             q->next = p->next;  //以下四步为删除操作
             printf("%d ", p->data);
             free(p);     //一定记得将删除链表处的内存释放,以免内存内存泄漏
             p = q->next;
             i = 1;     //删除后,重新从1开始报数
         }
         else {   //没有报数到m,则p,q结点都往后移一位
             q = p;  //先q移到p的位置
             p = q->next;  //然后p移到q的下一个位置
             i++;
         }
     }
     printf("%d", p->data);  //打印最后一位出局的人的号数
     return 0;
}

有什么不足的地方希望个位大佬在评论区多多指点!

数据结构—约瑟夫环问题(C语言版)文章来源地址https://www.toymoban.com/news/detail-513554.html

到了这里,关于数据结构—约瑟夫环问题(C语言版)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】使用循环链表结构实现约瑟夫环问题

    目录 1.循环链表的定义 2.约瑟夫环问题 3.创建循环链表 4.删除节点操作 5.打印所有节点 6.实现约瑟夫环问题的完整程序代码 🌈嗨!我是Filotimo__🌈。很高兴与大家相识,希望我的博客能对你有所帮助。 💡本文由Filotimo__✍️原创,首发于CSDN📚。 📣如需转载,请事先与我联

    2024年01月18日
    浏览(38)
  • C语言数据结构篇——约瑟夫环的实现

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

    2023年04月08日
    浏览(33)
  • 数据结构学习-循环链表:处理约瑟夫环问题

    目录 问题描述 一、基本概念  1.普通链表 2.单向循环链表  二、问题处理 1.创建链表 2.查找 3.删除  4.其他  三.实验环节 四.总结 约瑟夫环问题的一种描述是:编号为1,2,...,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数

    2024年02月07日
    浏览(39)
  • 数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题

    实验的写法多种多样,但本文并未采用 #define 定义容量的写法,这样写已经是很老旧过时的写法。所有实验主体采用均为动态开辟,后续如果利用 C++ 来写或许会应用更多语法… 本篇展示数据结构的两个实验 其中,重点分析约瑟夫问题 实验中代码的命名风格等均与下方博客

    2024年02月16日
    浏览(58)
  • 数据结构上机实验——栈和队列的实现、栈和队列的应用、进制转换、约瑟夫环问题

      1.利用栈的基本操作实现将任意一个十进制整数转化为R进制整数。   2.利用循环队列实现.约瑟夫环问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到k的那个人出圈;他的下一个人又从1开始报数,数到k的那个人出圈;依

    2024年02月08日
    浏览(40)
  • 数据结构与算法——约瑟夫环

    目录 一、例题引入         # 解题思路         #图例分析         #代码段         #题解小结  二、循环链表         分析:         直接看代码:  三、标记数组         分析:         代码: 四、递归算法          #沿用解释         设有n个人坐在圆桌周围,

    2024年02月08日
    浏览(42)
  • 数据结构实验1约瑟夫环

    刚开始m值为20 循环链表

    2024年02月08日
    浏览(41)
  • 【数据结构与算法】约瑟夫环(C/C++)

    约瑟夫问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始。按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上

    2024年02月12日
    浏览(28)
  • C语言:约瑟夫环问题详解

    前言 哈喽,宝子们!本期为大家带来一道C语言循环链表的经典算法题(约瑟夫环)。 据说著名历史学家Josephus有过以下的故事:在罗马人占领乔塔帕特后,39个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被人抓到,于是决定了一个自杀方式,41个人

    2024年04月13日
    浏览(31)
  • C语言 | 约瑟夫问题(猴王争夺战)

             约瑟夫问题有时也称为约瑟夫斯置换,是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环。下面我们将用猴子争大王这一故事以及采用单向循环链表这一方法来进行讲解这一问题。         设编号为1,2,……n得n个猴子围

    2024年02月01日
    浏览(31)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包