數據結構練手02 雙向鏈表實現

来源:http://www.cnblogs.com/androidshouce/archive/2016/06/23/5609286.html
-Advertisement-
Play Games

雙向鏈表實現 今天晚上用模板方法把雙向鏈表實現了下，由於有點小粗心，在 insert中手抖了下，把tail->prev 打成了 tail->next，由於錯誤是發生在drop函數執行時，讓我一直去調drop函數，調了半天還是一樣錯誤，最後我系統在vs中監視了下值的變化，終於看到是insert出錯了。 ...


雙向鏈表實現

今天晚上用模板方法把雙向鏈表實現了下，由於有點小粗心，在 insert中手抖了下，把tail->prev 打成了 tail->next，由於錯誤是發生在drop函數執行時，讓我一直去調drop函數，調了半天還是一樣錯誤，最後我系統在vs中監視了下值的變化，終於看到是insert出錯了。 看來程式員離不開調試呀。

另外，昨天說的模板輸出重載，我說要在友元的實現時加上 <>， 但是今天我在gcc中測試了下，居然說找不到匹配的函數，導致編譯不通過，真心蛋疼，vs和g++的區別還真心大，看來改天要好好專研下模板輸出重載，知道的朋友希望能夠告知下。

對數據結構的實現，其實都很簡單，思想就是：

1、定義結點結構類，包含數據域和指針域

2、定義 鏈表(樹，圖)結構，其中封裝包含幾個結點，作為數據介面，因為節點定義指向自身類型的指針，因此而後所有的操作都圍繞這個數據介面進行。

對於雙向鏈表來說，結點定義很簡單，一個數據域，一個next指針，表示以後他將指向下一個結點； 一個prev指針，表示它將指向前一個結點。

複製代碼 
template<typename T>

struct Node{

    T datum;

    Node* next;

    Node* prev;

};
複製代碼


由於鏈式結構添加的結點都要new出來，且結點類包含了數據域，因此需要對結點類進行構造函數的編寫，一般兩個，帶數據域的（以後new來做鏈表中結點），預設無參的(用於new給head和tail的)；析構函數就不用了，因為其指針域所指向的東西是由表結構new出來的，操作應該留給表。

結點類定義好了後，我們定義下鏈表類，主要部分就是要包含下 head 指針， tail 指針。

另外，所有的表（樹，圖結構）最好包含個 “表示長度的數據”，如size, 這樣求length()操作只要O(1)的複雜度，要不然就要遍歷整個鏈表，複雜度就是O(n)了。

對於head指針，規定 head->next 指向第一個結點，head->prev 指向自身或NULL;

對於tail指針，規定 tail->prev 指向最後一個結點，tail->next指向自身或NULL;  這樣規定了head，tail後，後面的操作就會很順暢，我們就可以next/prev到底了，哈哈。

空的條件為： size == 0 或者 head->next == NULL 或者 tail->prev == NULL ，看個人喜好。

剩下一些增刪改查操作，別手抖寫錯了指向關係就行，另外可以加上一個位置判斷，看看是從頭或從尾開始，哪邊移動的少。

函數寫法可以給的建議是:

若只是訪問不修改，成員函數為const;

若需要操作類類型，則用 & 或 const&;

好的，直接上代碼：

先是頭文件，註意最後一行；

 1 #ifndef MY_CHAIN_H
 2 #define MY_CHAIN_H
 3 #include <ostream>
 4 using namespace std;
 5 template <class T>
 6 struct Node{
 7     T datum;
 8     Node* prev;
 9     Node* next;
10 
11     Node(const T& x);
12     Node();
13 };
14 
15 
16 template<class T>
17 class dList{
18     public:
19         dList();
20         ~dList();
21         bool find(int pos,T& hold) const;
22         int search(const T& x) const;
23         int length() const;
24         bool isEmpty() const;
25         dList<T>& drop(int pos, T& hold);
26         dList<T>& insert(int pos, const T& x);
27         dList<T>& push_back(const T& x);
28         dList<T>& push_front(const T& x);
29         T& operator[](int pos);
30         void show(std::ostream& os) const;
31         friend ostream& operator<< <>(ostream& os, const dList& d);
32     protected:
33         Node<T>* head;
34         Node<T>* tail;
35         int size;
36 };
37 #endif 
38 
39 #include "chain.cpp"
View Code

接著是實現文件：

#ifndef MY_CHAIN_CPP
#define MY_CHAIN_CPP
#include "chain.h"
#include <ostream>
#include <cassert>
using std::ostream;
// 節點類的構造
template<class T>
Node<T>::Node(const T& x) : datum(x){
    next = prev = NULL;
}

template<class T>
Node<T>::Node(){
    next = prev = NULL;
    datum = 0;
}

// 雙向鏈表類的構造
template<class T>
dList<T>::dList()
{
    head = new Node<T>();
//    tail = new Node<T>();

    head->next = NULL;
    head->prev = head;
    tail = head;
    tail->next = tail;
    tail->prev = NULL;
    size = 0;
}
 // 析構
template<typename T>
dList<T>::~dList()
{
    if(head){   // 一個建議，若類中數據成員是指針類型，且指向是通過new出來的，那麼最好這裡加上一個判斷。 當然我這裡是多餘的，因為構造時必然new了。
        Node<T>* p = head->next;
        Node<T>* t;
        while(p != NULL){
            t = p;
            p = p->next;
            delete t;
        }
        delete head;
        head = NULL;  // 最好刪除後指向空
        tail = NULL;
    }
}

template<class T>
bool dList<T>::isEmpty() const
{
    return size == 0;
}

template<class T>
bool dList<T>::find(int pos,T& hold) const   // 訪問不修改，成員函數const
{
    if(pos < 1 || pos > size) return false;
    Node<T>* p;
        if(pos <= (size>>1)){      // 從頭開始比較快
            p  = head;
        int count = pos;
        while(count--){p = p->next;}    // next 給 head
        }else{
            p = tail;                      // 從尾開始比較快
            int count = size - pos;
            while(count--){p = p->prev;}    // 哈哈，中就是為什麼把prev給tail, 代碼是不是很順暢？
        }
    hold = p->datum;
    return true;
}

template<class T>
int dList<T>::search (const T& x) const
{
    Node<T>* p = head->next;
    int count = 1;
    while((p!= NULL) && (p->datum != x)){
        p = p->next;
        count++;
    }
    if (p == NULL) {
        return 0;
    }
    return count;
}
template<class T>
int dList<T>::length ()const
{
    return size;
}
template<class T>
dList<T>& dList<T>::push_front (const T& x)   // 前插
{
    Node<T>* p = new Node<T>(x);
    if (size == 0) {
        head->next = p;
        p->prev = NULL;
        tail->prev = p;
        p->next = NULL;
    }else{
        p->next = head->next;
        head->next->prev = p;
        p->prev = NULL;
        head->next = p;
    }
    ++size;
    return *this;
}

template<class T>
dList<T>& dList<T>::push_back (const T& x)     // 尾插
{
    Node<T>* p = new Node<T>(x);
    if (tail->prev == NULL) {
        head->next = p;
        p->prev = NULL;
        tail->prev = p;
        p->next = NULL;
    }else{
        tail->prev->next = p;
        p->prev = tail->prev;
        p->next = NULL;
        tail->prev = p;
    }
    ++size;
    return *this;
}

template<class T>
dList<T>& dList<T>::insert(int pos, const T& x)    // 指定位置插入，範圍[1,size+1]  註意，我的代碼中，1為下標開始；除了後邊重載的[]操作符。
{
    if (pos == 1) {
        return push_front (x);
    }
    if (pos == (size+1)) {
        return push_back (x);
    }
    Node<T>* in = new Node<T>(x);
    Node<T>* p;
    if (pos <= (size/2)) {
        p = head;
        int t = pos;
        while(t--){p = p->next;}
    }else{
        p = tail;
        int t = size - pos;
        while(t--){p = p->prev;}
    }
    in->next = p;
    in->prev = p->prev;    // 哎，這裡就是我萬惡粗心的地方，Mark下，下次要心細點。
    p->prev->next = in;
    p->prev = in;
    ++size;
    return *this;
}

template<class T>
dList<T>& dList<T>::drop(int pos, T& hold)
{
    if (pos < 1 || pos > size) {
        exit(1);
    }
    Node<T>* d = NULL;
    if(pos == 1){
        d = head->next;
        hold = d->datum;
        if(size == 1){            
            tail->prev = NULL;
            head->next = NULL;
        }else{
            head->next = d->next;
            d->next->prev = NULL;
        }
        --size;
        delete d;
        d = NULL;
        return *this;
    }
    if(pos == size){
        d = tail->prev;
        hold = d->datum;
        tail->prev = d->prev;
        d->prev->next = NULL;
        size--;
        delete d;
        d = NULL;
        return *this;
    }else{
        if(pos <= (size/2)){
            int c=pos;
            d = head;
            while(c--){d = d->next;}
        }else{
            int c = size - pos;
            d = tail;
            while(c--){d = d->prev;}
        }
        hold = d->datum;
        d->prev->next = d->next;
        d->next->prev = d->prev;
        --size;
        delete d;
        d = NULL;
        return *this;
    }

}

template<class T>
T& dList<T>::operator[](int pos)
{
    pos = pos + 1;
    if(pos<1 || pos> size) {
        exit(1);
    }
    Node<T>* p = NULL;
    if (pos <= (size>>1)) {
        int t = pos;
        p = head;
        while(t--){p = p->next;}
    }else{
        int t = size - pos;
        p = tail;
        while (t--) { p = p->prev;}
    }
    return p->datum;
}

template<class T>
void dList<T>::show (ostream& os) const
{
    Node<T>* p = head->next;
    int t = 0;
    while(p != NULL){
        os << p->datum << " ";
        p = p->next;
        t++;
    }
    assert(t==size);
}

template<class T>
ostream& operator<< <>(ostream& out, const dList<T>& x)
{
    x.show(out);
    return out;
}
#endif
View Code

最後是測試文件：

 1 #include "chain.h"
 2 #include <iostream>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     dList<int> dl;
 8     int x=0;
 9     dl.insert (1,5);
10     cout << "insert pos1 5: " << dl << endl;
11     cout << "length: " << dl.length() << endl;
12     dl.push_front (3);
13     cout << "push front 3: " << dl << endl;
14     cout << "length: " << dl.length() << endl;
15     dl.push_back (6);
16     cout << "push back 6: " << dl << endl;
17     cout << "length: " << dl.length() << endl;
18     dl.insert(4,8);
19     cout << "insert pos4 8: " << dl << endl;
20     cout << "length=" << dl.length () << endl;
21     dl.find (3,x);
22     dl.drop(2,x);
23     cout << "drop pos 2: " << dl << endl;
24     cout << "length=" << dl.length () << endl;
25     cout << "dl[0]=" << dl[0] << endl;
26     dl[0] = 10;
27     cout << "dl[0]=" << dl[0] << endl;
28     cout << dl << endl;
29 }
View Code

結果如下圖所示：

補充： 其實還可以重載更多的操作符，有心情的朋友可以自己添加下，比如++(int), ++操作等。甚至，可以加入個迭代器類，這樣更方便使用，有時間可以實現下哦。

另外，心細，心細，手別抖。 自勉下！


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 分道揚鑣
    Description 編號為1…N 的N個城市之間以單向路連接，每一條道路有兩個參數：路的長度和通過這條路需付的費用。 Bob和Alice生活在城市1，但是當Bob發現了Alice玩撲克時欺騙他之後，他決定與她翻臉，離開城市1前往城市N。Bob想儘快到達城市N，但是他的錢不多。 希望你幫助Bob找 ...
  • Java讀取Level-1行情dbf文件極致優化（1）
    最近架構一個項目，實現行情的接入和分發，需要達到極致的低時延特性，這對於證券系統是非常重要的。接入的行情源是可以配置，既可以是Level-1，也可以是Level-2或其他第三方的源。雖然Level-1行情沒有Level-2快，但是作為系統支持的行情源，我們還是需要優化它，使得從文件讀取，到用戶通過s... ...
  • python之進位轉換
    Python中二進位是以0b開頭的: 例如: 0b11 則表示十進位的3 8進位是以0開頭的: 例如: 011則表示十進位的9 16進位是以0x開頭的: 例如: 0x11則表示十進位的17 全局定義 二進位 to 十進位 : int(str,n=10) 十六進位 to 十進位 十進位 to 二進位: ...
  • opencv的學習筆記4
    通常更加高級的形態學變換，如開閉運算、形態學梯度、“頂帽”、“黑帽”等等，都是可以由常用的腐蝕膨脹技術結合來達到想要的效果。 1.開運算：先腐蝕後膨脹，用於用來消除小物體、在纖細點處分離物體、平滑較大物體的邊界的同時並不明顯改變其面積，就是使圖片過度更為順暢，填補小的空隙。 2.閉運算：先膨脹後腐蝕 ...
  • [Django]用戶許可權學習系列之User許可權基本操作指令
    針對Django 後臺自帶的用戶管理系統,雖說感覺還可以,但是為了方便用戶一些操作,特別設計自定義的用戶許可權管理系統. 在製作許可權頁面前,首先需要瞭解許可權和用戶配置許可權的指令,上章講到許可權的添加,刪除,查詢,本章介紹用戶許可權的操作指令. 首先需要導入Permission, User模塊: 添加許可權: ...
  • python 數據的拷貝
    python 數據的拷貝 ...
  • 電腦程式的思維邏輯 (20) - 為什麼要有抽象類？
    抽象類就是抽象的類，抽象是相對於具體而言的，一般而言，具體類有直接對應的對象，而抽象類沒有，它表達的是抽象概念 ... 但為什麼非要顯式將類設為抽象的呢？抽象類和介面某些地方很像，但其實根本不同，不過又互相聯繫，它們到底有著怎樣的關係呢？ ...
  • 利用PHP生成靜態HTML文檔的原理
    利用PHP，將資料庫中的文章數據生成單個的HTML文檔。首先，有利於搜索引擎的收錄。其次，避免資料庫中的欄位暴露在地址欄上，更安全。 給出代碼： <?php //引入資料庫配置文件 include( dirname(dirname(lxx_file))."\include\config.php" ) ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類