前言

??據說「前言」 寫太多會被人唾棄，所以，這次直接進入正題，

「畫解資料結構」

點擊我跳轉末尾 獲取 粉絲專屬 《演算法和資料結構》原始碼，

第一章 線性表

??《畫解資料結構》（1-1）畫解順序表??
??《畫解資料結構》（1-2）畫解鏈表??
??《畫解資料結構》（1-3）畫解堆疊??
??《畫解資料結構》（1-4）畫解佇列??
??《畫解資料結構》（1-5）畫解雙端佇列??
??《畫解資料結構》（1-6）畫解哈希表??

第二章 樹

??《畫解資料結構》（2-1）畫解樹??
??《畫解資料結構》（2-2）畫解二叉樹??
??《畫解資料結構》（2-3）畫解二叉搜索樹??
??《畫解資料結構》（2-4）畫解堆??
??《畫解資料結構》（2-5）畫解AVL樹??
??《畫解資料結構》（2-6）畫解線段樹??
??《畫解資料結構》（2-7）畫解字典樹??
??《畫解資料結構》（2-8）畫解霍夫曼樹??
??《畫解資料結構》（2-9）畫解并查集??

第三章 圖

??《畫解資料結構》（3-1）畫解圖??
??《畫解資料結構》（3-2）畫解二分匹配??
??《畫解資料結構》（3-3）畫解最短路??
??《畫解資料結構》（3-5）畫解最小生成樹??
??《畫解資料結構》（3-4）畫解強連通??

正文

第一章 線性表 （1-1）畫解順序表

一、順序表的概念

1、順序存盤

??順序存盤結構，是指用一段地址連續的存盤單元依次存盤線性表的資料元素，

2、存盤方式

??在編程語言中，用一維陣列來實作順序存盤結構，在C語言中，把第一個資料元素存盤到下標為 0 的位置中，把第 2 個資料元素存盤到下標為 1 的位置中，以此類推，

3、長度和容量

??陣列的長度指的是陣列當前有多少個元素，陣列的容量指的是陣列最大能夠存放多少個元素，如果陣列元素大于最大能存盤的范圍，在程式上是不允許的，可能會產生意想不到的問題，實作上是需要規避的，

??如上圖所示，陣列的長度為 5，即紅色部分；容量為 8，即紅色加藍色部分，

4、資料結構定義

#define MAXN 1024
#define DataType int        // (1)

struct SeqList {
    DataType data[MAXN];    // (2)
    int length;             // (3)
};

( 1 ) (1) (1) 陣列型別為DataType，定義為int；
( 2 ) (2) (2) SeqList定義的就是一個最多存放MAXN個元素的陣列，MAXN代表陣列容量；
( 3 ) (3) (3) length代表陣列長度，即當前的元素個數，

二、常用介面實作

1、只讀介面

1）索引

??索引就是通過 陣列下標 尋找 陣列元素 的程序，C語言實作如下：

DataType SeqListIndex(struct SeqList *sq, int i) {
    return sq->data[i];          // (1)
}

( 1 ) (1) (1) 呼叫方需要注意 i i i 的取值必須為非負整數，且小于陣列最大長度，否則有可能導致例外，引發崩潰，
索引的演算法時間復雜度為 O ( 1 ) O(1) O(1)，

2）查找

??查找就是通過 陣列元素 尋找 陣列下標 的程序，是索引的逆程序，
??對于有序陣列，可以采用二分進行查找，時間復雜度為 O ( l o g 2 n ) O(log_2n) O(log2?n)；對于無序陣列，只能通過遍歷比較，由于元素可能不在陣列中，可能遍歷全表，所以查找的最壞時間復雜度為 O ( n ) O(n) O(n)，
??簡單介紹一個線性查找的例子，實作如下：

DataType SeqListFind(struct SeqList *sq, DataType dt) {
    int i;
    for(i = 0; i < sq->length; ++i) { // (1)
        if(sq->data[i] == dt) {
            return i;                 // (2)
        }    
    }
    return -1;                        // (3)
}

( 1 ) (1) (1) 遍歷陣列元素；
( 2 ) (2) (2) 對陣列元素和傳入的資料進行判等，一旦發現相等就回傳對應資料的下標；
( 3 ) (3) (3) 當陣列遍歷完還是找不到，說明這個資料肯定是不存在的，直接回傳 ? 1 -1 ?1，

3）獲取長度

??獲取 陣列的長度 指的是查詢當前有多少元素，可以直接用結構體的內部變數，C語言代碼實作如下：

DataType SeqListGetLength(struct SeqList *sq) {
    return sq->length; 
}

2、可寫介面

1）插入

??插入介面定義為：在陣列的第 k k k 個元素前插入一個數 v v v，由于陣列是連續存盤的，那么從 k k k 個元素往后的元素都必須往后移動一位，當 k = 0 k=0 k=0 時，所有元素都必須移動，所以最壞時間復雜度為 O ( n ) O(n) O(n)，C語言代碼實作如下：

int SeqListInsert(struct SeqList *sq, int k, DataType v) {
    int i;
    if(sq->length == MAXN) {
        return 0;                        // (1) 
    } 
    for(i = sq->length; i > k; --i) {
        sq->data[i] = sq->data[i-1];     // (2) 
    }
    sq->data[k] = v;                     // (3) 
    sq->length ++;                       // (4) 
    return 1;                            // (5) 
}

( 1 ) (1) (1) 當元素個數已滿時，回傳 0 0 0 代表插入失敗；
( 2 ) (2) (2) 從第 k k k 個數開始，每個數往后移動一個位置，注意必須逆序；
( 3 ) (3) (3) 將第 k k k 個數變成 v v v；
( 4 ) (4) (4) 插入了一個數，陣列長度加一；
( 5 ) (5) (5) 回傳 1 1 1 代表插入成功；

2）洗掉

??插入介面定義為：將陣列的第 k k k 個元素洗掉，由于陣列是連續存盤的，那么第 k k k 個元素洗掉，往后的元素勢必要往前移動一位，當 k = 0 k=0 k=0 時，所有元素都必須移動，所以最壞時間復雜度為 O ( n ) O(n) O(n)，C語言代碼實作如下：

int SeqListDelete(struct SeqList *sq, int k) {
    int i;
    if(sq->length == 0) {
        return 0;                        // (1) 
    } 
    for(i = k; i < sq->length - 1; ++i) {
        sq->data[i] = sq->data[i+1];     // (2) 
    } 
    sq->length --;                       // (3) 
    return 1;                            // (4)  
}

( 1 ) (1) (1) 回傳0代表洗掉失敗；
( 2 ) (2) (2) 從前往后；
( 3 ) (3) (3) 陣列長度減一；
( 4 ) (4) (4) 回傳1代表洗掉成功；

三、優缺點

1、優點

??1）無須為表示表中元素邏輯關系而增加額外的存盤空間；
??2）隨機存取元素時可以達到 O ( 1 ) O(1) O(1)，效率高；

2、缺點

??1）插入和洗掉時需要移動大量元素；
??2）必須一開始就確定存盤空間的容量；

四、陣列相關演算法

1、線性列舉

1）問題描述

??給定一個長度為 n ( 1 ≤ n ≤ 1 0 5 ) n(1 \le n \le 10^5) n(1≤n≤105) 的整型陣列，求所有陣列元素中的其中的最小值，

2）動圖演示

3）示例說明

??藍色的資料代表的是陣列資料，紅色的資料代表當前列舉到的資料，這樣就可以遍歷所有的資料進行邏輯處理了，

4）演算法描述

??遍歷陣列，進行條件判斷，條件滿足則執行邏輯，這里的條件就是 列舉到的數 是否小于 當前最小值，執行邏輯為將 當前列舉到的數 賦值給 當前最小值；

5）原始碼詳解

int findMin(int* nums, int numsSize){
    int i, min = 100000;
    for(i = 0; i < numsSize; ++i) {     // (1)
        if(nums[i] < min) {             // (2)
            min = nums[i];
        }
    }
    return min;                         // (3)
}

( 1 ) (1) (1) 遍歷陣列中所有的數；
( 2 ) (2) (2) 如果 當前列舉到的數 比記錄的變數min小，則將它賦值給min；否則，不做任何處理；
( 3 ) (3) (3) 最后，min中存盤的就是整個陣列的最小值，

2、前綴和差分

1）問題描述

??給定一個 n ( n ≤ 1 0 5 ) n (n \le 10^5) n(n≤105) 個元素的整型陣列 a i a_i ai?，再給出 m ( m ≤ 1 0 5 ) m(m \le 10^5) m(m≤105) 次詢問，每次詢問是一個區間 [ l , r ] [l, r] [l,r]，求 h ( l , r ) = ∑ k = l r a k h(l,r) = \sum_{k=l}^r a_k h(l,r)=∑k=lr?ak?

2）動圖演示

3）樣例分析

??如上圖所示，只需要記錄一個前綴和，然后就可以通過一次減法將區間的值計算出來，時間復雜度 O ( 1 ) O(1) O(1)，這種就是差分的思想，

4）演算法描述

??第一個列舉，利用一個陣列sum，存盤前 i i i 個元素的和，
??第二個列舉，讀入 m m m 組資料 l , r l, r l,r，對每組資料，通過 O ( 1 ) O(1) O(1) 獲取答案，即 s u m r ? s u m l ? 1 sum_r - sum_{l-1} sumr??suml?1?，

5）原始碼詳解

int sum[maxn];
int* prefixSum(int* nums, int numsSize, int m, int *l, int *r){
    int i;
    int *ret;
    for(i = 0; i < numsSize; ++i) {
        sum[i] = nums[i];
        if(i) 
            sum[i] += sum[i-1];                 // (1) 
    }
    ret = (int *) malloc( m * sizeof(int) );    // (2) 
    for(i = 0; i < m; ++i) {
    	int leftsum = l==0? 0 : sum[l-1];       // (3) 
    	int rightsum = sum[r];
    	ret[i] = rightsum - leftsum;            // (4) 
    }
    return ret;
}

( 1 ) (1) (1) 計算前綴和；
( 2 ) (2) (2) 需要回傳的陣列；
( 3 ) (3) (3) 這里是為了防止陣列下標越界；
( 4 ) (4) (4) 核心 O ( 1 ) O(1) O(1) 的差分計算；

3、雙指標

1）問題描述

??給定一個長度為 n ( 1 ≤ n ≤ 1 0 7 ) n (1 \le n \le 10^7) n(1≤n≤107) 的字串 s s s，求一個最長的滿足所有字符不重復的子串，

2）動圖演示

3）樣例說明

??維護兩個指標 i i i 和 j j j，區間 [ i , j ] [i, j] [i,j] 內的子串，應該時刻保持其中所有字符不重復，一旦發現重復字符，就需要自增 i i i（即執行 i = i + 1 i = i + 1 i=i+1）；否則，執行 j = j + 1 j = j + 1 j=j+1，直到 j j j 不能再增加為止，
??程序中，記錄合法情況下 j ? i + 1 j - i + 1 j?i+1 的最大值，

4）演算法描述

??如上文所述，這種利用問題特性，通過兩個指標，不斷調整區間，從而求出問題最優解的演算法就叫 “尺取法”，由于利用的是兩個指標，所以又叫 “雙指標” 演算法，
??這里 “尺” 的含義，主要還是因為這類問題，最終要求解的都是連續的序列（子串），就好比一把尺子一樣，故而得名，

演算法描述如下：
??1）初始化 i = 0 i=0 i=0, j = i ? 1 j=i-1 j=i?1，代表一開始 “尺子” 的長度為 0；
??2）增加 “尺子” 的長度，即 j = j + 1 j = j +1 j=j+1；
??3）判斷當前這把 “尺子” [ i , j ] [i, j] [i,j] 是否滿足題目給出的條件：
????3.a）如果不滿足，則減小 “尺子” 長度，即 i = i + 1 i = i + 1 i=i+1，回到 3）；
????3.b）如果滿足，記錄最優解，回到 2）；

上面這段文字描述的比較官方，其實這個演算法的核心，只有一句話：滿足條件時， j j j++；不滿足條件時， i i i++；
如圖所示，當區間 [ i , j ] [i, j] [i,j] 滿足條件時，用藍色表示，此時 j j j 自增；反之閃紅，此時 i i i 自增，

5）原始碼詳解

int getmaxlen(int n, char *str, int& l, int& r) {
    int ans = 0, i = 0, j = -1, len;   // 1)
    memset(h, 0, sizeof(h));           // 2)
    while (j++ < n - 1) {              // 3)
        ++h[ str[j] ];                 // 4)
        while (h[ str[j] ] > 1) {      // 5)
            --h[ str[i] ];
            ++i;
        }
        len = j - i + 1;              
        if(len > ans)                  // 6)
            ans = len, l = i, r = j;
    }
    return ans;
}

1）初始化 i = 0, j = -1，代表 s [ i : j ] s[i:j] s[i:j] 為一個空串，從空串開始列舉；
2）需要維護一個哈希表，哈希表記錄的是當前列舉的區間 s [ i : j ] s[i:j] s[i:j] 中每個字符的個數；
3）只推進子串的右端點；
4）在哈希表中記錄字符的個數；
5）當 h[ str[j] ] > 1滿足時，代表出現了重復字符str[j]，這時候左端點 i i i 推進，直到沒有重復字符為止；
6）記錄當前最優解的長度 j - i + 1，更新；
這個演算法執行完畢，我們就可以得到最長不重復子串的長度為 a n s ans ans，并且 i i i 和 j j j 這兩個指標分別只自增 n n n 次，兩者自增相互獨立，是一個相加而非相乘的關系，所以這個演算法的時間復雜度為 O ( n ) O(n) O(n) ，

4、二分列舉

1）問題描述

??給定一個 n ( n ≤ 1 0 6 ) n(n \le 10^6) n(n≤106) 個元素的有序整型陣列和一個 t a r g e t target target 值，求在 O ( l o g 2 n ) O(log_2n) O(log2?n) 的時間內找到值為 t a r g e t target target 的整型的陣列下標，不存在則回傳 -1，

2）動圖演示

3）樣例說明

??需要找值為 5 5 5 的這個元素，
??黃色箭頭代表都是左區間端點 l l l，紅色箭頭代表右區間端點 r r r，藍色的資料為陣列資料，綠色的數字代表的是陣列下標，初始化 l = 0 l = 0 l=0， r = 7 r = 7 r=7，由于陣列有序，則可以直接折半，令 m i d = ( l + r ) / 2 = 3 mid = (l + r) / 2 = 3 mid=(l+r)/2=3，則 5 5 5 一定落入區間 [ 0 , 3 ] [0, 3] [0,3]，這時候令 r = 3 r = 3 r=3，繼續執行，直到 l > r l > r l>r 結束迭代，
??最后，當 m i d = 2 mid=2 mid=2 時，找到資料 5，

4）演算法描述

??a）令初始情況下，陣列下標從 0 開始，且陣列長度為 n n n，則定義一個區間，它的左端點是 l = 0 l=0 l=0，右端點是 r = n ? 1 r = n-1 r=n?1；
??b）生成一個區間中點 m i d = ( l + r ) / 2 mid = (l + r) / 2 mid=(l+r)/2，并且判斷 m i d mid mid 對應的陣列元素和給定的目標值的大小關系，主要有三種：
????b.1）目標值等于陣列元素，直接回傳 m i d mid mid；
????b.2）目標值大于陣列元素，則代表目標值應該出現在區間 [ m i d + 1 , r ] [mid+1, r] [mid+1,r]，迭代左區間端點： l = m i d + 1 l = mid + 1 l=mid+1；
????b.3）目標值小于陣列元素，則代表目標值應該出現在區間 [ l , m i d ? 1 ] [l, mid-1] [l,mid?1]，迭代右區間端點： r = m i d ? 1 r = mid - 1 r=mid?1；
??c）如果這時候 l > r l > r l>r，則說明沒有找到目標值，回傳 ? 1 -1 ?1；否則，回到 b）繼續迭代，

5）原始碼詳解

int search(int *nums, int numsSize, int target) {
    int l = 0, r = numsSize - 1;         // (1)
    while(l <= r) {                      // (2)
        int mid = (l + r) >> 1;          // (3)
        if(nums[mid] == target) {   
            return mid;                  // (4)
        }else if(target > nums[mid]) {
            l = mid + 1;                 // (5)
        }else if(target < nums[mid]) {
            r = mid - 1;                 // (6)
        }
    }
    return -1;                           // (7)
}

( 1 ) (1) (1) 初始化區間左右端點；
( 2 ) (2) (2) 一直迭代左右區間的端點，直到 左端點大于右端點 結束；
( 3 ) (3) (3) >> 1等價于除 2，也就是這里mid代表的是l和r的中點；
( 4 ) (4) (4) nums[mid] == target表示正好找到了這個數，則直接回傳下標mid；
( 5 ) (5) (5) target > nums[mid]表示target這個數在區間 [ m i d + 1 , r ] [mid+1, r] [mid+1,r] 中，所以才有左區間賦值如下：l = mid + 1;
( 6 ) (6) (6) target < nums[mid]表示target這個數在區間 [ l , m i d ? 1 ] [l, mid - 1] [l,mid?1] 中，所以才有右區間賦值如下：r = mid - 1;
( 7 ) (7) (7) 這一步呼應了 ( 2 ) (2) (2)，表示這不到給定的數，直接回傳 -1；

5、三分列舉

??三分列舉 類似 二分列舉 的思想，也是將區間一下子砍掉一塊基本完全不可能的塊，從而減小演算法的時間復雜度，只不過 二分列舉 解決的是單調性問題，而 三分列舉 解決的是極值問題，

6、插入排序

1）問題描述

??給定一個 n n n 個元素的陣列，陣列下標從 0 0 0 開始，采用「插入排序」將陣列按照 「升序」排列，

2）動圖演示

3）樣例說明

圖示	含義
■ 的柱形	代表尚未排好序的數
■ 的柱形	代表正在執行比較和移動的數
■ 的柱形	代表已經排好序的數
■ 的柱形	代表待執行插入的數

??我們看到，首先需要將 「第二個元素」 和 「第一個元素」 進行 「比較」，如果前者小于等于后者，則將后者進行向后 「移動」，前者則執行插入；
??然后，進行第二輪「比較」，即 「第三個元素」 和 「第二個元素」、「第一個元素」 進行 「比較」，直到 「前三個元素」 保持有序，
??最后，經過一定輪次的「比較」 和 「移動」之后，一定可以保證所有元素都是 「升序」 排列的，

4）演算法描述

整個演算法的執行程序分以下幾步：
??1）回圈迭代變數 i = 1 → n ? 1 i = 1 \to n-1 i=1→n?1；
??2）每次迭代，令 x = a [ i ] x = a[i] x=a[i]， j = i ? 1 j = i-1 j=i?1，回圈執行比較 x x x 和 a [ j ] a[j] a[j]，如果產生 x ≤ a [ j ] x \le a[j] x≤a[j] 則執行 a [ j + 1 ] = a [ j ] a[j+1] = a[j] a[j+1]=a[j]，然后執行 j = j + 1 j = j + 1 j=j+1，繼續執行 2）；否則，跳出回圈，回到 1），

5）原始碼詳解

#include <stdio.h>

int a[1010];

void Input(int n, int *a) {
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
}

void Output(int n, int *a) {
    for(int i = 0; i < n; ++i) {
        if(i)
            printf(" ");
        printf("%d", a[i]);
    }
    puts("");
}

void InsertSort(int n, int *a) {       // (1)
    int i, j; 
    for(i = 1; i < n; ++i) {
        int x = a[i];                  // (2)
        for(j = i-1; j >= 0; --j) {    // (3)
            if(x <= a[j]) {            // (4)
                a[j+1] = a[j];         // (5)
            }else
                break;                 // (6)
        }
        a[j+1] = x;                    // (7)
    }
} 

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        Input(n, a);
        InsertSort(n, a);
        Output(n, a);
    }
    return 0;
}

( 1 ) (1) (1) void InsertSort(int n, int *a)為 插入排序 的實作，代表對a[]陣列進行升序排序，
( 2 ) (2) (2) 此時a[i]前面的 i-1個數都認為是排好序的，令x = a[i]；
( 3 ) (3) (3) 逆序的列舉所有的已經排好序的數；
( 4 ) (4) (4) 如果列舉到的數a[j]比需要插入的數x大，則當前數往后挪一個位置；
( 5 ) (5) (5) 執行挪位置的 O ( 1 ) O(1) O(1) 操作；
( 6 ) (6) (6) 否則，跳出回圈；
( 7 ) (7) (7) 將x插入到合適位置；

7、選擇排序

1）問題描述

??給定一個 n n n 個元素的陣列，陣列下標從 0 0 0 開始，采用「選擇排序」將陣列按照 「升序」排列，

2）動圖演示

3）樣例說明

圖示	含義
■ 的柱形	代表尚未排好序的數
■ 的柱形	代表正在執行比較的數
■ 的柱形	代表已經排好序的數
■ 的柱形	有兩種：1、記錄最小元素 2、執行交換的元素

??我們發現，首先從 「第一個元素」 到 「最后一個元素」 中選擇出一個 「最小的元素」，和 「第一個元素」 進行 「交換」；
??然后，從 「第二個元素」 到 「最后一個元素」 中選擇出一個 「最小的元素」，和 「第二個元素」 進行 「交換」，
??最后，一定可以保證所有元素都是 「升序」 排列的，

4）演算法描述

整個演算法的執行程序分以下幾步：
??1）回圈迭代變數 i = 0 → n ? 1 i = 0 \to n-1 i=0→n?1；
??2）每次迭代，令 m i n = i min = i min=i， j = i + 1 j = i+1 j=i+1；
??3）回圈執行比較 a [ j ] a[j] a[j] 和 a [ m i n ] a[min] a[min]，如果產生 a [ j ] < a [ m i n ] a[j] \lt a[min] a[j]<a[min] 則執行 m i n = j min = j min=j，執行 j = j + 1 j = j + 1 j=j+1，繼續執行這一步，直到 j = = n j == n j==n；
??4）交換 a [ i ] a[i] a[i] 和 a [ m i n ] a[min] a[min]，回到 1），

5）原始碼詳解


#include <stdio.h>

int a[1010];

void Input(int n, int *a) {
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
}

void Output(int n, int *a) {
    for(int i = 0; i < n; ++i) {
        if(i)
            printf(" ");
        printf("%d", a[i]);
    }
    puts("");
}

void Swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void SelectionSort(int n, int *a) {  // (1)
    int i, j;
    for(i = 0; i < n - 1; ++i) {     // (2)
        int min = i;                 // (3)
        for(j = i+1; j < n; ++j) {   // (4)
            if(a[j] < a[min]) {
                min = j;             // (5)
            }
        }
        Swap(&a[i], &a[min]);        // (6) 
    }
}

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        Input(n, a);
        SelectionSort(n, a);
        Output(n, a);
    }
    return 0;
}

( 1 ) (1) (1) void SelectionSort(int n, int *a)為選擇排序的實作，代表對a[]陣列進行升序排序，
( 2 ) (2) (2) 從首元素個元素開始進行 n ? 1 n-1 n?1 次跌迭代，
( 3 ) (3) (3) 首先，記錄min代表當前第 i i i 輪迭代的最小元素的下標為 i i i，
( 4 ) (4) (4) 然后，迭代列舉第 i + 1 i+1 i+1 個元素到最后的元素，
( 5 ) (5) (5) 選擇一個最小的元素，并且存盤下標到min中，
( 6 ) (6) (6) 將第 i i i 個元素和最小的元素進行交換，

8、冒泡排序

1）問題描述

??給定一個 n n n 個元素的陣列，陣列下標從 0 0 0 開始，采用「冒泡排序」將陣列按照 「升序」排列，

2）動圖演示

3）樣例說明

圖示	含義
■ 的柱形	代表尚未排好序的數
■ 的柱形	代表正在執行比較的兩個數
■ 的柱形	代表已經排好序的數

??我們看到，首先需要將 「第一個元素」 和 「第二個元素」 進行 「比較」，如果前者大于后者，則進行 「交換」，然后再比較 「第二個元素」 和 「第三個元素」 ，以此類推，直到 「最大的那個元素」 被移動到 「最后的位置」 ，
??然后，進行第二輪「比較」，直到 「次大的那個元素」 被移動到 「倒數第二的位置」 ，
??最后，經過一定輪次的「比較」 和 「交換」之后，一定可以保證所有元素都是 「升序」 排列的，

4）演算法描述

整個演算法的執行程序分以下幾步：
??1）回圈迭代變數 i = 0 → n ? 1 i = 0 \to n-1 i=0→n?1；
??2）每次迭代，令 j = i j = i j=i，回圈執行比較 a [ j ] a[j] a[j] 和 a [ j + 1 ] a[j+1] a[j+1]，如果產生 a [ j ] > a [ j + 1 ] a[j] \gt a[j+1] a[j]>a[j+1] 則交換兩者的值，然后執行 j = j + 1 j = j + 1 j=j+1，這時候對 j j j 進行判斷，如果 j ≥ n ? 1 j \ge n-1 j≥n?1，則回到 1），否則繼續執行 2），

5）原始碼詳解

#include <stdio.h>

int a[1010];

void Input(int n, int *a) {
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
}

void Output(int n, int *a) {
    for(int i = 0; i < n; ++i) {
        if(i)
            printf(" ");
        printf("%d", a[i]);
    }
    puts("");
}

void Swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void BubbleSort(int n, int *a) {             // (1)
    bool swapped;
    int last = n;
    do {
        swapped = false;                     // (2)
        for(int i = 0; i < last - 1; ++i) {  // (3)
            if(a[i] > a[i+1]) {              // (4)
                Swap(&a[i], &a[i+1]);        // (5)
                swapped = true;              // (6)
            }
        }
        --last;
    }while (swapped);
} 

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        Input(n, a);
        BubbleSort(n, a);
        Output(n, a);
    }
    return 0;
}

( 1 ) (1) (1) void BubbleSort(int n, int *a)為冒泡排序的實作，代表對a[]陣列進行升序排序，
( 2 ) (2) (2) swapped標記本輪迭代下來，是否有元素產生了交換，
( 3 ) (3) (3) 每次冒泡的結果，會執行last的自減，所以待排序的元素會越來越少，
( 4 ) (4) (4) 如果發現兩個相鄰元素產生逆序，則將它們進行交換，保證右邊的元素一定不比左邊的小，
( 5 ) (5) (5) swap實作了元素的交換，這里需要用&轉換成地址作為傳參，
( 6 ) (6) (6) 標記更新，一旦標記更新，則代表進行了交換，所以下次迭代必須繼續，

（1-2）畫解鏈表

一、鏈表的概念

對于順序存盤的結構，如陣列，最大的缺點就是：插入和洗掉的時候需要移動大量的元素，所以，基于前人的智慧，他們發明了鏈表，

1、鏈表定義

??鏈表是由一個個結點組成，每個結點之間通過 鏈接關系 串聯起來，每個結點都有一個 后繼節點，最后一個結點的 后繼結點 為 空結點，如下圖所示：

由鏈接關系A -> B組織起來的兩個結點，B被稱為A的后繼結點，A被稱為B的前驅結點，
鏈表分為 單向鏈表、雙向鏈表、回圈鏈表 等等，本文要介紹的鏈表是 單向鏈表，
由于鏈表是由一個個結點組成，所以我們先來看下結點的實作，

2、結點結構體定義

typedef int DataType;
struct ListNode {
    DataType data;  // (1)
    ListNode *next; // (2)
};

( 1 ) (1) (1) 資料域：可以是任意型別，由編碼的人自行指定；這段代碼中，利用typedef將它和int同名，本文的 資料域 也會全部采用int型別進行講解；
( 2 ) (2) (2) 指標域：指向 后繼結點 的地址；
一個結點包含的兩部分如下圖所示：

3、結點的創建

我們通過 C語言中的庫函式malloc來創建一個 鏈表結點，然后對 資料域 和 指標域 進行賦值，代碼實作如下：

ListNode *ListCreateNode(DataType data) {
    ListNode *node = (ListNode *) malloc ( sizeof(ListNode) ); // (1)
    node->data = data;                                         // (2)
    node->next = NULL;                                         // (3)
    return node;                                               // (4)
}

( 1 ) (1) (1) 利用系統庫函式malloc分配一塊記憶體空間，用來存放ListNode即鏈表結點物件；
( 2 ) (2) (2) 將 資料域 置為函式傳參data；
( 3 ) (3) (3) 將 指標域 置空，代表這是一個孤立的 鏈表結點；
( 4 ) (4) (4) 回傳這個結點的指標，
創建完畢以后，這個孤立結點如下所示：

二、鏈表的創建 - 尾插法

那么接下來，讓我們看下如何通過一個 陣列中的資料 來創建一個鏈表，

1、演算法描述

??首先介紹 尾插法 ，顧名思義，即 從鏈表尾部插入 的意思，就是記錄一個 鏈表尾結點，然后遍歷給定陣列，將陣列元素一個一個插到鏈表的尾部，每插入一個結點，則將它更新為新的 鏈表尾結點，注意初始情況下，鏈表尾結點 為空，

2、影片演示

上圖演示的是 尾插法 的整個程序，其中：
??head 代表鏈表頭結點，創建完一個結點以后，它就保持不變了；
??tail 代表鏈表尾結點，即動圖中的 綠色結點；
??vtx 代表正在插入鏈表尾部的結點，即動圖中的 橙色結點，插入完畢以后，vtx 變成 tail；

看完這個動圖，你應該已經大致理解了 鏈表的創建程序，那么接下來，我們用程式語言來描述一下整個程序，這里采用的是 C語言 的形式，如果你是 Java、C#、Python 技術堆疊的，也可以試著寫出自己的版本，
語言并不是關鍵，思維才是關鍵，

3、原始碼詳解

C語言實作如下：

ListNode *ListCreateListByTail(int n, int a[]) {
    ListNode *head, *tail, *vtx;         // (1) 
    int idx;                              
    if(n <= 0)
        return NULL;                     // (2) 
    idx = 0;
    vtx = ListCreateNode(a[0]);          // (3) 
    head = tail = vtx;                   // (4)  
    while(++idx < n) {                   // (5) 
        vtx = ListCreateNode(a[idx]);    // (6) 
        tail->next = vtx;                // (7) 
        tail = vtx;                      // (8)  
    } 
    return head;                         // (9) 
}

對應的注釋如下：
?? ( 1 ) (1) (1) head存盤頭結點的地址，tail存盤尾結點的地址，vtx存盤當前正在插入結點的地址；
?? ( 2 ) (2) (2) 當需要創建的元素個數為 0 時，直接回傳空鏈表；
?? ( 3 ) (3) (3) 創建一個 資料域 為a[0]的鏈表結點；
?? ( 4 ) (4) (4) 由于初始情況下只有一個結點，所以將鏈表頭結點head和鏈表尾結點tail都置為vtx；
?? ( 5 ) (5) (5) 從陣列第 1 個元素 (0 - based) 開始，回圈遍歷陣列；
?? ( 6 ) (6) (6) 由于陣列中第 0 個元素已經創建過了，所以這里只需要對除了第 0 個元素以外的資料創建鏈表結點；
?? ( 7 ) (7) (7) 結點創建出來后，將當前鏈表尾結點tail的 后繼結點 置為vtx；
?? ( 8 ) (8) (8) 將最近創建的結點vtx作為新的 鏈表尾結點；
?? ( 9 ) (9) (9) 回傳鏈表頭結點；

尾插法 比較符合直觀的思維邏輯，但是就代碼量來說還是有點長（注意：在實作相同功能的情況下，代碼應該是越簡潔，越簡單越好的），
于是，我們引入了另一種創建鏈表的方式 —— 頭插法，

三、鏈表的創建 - 頭插法

1、演算法描述

??頭插法，顧名思義，就是每次從頭結點前面進行插入，但是這樣一來，就會導致插入的資料元素是逆序的，所以我們需要 逆序訪問陣列 執行插入，此所謂 負負得正 的思想，

它的特點是代碼量短，且 常數時間復雜度 低，雖然沒有 尾插法 那么直觀，但是代碼簡潔，更加容易閱讀，

2、影片演示

上圖所示的是 頭插法 的整個插入程序，其中：
??head 代表鏈表頭結點，即動圖中的 綠色結點，每新加一個結點，頭結點就變成了新加入的結點；
??tail 代表鏈表尾結點，創建完一個結點以后，它就保持不變了；
??vtx 代表正在插入鏈表頭部的結點，即動圖中的 橙色結點，插入完畢以后，vtx 變成 head；

3、原始碼詳解

ListNode *ListCreateListByHead(int n, int *a) {
    ListNode *head = NULL, *vtx;       // (1) 
    while(n--) {                       // (2) 
        vtx = ListCreateNode(a[n]);    // (3) 
        vtx->next = head;              // (4) 
        head = vtx;                    // (5) 
    } 
    return head;                       // (6) 
}

對應的注釋如下：
?? ( 1 ) (1) (1) head存盤頭結點的地址，初始為空鏈表， vtx存盤當前正在插入結點的地址；
?? ( 2 ) (2) (2) 總共需要插入 n n n 個結點，所以采用逆序的 n n n 次回圈；
?? ( 3 ) (3) (3) 創建一個元素值為a[i]的鏈表結點，注意，由于逆序，所以這里 i i i 的取值為 n ? 1 → 0 n-1 \to 0 n?1→0；
?? ( 4 ) (4) (4) 將當前創建的結點的 后繼結點 置為鏈表的頭結點head；
?? ( 5 ) (5) (5) 將鏈表頭結點head置為vtx；
?? ( 6 ) (6) (6) 回傳鏈表頭結點；

頭插法 的代碼量比 尾插法 少了三分之一，而且將 創建結點的邏輯 統一起來了，這句話什么意思呢？仔細觀察可以發現，尾插法 在實作程序中，ListCreateNode在代碼里出現了兩次，而 頭插法 只出現了一次，將流程簡化了，所以還是推薦使用 頭插法，

四、鏈表的列印

1、列印的作用

可視化 能夠幫助我們更好的理解資料結構，所以，對于一種資料結構，如何通過 輸出函式 將它 列印到控制臺 上，就成了我們接下來要做的事情，
我會用 C語言來實作，但是只要你掌握了這套自己驗證的方法，那么就算用其他語言，一樣可以驗證自己代碼的正確性，

那么，如何列印一個鏈表呢？我們可以這么思考：
??鏈表的每個結點都有一個 后繼結點 ，我們可以用A -> B代表結點B是結點A的 后繼結點，而對于最后一個結點而言，它的后繼可以用NULL表示，所以，我們可以回圈輸出所有結點并且帶上->，然后在最后加上NULL，

2、原始碼詳解

C語言實作如下：

void ListPrint(ListNode *head) {
    ListNode *vtx = head;
    while(vtx) {                      // (1)
        printf("%d -> ", vtx->data);  // (2) 
        vtx = vtx->next;              // (3)
    }
    printf("NULL\n");                 // (4)
}

對應的注釋如下：
?? ( 1 ) (1) (1) 從頭結點開始，回圈遍歷所有結點；
?? ( 2 ) (2) (2) 遍歷到的結點，將結點的 資料域 帶上->后輸出;
?? ( 3 ) (3) (3) 將 當前結點 置為 當前結點 的 后繼結點，繼續迭代；
?? ( 4 ) (4) (4) 最后輸出一個NULL，代表一個完整的鏈表；

對于上面例子中的鏈表，呼叫這個函式，得到的結果為：

1 -> 3 -> 8 -> 2 -> 6 -> NULL

3、測驗用例

例如，我們在 頭插法 的實作程序中，加上一句 鏈表的列印 陳述句，代碼實作如下：

ListNode *ListCreateListByHead(int n, int *a) {
    ListNode *head = NULL, *vtx;
    while(n--) { 
        vtx = ListCreateNode(a[n]);
        vtx->next = head;
        head = vtx;
        ListPrint(head);    /*看這里，看這里！*/
    } 
    return head;
}

運行后得到的結果如下：

6 -> NULL
2 -> 6 -> NULL
8 -> 2 -> 6 -> NULL
3 -> 8 -> 2 -> 6 -> NULL
1 -> 3 -> 8 -> 2 -> 6 -> NULL

這樣，我們就能更加進一步的確保我們實作 頭插法 這個演算法的正確性了，

驗證演算法的正確性有兩個有效的辦法：
?? ( 1 ) (1) (1) 構造大量的 測驗資料 進行輸入輸出測驗；
?? ( 2 ) (2) (2) 列印每一個操作后，資料結構的 當前狀態，看是否和預期相符；

對鏈表進行列印，就是利用了這里的第 ( 2 ) (2) (2) 點，這個方法雖然原始，但是能夠讓你對每一步操作都了然于胸，尤其是寫到后面，代碼量爆炸的時候，這個方法往往能夠讓你規避很多不必要的邏輯錯誤，

五、鏈表元素的索引

1、演算法描述

??給定一個鏈表頭結點head，并且給定一個索引值 i ( i ≥ 0 ) i (i \ge 0) i(i≥0)，求這個鏈表的第 i i i 個結點（為了和 C語言的陣列下標保持一致，我們假定鏈表頭結點代表第 0 個結點），

這實際上是一個 遍歷鏈表 的程序，我們先來看下影片演示，

2、影片演示

上圖演示的是通過遍歷，索引到第 3 個結點（下標從 0 開始計數）的程序，其中：
??head 代表鏈表頭結點；
??tail 代表鏈表尾結點；
??j / temp 代表當前列舉到的第 j ( j ≥ 0 ) j (j \ge 0) j(j≥0)個結點，即動圖中的 橙色實心結點；

3、原始碼詳解

ListNode *ListGetNode(ListNode *head, int i) {
    ListNode *temp = head;       // (1) 
    int j = 0;                   // (2) 
    while(temp && j < i) {       // (3) 
        temp = temp->next;       // (4) 
        ++j;                     // (5) 
    }
    if(!temp || j > i) {
        return NULL;             // (6) 
    }
    return temp;                 // (7) 
}

( 1 ) (1) (1) temp代表從鏈表頭開始的 游標指標，用于對鏈表進行遍歷操作；
( 2 ) (2) (2) j代表當前訪問到了第 j j j 個結點；
( 3 ) (3) (3) 如果 游標指標 非空，并且j < i，則代表還沒訪問到目標結點，繼續執行回圈；
( 4 ) (4) (4) 將 游標指標 的 后繼結點 作為新一輪的 游標指標，繼續迭代；
( 5 ) (5) (5) j自增，等價于j = j + 1;
( 6 ) (6) (6) 當 游標指標 為空，或者j > i，則說明給定的i超過了鏈表長度，回傳 空結點；
( 7 ) (7) (7) 最后，回傳找到的第i個結點；

4、測驗用例

void testListGetNode(ListNode *head) {
    int i;
    for(i = 0; i < 7; ++i) {
        ListNode *node = ListGetNode(head, i);
        if(!node)
            printf("index(%d) is out of range.\n", i);
        else 
            printf("node(%d) is %d.\n", i, node->data);
    }    
}
int main() {    
    int a[5] = {1, 3, 8, 2, 6};
    ListNode *head = ListCreateListByHead(5, a);   // (1)
    testListGetNode(head);                         // (2)
    return 0;
}

這個測驗用例，首先第 ( 1 ) (1) (1) 步，利用 頭插法 對給定陣列創建了一個鏈表；然后第 ( 2 ) (2) (2) 步，列舉 i ∈ [ 0 , 6 ] i \in [0, 6] i∈[0,6]，分別去取鏈表的第 i i i 個結點，運行結果如下：

node(0) is 1.
node(1) is 3.
node(2) is 8.
node(3) is 2.
node(4) is 6.
index(5) is out of range.
index(6) is out of range.

這表明當下標在鏈表元素個數范圍內時，能夠找到對應結點；否則，回傳的是空節點；進一步驗證了程式實作的正確性，

5、演算法分析

1）時間復雜度

索引結點的操作，最壞情況下需要遍歷整個鏈表，所以時間復雜度為 O ( n ) O(n) O(n)，

2）空間復雜度

整個索引程序只記錄了兩個變數：游標結點 和 當前索引值，和鏈表長度無關，所以空間復雜度為 O ( 1 ) O(1) O(1)，

六、鏈表元素的查找

1、演算法描述

??給定一個鏈表頭head，并且給定一個值 v v v，查找出這個鏈表上 資料域 等于 v v v 的第一個結點，

查找的程序，基本和索引類似，也是對鏈表的遍歷操作，首先請看影片演示，

2、影片演示

上圖演示的是通過遍歷，查找到值為 2 的結點的程序，其中：
??head 代表鏈表頭結點；
??tail 代表鏈表尾結點；
??j / temp 代表當前列舉到的第 j ( j ≥ 0 ) j (j \ge 0) j(j≥0)個結點，即動圖中的 橙色實心結點；

3、原始碼詳解

ListNode *ListFindNodeByValue(ListNode *head, DataType v) {
    ListNode *temp = head;       // (1) 
    while(temp) {                // (2) 
        if(temp->data == v) {
            return temp;         // (3) 
        } 
        temp = temp->next;       // (4) 
    }
    return NULL;                 // (5) 
}

( 1 ) (1) (1) temp代表從 鏈表頭 開始遍歷的 游標指標；
( 2 ) (2) (2) 如果 游標指標 非空，繼續回圈；
( 3 ) (3) (3) 一旦發現 資料域 和給定的引數v相等，立即回傳該結點對應的指標；
( 4 ) (4) (4) 否則，將 游標指標 的 后繼結點 作為新一輪的 游標指標，繼續迭代；
( 5 ) (5) (5) 一直到鏈表尾都找不到，回傳 NULL；

4、測驗用例

void testListFindNodeByValue(ListNode *head) {
    int i;
    for(i = 1; i <= 6; ++i) { 
        ListNode *node = ListFindNodeByValue(head, i); 
        if(!node)
            printf("value(%d) is not found!\n", i);
        else 
            printf("value(%d) is found!\n", i);
    }    
}
int main() {    
    int a[5] = {1, 3, 8, 2, 6};
    ListNode *head = ListCreateListByHead(5, a);   
    testListFindNodeByValue(head);
    return 0;
}

這個測驗用例，就是選擇了 [ 1 , 6 ] [1, 6] [1,6] 這六個數，然后依次利用ListFindNodeByValue去鏈表中查找，運行結果如下：

value(1) is found!
value(2) is found!
value(3) is found!
value(4) is not found!
value(5) is not found!
value(6) is found!

5、演算法分析

1）時間復雜度

查找結點的操作，最壞情況下就是找不到，需要遍歷整個鏈表，所以時間復雜度為 O ( n ) O(n) O(n)，

2）空間復雜度

整個查找程序只記錄了一個變數：游標指標，和鏈表長度無關，所以空間復雜度為 O(1)，

七、鏈表結點的插入

1、演算法描述

??給定一個鏈表頭head，并且給定一個位置 i ( i ≥ 0 ) i(i \ge 0) i(i≥0) 和一個值 v v v，求生成一個值為 v v v 的結點，并且將它插入到鏈表第 i i i 個結點之后，

首先，我們需要找到第 i i i 個位置，可以利用上文提到的 鏈表結點的索引；然后，再執行插入操作，而插入操作分為兩步：第一步就是 創建結點 的程序；第二步，是斷開之前第 i i i 個結點和第 i + 1 i+1 i+1 個結點之間的 “鏈”，并且將創建出來的結點 “鏈接” 到兩者之間，來看下動圖演示，

2、影片演示

上圖演示的是通過遍歷，將資料為 8 的結點插入到鏈表第 1 個（下標從 0 開始）結點后的程序，其中：
??head 代表鏈表頭結點；
??tail 代表鏈表尾結點；
??pre 代表待插入結點的 前驅結點，也是 游標指標 指代的結點，即動圖中的 橙色實心結點；
??aft 代表 待插入結點 的 后繼結點，即動圖中的 藍色實心結點；
??vtx 代表將要插入的結點，即動圖中的 綠色實心結點；

3、原始碼詳解

ListNode *ListInsertNode(ListNode *head, int i, DataType v) {
    ListNode *pre, *vtx, *aft;                     // (1) 
    int j = 0;                                     // (2) 
    pre = head;                                    // (3) 
    while(pre && j < i) {                          // (4) 
        pre = pre->next;                           // (5) 
        ++j;                                       // (6) 
    }
    if(!pre) { 
        return NULL;                               // (7) 
    }
    vtx = ListCreateNode(v);                       // (8) 
    aft = pre->next;                               // (9)
    vtx->next = aft;                               // (10)
    pre->next = vtx;                               // (11)
    return vtx;                                    // (12)  
}

( 1 ) (1) (1) 預先定義三個指標，當結點插入完畢后， pre -> vtx -> aft；
( 2 ) (2) (2) 定義一個計數器，當 j == i時，表明找到要插入的位置；
( 3 ) (3) (3) 從 鏈表頭結點 開始迭代遍歷鏈表；
( 4 ) (4) (4) 如果還沒有到鏈表尾，或者沒有找到插入位置則繼續回圈；
( 5 ) (5) (5) 將 游標指標 的 后繼結點 作為新一輪的 游標指標，繼續迭代；
( 6 ) (6) (6) 計數器加 1；
( 7 ) (7) (7) 元素個數不足，無法找到給定位置，回傳 NULL；
( 8 ) (8) (8) 創建一個值為v的 孤立結點；
( 9 ) → ( 11 ) (9) \to (11) (9)→(11) 這三步就是為了將vtx插入到pre -> aft之間，插入完畢后pre -> vtx -> aft，
( 12 ) (12) (12) 最后，回傳插入的那個結點；

4、測驗用例

void testListInsertNode(ListNode *head) {
    ListPrint(head);
    ListInsertNode(head, 1, 8);
    ListPrint(head);
}

int main() {    
    int a[5] = {1, 3, 2, 6};
    ListNode *head = ListCreateListByHead(4, a);
    testListInsertNode(head);
    return 0;
}

這個測驗用例，就是在原鏈表1 -> 3 -> 2 -> 6的基礎上，在第 1 個結點（0 - based）的后面插入一個值為 8 的結點，并且回傳這個結點，這個例子的運行結果如下：

1 -> 3 -> 2 -> 6 -> NULL
執行插入操作！
1 -> 3 -> 8 -> 2 -> 6 -> NULL

5、演算法分析

1）時間復雜度

雖然插入操作本身是 O ( 1 ) O(1) O(1) 的，但是這里有一步 索引結點 的操作，最壞情況下就是找不到對應的結點，需要遍歷整個鏈表，所以時間復雜度為 O ( n ) O(n) O(n)，

2）空間復雜度

整個查找和插入的程序只記錄了三個變數，和鏈表長度無關，所以空間復雜度為 O ( 1 ) O(1) O(1)，

八、鏈表結點的洗掉

1、演算法描述

??給定一個鏈表頭head，并且給定一個位置 i ( i ≥ 0 ) i(i \ge 0) i(i≥0)，將位置為 i i i 的結點洗掉，并且回傳新鏈表的頭結點（為什么要回傳頭結點？因為被刪掉的有可能是原來的頭結點），

鏈表結點的洗掉問題可以分為三種情況進行討論，如下：
( 1 ) (1) (1) 空鏈表：無法進行洗掉，直接回傳空結點；
( 2 ) (2) (2) 非空鏈表洗掉頭結點：快取下 頭結點 的 后繼結點，釋放 頭結點 記憶體，再回傳這個 后繼結點；
( 3 ) (3) (3) 非空鏈表洗掉非頭結點：通過遍歷，找到 需要洗掉結點 的 前驅結點，如果 需要洗掉結點 自身為空，則回傳 鏈表頭結點；否則，快取 需要洗掉結點 以及它的 后繼結點，將 前驅結點 指向 后繼結點，然后再釋放 需要洗掉結點 的記憶體，回傳 鏈表頭結點；

2、影片演示

上圖演示的是通過遍歷，將第 2 號結點（下標從 0 開始）洗掉的程序，其中：
??head 代表鏈表頭結點；
??tail 代表鏈表尾結點；
??pre 代表待洗掉結點的前驅結點，也是游走指標指代的結點，即動圖中的 橙色實心結點；
??aft 代表待洗掉結點的后繼結點，即動圖中的 綠色實心結點；
??del 代表將要洗掉的結點，即動圖中的 紅色實心結點；

3、原始碼詳解

ListNode *ListDeleteNode(ListNode *head, int i) {
    ListNode *pre, *del, *aft;
    int j = 0;
    if(head == NULL) {
        return NULL;              // (1)  
    }
    if(i == 0) {                  // (2) 
        del = head;               // (3)       
        head = head->next;        // (4)  
        free(del);                // (5) 
        return head;              // (6)  
    }
    
    pre = head;                   // (7)  
    while(pre && j < i - 1) {     // (8)  
        pre = pre->next;
        ++ j;
    }
    if(!pre || !pre->next) {      // (9) 
        return head;
    }
    del = pre->next;              // (10) 
    aft = del->next;              // (11) 
    pre->next = aft;              // (12) 
    free(del);                    // (13) 
    return head;                  // (14) 
}

( 1 ) (1) (1) 空鏈表，無法執行洗掉，直接回傳；
( 2 ) (2) (2) 需要洗掉鏈表第 0 個結點；
( 3 ) (3) (3) 快取第 0 個結點；
( 4 ) (4) (4) 將新的 鏈表頭結點 變為 當前頭結點 的 后繼結點；
( 5 ) (5) (5) 呼叫系統庫函式free釋放記憶體；
( 6 ) (6) (6) 回傳新的 鏈表頭結點；
( 7 ) (7) (7) 從 鏈表頭結點 開始遍歷鏈表；
( 8 ) (8) (8) 找到將要被洗掉結點的 前驅結點pre；
( 9 ) (9) (9) 如果 前驅結點 為空，或者 需要洗掉的結點 為空，則直接回傳當前 鏈表頭結點；
( 10 ) (10) (10) 快取需要洗掉的結點到del；
( 11 ) (11) (11) 快取需要洗掉結點的后繼結點到aft；
( 12 ) (12) (12) 將需要洗掉的結點的前驅結點指向它的后繼結點；
( 13 ) (13) (13) 釋放需要洗掉結點的記憶體空間；
( 14 ) (14) (14) 回傳鏈表頭結點；

4、測驗用例

void testListDeleteNode(ListNode *head) {
    ListPrint(head);
    printf("執行 2 號結點洗掉操作！\n"); 
    head = ListDeleteNode(head, 2);
    ListPrint(head);

    printf("執行 0 號結點洗掉操作！\n"); 
    head = ListDeleteNode(head, 0);
    ListPrint(head);
}

int main() {    
    int a[5] = {1, 3, 8, 2, 6};
    ListNode *head = ListCreateListByHead(5, a);   // (1)
    testListDeleteNode(head);                      // (2)
    return 0;
}

這個用例的第 ( 1 ) (1) (1) 步通過 頭插法 創建了一個 1 -> 3 -> 8 -> 2 -> 6的鏈表，然后將 2 號結點洗掉，再將頭結點洗掉，運行結果如下：

1 -> 3 -> 8 -> 2 -> 6 -> NULL
執行 2 號結點洗掉操作！
1 -> 3 -> 2 -> 6 -> NULL
執行 0 號結點洗掉操作！
3 -> 2 -> 6 -> NULL

5、演算法分析

1）時間復雜度

洗掉結點本身的時間復雜度為 O ( 1 ) O(1) O(1)，
但是由于需要查找到需要洗掉的結點，所以總的時間復雜度還是 O ( n ) O(n) O(n) 的，

2）空間復雜度

不需要用到額外空間，所以總的時間復雜度為 O ( 1 ) O(1) O(1)，

九、鏈表的銷毀

1、演算法描述

??鏈表的銷毀，就是需要將 所有結點 的記憶體空間進行釋放，并且需要將 鏈表的頭結點 置空，

鏈表的銷毀，可以理解成不斷洗掉第 0 號結點的程序，直到鏈表頭為空位置，只是一個回圈呼叫，這里就不多做介紹，有興趣的朋友可以自行實作一下，

2、影片演示

上圖所示的是 鏈表銷毀 的整個插入程序，其中：
??head 代表鏈表頭結點，即動圖中的 綠色結點，每洗掉一個結點，頭結點 就變成了之前頭結點的 后繼結點；
??tail 代表鏈表尾結點；
??temp 代表 待洗掉結點，即動圖中的 橙色結點，執行洗掉后，它的記憶體空間就釋放了；

3、原始碼詳解

void ListDestroyList(ListNode **pHead) { // (1) 
    ListNode *head = *pHead;             // (2) 
    while(head) {                        // (3) 
        head = ListDeleteNode(head, 0);  // (4) 
    }
    *pHead = NULL;                       // (5) 
}

( 1 ) (1) (1) 這里必須用二級指標，因為洗掉后需要將鏈表頭置空，普通的指標傳參無法影響外部指標變數；
( 2 ) (2) (2) 給 鏈表頭結點 解參考，即通過 鏈表頭結點的地址 獲取 鏈表頭結點；
( 3 ) (3) (3) 如果鏈表非空，則繼續回圈；
( 4 ) (4) (4) 每次迭代，洗掉 鏈表頭結點，并且回傳其 后繼結點 作為新的 鏈表頭結點；
( 5 ) (5) (5) 最后，將 鏈表頭結點 置空，這樣當函式回傳時，傳參的head才能是NULL，否則外部會得到一個記憶體已經釋放了的 野指標；

4、測驗用例

void ListDestroyList(ListNode **pHead) {
    ListNode *head = *pHead;
    while(head) {
        head = ListDeleteNode(head, 0);
    }
    *pHead = NULL;
}
void testListDestroyList(ListNode **head) {
    ListPrint(*head);
    ListDestroyList(head); 
    ListPrint(*head);
}

int main() {    
    int a[5] = {1, 3, 8, 2, 6};
    ListNode *head = ListCreateListByHead(5, a);
    testListDestroyList(&head); 
    return 0;
}

測驗用例主要是先創建了一個鏈表，然后通過不斷洗掉 鏈表頭結點，并且列印當前鏈表的程序，所以運行結果中我們可以看到整個鏈表的洗掉程序，當所有結點都被洗掉以后，head變為NULL，

1 -> 3 -> 8 -> 2 -> 6 -> NULL
3 -> 8 -> 2 -> 6 -> NULL
8 -> 2 -> 6 -> NULL
2 -> 6 -> NULL
6 -> NULL
NULL
NULL

5、演算法分析

1）時間復雜度

洗掉鏈表頭結點的程序，每次從頭部開始洗掉，所以時間復雜度為 O ( 1 ) O(1) O(1)，
總共遍歷 n n n 次洗掉，是乘法關系，所以總的時間復雜度是 O ( n ) O(n) O(n) 的，

2）空間復雜度

全程只需要一個 游標指標 用于遍歷鏈表，和鏈表長度無關，所以總的時間復雜度為 O ( 1 ) O(1) O(1)，

十、鏈表的優缺點

1、優點

記憶體分配：
??由于是鏈式存盤，隨時增加元素隨時分配記憶體，不需要像陣列那樣進行預分配存盤空間；
插入：
??當擁有鏈表某個結點的指標時，在它 后繼位置 插入一個新的結點的的時間復雜度為 O ( 1 ) O(1) O(1)；
洗掉：
??當擁有鏈表某個結點的指標時，洗掉它的 后繼結點 的時間復雜度為 O ( 1 ) O(1) O(1)；

2、缺點

索引：
??索引第幾個結點時，時間復雜度為 O ( n ) O(n) O(n)；
查找：
??查找是否存在某個結點時，時間復雜度為 O ( n ) O(n) O(n)；

（1-3）畫解堆疊

一、堆疊的概念

1、堆疊的定義

??堆疊是僅限在表尾進行插入和洗掉的 線性表，
??堆疊又被稱為后進先出（Last In First Out）的線性表，簡稱 LIFO ，

2、堆疊頂

??堆疊是一個線性表，我們把允許插入和洗掉的一端稱為 堆疊頂，

3、堆疊底

??和 堆疊頂 相對，另一端稱為 堆疊底，實際上，堆疊底的元素我們不需要關心，

二、介面

1、可寫介面

1）資料入堆疊

??堆疊的插入操作，叫做 入堆疊，也可稱為進堆疊、壓堆疊，如下圖所示，代表了三次入堆疊操作：

2）資料出堆疊

??堆疊的洗掉操作，叫做 出堆疊，也可稱為彈堆疊，如下圖所示，代表了兩次出堆疊操作：
在這里插入圖片描述

3）清空堆疊

??一直 出堆疊，直到堆疊為空，如下圖所示：

2、只讀介面

1）獲取堆疊頂資料

??對于一個堆疊來說只能獲取 堆疊頂 資料，一般不支持獲取其它資料，

2）獲取堆疊元素個數

??堆疊元素個數一般用一個額外變數存盤，入堆疊 時加一，出堆疊 時減一，這樣獲取堆疊元素的時候就不需要遍歷整個堆疊，通過 O ( 1 ) O(1) O(1) 的時間復雜度獲取堆疊元素個數，

3）堆疊的判空

??當堆疊元素個數為零時，就是一個空堆疊，空堆疊不允許 出堆疊 操作，

三、堆疊的順序表實作

1、資料結構定義

對于順序表，在 C語言中表現為陣列，在進行 堆疊的定義 之前，我們需要考慮以下幾個點：
??1）堆疊資料的存盤方式，以及堆疊資料的資料型別；
??2）堆疊的大小；
??3）堆疊頂指標；

我們可以定義一個堆疊的 結構體，C語言實作如下所示：

#define DataType int        // (1)
#define maxn 100005         // (2)

struct Stack {              // (3)
    DataType data[maxn];    // (4)
    int top;                // (5)
};

( 1 ) (1) (1) 用DataType這個宏定義來統一代表堆疊中資料的型別，這里將它定義為整型，根據需要可以定義成其它型別，例如浮點型、字符型、結構體等等；
( 2 ) (2) (2) maxn代表我們定義的堆疊的最大元素個數；
( 3 ) (3) (3) Stack就是我們接下來會用到的 堆疊結構體；
( 4 ) (4) (4) DataType data[maxn]作為堆疊元素的存盤方式，資料型別為DataType，可以自行定制；
( 5 ) (5) (5) top即堆疊頂指標，data[top-1]表示堆疊頂元素，top == 0代表空堆疊；

2、入堆疊

1、影片演示

??如圖所示，藍色元素 為原本在堆疊中的元素，紅色元素 為當前需要 入堆疊 的元素，執行完畢以后，堆疊頂指標加一，具體來看下代碼實作，

2、原始碼詳解

入堆疊 操作，算上函式引數串列，總共也才幾句話，代碼實作如下：

void StackPushStack(struct Stack *stk, DataType dt) { // (1)
    stk->data[ stk->top ] = dt;                       // (2)
    stk->top = stk->top + 1;                          // (3)
}

( 1 ) (1) (1) stk是一個指向堆疊物件的指標，由于這個介面會修改堆疊物件的成員變數，所以這里必須傳指標，否則，就會導致函式執行完畢，傳參物件沒有任何改變；
( 2 ) (2) (2) 將傳參的元素放入堆疊中；
( 3 ) (3) (3) 將堆疊頂指標自增 1；
注意，這個介面在呼叫前，需要保證 堆疊頂指標 小于 堆疊元素最大個數，即stk->top < maxn，
如果 C語言寫的熟練，我們可以把 ( 2 ) (2) (2) 和 ( 3 ) (3) (3) 合成一句話，如下：

void StackPushStack(struct Stack *stk, DataType dt) {
    stk->data[ stk->top++ ] = dt;                    
}

stk->top++表達式的值是自增前的值，并且自身進行了一次自增，

3、出堆疊

1、影片演示

??如圖所示，藍色元素 為原本在堆疊中的元素，紅色元素 為當前需要 出堆疊 的元素，執行完畢以后，堆疊頂的指標減一，具體來看下代碼實作，

2、原始碼詳解

出堆疊 操作，只需要簡單改變將 堆疊頂 減一即可，代碼實作如下：

void StackPopStack(struct Stack* stk) {
    --stk->top;
}

4、清空堆疊

1、影片演示

??如圖所示，對于陣列來說，清空堆疊的操作只需要將 堆疊頂指標 置為堆疊底，也就是陣列下標 0 即可，下次繼續 入堆疊 的時候會將之前的記憶體重復利用，

2、原始碼詳解

清空堆疊的操作只需要將 堆疊頂 指標直接指向 堆疊底 即可，對于順序表，也就是 C語言中的陣列來說，堆疊底 就是下標 0 的位置了，代碼實作如下：

void StackClear(struct Stack* stk) {
    stk->top = 0;
}

5、只讀介面

只讀介面包含：獲取堆疊頂元素、獲取堆疊大小、堆疊的判空，實作如下：

DataType StackGetTop(struct Stack* stk) {
    return stk->data[ stk->top - 1 ];      // (1)
}
int StackGetSize(struct Stack* stk) {
    return stk->top;                       // (2)
}
bool StackIsEmpty(struct Stack* stk) {
    return !StackGetSize(stk);             // (3)
}

( 1 ) (1) (1) 陣列中堆疊元素從 0 開始計數，所以實際獲取元素時，下標為堆疊頂元素下標減一；
( 2 ) (2) (2) 因為只有在入堆疊的時候，堆疊頂指標才會加一，所以它正好代表了堆疊元素個數；
( 3 ) (3) (3) 當 堆疊元素 個數為零時，堆疊為空，

6、堆疊的順序表實作原始碼

堆疊的順序表實作的原始碼如下：

/************************************* 堆疊的順序表實作 *************************************/
#define DataType int
#define bool int
#define maxn 100010

struct Stack {
    DataType data[maxn];
    int top;
};

void StackClear(struct Stack* stk) {
    stk->top = 0;
}
void StackPushStack(struct Stack *stk, DataType dt) {
    stk->data[ stk->top++ ] = dt;
}
void StackPopStack(struct Stack* stk) {
    --stk->top;
}
DataType StackGetTop(struct Stack* stk) {
    return stk->data[ stk->top - 1 ];
}
int StackGetSize(struct Stack* stk) {
    return stk->top;
}
bool StackIsEmpty(struct Stack* stk) {
    return !StackGetSize(stk);
}
/************************************* 堆疊的順序表實作 *************************************/

四、堆疊的鏈表實作

1、資料結構定義

對于鏈表，在進行 堆疊的定義 之前，我們需要考慮以下幾個點：
??1）堆疊資料的存盤方式，以及堆疊資料的資料型別；
??2）堆疊的大小；
??3）堆疊頂指標；

我們可以定義一個堆疊的 結構體，C語言實作如下所示：

typedef int DataType;             // (1)
struct StackNode;                 // (2)
struct StackNode {                // (3)
    DataType data;
    struct StackNode *next;
};
struct Stack {                    
    struct StackNode *top;        // (4)
    int size;                     // (5)
};

( 1 ) (1) (1) 堆疊結點元素的 資料域，這里定義為整型；
( 2 ) (2) (2) struct StackNode;是對鏈表結點的宣告；
( 3 ) (3) (3) 定義鏈表結點，其中DataType data代表 資料域；struct StackNode *next代表 指標域；
( 4 ) (4) (4) top作為 堆疊頂指標，當堆疊為空的時候，top == NULL；否則，永遠指向堆疊頂；
( 5 ) (5) (5) 由于 求鏈表長度 的演算法時間復雜度是 O ( n ) O(n) O(n) 的，所以我們需要記錄一個size來代表現在堆疊中有多少元素，每次 入堆疊時size自增，出堆疊時size自減，這樣在詢問堆疊的大小的時候，就可以通過 O ( 1 ) O(1) O(1) 的時間復雜度，

2、入堆疊

1、影片演示

??如圖所示，head 為堆疊頂，tail 為堆疊底，vtx 為當前需要 入堆疊 的元素，即圖中的 橙色結點，入堆疊 操作完成后，堆疊頂 元素變為 vtx，即圖中 綠色結點，

2、原始碼詳解

入堆疊 操作，其實就是類似 頭插法，往鏈表頭部插入一個新的結點，代碼實作如下：

void StackPushStack(struct Stack *stk, DataType dt) {
    struct StackNode *insertNode = (struct StackNode *) malloc( sizeof(struct StackNode) ); // (1)
    insertNode->next = stk->top;     // (2)
    insertNode->data = dt;           // (3)
    stk->top = insertNode;           // (4)
    ++ stk->size;                    // (5)
}

( 1 ) (1) (1) 利用malloc生成一個鏈表結點insertNode；
( 2 ) (2) (2) 將 當前堆疊頂 作為insertNode的 后繼結點；
( 3 ) (3) (3) 將 insertNode的 資料域 設定為傳參 dt；
( 4 ) (4) (4) 將insertNode作為 新的堆疊頂；
( 5 ) (5) (5) 堆疊元素加一；

3、出堆疊

1、影片演示

??如圖所示，head 為堆疊頂，tail 為堆疊底，temp 為當前需要 出堆疊 的元素，即圖中的 橙色結點，出堆疊 操作完成后，堆疊頂 元素變為之前 head 的 后繼結點，即圖中 綠色結點，

2、原始碼詳解

出堆疊 操作，由于鏈表頭結點就是堆疊頂，其實就是洗掉這個鏈表的頭結點的程序，代碼實作如下：

void StackPopStack(struct Stack* stk) {
    struct StackNode *temp = stk->top;  // (1)
    stk->top = temp->next;              // (2)
    free(temp);                         // (3)
    --stk->size;                        // (4)    
}

( 1 ) (1) (1) 將 堆疊頂指標 保存到temp中；
( 2 ) (2) (2) 將 堆疊頂指標 的 后繼結點 作為新的 堆疊頂；
( 3 ) (3) (3) 釋放之前 堆疊頂指標 對應的記憶體；
( 4 ) (4) (4) 堆疊元素減一；

4、清空堆疊

1、影片演示

??清空堆疊 可以理解為，不斷的出堆疊，直到堆疊元素個數為零，

2、原始碼詳解

對于鏈表而言，清空堆疊 的操作需要洗掉每個鏈表結點，代碼實作如下：

void StackClear(struct Stack* stk) {
    while(!StackIsEmpty(stk)) {       // (1)
        StackPopStack(stk);           // (2)
    }
    stk->top = NULL;                  // (3)
}

( 1 ) (1) (1) - ( 2 ) (2) (2) 的每次操作其實就是一個 出堆疊 的程序，如果堆疊不為空；則進行 出堆疊 操作，直到堆疊為空；
( 2 ) (2) (2) 然后將 堆疊頂指標 置為空，代表這是一個空堆疊了；

5、只讀介面

只讀介面包含：獲取堆疊頂元素、獲取堆疊大小、堆疊的判空，實作如下：

DataType StackGetTop(struct Stack* stk) {
    return stk->top->data;                 // (1)
}
int StackGetSize(struct Stack* stk) {
    return stk->size;                      // (2)
}

int StackIsEmpty(struct Stack* stk) {
    return !StackGetSize(stk);
}

( 1 ) (1) (1) stk->top作為 堆疊頂指標，它的 資料域 data就是 堆疊頂元素的值，回傳即可；
( 2 ) (2) (2) size記錄的是堆疊元素個數；
( 3 ) (3) (3) 當 堆疊元素 個數為零時，堆疊為空，

6、堆疊的鏈表實作原始碼

堆疊的鏈表實作原始碼如下：

/************************************* 堆疊的鏈表實作 *************************************/
typedef int DataType;

struct StackNode;
 
struct StackNode {
    DataType data;
    struct StackNode *next;
};

struct Stack {
    struct StackNode *top;
    int size;
};

void StackPushStack(struct Stack *stk, DataType dt) {
    struct StackNode *insertNode = (struct StackNode *) malloc( sizeof(struct StackNode) );
    insertNode->next = stk->top;
    insertNode->data = dt;
    stk->top = insertNode;
    ++ stk->size;
}
void StackPopStack(struct Stack* stk) {
    struct StackNode *temp = stk->top;
    stk->top = temp->next;
    --stk->size; 
    free(temp);
}

DataType StackGetTop(struct Stack* stk) {
    return stk->top->data;
}
int StackGetSize(struct Stack* stk) {
    return stk->size;
}

int StackIsEmpty(struct Stack* stk) {
    return !StackGetSize(stk);
}

void StackClear(struct Stack* stk) {
    while(!StackIsEmpty(stk)) {
        StackPopStack(stk);
    }
    stk->top = NULL; 
    stk->size = 0;
}
/************************************* 堆疊的鏈表實作 *************************************/

五、兩種實作的優缺點

1、順序表實作

??在利用順序表實作堆疊時，入堆疊 和 出堆疊 的常數時間復雜度低，且 清空堆疊 操作相比 鏈表實作 能做到 O ( 1 ) O(1) O(1)，唯一的不足之處是：需要預先申請好空間，而且當空間不夠時，需要進行擴容，擴容方式本文未提及，可以參考以下文章：《C/C++ 面試 100 例》（四）vector 擴容策略，

2、鏈表實作

??在利用鏈表實作堆疊時，入堆疊 和 出堆疊 的常數時間復雜度略高，主要是每插入一個堆疊元素都需要申請空間，每洗掉一個堆疊元素都需要釋放空間，且 清空堆疊 操作是 O ( n ) O(n) O(n) 的，直接將 堆疊頂指標 置慷訓導致記憶體泄漏，好處就是：不需要預先分配空間，且在記憶體允許范圍內，可以一直 入堆疊，沒有順序表的限制，

（1-4）畫解佇列

一、概念

1、佇列的定義

??佇列是僅限在一端進行插入，另一端 進行洗掉的 線性表，
??佇列又被稱為先進先出（First In First Out）的線性表，簡稱 FIFO ，

2、隊首

??允許進行元素洗掉的一端稱為隊首，如下圖所示：

3、隊尾

??允許進行元素插入的一端稱為隊尾，如下圖所示：

二、介面

1、可寫介面

1）資料入隊

??佇列的插入操作，叫做入隊，它是將 資料元素 從隊尾進行插入的程序，如圖所示，表示的是插入兩個資料（綠色和藍色）的程序：

2）資料出隊

??佇列的洗掉操作，叫做出隊，它是將隊首元素進行洗掉的程序，如圖所示，表示的是依次洗掉兩個資料（紅色和橙色）的程序：

3）清空佇列

??佇列的清空操作，就是一直出隊，直到佇列為空的程序，當隊首和隊尾重合時，就代表隊尾為空了，如圖所示：

2、只讀介面

1）獲取隊首資料

??對于一個佇列來說只能獲取隊首資料，一般不支持獲取其它資料，

2）獲取佇列元素個數

??佇列元素個數一般用一個額外變數存盤，入隊時加一，出隊時減一，這樣獲取佇列元素的時候就不需要遍歷整個佇列，通過 O ( 1 ) O(1) O(1) 的時間復雜度獲取佇列元素個數，

3）佇列的判空

??當佇列元素個數為零時，就是一個空隊，空隊不允許出隊操作，

三、佇列的順序表實作

1、資料結構定義

對于順序表，在 C語言中表現為陣列，在進行 佇列的定義 之前，我們需要考慮以下幾個點：
??1）佇列資料的存盤方式，以及佇列資料的資料型別；
??2）佇列的大小；
??3）隊首指標；
??4）隊尾指標；

我們可以定義一個佇列的 結構體，C語言實作如下所示：

#define DataType int       // (1)
#define maxn 100005        // (2)

struct Queue {             // (3)
    DataType data[maxn];   // (4)
    int head, tail;        // (5)
};

( 1 ) (1) (1) 用DataType這個宏定義來統一代表佇列中資料的型別，這里將它定義為整型，根據需要可以定義成其它型別，例如浮點型、字符型、結構體等等；
( 2 ) (2) (2) maxn代表我們定義的佇列的最大元素個數；
( 3 ) (3) (3) Queue就是我們接下來會用到的 佇列結構體；
( 4 ) (4) (4) DataType data[maxn]作為佇列元素的存盤方式，即陣列，資料型別為DataType，可以自行定制；
( 5 ) (5) (5) head即隊首指標，tail即隊尾指標，head == tail代表空隊；當佇列非空時，data[head]代表了隊首元素（而隊尾元素是不需要關心的）；

2、入隊

1、影片演示

??如圖所示，綠色元素 為新插入隊尾的資料，執行完畢以后，隊尾指標加一，隊首指標不變，需要注意的是，順序表實作時，隊尾指標指向的位置是沒有資料的，具體來看下代碼實作，

2、原始碼詳解

入隊操作，算上函式引數串列，總共也才幾句話，代碼實作如下：

void QueueEnqueue(struct Queue *que, DataType dt) {  // (1)
    que->data[ que->tail ] = dt;                     // (2)
    que->tail = que->tail + 1;                       // (3)
}

( 1 ) (1) (1) que是一個指向佇列物件的指標，由于這個介面會修改佇列物件的成員變數，所以這里必須傳指標，否則，就會導致函式執行完畢，傳參物件沒有任何改變；
( 2 ) (2) (2) 將傳參的元素入隊；
( 3 ) (3) (3) 將 隊尾指標 自增 1；
注意，這個介面在呼叫前，需要保證 隊尾指標 小于 佇列元素最大個數，即que->tail < maxn，
如果 C語言寫的熟練，我們可以把 ( 2 ) (2) (2) 和 ( 3 ) (3) (3) 合成一句話，如下：

void QueueEnqueue(struct Queue *que, DataType dt) {
    que->data[ que->tail++ ] = dt;
}

que->tail++運算式的值是自增前的值，并且自身進行了一次自增，

3、出隊

1、影片演示

??如圖所示，橙色元素 為原先的 隊首元素，執行出隊操作以后，黃色元素 成為當前的 隊首元素，執行完畢以后，隊首指標加一，由于是順序表實作，隊首元素前面的那些元素已經變成無效的了，具體來看下代碼實作，

2、原始碼詳解

出隊操作，只需要簡單的改變，將 隊首指標 加一即可，代碼實作如下：

void QueueDequeue(struct Queue* que) {
    ++que->head;
}

4、清空佇列

1、影片演示

??如圖所示，對于陣列來說，清空佇列的操作只需要將 隊首指標 和 隊尾指標 都置零即可，資料不需要清理，下次繼續入隊的時候會將之前的記憶體重復利用，

2、原始碼詳解

清空佇列的操作只需要將 隊首指標 和 隊尾指標 都歸零即可，代碼實作如下：

void QueueClear(struct Queue* que) {
    que->head = que->tail = 0;
}

5、只讀介面

只讀介面包含：獲取隊首元素、獲取佇列大小、佇列的判空，實作如下：

DataType QueueGetFront(struct Queue* que) {
    return que->data[ que->head ];      // (1)
}
int QueueGetSize(struct Queue* que) {
    return que->tail - que->head;       // (2)
}
int QueueIsEmpty(struct Queue* que) {
    return !QueueGetSize(que);          // (3)
}

( 1 ) (1) (1) que->head代表了 隊首指標，即 隊首下標，所以真正的 隊首元素 是 que->data[ que->head ]；
( 2 ) (2) (2) 因為只有在入隊的時候，隊尾指標 加一；出隊的時候，隊首指標 加一；所以 佇列元素個數 就是兩者的差值；
( 3 ) (3) (3) 當 佇列元素 個數為零時，佇列為空，

6、佇列的順序表實作原始碼

佇列的順序表實作的原始碼如下：

/**************************** 順序表 實作佇列 ****************************/
#define DataType int
#define maxn 100005

struct Queue {
    DataType data[maxn];
    int head, tail;
};

void QueueClear(struct Queue* que) {
    que->head = que->tail = 0;
}
void QueueEnqueue(struct Queue *que, DataType dt) {
    que->data[ que->tail++ ] = dt;
}
void QueueDequeue(struct Queue* que) {
    ++que->head;
}

DataType QueueGetFront(struct Queue* que) {
    return que->data[ que->head ];
}
int QueueGetSize(struct Queue* que) {
    return que->tail - que->head;
}
int QueueIsEmpty(struct Queue* que) {
    return !QueueGetSize(que);
}

/**************************** 順序表 實作佇列 ****************************/

四、佇列的鏈表實作

1、資料結構定義

對于鏈表，在進行 佇列的定義 之前，我們需要考慮以下幾個點：
??1）佇列資料的存盤方式，以及佇列資料的資料型別；
??2）佇列的大小；
??3）隊首指標；
??4）隊尾指標；

我們可以定義一個佇列的 結構體，C語言實作如下所示：

typedef int DataType;               // (1)
struct QueueNode;                   // (2)
struct QueueNode {                  // (3)
    DataType data;
    struct QueueNode *next;
};

struct Queue {
    struct QueueNode *head, *tail;  // (4)
    int size;                       // (5)
};

( 1 ) (1) (1) 佇列結點元素的 資料域，這里定義為整型；
( 2 ) (2) (2) struct QueueNode;是對 鏈表結點 的宣告；
( 3 ) (3) (3) 定義鏈表結點，其中DataType data代表 資料域；struct QueueNode *next代表 指標域；
( 4 ) (4) (4) head作為 隊首指標，tail作為 隊尾指標；
( 5 ) (5) (5) 由于 求鏈表長度 的演算法時間復雜度是 O ( n ) O(n) O(n) 的，所以我們需要記錄一個size來代表現在佇列中有多少元素，每次入隊時size自增，出隊時size自減，這樣在詢問佇列的大小的時候，就可以通過 O ( 1 ) O(1) O(1) 的時間復雜度，

2、入隊

1、影片演示

??如圖所示，head 為 隊首元素，tail 為 隊尾元素，vtx 為當前需要入隊的元素，即圖中的 橙色結點，入隊操作完成后，隊尾元素 變為 vtx，即圖中 綠色結點，

2、原始碼詳解

入隊操作，其實就是類似 尾插法，往鏈表尾部插入一個新的結點，代碼實作如下：

void QueueEnqueue(struct Queue *que, DataType dt) {
    struct QueueNode *insertNode = (struct QueueNode *) malloc( sizeof(struct QueueNode) );           
    insertNode->data = dt;                  // (1)
    insertNode->next = NULL;
    if(que->tail) {                         // (2)
        que->tail->next = insertNode;
        que->tail = insertNode;
    }else {
        que->head = que->tail = insertNode; // (3)
    }
    ++que->size;                            // (4)
}

( 1 ) (1) (1) 利用malloc生成一個鏈表結點insertNode，并且填充 資料域 和 指標域；
( 2 ) (2) (2) 如果當前隊尾不為空，則將insertNode作為隊尾的 后繼結點，并且更新insertNode作為新的 后繼結點；
( 3 ) (3) (3) 否則，隊首和隊尾都為insertNode；
( 4 ) (4) (4) 佇列元素加一；

3、出隊

1、影片演示

??如圖所示，head 為 隊首元素，tail 為 隊尾元素，temp 為當前需要出隊的元素，即圖中的 橙色結點，出隊操作完成后，隊首元素 變為之前 head 的 后繼結點，即圖中 綠色結點，

2、原始碼詳解

出隊操作，由于鏈表頭結點就是隊首，其實就是洗掉這個鏈表的頭結點的程序，代碼實作如下：

void QueueDequeue(struct Queue* que) {
    struct QueueNode *temp = que->head;  // (1)
    que->head = temp->next;              // (2)
    free(temp);                          // (3)
    --que->size;                         // (4)
    if(que->size == 0) {                 // (5)
        que->tail = NULL;
    } 
}

( 1 ) (1) (1) 將隊首保存到temp中；
( 2 ) (2) (2) 將隊首的 后繼結點 作為新的隊首；
( 3 ) (3) (3) 釋放之前隊首對應的記憶體；
( 4 ) (4) (4) 佇列元素減一；
( 5 ) (5) (5) 當佇列元素為空時，別忘了將隊尾指標置空；

4、清空佇列

1、影片演示

??清空佇列 可以理解為：不斷的出隊，直到 佇列元素 個數為零為止，由于鏈表結點是動態申請的記憶體，所以在沒有其它結點參考時，是需要釋放記憶體的，不像陣列那樣直接將 隊首指標 和 隊尾指標 置空就行的，

2、原始碼詳解

對于鏈表而言，清空佇列 的操作需要洗掉每個鏈表結點，代碼實作如下：

void QueueClear(struct Queue* que) {
    while(!QueueIsEmpty(que)) {     // (1)
        QueueDequeue(que);          // (2)
    }
}

( 1 ) (1) (1) - ( 2 ) (2) (2) 的每次操作其實就是一個出隊的程序，如果佇列不為空；則進行出隊操作，直到佇列為空；

5、只讀介面

只讀介面包含：獲取隊首元素、獲取佇列大小、佇列的判空，實作如下：

DataType QueueGetFront(struct Queue* que) {
    return que->head->data;              // (1)
}
int QueueGetSize(struct Queue* que) {
    return que->size;                    // (2)
}
int QueueIsEmpty(struct Queue* que) {
    return !QueueGetSize(que);           // (3)
}

( 1 ) (1) (1) que->head作為 隊首指標，它的 資料域 data就是 隊首元素的值，回傳即可；
( 2 ) (2) (2) size記錄的是 佇列元素 的個數；
( 3 ) (3) (3) 當 佇列元素 個數為零時，佇列為空，

6、佇列的鏈表實作原始碼

/**************************** 鏈表 實作佇列 ****************************/
typedef int DataType;

struct QueueNode;
struct QueueNode {
    DataType data;
    struct QueueNode *next;
};

struct Queue {
    struct QueueNode *head, *tail;
    int size;
};

void QueueEnqueue(struct Queue *que, DataType dt) {
    struct QueueNode *insertNode = (struct QueueNode *) malloc( sizeof(struct QueueNode) );
    insertNode->data = dt;
    insertNode->next = NULL;
    if(que->tail) {
        que->tail->next = insertNode;
        que->tail = insertNode;
    }else {
        que->head = que->tail = insertNode;
    }
    ++que->size;
}

void QueueDequeue(struct Queue* que) {
    struct QueueNode *temp = que->head;
    que->head = temp->next;
    free(temp);
    --que->size;
    if(que->size == 0) {
        que->tail = NULL;
    } 
}

DataType QueueGetFront(struct Queue* que) {
    return que->head->data;
}
int QueueGetSize(struct Queue* que) {
    return que->size;
}
int QueueIsEmpty(struct Queue* que) {
    return !QueueGetSize(que);
}
void QueueClear(struct Queue* que) {
    que->head = que->tail = NULL;
    que->size = 0;
}

/**************************** 鏈表 實作佇列 ****************************/

五、兩種實作的優缺點

1、順序表實作

??在利用順序表實作佇列時，入隊和出隊的常數時間復雜度低，且 清空佇列 操作相比 鏈表實作 能做到 O ( 1 ) O(1) O(1)，唯一的不足之處是：需要預先申請好空間，而且當空間不夠時，需要進行擴容，擴容方式本文未提及，可以參考以下文章：《C/C++ 面試 100 例》（四）vector 擴容策略，
??當然，可以采用 回圈佇列，能夠很大程度上避免擴容問題，但是當 入隊速度 大于 出隊速度 時，不免還是會遇到擴容的問題，

2、鏈表實作

??在利用鏈表實作佇列時，入隊和出隊的常數時間復雜度略高，主要是每插入一個佇列元素都需要申請空間，每洗掉一個佇列元素都需要釋放空間，且 清空佇列 操作是 O ( n ) O(n) O(n) 的，直接將 隊首指標 和 隊尾指標 置慷訓導致記憶體泄漏，
??好處就是：不需要預先分配空間，且在記憶體允許范圍內，可以一直入隊，沒有順序表的限制，當然，鏈表的實作明顯比陣列實作要復雜，編碼的時候容易出錯，

??需要注意的是，本文在講解程序中，順序表實作 的隊尾和 鏈表實作 的隊尾不是一個概念，順序表實作的隊尾沒有實際元素值，而鏈表實作的則不然，請自行加以區分，

（1-5）畫解雙端佇列

?? 本文已超五萬字，為了增加閱讀體驗，更多內容請收看：畫解雙端佇列，

（1-6）畫解哈希表

在這里插入圖片描述

?? 本文已超五萬字，為了增加閱讀體驗，更多內容請收看：畫解哈希表，

第二章 樹 （2-1）畫解樹

?? 本文已超五萬字，為了增加閱讀體驗，更多內容請收看：畫解樹，

（2-2）畫解二叉樹

?? 本文已超五萬字，為了增加閱讀體驗，更多內容請收看：畫解二叉樹，

（2-3）畫解二叉搜索樹

?? 本文已超五萬字，為了增加閱讀體驗，更多內容請收看：畫解二叉搜索樹，

（2-4）畫解堆

?? 本文已超五萬字，為了增加閱讀體驗，更多內容請收看：畫解堆，

（2-5）畫解AVL樹

?? 本文已超五萬字，為了增加閱讀體驗，更多內容請收看：畫解二叉平衡樹，

（2-6）畫解線段樹

?? 本文已超五萬字，為了增加閱讀體驗，更多內容請收看：畫解線段樹，

（2-7）畫解字典樹

在這里插入圖片描述

?? 本文已超五萬字，為了增加閱讀體驗，更多內容請收看：畫解字典樹，

（2-8）畫解霍夫曼樹

在這里插入圖片描述

?? 本文已超五萬字，為了增加閱讀體驗，更多內容請收看：畫解霍夫曼樹，

（2-9）畫解并查集

?? 本文已超五萬字，為了增加閱讀體驗，更多內容請收看：畫解并查集，

第三章 圖 （3-1）畫解圖

?? 本文已超五萬字，為了增加閱讀體驗，更多內容請收看：畫解圖，

（3-2）畫解二分匹配

?? 本文已超五萬字，為了增加閱讀體驗，更多內容請收看：畫解二分匹配，

（3-3）畫解最短路

在這里插入圖片描述

?? 本文已超五萬字，為了增加閱讀體驗，更多內容請收看：畫解最短路，

（3-4）畫解最小生成樹

?? 本文已超五萬字，為了增加閱讀體驗，更多內容請收看：畫解最小生成樹，

（3-5）畫解強連通

?? 本文已超五萬字，為了增加閱讀體驗，更多內容請收看：畫解強連通，

??有關🌳《畫解資料結構》🌳 的原始碼均開源，鏈接如下：《畫解資料結構》

??相信看我文章的大多數都是「大學生」，能上大學的都是「精英」，那么我們自然要「精益求精」，如果你還是「大一」，那么太好了，你擁有大把時間，當然你可以選擇「刷劇」，然而，「學好演算法」，三年后的你自然「不能同日而語」，
??那么這里，我整理了「幾十個基礎演算法」 的分類，點擊開啟：

🌌《演算法入門指引》🌌
??如果鏈接被屏蔽，或者有權限問題，可以私聊作者解決，
??大致題集一覽：

??為了讓這件事情變得有趣，以及「照顧初學者」，目前題目只開放最簡單的演算法 「列舉系列」 （包括：線性列舉、雙指標、前綴和、二分列舉、三分列舉），當有一半成員刷完 「列舉系列」 的所有題以后，會開放下個章節，等這套題全部刷完，你還在群里，那么你就會成為「夜深人靜寫演算法」專家團 的一員，
??不要小看這個專家團，三年之后，你將會是別人 望塵莫及 的存在，如果要加入，可以聯系我，考慮到大家都是學生， 沒有「主要經濟來源」，在你成為神的路上，「不會索取任何」，

🔥讓天下沒有難學的演算法🔥
C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
入門級C語言真題匯總 🧡《C語言入門100例》🧡
幾張動圖學會一種資料結構 🌳《畫解資料結構》🌳
組團學習，抱團生長 🌌《演算法入門指引》🌌
競賽選手金典圖文教程 💜《夜深人靜寫演算法》💜

粉絲專屬福利

語言入門：《光天化日學C語言》(示例代碼)
語言訓練：《C語言入門100例》試用版
資料結構：《畫解資料結構》原始碼
演算法入門：《演算法入門》指引
演算法進階：《夜深人靜寫演算法》演算法模板

👇🏻 驗證碼 可通過搜索下方 公眾號 獲取👇🏻

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/302556.html

標籤：其他

上一篇：二進制方式搭建Kubernetes高可用集群（超豐富的組件概念理論總結）

下一篇：??是你的期末大作業嗎？Java基礎語法就能實作的圖書管理系統 ??(建議收藏)

??六萬字《演算法和資料結構》之《畫解資料結構》總綱，演算法零基礎教程??(建議收藏)

前言

一、順序表的概念

1、順序存盤

2、存盤方式

3、長度和容量

4、資料結構定義

二、常用介面實作

1、只讀介面

1）索引

2）查找

3）獲取長度

2、可寫介面

1）插入

2）洗掉

三、優缺點

1、優點

2、缺點

四、陣列相關演算法

1、線性列舉

1）問題描述

2）動圖演示

3）示例說明

4）演算法描述

5）原始碼詳解

2、前綴和差分

1）問題描述

2）動圖演示

3）樣例分析

4）演算法描述

5）原始碼詳解

3、雙指標

1）問題描述

2）動圖演示

3）樣例說明

4）演算法描述

5）原始碼詳解

4、二分列舉

1）問題描述

2）動圖演示

3）樣例說明

4）演算法描述

5）原始碼詳解

5、三分列舉

6、插入排序

1）問題描述

2）動圖演示

3）樣例說明

4）演算法描述

5）原始碼詳解

7、選擇排序

1）問題描述

2）動圖演示

3）樣例說明

4）演算法描述

5）原始碼詳解

8、冒泡排序

1）問題描述

2）動圖演示

3）樣例說明

4）演算法描述

5）原始碼詳解

一、鏈表的概念

1、鏈表定義

2、結點結構體定義

3、結點的創建

二、鏈表的創建 - 尾插法

1、演算法描述

2、影片演示

3、原始碼詳解

三、鏈表的創建 - 頭插法

1、演算法描述

2、影片演示

3、原始碼詳解

四、鏈表的列印

1、列印的作用

2、原始碼詳解

3、測驗用例

五、鏈表元素的索引

1、演算法描述