|
|
这段代码是使用双向循环链表实现约瑟夫问题的一个例子。具体来说，给定n个人，编号为1~n，在这n个人中按顺序围成一圈，从第1个人开始报数，每报数到m的人将出列，然后从下一个人重新开始报数，直到所有人都出列。要求依次输出出列的人的编号。
解题思路：
我们可以创建一个带有n个节点的双向循环链表来模拟这个过程，每个节点表示一个人。
在代码中，我们先创建一个头结点head，并用一个指针prev来指向最后一个节点，然后循环从2到n，创建新的节点curr，并将prev的next指向curr，curr的prev指向prev，再将prev更新为curr，这样就创建了一个带有n个节点的双向循环链表。
最后，将prev的next指向head，head的prev指向prev，把链表闭合成环。
接着，我们定义一个指针curr来指向当前处理的节点，它初始指向head。我们需要循环遍历整个链表，每次找到要出列的节点的前一个节点，即从curr开始顺时针遍历m-1个节点，然后输出并删除该节点。
删除节点时，我们需要保存要删除的节点的指针temp，然后把curr的next指向temp的next，temp的next的prev指向curr，最后释放temp所占用的内存。循环这个过程，直到所有的节点都被删除。
注意，由于这个双向循环链表是动态分配内存的，我们需要在程序结束时手动释放节点所占用的内存。此处释放内存时需要使用一个do-while循环来遍历整个链表，并且要判断链表是否已经遍历完了一圈（即当前节点是否等于头结点），才能正确地释放内存。
时间复杂度：
由于每次需要遍历m个节点来找到要出列的节点，因此总共需要遍历n * m个节点。因此时间复杂度为O(nm)。
源码：
#include <iostream>
using namespace std;
struct Node {
int data;
Node* prev;
Node* next;
Node(int d): data(d), prev(nullptr), next(nullptr) {}
};
void josephus(int n, int m) {
Node* head = new Node(1);
Node* prev = head;
for (int i = 2; i <= n; i++) {
Node* curr = new Node(i);
prev->next = curr;
curr->prev = prev;
prev = curr;
}
prev->next = head; // 将链表闭合成环
head->prev = prev;
Node* curr = head;
while (n > 0) {
// 找到要出列的节点的前一个节点
for (int i = 0; i < m-1; i++) {
curr = curr->next;
}
// 输出并删除节点
cout << curr->next->data << &#34; &#34;;
Node* temp = curr->next;
curr->next = temp->next;
temp->next->prev = curr;
delete temp;
n--;
}
// 释放内存
Node* temp = head;
do {
Node* next = temp->next;
delete temp;
temp = next;
} while (temp != head);
}
int main() {
josephus(5, 3); // 输出: 3 1 5 2 4
return 0;
}
该代码首先创建了一个带有n个节点的双链表，然后找到要出列的节点的前一个节点，输出并删除该节点，直到所有的节点都被删除。由于每次需要遍历m个节点来找到要出列的节点，因此时间复杂度为O(nm)。注意在最后需要释放内存。
公众号：奇牛编程 |
|
发表于 2023-4-16 00:30:48