利用C++實現(xiàn)雙鏈表基本接口示例代碼
鏈表
鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(鏈表中每一個元素稱為結(jié)點)組成,結(jié)點可以在運行時動態(tài)生成。每個結(jié)點包括兩個部分:一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域,另一個是存儲下一個結(jié)點地址的指針域。 相比于線性表順序結(jié)構(gòu),鏈表比較方便插入和刪除操作。
本文主要給大家介紹了關(guān)于C++實現(xiàn)雙鏈表基本接口的相關(guān)內(nèi)容,分享出來供大家參考學(xué)習(xí),話不多說,來一起看看詳細的介紹吧。
首先先簡單通過圖示區(qū)分單鏈表和雙鏈表的結(jié)構(gòu)差異:
單鏈表的基本接口實現(xiàn)可參考:單鏈表簡單實現(xiàn)
接下來就是雙鏈表的基本接口實現(xiàn):
#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; };
注:在一些操作實現(xiàn)時,一定要要考慮清楚各種情況,再進行情況的分類盡量提高代碼的復(fù)用程度。
總結(jié)
以上就是這篇文章的全部內(nèi)容了,希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作能帶來一定的幫助,如果有疑問大家可以留言交流,謝謝大家對腳本之家的支持
相關(guān)文章
淺析C語言中printf(),sprintf(),scanf(),sscanf()的用法和區(qū)別
以下是對C語言中printf(),sprintf(),scanf(),sscanf()的用法以及區(qū)別進行了詳細的分析介紹,需要的朋友可以參考下2013-07-07C++ 中malloc()和free()函數(shù)的理解
這篇文章主要介紹了C++ 中malloc()和free()函數(shù)的理解的相關(guān)資料,這里提供用法示例幫助大家理解這部分知識,需要的朋友可以參考下2017-08-08C++的sstream標(biāo)準(zhǔn)庫詳細介紹
以下是對C++中的的sstream標(biāo)準(zhǔn)庫進行了詳細的介紹,需要的朋友可以過來參考下2013-09-09