当前位置: 首页 > news >正文

双向链表实现约瑟夫问题


title: 双向链表实现约瑟夫问题
date: 2023-05-16 11:42:26
tags:


  • **问题:**知n个人围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。

  • git地址:https://github.com/944613709/HIT-Data-Structures-and-Algorithms

    算法思想:

    \1. 构建n个结点的双向链表,初始化按照先后顺序给链表的每个节点data值赋值为i(代表是链表第i个)

    \2. 执行search函数,从Head开始寻找第P个节点,while循环head = head->next;直到来到第P个结点

    \3. 执行Jump函数,将从当前head的前m-1次结点进行正常报数,然后返回第m个结点

    \4. 对Jump函数返回来的第m个结点作为新head执行Delete语句,删除当前的结点,并且返回下一个节点,进行下一轮报数

    \5. 利用Delete函数返回来的结点作为新head,重复3,4操作

    \6. 上述重复操作总共执行n-1次出列之后,剩下最后一个人

    算法步骤:

    \1. 建立n个结点的双向链表

    (1) 定义一个Node *head作为头结点data赋值1,再定义一个Node *tail记录尾结点

    (2) For循环n-1次,for(int i=2;i<=len;i++)

    ① 定义Node *node,并且将data值赋值为当前的i

    ② 尾插法,将node插入链表

    \2. 执行search函数

    (1) 执行while循环直到第k个结点,while (head->data != k)

    ① head = head->next;

    (2) 返回第k个结点Return head

    \3. 利用while循环对jump和delete重复操作,同时利用count记录出列次数

    3.1 执行Jump函数

    (1) int count=0;利用count计数记录报数

    (2) While循环直到count=m-1

    ① Count++代表计数加1

    ② Printf执行报数

    ③ 让head指向下一位结点

    \1) 如果head此时已经指向尾结点,则while循环不断head=head->pre,直到head再次指向链表第一个节点

    \2) 如果head不指向尾结点,则head=head->next;即可

    (3) 返回结点Return head

    3.2执行Delete语句

    (4) Node *temp=head;

    (5) 执行printf,声明这个节点要被删除,分三种情况讨论

    ① 对于删除头节点(temp->pre == NULL),直接 head=head->next;然后temp->next=NULL;head->pre=NULL;free(temp); return head;

    ② 对于删除尾结点if(temp->next == NULL) ,利用while循环head=head->pre;,使得head跳到链表第一个,然后执行删除原尾结点temp->pre->next=NULL;temp->pre=NULL;free(temp);

    ③ 对于删除中间结点head=head->next; temp->pre->next=temp->next; temp->next->pre=temp->pre; free(temp);

    测试样例:

    img

    具体代码

    #include<stdio.h>

  **#include<stdlib.h>****#include<math.h>****int delTime=0;****typedef struct Node****{**​     **int data;**​     **struct Node \*pre;**​     **struct Node \*next;****}Node;****Node\* CreatNode(int data)//****新建结点并赋值** **{**​     **Node \*node=(Node\*)malloc(sizeof(Node));**​     **node->data=data;**​     **node->pre=NULL;**​     **node->next=NULL;**​     **return node;****}****Node\* CreatList(int len)****{**​     **int num=1;**​     **Node \*head= CreatNode(1);**​     **Node \*tail=head;**​     **for(int i=2;i<=len;i++)**​     **{**​          **Node \*node=CreatNode(i);**​          **tail->next=node;**​          **node->pre=tail;**​          **tail=tail->next;**​     **}**​     **tail->next=NULL;**​     **return head;****}****Node\* Delete(Node \*head)//****删除当前的,并且返回下一个节点,进行下一轮报数** **{**​     **Node \*temp=head;**​     **delTime++;//****用以判断是否到删除的数** ​     **printf("****本轮报数正好出列,第%d****次执行删除编号为%d\n",delTime,temp->data);**​     **if(temp->pre == NULL)//****对于删除头节点** ​      **{**​      **head=head->next;**​      **temp->next=NULL;**​      **head->pre=NULL;**​      **free(temp);**​      **return head;**​      **}**​      **/\*****判断是否是尾节点\*/**​      **else if(temp->next == NULL)//****对于删除尾结点** ​      **{**​           **while(head->pre!=NULL)**​                 **head=head->pre;//****删除后head****跳到当前链表第一个** ​        **temp->pre->next=NULL;**​        **temp->pre=NULL;**​        **free(temp);**​        **return head;**​      **}**​      **else//****删除中间结点** ​      **{**​           **head=head->next;**​        **temp->pre->next=temp->next;**​        **temp->next->pre=temp->pre;**​        **free(temp);**  ​        **return head;**  ​      **}**​       **}** **Node \*Search(Node \*head, int k) {  //****从Head****开始寻找第P****个节点**​     **while (head->data != k) {**​          **head = head->next;**​     **}**​     **return head;****}****Node \*Jump(Node \*head, int m)//****将head****前m-1****次正常报数,然后返回第m****次** **{**​     **int count=0;**​     **while(count!=m-1)//****前m-1****个人都能正常报数**​     **{**​          **count++;**​          **printf("****报数为->%d,****编号data****为->%d\n",count,head->data);//****报数** ​          **if(head->next==NULL)**​          **{**​              **while(head->pre!=NULL)**​                   **head=head->pre;**​          **}//****换行** ​          **else**​              **head=head->next;**​     **}**​     **return head;** **}****int main()//****已知n****个人围坐在一张圆桌周围。从编号为k****的人开始报数,数到m****的那个人出列;他的下一个人又从1****开始报数,数到m****的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。(****摘自百度百科)****{**​     **int n,k,m;**​     **int count=0;**​     **printf("****按照n,k,m\n");**​     **while(scanf("%d,%d,%d",&n,&k,&m)!=3)**​     **{**​     **}**​     **Node \*head=CreatList(n);**​     **head=Search(head,k);**​     **while(count!=n-1)//****执行n-1****次出列,来完成剩下最后一个人**​     **{**​          **count++;**​          **head=Jump(head,m);//****将head****前m-1****次正常报数,然后返回第m****次** ​          **head=Delete(head);//****删除当前的,并且返回下一个节点,进行下一轮报数** ​     **}**​     **printf("****最后剩下的是编号为%d\n",head->data);****}**

相关文章:

双向链表实现约瑟夫问题

title: 双向链表实现约瑟夫问题 date: 2023-05-16 11:42:26 tags: **问题&#xff1a;**知n个人围坐在一张圆桌周围。从编号为k的人开始报数&#xff0c;数到m的那个人出列&#xff1b;他的下一个人又从1开始报数&#xff0c;数到m的那个人又出列&#xff1b;依此规律重复下去&…...

日心说为人类正确认识宇宙打下了基础(善用工具的重要性)

文章目录 引言I 伽利略1.1 借助天文望远镜获得了比别人更多的信息。1.2 确定了科学研究方法&#xff1a;实验和观测 II 开普勒三定律 引言 享有科学史上崇高地位的人&#xff0c;都需要在构建科学体系上有重大贡献。 日心说在哥白尼那里还是一个假说&#xff0c;伽利略拿事实…...

Kali-linux系统指纹识别

现在一些便携式计算机操作系统使用指纹识别来验证密码进行登录。指纹识别是识别系统的一个典型模式&#xff0c;包括指纹图像获取、处理、特征提取和对等模块。如果要做渗透测试&#xff0c;需要了解要渗透测试的操作系统的类型才可以。本节将介绍使用Nmap工具测试正在运行的主…...

Java版本电子招标采购系统源码:营造全面规范安全的电子招投标环境,促进招投标市场健康可持续发展

营造全面规范安全的电子招投标环境&#xff0c;促进招投标市场健康可持续发展 传统采购模式面临的挑战 一、立项管理 1、招标立项申请 功能点&#xff1a;招标类项目立项申请入口&#xff0c;用户可以保存为草稿&#xff0c;提交。 2、非招标立项申请 功能点&#xff1a;非招标…...

Java字符串知多少:String、StringBuffer、StringBuilder

一、String 1、简介 String 是 Java 中使用得最频繁的一个类了&#xff0c;不管是作为开发者的业务使用&#xff0c;还是一些系统级别的字符使用&#xff0c; String 都发挥着重要的作用。String 是不可变的、final的&#xff0c;不能被继承&#xff0c;且 Java 在运行时也保…...

中国20强(上市)游戏公司2022年财报分析:营收结构优化,市场竞争进入白热化

易观&#xff1a;受全球经济增速下行的消极影响&#xff0c;2022年国内外游戏市场规模普遍下滑。但中国游戏公司凭借处于全球领先水平的研发、发行和运营的能力与经验&#xff0c;继续加大海外市场布局&#xff0c;推动高质量发展迈上新台阶。 风险提示&#xff1a;本文内容仅代…...

如何自学C++编程语言,聊聊C++的特点,别轻易踩坑

为什么现在有那么多C培训班呢&#xff1f;因为这些培训班可以为学生安排工作&#xff0c;而外包公司因为缺人&#xff0c;需要做很多项目&#xff0c;可能需要在全国各地分配不同的程序员去干不同的项目&#xff0c;因此需要大量的程序员入职。这样&#xff0c;外包公司就会找培…...

算法Day07 | 454.四数相加II,383. 赎金信,15. 三数之和, 18. 四数之和

Day07 454.四数相加II383. 赎金信15. 三数之和18. 四数之和 454.四数相加II 题目链接&#xff1a;454.四数相加II 寻找两个数组之和&#xff0c;是否与另外两个数组之和有特定的关系。 因为数值可能跨度太大&#xff0c;选择使用下标表示为对应的数值大小&#xff0c;会很浪费…...

ps抠图、抠头发去背景等

方法一&#xff1a;背景橡皮擦 一、很早之前我们使用的是魔术棒工具&#xff0c;但现在我们可以使用Photoshop 有内置的“背景橡皮擦” 步骤&#xff1a; 第1步&#xff1a;在Photoshop中打开需要修的图。 第2步&#xff1a;单击并按住工具栏…...

计算机组成原理基础练习题第一章

有些计算机将一部分软件永恒地存于只读存储器中&#xff0c;称之为&#xff08;&#xff09; A.硬件    B.软件C.固件    D.辅助存储器输入、输出装置以及外界的辅助存储器称为&#xff08;&#xff09; A.操作系统    B.存储器 C.主机      D.外围设备完整的计算机系…...

[PyTorch][chapter 34][池化层与采样]

前言&#xff1a; 这里主要讲解一下卷积神经网络中的池化层与采样 目录 DownSampleMax poolingavg poolingupsampleReLu 1&#xff1a; DownSample 下采样,间隔一定行或者列进行采样&#xff0c;达到降维效果 早期LeNet-5 就采样该采样方式。 LeNet-5 2 Max pooling 最大值采样…...

Java进阶-字符串的使用

1.API 1.1API概述 什么是API ​ API (Application Programming Interface) &#xff1a;应用程序编程接口 java中的API ​ 指的就是 JDK 中提供的各种功能的 Java类&#xff0c;这些类将底层的实现封装了起来&#xff0c;我们不需要关心这些类是如何实现的&#xff0c;只需要…...

接口自动化框架对比 | 质量工程

一、前言 自动化测试是把将手工驱动的测试行为转化为机器自动执行&#xff0c;通常操作是在某一框架下进行代码编写&#xff0c;实现用例自动发现与执行&#xff0c;托管在CI/CD平台上&#xff0c;通过条件触发或手工触发&#xff0c;进行回归测试&线上监控&#xff0c;代替…...

谷歌浏览器network error解决方法

很多用户在使用谷歌浏览器时候会出现network error网页提示&#xff0c;很多用户不知道该如何处理这一问题&#xff0c;其实解决方法不止一种&#xff0c;小编整理了两种谷歌浏览器network error解决方法&#xff0c;一起来看看吧~ 谷歌浏览器network error解决方法&#xff1…...

自动化测试如何做?接口自动化测试框架必备的9个功能,测试老鸟总结...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 当你准备使用一个…...

ANR原理篇 - ANR原理总览

系列文章目录 提示&#xff1a;这里可以添加系列文章的所有文章的目录&#xff0c;目录需要自己手动添加 例如&#xff1a;第一章 Python 机器学习入门之pandas的使用 文章目录 系列文章目录前言ANR流程概览ANR触发机制一、service超时机制二、broadcast超时机制三、provider超…...

新版Mamba体验超快的软件安装

在一文掌握Conda软件安装&#xff1a;虚拟环境、软件通道、加速solving、跨服务器迁移中详细介绍的conda的基本使用和遇到问题的解决方式&#xff0c;也提到了mamba作为一个替代工具&#xff0c;可以很好的加速conda的solving environemnt过程。但有时也会遇到一个很尴尬的问题…...

LDAP配置与安装

LDAP配置与安装 一、安装LDAP1、安装OpenLDAP及相关依赖包2、查看OpenLDAP版本3、配置OpenLDAP数据库4、设置OpenLDAP的管理员密码5、修改配置文件5.1. 修改{2}hdb.ldif文件5.2. 修改{1}monitor.ldif文件5.3. 修改{-1}frontend.ldif文件 6、验证LDAP的基本配置7、修改LDAP文件权…...

1-Linux环境安装JDK

Linux环境安装JDK 准备&#xff1a; ① Linux 环境 本文中Linux环境为 CentOS Linux 7 可使用以下命令查询 linux 系统版本&#xff1a; hostnamectl② 准备JDK包 进入官网 https://www.oracle.com/java/technologies/downloads/#java17下载对应jdk包 此处使用以前下载的旧…...

通胀数据回落助金价小幅回升

现货黄金窄幅震荡&#xff0c;目前交投于2032.92美元/盎司附近。隔夜美国通胀数据弱于市场预期&#xff0c;市场对美联储6月份加息预期降温&#xff0c;美元指数走弱&#xff0c;金价一度冲高至2050关口附近&#xff0c;不过&#xff0c;随后金价回吐全部涨幅&#xff0c;并一度…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...