双向链表实现约瑟夫问题
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);
测试样例:

具体代码
#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: **问题:**知n个人围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去&…...
日心说为人类正确认识宇宙打下了基础(善用工具的重要性)
文章目录 引言I 伽利略1.1 借助天文望远镜获得了比别人更多的信息。1.2 确定了科学研究方法:实验和观测 II 开普勒三定律 引言 享有科学史上崇高地位的人,都需要在构建科学体系上有重大贡献。 日心说在哥白尼那里还是一个假说,伽利略拿事实…...
Kali-linux系统指纹识别
现在一些便携式计算机操作系统使用指纹识别来验证密码进行登录。指纹识别是识别系统的一个典型模式,包括指纹图像获取、处理、特征提取和对等模块。如果要做渗透测试,需要了解要渗透测试的操作系统的类型才可以。本节将介绍使用Nmap工具测试正在运行的主…...
Java版本电子招标采购系统源码:营造全面规范安全的电子招投标环境,促进招投标市场健康可持续发展
营造全面规范安全的电子招投标环境,促进招投标市场健康可持续发展 传统采购模式面临的挑战 一、立项管理 1、招标立项申请 功能点:招标类项目立项申请入口,用户可以保存为草稿,提交。 2、非招标立项申请 功能点:非招标…...
Java字符串知多少:String、StringBuffer、StringBuilder
一、String 1、简介 String 是 Java 中使用得最频繁的一个类了,不管是作为开发者的业务使用,还是一些系统级别的字符使用, String 都发挥着重要的作用。String 是不可变的、final的,不能被继承,且 Java 在运行时也保…...
中国20强(上市)游戏公司2022年财报分析:营收结构优化,市场竞争进入白热化
易观:受全球经济增速下行的消极影响,2022年国内外游戏市场规模普遍下滑。但中国游戏公司凭借处于全球领先水平的研发、发行和运营的能力与经验,继续加大海外市场布局,推动高质量发展迈上新台阶。 风险提示:本文内容仅代…...
如何自学C++编程语言,聊聊C++的特点,别轻易踩坑
为什么现在有那么多C培训班呢?因为这些培训班可以为学生安排工作,而外包公司因为缺人,需要做很多项目,可能需要在全国各地分配不同的程序员去干不同的项目,因此需要大量的程序员入职。这样,外包公司就会找培…...
算法Day07 | 454.四数相加II,383. 赎金信,15. 三数之和, 18. 四数之和
Day07 454.四数相加II383. 赎金信15. 三数之和18. 四数之和 454.四数相加II 题目链接:454.四数相加II 寻找两个数组之和,是否与另外两个数组之和有特定的关系。 因为数值可能跨度太大,选择使用下标表示为对应的数值大小,会很浪费…...
ps抠图、抠头发去背景等
方法一:背景橡皮擦 一、很早之前我们使用的是魔术棒工具,但现在我们可以使用Photoshop 有内置的“背景橡皮擦” 步骤: 第1步:在Photoshop中打开需要修的图。 第2步:单击并按住工具栏…...
计算机组成原理基础练习题第一章
有些计算机将一部分软件永恒地存于只读存储器中,称之为() A.硬件 B.软件C.固件 D.辅助存储器输入、输出装置以及外界的辅助存储器称为() A.操作系统 B.存储器 C.主机 D.外围设备完整的计算机系…...
[PyTorch][chapter 34][池化层与采样]
前言: 这里主要讲解一下卷积神经网络中的池化层与采样 目录 DownSampleMax poolingavg poolingupsampleReLu 1: DownSample 下采样,间隔一定行或者列进行采样,达到降维效果 早期LeNet-5 就采样该采样方式。 LeNet-5 2 Max pooling 最大值采样…...
Java进阶-字符串的使用
1.API 1.1API概述 什么是API API (Application Programming Interface) :应用程序编程接口 java中的API 指的就是 JDK 中提供的各种功能的 Java类,这些类将底层的实现封装了起来,我们不需要关心这些类是如何实现的,只需要…...
接口自动化框架对比 | 质量工程
一、前言 自动化测试是把将手工驱动的测试行为转化为机器自动执行,通常操作是在某一框架下进行代码编写,实现用例自动发现与执行,托管在CI/CD平台上,通过条件触发或手工触发,进行回归测试&线上监控,代替…...
谷歌浏览器network error解决方法
很多用户在使用谷歌浏览器时候会出现network error网页提示,很多用户不知道该如何处理这一问题,其实解决方法不止一种,小编整理了两种谷歌浏览器network error解决方法,一起来看看吧~ 谷歌浏览器network error解决方法࿱…...
自动化测试如何做?接口自动化测试框架必备的9个功能,测试老鸟总结...
目录:导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结(尾部小惊喜) 前言 当你准备使用一个…...
ANR原理篇 - ANR原理总览
系列文章目录 提示:这里可以添加系列文章的所有文章的目录,目录需要自己手动添加 例如:第一章 Python 机器学习入门之pandas的使用 文章目录 系列文章目录前言ANR流程概览ANR触发机制一、service超时机制二、broadcast超时机制三、provider超…...
新版Mamba体验超快的软件安装
在一文掌握Conda软件安装:虚拟环境、软件通道、加速solving、跨服务器迁移中详细介绍的conda的基本使用和遇到问题的解决方式,也提到了mamba作为一个替代工具,可以很好的加速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 准备: ① Linux 环境 本文中Linux环境为 CentOS Linux 7 可使用以下命令查询 linux 系统版本: hostnamectl② 准备JDK包 进入官网 https://www.oracle.com/java/technologies/downloads/#java17下载对应jdk包 此处使用以前下载的旧…...
通胀数据回落助金价小幅回升
现货黄金窄幅震荡,目前交投于2032.92美元/盎司附近。隔夜美国通胀数据弱于市场预期,市场对美联储6月份加息预期降温,美元指数走弱,金价一度冲高至2050关口附近,不过,随后金价回吐全部涨幅,并一度…...
多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
招商蛇口 | 执笔CID,启幕低密生活新境
作为中国城市生长的力量,招商蛇口以“美好生活承载者”为使命,深耕全球111座城市,以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子,招商蛇口始终与城市发展同频共振,以建筑诠释对土地与生活的…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
