欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++實(shí)現(xiàn)雙向鏈表代碼分析

 更新時(shí)間:2022年03月11日 10:45:56   作者:機(jī)器學(xué)習(xí)入坑者  
這篇文章主要介紹了C++實(shí)現(xiàn)雙向鏈表代碼分析,前面文章分析了單向鏈表,這篇文章就來(lái)給大家分享雙鏈表的實(shí)現(xiàn)吧,需要的朋友可以參考一下

前言:

前面文章分析了單向鏈表,并給出了python和C++實(shí)現(xiàn):單鏈表從原理到實(shí)現(xiàn),python和C++兩個(gè)版本

本文介紹的雙向鏈表是在單向鏈表基礎(chǔ)上的一個(gè)改進(jìn),每個(gè)節(jié)點(diǎn)指向其直接前驅(qū)和直接后繼節(jié)點(diǎn)。因此,從雙向鏈表的任意位置開始,都能訪問所有的節(jié)點(diǎn)。

一、雙向鏈表優(yōu)缺點(diǎn)

雙向鏈表的缺點(diǎn):

從節(jié)點(diǎn)的結(jié)構(gòu)上可以看出,雙向鏈表的所需的存儲(chǔ)空間大于單向鏈表。同時(shí),對(duì)于插入和刪除等操作來(lái)說(shuō),雙向鏈表的節(jié)點(diǎn)操作更加復(fù)雜,涉及到節(jié)點(diǎn)的前后兩個(gè)節(jié)點(diǎn)。

雙向鏈表的節(jié)點(diǎn):

對(duì)于雙向鏈表來(lái)說(shuō),它的每個(gè)節(jié)點(diǎn)要指向“直接前驅(qū)”和“直接后繼”,所以節(jié)點(diǎn)類需要含有兩個(gè)指針域。指向直接前驅(qū)的指針使用pre表示,指向后繼的指針使用next表示。

二、C++實(shí)現(xiàn)分析

(1)節(jié)點(diǎn)類

雙向鏈表的節(jié)點(diǎn)含有兩個(gè)指針域,即直接前驅(qū)pre和直接后繼next。節(jié)點(diǎn)類采用的是模板實(shí)現(xiàn),這樣其所存儲(chǔ)的數(shù)據(jù)就不再依賴于特定類型。

template<class T>
class Node {
public:
?? ?Node() {}
?? ?Node *pre;
?? ?Node *next;
? ? // 由于data屬性是私有的
? ? // 所以采用get和set對(duì)data進(jìn)行處理
?? ?void setData(T data) { this->data = data; }
?? ?T getData() { return this->data; }
private:
?? ?T data;
};

(2)鏈表類分析

鏈表類應(yīng)該包含基本的增、改、刪、查等操作,由于其各種功能的實(shí)現(xiàn)是很相似的,

所以下面給出了需要實(shí)現(xiàn)的典型函數(shù):

  • 構(gòu)造函數(shù):
  • isEmpty()判斷是否為空;
  • size()返回鏈表長(zhǎng)度;
  • insert()頭插、尾插、中間插入節(jié)點(diǎn);
  • delete()刪除節(jié)點(diǎn);
  • getNode()獲取節(jié)點(diǎn);
  • traversal()遍歷鏈表;

鏈表類的定義如下:

template<class P>
class DoubleLinkedList {
public:
?? ?DoubleLinkedList();
?? ?bool isEmpty();
?? ?Node<P> ?*getNode(int index);
?? ?int size();
?? ?void insert(int data, int index);
?? ?void traversal();
?? ?void remove(int index);

private:
?? ?Node<P> *head;
};

(3)鏈表類構(gòu)造函數(shù)

初始化時(shí)需要?jiǎng)?chuàng)建頭節(jié)點(diǎn),作為頭指針:

template<class P>
DoubleLinkedList<P>::DoubleLinkedList() {
?? ?// 創(chuàng)建頭結(jié)點(diǎn)
?? ?head = new Node<P>();
?? ?head->pre = NULL;
?? ?head->next = NULL;
?? ?head->setData(666);
}

(4)isEmpty()判斷是否為空

對(duì)于雙向鏈表來(lái)說(shuō),判斷是否為空只需要判斷頭指針是否指向其他Node節(jié)點(diǎn):

template<class P>
bool DoubleLinkedList<P>::isEmpty() {
?? ?if (head->next == NULL) {
?? ??? ?return true;
?? ?}
?? ?else
?? ?{
?? ??? ?return false;
?? ?}
}

(5)size()獲取鏈表長(zhǎng)度

獲取鏈表長(zhǎng)度時(shí)需要判斷鏈表是否為空,從而確定是否采用遍歷的方式計(jì)算鏈表的長(zhǎng)度。

由于采用的不是循環(huán)鏈表,所以循環(huán)的結(jié)束條件是判斷是否指向空節(jié)點(diǎn):

template<class P>
int DoubleLinkedList<P>::size() {
?? ?if (isEmpty()) {
?? ??? ?return 0;
?? ?}
?? ?else {
?? ??? ?int count = 0;
?? ??? ?Node<P> *current = head->next;
? ? ? ? ? ? // 循環(huán)結(jié)束條件
?? ??? ?while (current!=NULL)
?? ??? ?{
?? ??? ??? ?current = current->next;
?? ??? ??? ?count++;
?? ??? ?}
?? ??? ?return count;
?? ?}
}

(6)getNode()獲取節(jié)點(diǎn)

在插入和刪除等操作中,需要頻繁的進(jìn)行節(jié)點(diǎn)獲取操作。

所以應(yīng)該封裝為單獨(dú)的函數(shù)用于節(jié)點(diǎn)獲取,如下:

template<class P>
Node<P> *DoubleLinkedList<P>::getNode(int index) {?
?? ?Node<P> *current = head;
?? ?int currentCount = 0;
? ? // 循環(huán)結(jié)束條件
?? ?while (currentCount<=index)
?? ?{
?? ??? ?current = current->next;
?? ??? ?currentCount++;
?? ?}
?? ?return current;
}

(7)insert()插入節(jié)點(diǎn)

插入節(jié)點(diǎn)依舊包含頭插法,尾插法和任意位置的插入。插入操作與單向鏈表的最大區(qū)別在于節(jié)點(diǎn)的指針移動(dòng)較為復(fù)雜,需要將插入位置前后兩個(gè)節(jié)點(diǎn)與新節(jié)點(diǎn)均建立聯(lián)系:

template<class P>
void DoubleLinkedList<P>::insert(int data, int index) {
?? ?Node<P> *node = new Node<P>();
?? ?node->setData(data);
?? ?// 1、列表為空時(shí)
?? ?if (isEmpty()) {
?? ??? ?head->next = node;
?? ??? ?node->pre = head;
?? ??? ?return;
?? ?}
?? ?// 2、頭插法
?? ?if (index == 0) {
?? ??? ?node->next = head->next;
?? ??? ?head->next->pre = node;
?? ??? ?node->pre = head;
?? ??? ?head->next = node;
?? ?}
?? ?// 3、尾插法
?? ?else if (index >= this->size() - 1) {
?? ??? ?// printf("index %d, size %d \n", index, this->size());
?? ??? ?Node<P> *temp = this->getNode(this->size()-1);
?? ??? ?temp->next = node;
?? ??? ?node->pre = temp;
?? ?}
?? ?// 4、任意位置插入
?? ?else
?? ?{
?? ??? ?Node<P> *pre = this->getNode(index);
?? ??? ?Node<P> *next = pre->next;
?? ??? ?node->next = pre->next;
?? ??? ?node->pre = pre;
?? ??? ?pre->next = node;
?? ??? ?node->next->pre = node;
?? ?}
}

(8)、remove()刪除節(jié)點(diǎn)

前面已經(jīng)定義了用于獲取節(jié)點(diǎn)的getNode()函數(shù),所以remove()函數(shù)只需要進(jìn)行指針移動(dòng)操作。

將所要?jiǎng)h除的節(jié)點(diǎn)的直接前驅(qū)節(jié)點(diǎn)和直接后繼節(jié)點(diǎn)相連:

template<class P>
void DoubleLinkedList<P>::remove(int index) {
?? ?// 保證索引有意義
?? ?if ((index < (this->size()-1)) && (index>0)) {
?? ??? ?Node<P> *node = this->getNode(index);
?? ??? ?Node<P> *pre = node->pre;
?? ??? ?Node<P> *next = node->next;
?? ??? ?pre->next = next;
?? ??? ?next->pre = pre;
?? ?}
}

(9)traversal()遍歷鏈表函數(shù)

雖然可以從雙向鏈表的任一個(gè)節(jié)點(diǎn)開始遍歷整個(gè)鏈表,但是下面的實(shí)現(xiàn)依舊是從頭結(jié)點(diǎn)開始的,循環(huán)的結(jié)束依舊是指向空指針:

template<class P>
void DoubleLinkedList<P>::traversal() {
?? ?if (!isEmpty()) {
?? ??? ?Node<P> *current = head;
?? ??? ?while (current)
?? ??? ?{
?? ??? ??? ?cout << current->getData() << endl;
?? ??? ??? ?current = current->next;
?? ??? ?}
?? ?}
}?

到此這篇關(guān)于C++實(shí)現(xiàn)雙向鏈表代碼分析的文章就介紹到這了,更多相關(guān)C++雙向鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C++ 基于BFS算法的走迷宮自動(dòng)尋路的實(shí)現(xiàn)

    C++ 基于BFS算法的走迷宮自動(dòng)尋路的實(shí)現(xiàn)

    這篇文章主要為大家介紹了C++ 基于BFS算法實(shí)現(xiàn)走迷宮自動(dòng)尋路,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-11-11
  • C語(yǔ)言實(shí)現(xiàn)反彈球小游戲

    C語(yǔ)言實(shí)現(xiàn)反彈球小游戲

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)反彈球小游戲,利用函數(shù)寫的C語(yǔ)言小游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-02-02
  • C++實(shí)踐Time類中的運(yùn)算符重載參考方法

    C++實(shí)踐Time類中的運(yùn)算符重載參考方法

    今天小編就為大家分享一篇關(guān)于C++實(shí)踐Time類中的運(yùn)算符重載參考方法,小編覺得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來(lái)看看吧
    2019-02-02
  • C++中的運(yùn)算符和表達(dá)式

    C++中的運(yùn)算符和表達(dá)式

    這篇文章主要介紹了C++中的運(yùn)算符和表達(dá)式,學(xué)習(xí)使用表達(dá)式,對(duì)數(shù)據(jù)類型進(jìn)行處理.詳細(xì)介紹內(nèi)容需要的小伙伴可以參考下面文章相關(guān)內(nèi)容
    2022-03-03
  • C/C++中文件的隨機(jī)讀寫詳解及其作用介紹

    C/C++中文件的隨機(jī)讀寫詳解及其作用介紹

    這篇文章主要介紹了C/C++中文件的隨機(jī)讀寫詳解及其作用,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2021-09-09
  • c++編寫簡(jiǎn)單的計(jì)算器程序

    c++編寫簡(jiǎn)單的計(jì)算器程序

    用c++語(yǔ)言實(shí)現(xiàn)一個(gè)簡(jiǎn)單的計(jì)算器,新手作品,僅僅包括基本的加減乘除運(yùn)算。希望能夠給菜鳥們一些啟發(fā)
    2016-05-05
  • tcp socket客戶端和服務(wù)端示例分享

    tcp socket客戶端和服務(wù)端示例分享

    這篇文章主要介紹了tcp socket客戶端和服務(wù)端示例,需要的朋友可以參考下
    2014-03-03
  • Qt創(chuàng)建項(xiàng)目實(shí)戰(zhàn)之手把手創(chuàng)建第一個(gè)Qt項(xiàng)目

    Qt創(chuàng)建項(xiàng)目實(shí)戰(zhàn)之手把手創(chuàng)建第一個(gè)Qt項(xiàng)目

    我們?cè)谶M(jìn)行軟件開發(fā)學(xué)習(xí)時(shí),有時(shí)候需要qt軟件進(jìn)行代碼的敲寫,下面這篇文章主要給大家介紹了關(guān)于Qt創(chuàng)建項(xiàng)目實(shí)戰(zhàn)之手把手創(chuàng)建第一個(gè)Qt項(xiàng)目的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2023-04-04
  • C++通過(guò)文件指針獲取文件大小的方法實(shí)現(xiàn)

    C++通過(guò)文件指針獲取文件大小的方法實(shí)現(xiàn)

    本文主要介紹了C++通過(guò)文件指針獲取文件大小的方法實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-01-01
  • C++超詳細(xì)講解拷貝構(gòu)造函數(shù)

    C++超詳細(xì)講解拷貝構(gòu)造函數(shù)

    我們經(jīng)常會(huì)用一個(gè)變量去初始化一個(gè)同類型的變量,那么對(duì)于自定義的類型也應(yīng)該有類似的操作,那么創(chuàng)建對(duì)象時(shí)如何使用一個(gè)已經(jīng)存在的對(duì)象去創(chuàng)建另一個(gè)與之相同的對(duì)象呢
    2022-06-06

最新評(píng)論