数据结构双向带头循环链表
程序员文章站
2024-03-22 11:24:52
...
先上类模板
template<typename T>
class DList {
private:
struct Node {
T data;
Node* prev;
Node* next;
Node() {
data = 0;
prev = nullptr;
next = nullptr;
}
Node(T data) {
this->data = data;
prev = nullptr;
next = nullptr;
}
};
Node* head;
public:
DList();
DList(const DList<T>& dl);
~DList();
//尾插
void DListPushBack(T data);
//尾删
void DListPopBack();
//头插
void DListPushFront(T data);
//头删
void DListPopFront();
//在链表中查找值为data的节点,找到返回结点的位置
Node* DListFind(T data);
//在pos位置(插入成功后新节点实际在pos前)插入值为data的元素
void DListInsert(Node* pos, T data);
//删除pos位置的节点
void DListErase(Node* pos);
//将链表中的所有节点清空
void DListClear();
//重载赋值运算符
DList<T>& operator=(const DList<T>& dl);
//重载<<
template<typename T>
friend std::ostream& operator<<(std::ostream& os,DList<T>& dl);
};
构造函数
template<typename T>
DList<T>::DList() {
head = new Node;
head->prev = head;
head->next = head;
}
复制构造函数
template<typename T>
DList<T>::DList(const DList<T>& dl) {
head = new Node;
head->data = dl.head->data;
Node* tmp = dl.head;
Node* newhead = head;
while (tmp->next != dl.head) {
tmp = tmp->next;
Node* node = new Node(tmp->data);
newhead->next = node;
node->prev = newhead;
newhead = node;
}
newhead->next = head;
head->prev = newhead;
}
析构函数
template<typename T>
DList<T>::~DList() {
Node* node = head->next;
while (node != head) {
Node* tmp = node;
node = node->next;
delete tmp;
}
delete head;
}
尾插
template<typename T>
void DList<T>::DListPushBack(T data) {
Node* node = new Node(data);
head->prev->next = node;
node->prev = head->prev;
head->prev = node;
node->next = head;
++head->data;
}
尾删
template<typename T>
void DList<T>::DListPopBack() {
head->prev = head->prev->prev;
delete head->prev->next;
head->prev->next = head;
--head->data;
}
头插
template<typename T>
void DList<T>::DListPushFront(T data) {
Node* node = new Node(data);
head->next->prev = node;
node->next = head->next;
head->next = node;
node->prev = head;
++head->data;
}
头删
template<typename T>
void DList<T>::DListPopFront() {
head->next = head->next->next;
delete head->next->prev;
head->next->prev = head;
--head->data;
}
查找
template<typename T>
typename DList<T>::Node* DList<T>::DListFind(T data) {
Node* node = head->next;
while (node != head) {
if (node->data == data) {
return node;
}
else {
node = node->next;
}
}
return nullptr;
}
插入
template<typename T>
void DList<T>::DListInsert(Node* pos, T data) {
if (pos == head) {
DListPushBack(data);
}
else {
Node* node = head->next;
while (node != pos) {
if (node == head) {
return;
}
node = node->next;
}
node = new Node(data);
pos->prev->next = node;
node->prev = pos->prev;
pos->prev = node;
node->next = pos;
++head->data;
}
}
删除
template<typename T>
void DList<T>::DListErase(Node * pos) {
if (pos != head) {
Node* node = head->next;
while (node != pos) {
if (node == head) {
return;
}
node = node->next;
}
node->prev->next = node->next;
node->next->prev = node->prev;
delete node;
}
}
清空
template<typename T>
void DList<T>::DListClear() {
Node* node = head->next;
while (node != head) {
Node* tmp = node;
node = node->next;
delete tmp;
}
head->prev = head;
head->next = head;
head->data = 0;
}
赋值运算符重载
template<typename T>
DList<T>& DList<T>::operator=(const DList<T>& dl) {
if (this != &dl) {
DListClear();
head->data = dl.head->data;
Node* tmp = dl.head;
Node* newhead = head;
while (tmp->next != dl.head) {
tmp = tmp->next;
Node* node = new Node(tmp->data);
newhead->next = node;
node->prev = newhead;
newhead = node;
}
newhead->next = head;
head->prev = newhead;
}
return *this;
}
<<重载
template<typename T>
std::ostream & operator<<(std::ostream & os,DList<T>& dl) {
typename DList<T>::Node* node = dl.head->next;
while (node != dl.head) {
os << node->data << " ";
node = node->next;
}
return os;
}
上一篇: 双向链表基本操作
下一篇: Excel批量导入数据库——SSIS