用C++解决约瑟夫问题的循环链表实现 |21xrx.com

用C++解决约瑟夫问题的循环链表实现

2023-06-30 05:06:30 深夜i -- --

C++ 约瑟夫问题循环链表实现节点删除操作

约瑟夫问题是一个古老的数学问题，它涉及到一个固定大小的圆桌和一群人。所有人围坐在圆桌周围，每个人都被编号。从编号1开始，每隔k个人就将其中一个人杀掉，然后重新开始计数，直到只剩下一个人。本文将介绍使用C++解决约瑟夫问题的循环链表实现。

循环链表是指链表中最后一个节点的next指针指向链表的第一个节点，形成了一个环。在本问题中，我们需要使用循环链表来模拟人们围坐在圆桌周围的情景。每当有人被杀掉时，我们将从循环链表中删除该节点，并将下一个节点设置为当前节点，继续计数。

下面是使用C++的代码实现：


#include <iostream>
#include <cstdlib>
using namespace std;
struct Node {
  int data;
  Node* next;
  Node(int d = 0) : data(d), next(NULL) {};
};
Node* createCircularList(int n) {
  if (n <= 0) return NULL;
  Node* head = new Node(1);
  Node* prev = head;
  for (int i = 2; i <= n; i++) {
    Node* cur = new Node(i);
    prev->next = cur;
    prev = cur;
  }
  prev->next = head;
  return head;
}
void josephus(int n, int k) {
  Node* head = createCircularList(n);
  Node* cur = head;
  while (cur->next != cur) {
    for (int i = 1; i < k; i++)
      cur = cur->next;
    
    Node* tmp = cur->next;
    cur->next = cur->next->next;
    delete tmp;
  }
  cout << "Survivor: " << cur->data << endl;
}
int main() {
  josephus(10, 3);
  return 0;
}

该代码首先定义了一个Node结构体表示循环链表的节点，其中包含data数据和next指针。createCircularList函数用来创建含有n个节点的循环链表。在josephus函数中，我们使用cur指针标识当前节点位置，每经过k个人就将当前节点指向下一个节点，并删除下一个节点。最后，当链表只剩一个节点时，输出该节点的data值。

在上述代码中可以看到，循环链表常用于需要反复遍历的场景中。在约瑟夫问题中，我们需要反复计数，找出需要杀掉的人，因此使用循环链表是比较好的选择。

上一篇: idea打包java可执行jar包

下一篇: C++语言的设计和演化

评论区

()

相似文章