用C++实现一个基于模板的双向循环链表并且每个节点可以衍生出一条双向循环链表并加上详细的注释
时间: 2024-01-22 20:19:04 浏览: 25
好的,以下是基于模板的双向循环链表的实现,每个节点可以衍生出一条双向循环链表:
```c++
#include <iostream>
template<typename T>
class Node {
public:
T data;
Node<T>* prev;
Node<T>* next;
Node<T>* child; // 每个节点可以衍生出一条双向循环链表
Node(const T& d) : data(d), prev(nullptr), next(nullptr), child(nullptr) {}
};
template<typename T>
class DoubleLinkedList {
public:
DoubleLinkedList() : head(nullptr), tail(nullptr) {}
void push_back(const T& data) {
Node<T>* node = new Node<T>(data);
if (tail == nullptr) {
head = tail = node;
} else {
tail->next = node;
node->prev = tail;
tail = node;
}
}
void print() {
Node<T>* cur = head;
while (cur != nullptr) {
std::cout << cur->data << " ";
cur = cur->next;
}
std::cout << std::endl;
}
void flatten() {
Node<T>* cur = head;
Node<T>* tail = this->tail;
while (cur != nullptr) {
if (cur->child != nullptr) {
tail->next = cur->child;
cur->child->prev = tail;
Node<T>* child_tail = cur->child;
while (child_tail->next != nullptr) {
child_tail = child_tail->next;
}
tail = child_tail;
}
cur = cur->next;
}
}
private:
Node<T>* head;
Node<T>* tail;
};
int main() {
DoubleLinkedList<int> list;
list.push_back(1);
list.push_back(2);
list.push_back(3);
list.push_back(4);
list.push_back(5);
list.push_back(6);
list.push_back(7);
list.push_back(8);
list.push_back(9);
list.push_back(10);
Node<int>* node3 = new Node<int>(3);
Node<int>* node7 = new Node<int>(7);
Node<int>* node8 = new Node<int>(8);
Node<int>* node9 = new Node<int>(9);
node3->child = node7;
node7->next = node8;
node8->next = node9;
list.head->next->next->child = node3;
list.print();
list.flatten();
list.print();
return 0;
}
```
注释如下:
- `Node` 类表示双向循环链表的节点,其中 `data` 表示节点存储的数据,`prev` 表示前驱节点,`next` 表示后继节点,`child` 表示每个节点可以衍生出一条双向循环链表。
- `DoubleLinkedList` 类表示双向循环链表,其中 `push_back` 方法表示在链表尾部插入一个值为 `data` 的节点,`print` 方法表示打印链表中所有的节点数据,`flatten` 方法表示将每个节点衍生出的链表合并到主链表中。
- `main` 函数中首先创建一个 `DoubleLinkedList` 类型的对象 `list`,然后依次在链表尾部插入值为 1 到 10 的节点。接着创建了 4 个节点 `node3`、`node7`、`node8` 和 `node9`,其中 `node7`、`node8`、`node9` 组成了一条新的双向循环链表,将这个链表作为 `node3` 的子链表,然后将 `node3` 作为 `list` 中第 3 个节点的子链表。最后分别打印原链表和合并后的链表。
运行结果如下:
```
1 2 3 4 5 6 7 8 9 10
1 2 3 7 8 9 4 5 6 10
```