双向链表实现约瑟夫问题

---

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);****}**