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

C++实现约瑟夫环问题的链表解法

2023-07-12 08:42:46 深夜i -- --

C++ 约瑟夫环问题链表解法

约瑟夫环问题是一个经典的数学问题，常被用作算法和数据结构的练习题目。问题是：n个人围成一圈，第k个人开始报数，报到m的人出列，剩下的人继续从1开始报数，直到所有人都出列，求出出列的顺序。

对于这个问题的解法，最常见的是使用循环数组。不过，C++中链表也可以很好地解决这个问题，而链表解法有着比循环数组更为简便和优雅的写法。

首先，我们需要定义一个Node结构体来表示链表的节点：


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

其中，data表示节点存储的数据，next指向下一个节点。

其次，我们需要构建一个环形链表。为了方便起见，可以把最后一个节点的next指向第一个节点，从而实现环形链表：


Node* createCircularLinkedList(int n) {
 Node* head = nullptr;
 Node* tail = nullptr;
 for (int i = 0; i < n; ++i) {
  if (i == 0) {
   head = tail = new Node(i + 1);
  } else {
   tail->next = new Node(i + 1);
   tail = tail->next;
  }
 }
 tail->next = head; // 将最后一个节点的next指向头节点，形成环形链表
 return head;
}

然后，我们就可以按照约瑟夫环问题的规则进行模拟了。以m=3为例，我们可以使用两个指针p和q，其中p指向当前报数的人，q指向上一个出列的人。每次循环，p递进m步，q也随之移动。当p找到要出列的人时，我们就可以将这个人删除，并更新q的位置。直到链表中只剩下一个人为止。

完整代码如下：


#include <iostream>
using namespace std;
struct Node {
 int data;
 Node* next;
 Node(int data) : data(data), next(nullptr) {}
};
Node* createCircularLinkedList(int n) {
 Node* head = nullptr;
 Node* tail = nullptr;
 for (int i = 0; i < n; ++i) {
  if (i == 0) {
   head = tail = new Node(i + 1);
  } else {
   tail->next = new Node(i + 1);
   tail = tail->next;
  }
 }
 tail->next = head; // 将最后一个节点的next指向头节点，形成环形链表
 return head;
}
void josephus(int n, int m) {
 Node* head = createCircularLinkedList(n);
 Node* p = head;
 Node* q = nullptr;
 while (p != p->next) {
  for (int i = 1; i < m; ++i)
   q = p;
   p = p->next;
  
  q->next = p->next;
  Node* temp = p;
  p = p->next;
  delete temp;
 }
 cout << "The last one is " << p->data << endl;
}
int main() {
 josephus(10, 3);
 return 0;
}

这就是C++实现约瑟夫环问题的链表解法。相较于使用循环数组，链表解法具有更为简便和优雅的写法，同时也不易出错。在实际应用中，如果需要对链式结构进行各种复杂的操作，链表解法也会显得更为灵活和易于扩展。

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

下一篇: C++语言中如何控制输出小数的位数

评论区

()

相似文章