【C++代码实现】约瑟夫环循环链表 |21xrx.com

【C++代码实现】约瑟夫环循环链表

2023-07-14 13:42:04 深夜i -- --

C++代码约瑟夫环循环链表

约瑟夫环问题是一个经典的问题，在数学和计算机领域都有广泛的应用。而在编程中，使用循环链表来实现约瑟夫环也是一种广泛使用的方法。本文将用C++语言给出约瑟夫环循环链表的代码实现。

1. 定义链表节点

首先，我们需要定义链表节点的结构体。每个链表节点包含两个属性：编号和指向下一个节点的指针。代码如下：


struct Node {
 int num; // 节点编号
 Node* next; // 指向下一个节点的指针
};

2. 创建循环链表

接下来，我们将创建一个循环链表。实现这一步骤的关键是将最后一个节点指向第一个节点，从而形成循环。我们定义一个函数`createLinkList`实现该功能。代码如下：


Node* createLinkList(int n) {
 Node* head = new Node nullptr; // 头节点，编号为1
 Node* tail = head;
 for (int i = 2; i <= n; ++i) {
  Node* node = new Nodei;
  tail->next = node; // 将前一个节点的指针指向当前节点
  tail = node; // 更新尾节点
 }
 tail->next = head; // 尾节点指向头节点，形成循环
 return head;
}

3. 模拟出圈过程

接下来，我们将模拟出圈的过程。具体来说，每次从当前节点开始数k个人，找到第k个人并将其删除，然后继续从下一个节点开始数k个人。我们定义一个函数`josephus`实现该功能。代码如下：


void josephus(Node* head, int k) {
 Node* p = head;
 // 找到链表的最后一个节点
 while (p->next != head)
  p = p->next;
 
 // 从头节点开始数k个人
 Node* q = head;
 while (q->next != q) { // 只剩一个节点时退出循环
  for (int i = 1; i < k; ++i)  // 找到第k个人
   p = q;
   q = q->next;
  
  // 删除第k个节点，并更新当前节点
  p->next = q->next;
  std::cout << q->num << " ";
  delete q;
  q = p->next;
 }
 std::cout << q->num << std::endl; // 输出最后一个节点的编号
 delete q;
}

4. 测试代码

最后，我们编写测试代码，验证我们的约瑟夫环循环链表实现是否正确。代码如下：


int main() {
 int n, k;
 std::cin >> n >> k; // 输入参与约瑟夫环的总人数和每次出圈的第k个人
 Node* head = createLinkList(n);
 josephus(head, k);
 return 0;
}

输入样例：

7 3

输出样例：

3 6 2 7 5 1 4

以上就是实现约瑟夫环循环链表的完整C++代码。通过这个例子，我们可以看到，使用循环链表来实现约瑟夫环问题是非常简单和直观的。

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

下一篇: C++中的.size()函数

评论区

()

相似文章