C++编程实现约瑟夫环数据结构 |21xrx.com

C++编程实现约瑟夫环数据结构

2023-07-07 07:05:57 深夜i -- --

C++编程约瑟夫环数据结构算法循环链表

约瑟夫环是一个经典的数据结构问题，它的应用广泛，比如密码学、数学、游戏设计等多个领域都有涉及。本文将介绍如何使用 C++ 编程实现约瑟夫环数据结构。

首先，我们需要明确“约瑟夫环”的定义，它通常是在一个环形链表中的一群人按照一定规律操作，一个人接一个人地被从环中剔除，直到只剩下一个人为止。这样的操作叫做“出圈”，而被剔除的人则被称为“出局者”。

在 C++ 中，我们可以使用链表数据结构来表示这个环。具体来说，我们可以定义一个结构体来表示链表上的每一个节点，包括该节点的元素和下一个节点的指针。


struct Node {
  int val;
  Node *next;
  Node(int v) : val(v), next(nullptr) {}
};

接下来，我们可以使用一个循环来构建链表，同时定义一个变量来记忆最后一个节点的位置。备选的数值可以使用一个数组来保存。


int nums[] = 4;
int n = sizeof(nums) / sizeof(int);
Node *head = new Node(nums[0]);
Node *prev = head;
for (int i = 1; i < n; i++) {
  Node *current = new Node(nums[i]);
  prev->next = current;
  prev = current;
}
prev->next = head;  //将链表环形化

以上代码将会生成一个包含了值为 1~10 的节点链表（如下图），并把尾节点指向头节点，形成了一个环。


1 -> 2 -> 3 -> 4 -> 5 ->
^            |
|            |
|_______________________|

接下来是最重要的部分——模拟出圈过程。我们需要定义一个指向链表头结点的指针 p 和另一个指针 prev，每次循环 prev 都指向被删除节点的前一个节点，p 指向被删除节点的下一个节点。

每次删掉和操作数 m 相等的节点。当链表中只剩下一个元素时，我们就可以停止循环，输出最后一个元素即为约瑟夫环的赢家。

下面是完整的代码实现：


#include <iostream>
using namespace std;
struct Node {
  int val;
  Node *next;
  Node(int v) : val(v), next(nullptr) {}
};
Node *build_list(int nums[], int n) {
  Node *head = new Node(nums[0]);
  Node *prev = head;
  for (int i = 1; i < n; i++) {
    Node *current = new Node(nums[i]);
    prev->next = current;
    prev = current;
  }
  prev->next = head;  //将链表环形化
  return head;
}
Node *josephus(Node *head, int m) {
  if (head->next == head) //如果链表中只有一个元素则直接返回该节点指针
    return head;
  Node *p = head; //指向头结点的指针p
  Node *prev = nullptr; //指向删除节点之前的节点的指针
  int counter = 1;
  while (head->next != head) {  //当链表中只剩下一个元素时，循环结束
    if (counter == m) 删除该节点
      prev->next = p->next;
      cout << p->val << " "; //输出出局者的编号
      delete p; //释放被删除节点的内存
      p = prev->next;
      counter = 1;
     else { //计数加1，指针后移
      prev = p;
      p = p->next;
      counter++;
    }
  }
  return head;
}
int main() {
  int nums[] = 8;
  int n = sizeof(nums) / sizeof(int);
  Node *head = build_list(nums, n);
  int m = 4;
  head = josephus(head, m);
  cout << endl << "The winner is: " << head->val << endl;
  return 0;
}

运行代码，程序输出的结果应该是：

4 8 2 7 3 10 6 1 9 The winner is: 5

以上代码使用了链表数据结构以及指针操作来实现约瑟夫环问题，代码逻辑相对清晰并且实现起来也不复杂。了解约瑟夫环数据结构的实现方式，不仅有助于编程技能的提升，也能增加对该结构在实际应用中的理解。

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

下一篇: C++图形界面下实现goc编程

评论区

()

相似文章