当前位置: 首页 > 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);****}**
http://www.lryc.cn/news/68063.html

相关文章:

  • 日心说为人类正确认识宇宙打下了基础(善用工具的重要性)
  • Kali-linux系统指纹识别
  • Java版本电子招标采购系统源码:营造全面规范安全的电子招投标环境,促进招投标市场健康可持续发展
  • Java字符串知多少:String、StringBuffer、StringBuilder
  • 中国20强(上市)游戏公司2022年财报分析:营收结构优化,市场竞争进入白热化
  • 如何自学C++编程语言,聊聊C++的特点,别轻易踩坑
  • 算法Day07 | 454.四数相加II,383. 赎金信,15. 三数之和, 18. 四数之和
  • ps抠图、抠头发去背景等
  • 计算机组成原理基础练习题第一章
  • [PyTorch][chapter 34][池化层与采样]
  • Java进阶-字符串的使用
  • 接口自动化框架对比 | 质量工程
  • 谷歌浏览器network error解决方法
  • 自动化测试如何做?接口自动化测试框架必备的9个功能,测试老鸟总结...
  • ANR原理篇 - ANR原理总览
  • 新版Mamba体验超快的软件安装
  • LDAP配置与安装
  • 1-Linux环境安装JDK
  • 通胀数据回落助金价小幅回升
  • 正则表达式的基本语法以及技巧和示例
  • 蓝牙耳机怎么挑选?小编分享2023畅销蓝牙耳机排行榜
  • Linux快照太有趣了!
  • 【改进粒子群优化算法】自适应惯性权重粒子群算法(Matlab代码实现)
  • ROS 下 激光扫描仪 YDLidar-G4 使用
  • 智能边缘:数字化时代的关键战略之一
  • EasyRecovery16中文最新版电脑数据恢复软件下载使用教程
  • 什么是鉴权?这些postman鉴权方式你又知道多少?
  • 最新的经典mysql面试题及答案
  • 算法修炼之练气篇——练气十九层
  • 记录一次Windows7操作系统渗透测试