利用C++實(shí)現(xiàn)雙鏈表基本接口示例代碼
鏈表
鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)(鏈表中每一個(gè)元素稱為結(jié)點(diǎn))組成,結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分:一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域,另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。 相比于線性表順序結(jié)構(gòu),鏈表比較方便插入和刪除操作。
本文主要給大家介紹了關(guān)于C++實(shí)現(xiàn)雙鏈表基本接口的相關(guān)內(nèi)容,分享出來(lái)供大家參考學(xué)習(xí),話不多說(shuō),來(lái)一起看看詳細(xì)的介紹吧。
首先先簡(jiǎn)單通過(guò)圖示區(qū)分單鏈表和雙鏈表的結(jié)構(gòu)差異:
單鏈表的基本接口實(shí)現(xiàn)可參考:單鏈表簡(jiǎn)單實(shí)現(xiàn)
接下來(lái)就是雙鏈表的基本接口實(shí)現(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; } } //逆序整個(gè)雙鏈表 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; };
注:在一些操作實(shí)現(xiàn)時(shí),一定要要考慮清楚各種情況,再進(jìn)行情況的分類盡量提高代碼的復(fù)用程度。
總結(jié)
以上就是這篇文章的全部?jī)?nèi)容了,希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來(lái)一定的幫助,如果有疑問(wèn)大家可以留言交流,謝謝大家對(duì)腳本之家的支持
- C++ 雙鏈表的基本操作(詳解)
- C數(shù)據(jù)結(jié)構(gòu)之雙鏈表詳細(xì)示例分析
- C/C++ 雙鏈表之逆序的實(shí)例詳解
- C語(yǔ)言雙向鏈表的表示與實(shí)現(xiàn)實(shí)例詳解
- C語(yǔ)言實(shí)現(xiàn)雙向鏈表
- C語(yǔ)言之雙向鏈表詳解及實(shí)例代碼
- C語(yǔ)言數(shù)據(jù)結(jié)構(gòu) 雙向鏈表的建立與基本操作
- C語(yǔ)言中雙向鏈表和雙向循環(huán)鏈表詳解
- C語(yǔ)言 數(shù)據(jù)結(jié)構(gòu)雙向鏈表簡(jiǎn)單實(shí)例
- C語(yǔ)言實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)和雙向鏈表操作
- C語(yǔ)言實(shí)現(xiàn)的雙鏈表功能完整示例
相關(guān)文章
C語(yǔ)言代碼實(shí)現(xiàn)簡(jiǎn)單掃雷游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言代碼實(shí)現(xiàn)簡(jiǎn)單掃雷游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-02-02C++從匯編的視角審視對(duì)象的創(chuàng)建問(wèn)題
這篇文章主要介紹了C++從匯編的視角看對(duì)象的創(chuàng)建,從匯編的視角來(lái)看,調(diào)用構(gòu)造器和調(diào)用 “返回對(duì)象” 的函數(shù)是一樣的,從匯編的角度來(lái)看,對(duì)象就是一堆數(shù)據(jù)的排列,比如說(shuō)最普通的對(duì)象就是數(shù)據(jù)成員按照聲明順序直接排列,需要的朋友可以參考下2022-01-01淺析C語(yǔ)言中printf(),sprintf(),scanf(),sscanf()的用法和區(qū)別
以下是對(duì)C語(yǔ)言中printf(),sprintf(),scanf(),sscanf()的用法以及區(qū)別進(jìn)行了詳細(xì)的分析介紹,需要的朋友可以參考下2013-07-07C++ 中malloc()和free()函數(shù)的理解
這篇文章主要介紹了C++ 中malloc()和free()函數(shù)的理解的相關(guān)資料,這里提供用法示例幫助大家理解這部分知識(shí),需要的朋友可以參考下2017-08-08C++的sstream標(biāo)準(zhǔn)庫(kù)詳細(xì)介紹
以下是對(duì)C++中的的sstream標(biāo)準(zhǔn)庫(kù)進(jìn)行了詳細(xì)的介紹,需要的朋友可以過(guò)來(lái)參考下2013-09-09Qt實(shí)現(xiàn)自定義驗(yàn)證碼輸入框控件的方法
本文主要介紹了Qt實(shí)現(xiàn)自定義驗(yàn)證碼輸入框控件的方法,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-04-04C++控制臺(tái)實(shí)現(xiàn)俄羅斯方塊游戲
這篇文章主要為大家詳細(xì)介紹了C++控制臺(tái)實(shí)現(xiàn)俄羅斯方塊游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-06-06解決scanf_s輸入%d%c%d格式錯(cuò)誤的問(wèn)題
這篇文章主要介紹了解決scanf_s輸入%d%c%d格式錯(cuò)誤的問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-12-12