用C++实现一个基于模板的双向循环链表并且每个节点可以衍生出一条双向循环链表并加上详细的注释
时间: 2024-01-22 21:19:20 浏览: 32
好的,以下是基于模板的双向循环链表的实现,每个节点可以衍生出一条双向循环链表,并附有详细注释:
```c++
#include <iostream>
// 双向循环链表节点类
template <class T>
class DNode {
public:
T data; // 数据域
DNode<T> *next; // 指向后继节点的指针
DNode<T> *prev; // 指向前驱节点的指针
DNode<T> *child; // 指向子链表的指针
// 构造函数
DNode(T d = 0, DNode<T> *n = nullptr, DNode<T> *p = nullptr, DNode<T> *c = nullptr) :
data(d), next(n), prev(p), child(c) {}
};
// 双向循环链表类
template <class T>
class DList {
public:
DList() : head(nullptr) {} // 默认构造函数
// 析构函数
~DList() {
// 释放链表内存
DNode<T> *p = head;
while (p != nullptr) {
if (p->child != nullptr) {
delete p->child; // 递归删除子链表
}
DNode<T> *q = p->next;
delete p;
p = q;
if (p == head) {
break; // 遍历完整个链表
}
}
}
// 将元素添加到链表末尾
void insert(T d) {
DNode<T> *node = new DNode<T>(d);
if (head == nullptr) {
head = node; // 空链表
head->next = head;
head->prev = head;
} else {
DNode<T> *tail = head->prev;
tail->next = node;
node->prev = tail;
node->next = head;
head->prev = node;
}
}
// 将链表合并到当前节点的子链表
void merge(DList<T> &list) {
if (head == nullptr) {
head = list.head; // 空链表
} else if (list.head != nullptr) {
DNode<T> *tail = head->prev;
DNode<T> *listTail = list.head->prev;
tail->next = list.head;
list.head->prev = tail;
listTail->next = head;
head->prev = listTail;
}
list.head = nullptr; // 避免析构函数释放内存
}
// 递归打印链表及子链表
void print() {
std::cout << "[";
DNode<T> *p = head;
while (p != nullptr) {
std::cout << p->data;
if (p->child != nullptr) {
p->child->print(); // 递归打印子链表
}
p = p->next;
if (p != head) {
std::cout << ", ";
}
}
std::cout << "]";
}
private:
DNode<T> *head; // 链表头指针
};
int main() {
// 创建链表1
DList<int> list1;
list1.insert(1);
list1.insert(2);
list1.insert(3);
// 创建链表2
DList<int> list2;
list2.insert(4);
list2.insert(5);
list2.insert(6);
// 创建链表3
DList<int> list3;
list3.insert(7);
list3.insert(8);
list3.insert(9);
// 将链表2和链表3合并到链表1的节点2和节点3的子链表中
list1.head->next->child = &list2;
list1.head->next->next->child = &list3;
// 打印链表1及其子链表
list1.print(); // 输出:[1, 2, [4, 5, 6], 3, [7, 8, 9]]
return 0;
}
```
注释中解释了每个类和函数的作用,代码使用了模板来支持各种类型的数据,同时也支持子链表的递归。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)