用C++实现一个具备规范且详尽的注释的基于模板并且每个节点都是一条双向循环链表的双向循环链表。
时间: 2024-01-22 08:19:18 浏览: 62
基于C++实现的基础数据结构、泛型数据结构及高阶数据结构,含链式栈、顺序栈、单链表、带头双向循环链表、顺序表、泛型数据结构
以下是一个基于模板的双向循环链表的 C++ 实现,每个节点都是一条双向循环链表,并且代码中带有详尽的注释。
```cpp
#include <iostream>
using namespace std;
// 定义双向循环链表节点的结构体
template <typename T>
struct ListNode {
T val;
ListNode *prev;
ListNode *next;
// 构造函数,初始化节点的值、前驱和后继指针
ListNode(T x) : val(x), prev(nullptr), next(nullptr) {}
};
// 定义双向循环链表的类
template <typename T>
class DoublyLinkedList {
public:
// 构造函数,初始化头节点
DoublyLinkedList() {
head = new ListNode<T>(0);
head->prev = head;
head->next = head;
}
// 在链表尾部添加一个节点
void addAtTail(T val) {
// 创建新节点
ListNode<T> *newNode = new ListNode<T>(val);
// 在尾部插入新节点
newNode->prev = head->prev;
newNode->next = head;
head->prev->next = newNode;
head->prev = newNode;
}
// 在链表头部添加一个节点
void addAtHead(T val) {
// 创建新节点
ListNode<T> *newNode = new ListNode<T>(val);
// 在头部插入新节点
newNode->prev = head;
newNode->next = head->next;
head->next->prev = newNode;
head->next = newNode;
}
// 删除链表中第一个值为 val 的节点
void deleteNode(T val) {
// 从头节点开始遍历链表
ListNode<T> *cur = head->next;
while (cur != head) {
// 找到值为 val 的节点
if (cur->val == val) {
// 删除该节点
cur->prev->next = cur->next;
cur->next->prev = cur->prev;
delete cur;
return;
}
cur = cur->next;
}
}
// 输出链表中的所有节点
void printList() {
// 从头节点开始遍历链表
ListNode<T> *cur = head->next;
while (cur != head) {
cout << cur->val << " ";
cur = cur->next;
}
cout << endl;
}
private:
ListNode<T> *head; // 头节点指针
};
```
使用示例:
```cpp
int main() {
DoublyLinkedList<int> dll;
dll.addAtTail(1);
dll.addAtTail(2);
dll.addAtTail(3);
dll.addAtHead(4);
dll.deleteNode(2);
dll.printList(); // 输出:4 1 3
return 0;
}
```
阅读全文