溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
鏈表
鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。 相比于線性表順序結構，鏈表比較方便插入和刪除操作。
本文主要給大家介紹了關于C++實現雙鏈表基本接口的相關內容，分享出來供大家參考學習，話不多說，來一起看看詳細的介紹吧。
首先先簡單通過圖示區分單鏈表和雙鏈表的結構差異：
單鏈表的基本接口實現可參考：單鏈表簡單實現
接下來就是雙鏈表的基本接口實現：
#include <iostream>
#include <assert.h>
using namespace std;
typedef int DataType;
struct ListNode
{
ListNode* _next;
ListNode* _prev;
DataType _data;
ListNode(DataType x)
:_next(NULL)
, _prev(NULL)
, _data(x)
{}
};
typedef ListNode Node;
class List
{
public:
List()
:_head(NULL)
,_tail(NULL)
{}
List(const List& l)
:_head(NULL)
,_tail(NULL)
{
Copy(l);
}
void Copy(const List& l)
{
Node* cur = l._head;
while (cur)
{
PushBack(cur->_data);
cur = cur->_next;
}
}
List& operator=(const List& l)
{
Destory();
Copy(l);
return *this;
}
~List()
{
Destory();
}
void Destory()
{
if (_head)
{
Node* cur = _head;
while (_head)
{
cur = _head;
_head = _head->_next;
delete cur;
}
_head = _tail = NULL;
}
}
void PushBack(DataType x)
{
if (_head == NULL)
{
Node* tmp = new Node(x);
tmp->_next = tmp->_prev = NULL;
_head = _tail = tmp;
}
else
{
Node* tmp = new Node(x);
_tail->_next = tmp;
tmp->_prev = _tail;
_tail = tmp;
}
}
void PopBack()
{
if (_head == NULL)
{
return;
}
else if (_head->_next == NULL)
{
delete _head;
_head = _tail = NULL;
}
else
{
Node* tmp = _tail;
_tail = _tail->_prev;
_tail->_next = NULL;
delete tmp;
}
}
void PushFront(DataType x)
{
if (_head == NULL)
{
_head = _tail = new Node(x);
}
else
{
Node* tmp = new Node(x);
tmp->_next = _head;
_head->_prev = tmp;
_head = _head->_prev;
}
}
void PopFront()
{
if (_head == NULL)
{
return;
}
else if (_head->_next == NULL)
{
delete _head;
_head = _tail = NULL;
}
else
{
Node* tmp = _head;
_head = _head->_next;
delete tmp;
_head->_prev = NULL;
}
}
Node* Find(DataType x)
{
Node* cur = _head;
while (cur)
{
if (cur->_data == x)
return cur;
cur = cur->_next;
}
return NULL;
}
// 在pos的前面插入x
void Insert(Node* pos, DataType x)
{
assert(pos);
if ((pos == 0) || (pos->_prev == NULL))
{
PushFront(x);
}
else
{
Node* font = pos->_prev;
Node* tmp = new Node(x);
tmp->_prev = font;
tmp->_next = pos;
font->_next = tmp;
pos->_prev = tmp;
}
}
//刪除pos位置的元素
void Erase(Node* pos)
{
assert(pos);
if ((pos == 0) || (pos->_prev == NULL))
{
PopFront();
}
else if (pos->_next == NULL)
{
PopBack();
}
else
{
Node* font = pos->_prev;
Node* last = pos->_next;
font->_next = last;
last->_prev = font;
delete pos;
}
}
//逆序整個雙鏈表
void Reverse()
{
Node* cur = _head;
while (cur)
{
swap(cur->_next,cur->_prev);
cur = cur->_prev;
}
swap(_head, _tail);
}
void Print()
{
Node* cur = _head;
while (cur)
{
cout << cur->_data << "->";
cur = cur->_next;
}
cout << "NULL" << endl;
}
private:
Node* _head;
Node* _tail;
};
注：在一些操作實現時，一定要要考慮清楚各種情況，再進行情況的分類盡量提高代碼的復用程度。
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作能帶來一定的幫助，如果有疑問大家可以留言交流，謝謝大家對億速云的支持
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
