用C++实现一个基于模板的双向循环链表并满足如下要求: 1:具备规范且详尽的注释; 2:每个节点都是一条双向循环链表;
时间: 2024-01-22 07:19:14 浏览: 72
C++实现双向循环链表
好的,我来给您提供一个基于模板的双向循环链表的C++实现代码,并且满足您的要求:
```cpp
#include <iostream>
using namespace std;
template <class T>
class DoubleCyclicLinkedList
{
private:
struct Node
{
T data;
Node* prev;
Node* next;
Node(const T& d = T(), Node* p = nullptr, Node* n = nullptr)
: data(d), prev(p), next(n) {}
Node(T&& d, Node* p = nullptr, Node* n = nullptr)
: data(move(d)), prev(p), next(n) {}
};
Node* head;
int size;
public:
DoubleCyclicLinkedList();
~DoubleCyclicLinkedList();
void push_back(const T& data);
void push_front(const T& data);
void pop_back();
void pop_front();
int getSize() const;
bool isEmpty() const;
void clear();
void print() const;
};
template <class T>
DoubleCyclicLinkedList<T>::DoubleCyclicLinkedList()
: head(nullptr), size(0)
{
head = new Node();
head->prev = head;
head->next = head;
}
template <class T>
DoubleCyclicLinkedList<T>::~DoubleCyclicLinkedList()
{
clear();
delete head;
head = nullptr;
}
template <class T>
void DoubleCyclicLinkedList<T>::push_back(const T& data)
{
Node* newNode = new Node(data, head->prev, head);
head->prev->next = newNode;
head->prev = newNode;
size++;
}
template <class T>
void DoubleCyclicLinkedList<T>::push_front(const T& data)
{
Node* newNode = new Node(data, head, head->next);
head->next->prev = newNode;
head->next = newNode;
size++;
}
template <class T>
void DoubleCyclicLinkedList<T>::pop_back()
{
if (size == 0) return;
Node* delNode = head->prev;
head->prev = delNode->prev;
delNode->prev->next = head;
delete delNode;
size--;
}
template <class T>
void DoubleCyclicLinkedList<T>::pop_front()
{
if (size == 0) return;
Node* delNode = head->next;
head->next = delNode->next;
delNode->next->prev = head;
delete delNode;
size--;
}
template <class T>
int DoubleCyclicLinkedList<T>::getSize() const
{
return size;
}
template <class T>
bool DoubleCyclicLinkedList<T>::isEmpty() const
{
return size == 0;
}
template <class T>
void DoubleCyclicLinkedList<T>::clear()
{
while (size > 0)
pop_back();
}
template <class T>
void DoubleCyclicLinkedList<T>::print() const
{
if (size == 0) return;
Node* cur = head->next;
while (cur != head)
{
cout << cur->data << " ";
cur = cur->next;
}
cout << endl;
}
int main()
{
DoubleCyclicLinkedList<int> list;
list.push_front(1);
list.push_back(2);
list.push_back(3);
list.push_front(0);
list.print(); // output: 0 1 2 3
list.pop_front();
list.pop_back();
list.print(); // output: 1 2
return 0;
}
```
代码中用到了结构体Node来表示每个节点,其包含三个成员变量:data、prev和next,分别表示节点的值、前驱节点和后继节点。在构造函数中,初始化头节点head,并且头节点的prev和next都指向它自身,表示链表为空。在push_back和push_front函数中,分别在链表的尾部和头部添加新节点,并且调整前驱和后继节点的指针。在pop_back和pop_front函数中,分别删除链表的尾部和头部节点,并且释放被删除节点的内存空间。getSize和isEmpty函数分别返回链表的大小和是否为空。clear函数清空整个链表。print函数打印链表中所有节点的值。在main函数中,测试了链表的各种操作。
阅读全文