時間：2021年3月9日13:43:06
作者：along

參考1：
https://www.runoob.com/data-structures/data-structures-tutorial.html
參考2：
https://weread.qq.com/web/reader/f66323605a0426f66836979ka87322c014a87ff679a21ea

c語言的特點是面向過程，有它的應用領域，但也有局限性：在編寫某些類型的大程序是，沒有高級語言快捷和方便。

一、緒論

由來

• 由現(xiàn)實問題引申而來。人們發(fā)明計算機，起初的目的就是為計算數(shù)值提供便利。
• 數(shù)學理論可以抽象一般的生活問題，從而建立“模型”；根據(jù)數(shù)學模型，我們可以設計數(shù)據(jù)結(jié)構(gòu)，并配套相應的算法（可以探討優(yōu)化）；最后確定數(shù)據(jù)類型，編寫對應的程序流程、結(jié)構(gòu)（順序、判斷、循環(huán)、跳轉(zhuǎn)等），由此達到解決實際問題的目的。
• 所以這個過程描述為：

現(xiàn)實問題,抽象為===>
數(shù)學模型（解題思路），設計===>
數(shù)據(jù)結(jié)構(gòu)（算法），編碼===>
數(shù)據(jù)類型（程序），運行===>
結(jié)果

• 描述非數(shù)值計算問題的數(shù)學模型不再是數(shù)學方程，而是諸如表、樹、圖之類的數(shù)據(jù)結(jié)構(gòu)

1.1 概念

• 數(shù)據(jù)
• 數(shù)據(jù)元素
  一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項（Data Item）組成。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點、頂點、記錄等；
• 數(shù)據(jù)項
  數(shù)據(jù)項（Data Item）指不可分割的、具有獨立意義的最小數(shù)據(jù)單位，數(shù)據(jù)項有時也稱為字段（field）或域；
• 數(shù)據(jù)結(jié)構(gòu)
  數(shù)據(jù)元素都不會是孤立的，在它們之間存在著這樣或那樣的關系，這種數(shù)據(jù)元素之間存在的關系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)；
• 數(shù)據(jù)類型
  在高級程序設計語言中用以限制變量取值范圍和可能進行的操作的總和稱為數(shù)據(jù)類型；
• 抽象數(shù)據(jù)類型
  抽象數(shù)據(jù)類型（Abstract Data Type，ADT）是指一個數(shù)學模型及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義取決于它的一組邏輯特性，而與其在計算機內(nèi)部如何表示和實現(xiàn)無關。

1.2 數(shù)據(jù)結(jié)構(gòu)的分類

（1）集合結(jié)構(gòu)：在集合結(jié)構(gòu)中，數(shù)據(jù)元素之間的關系是“屬于同一個集合”。數(shù)據(jù)元素之間除了同屬一個集合外，不存在其他關系。
（2）線性結(jié)構(gòu)：在該結(jié)構(gòu)中，數(shù)據(jù)元素除了同屬于一個集合外，數(shù)據(jù)元素之間還存在著一對一的順序關系。
（3）樹形結(jié)構(gòu)：該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對多的層次關系。（4）圖狀結(jié)構(gòu)：該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對多的任意關系，圖狀結(jié)構(gòu)也稱為網(wǎng)狀結(jié)構(gòu)。
（4）圖狀結(jié)構(gòu)：該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對多的任意關系，圖狀結(jié)構(gòu)也稱為網(wǎng)狀結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)有兩個要素：一是數(shù)據(jù)元素，二是數(shù)據(jù)元素之間的關系。

1.3 邏輯存儲和物理存儲

• 數(shù)據(jù)的邏輯結(jié)構(gòu)可以看做從具體問題抽象出來的數(shù)學模型，它與數(shù)據(jù)的存儲無關；
• 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的存儲表示（又稱映像）稱為數(shù)據(jù)的物理結(jié)構(gòu)，數(shù)據(jù)的存儲方法包括順序存儲和鏈式存儲。

1.4 算法

1.4.1 特性

• 有窮性
• 確定性
• 可行性
• 輸入
• 輸出

1.4.2 要求

• 確定性
• 可讀性
• 健壯性
• 高效性

1.4.3 基本操作

• 查找
• 讀取
• 插入
• 刪除
• 更新

1.4.4 算法描述

• 自然語言
• 框圖
• 偽代碼
• 高級程序語言

1.4.5 算法分析

• 硬件的速度。即主機本身運行速度，主要與CPU的主頻和字長有關，也與主機系統(tǒng)采用的技術有關，如多機系統(tǒng)的運算速度一般比單機系統(tǒng)要快。
• 實現(xiàn)算法的程序設計語言。實現(xiàn)算法的語言的級別越高，其執(zhí)行效率相對就越低。
• 編譯程序所生成目標代碼的質(zhì)量。代碼優(yōu)化較好的編譯程序所生成的程序質(zhì)量較高。
• 算法所采用的策略。采用不同設計思路與解題方法，其時空代價是不同的，一般情況下時間指標與空間指標常常是矛盾的兩個方面。
• 問題的規(guī)模。例如，求100以內(nèi)的素數(shù)與求1 000以內(nèi)的素數(shù)的執(zhí)行時間必然不同。

（1）時間復雜度
同一問題的不同的算法，通常的做法是：

• 從算法中選取一種對于所研究的問題來說是基本運算的原操作，以該原操作重復執(zhí)行的次數(shù)為算法的時間度量；
• 一般情況下，算法中原操作重復執(zhí)行的次數(shù)是該算法所處理問題的規(guī)模n的某個函數(shù)T(n)。
• 公式定義
  定義（大Ο記號）：如果存在兩個正常數(shù)c和n0，使得對所有的n（n≥n0），有：
  T(n) ≤ c*f (n)
  則T(n)＝Ο( f (n))。
  例如，一個程序的實際執(zhí)行時間為T(n)＝2.7n3+3.8n2+5.3，則T(n)＝Ο(n3)。使用大Ο記號表示的算法的時間復雜度稱為算法的漸進時間復雜度（AsymptoticTimeComplexity）。
• Ο(1)表示常數(shù)級時間復雜度，表明這樣的算法執(zhí)行時間是恒定的，不隨問題規(guī)模的擴大而增長；
• O(log2n)，對數(shù)級復雜度；
• Ο(n)，線性復雜度；
• Ο(n2)和Ο(n3)，分別為平方級和立方級復雜度；
• Ο(2n)，指數(shù)級復雜度；
• 增長速度的快慢次序為：Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<Ο(2n)

（2）空間復雜度
空間復雜度一個程序的空間復雜度（Space Complexity）是指程序運行從開始到結(jié)束所需的存儲量與問題規(guī)模的對應關系，記做：S(n)=Ο(f(n))

二、線性表

線性表（Linear List）是一種線性結(jié)構(gòu)

三、棧和隊列

• 棧和隊列是軟件設計中常用的兩種數(shù)據(jù)結(jié)構(gòu)，它們的邏輯結(jié)構(gòu)和線性表相同。
• 棧：先進后處的受限線性表
• 隊列：先進先出的受限線性表

3.1 棧

• 棧（Stack）是限制在表的一端進行插入和刪除操作的線性表；
• 允許進行插入、刪除操作的這一端稱為棧頂（Top）；
• 固定端稱為棧底；
• 當表中沒有元素時稱為空棧。
• 也稱作FILO（First-In Last-Out）表

3.1.1 順序棧

利用順序存儲方式實現(xiàn)的棧稱為順序棧。
（1）例子：

#define MAX_NUM 100
typedef struct stack{
  int ele[MAC_NUM];
  int top;
}stack_t;

序號為0的元素為棧底，top記錄的時棧頂元素的序號。
（2）順序棧初始化

stack_t *init_stack(void)
{
  stack_t *p;
  p = (stack_t *)malloc(sizeof(stack_t ));
  p->top = -1;
  return p;
}

3.1.2 鏈棧

用鏈式存儲結(jié)構(gòu)實現(xiàn)的棧稱為鏈棧。
用單鏈表來實現(xiàn)。
應用：

• 十進制數(shù)轉(zhuǎn)換為任意進制數(shù)
• 表達式求值
  表達式求值是程序設計語言編譯中一個最基本的問題。
  一個表達式是由運算數(shù)（operand）、運算符（operator）和界限符（delimiter）組成的有意義的式子。

運算符按優(yōu)先級排列優(yōu)先級為：（）→ ^ → *、/、%→ +、-

3.1.3 棧與遞歸

例子：

• 數(shù)學里的階乘
• 遞歸的數(shù)據(jù)結(jié)構(gòu)的處理
• Hanoi塔問題
  假設有三個分別命名為X、Y、Z的塔座，在塔座X上疊放著n個直徑大小各不相同、小盤壓在大盤之上的圓盤堆?，F(xiàn)要求將塔座X上的n個圓盤移至塔座Z上，并仍按同樣的順序疊放。移動圓盤時必須遵循下列規(guī)則：
  （1）每一次只能夠移動一個圓盤；
  （2）圓盤可以插放在X、Y和Z中任何一個塔座上；
  （3）任何時刻都不能將一個較大的圓盤壓在較小的圓盤之上。
• 遞歸問題特點
  （1）原問題可以層層分解為類似的子問題，且子問題比原問題的規(guī)模更??；（2）規(guī)模最小的子問題具有直接解，即不需要再調(diào)用自身。
• 二階菲波那切數(shù)列

3.2 隊列

• “先進先出”（First-In First-Out，F(xiàn)IFO）的數(shù)據(jù)結(jié)構(gòu)
• 插入在表一端進行，而刪除在表的另一端進行，這種數(shù)據(jù)結(jié)構(gòu)被稱為隊或隊列（Queue）；
• 允許插入的一端稱為隊尾（rear）；
• 允許刪除的一端稱為隊頭（front）。

3.2.1 順序隊

用順序存儲結(jié)構(gòu)來存儲數(shù)據(jù)。

typedef int data_type 
#define MAX_SIZE 10
typedef struct queue{
    data_type data[MAX_SIZE];
    int front, rear;    //隊頭和隊尾
    int num;    //元素個數(shù)
}queue_t;

• 隊尾指針已經(jīng)移到了最后，再有元素入隊就會出現(xiàn)溢出，而事實上此時隊中并未真的“滿員”，這種現(xiàn)象為“假溢出”；
• 解決假溢出的方法之一是將隊列的數(shù)據(jù)區(qū)data[0..MAXSIZE-1]看成頭尾相接的循環(huán)結(jié)構(gòu)，頭尾指針的關系不變，將其稱為“循環(huán)隊列”。

3.2.2 鏈隊列

隊列采用帶頭結(jié)點的鏈表結(jié)構(gòu)

3.3 隊列的應用

• 鍵盤輸入事件處理

四、串和數(shù)組

串線性表：以字符串為數(shù)據(jù)元素的線性表
數(shù)組線性表：以數(shù)組為數(shù)據(jù)元素的線性表

4.1 串

• 串（String）是由零個或多個任意字符組成的字符序列；
• 串中任意連續(xù)的字符組成的子序列稱為該串的子串；
• 包含子串的串相應地稱為主串。

4.1.1 順序存儲結(jié)構(gòu)（定長）

#define MAX_SIZE 256
typedef struct str{
    char data[MAX_SIZE];
    int len;
}str_t;

//或者
char s[MAXP_SIZE];

子串的定位操作通常稱做串的模式匹配。
基本運算：

• 串連接
• 求子串
• 串比較
• 串定位

4.1.2 對分配存儲結(jié)構(gòu)

typedef struct str{
    char *data_p;
    int len;
}str_t;

動態(tài)分配內(nèi)存，更加靈活，解決了可能“溢出”的問題。

4.2 數(shù)組

• 數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)有序集，即，一旦定義了數(shù)組的維數(shù)和每維的上、下限，數(shù)組的元素個數(shù)就固定了，而且數(shù)組中的每一個元素也由唯一的一組下標來標識。因此，在數(shù)組上一般不能做插入、刪除數(shù)據(jù)元素的操作。對數(shù)組的操作只有取值和賦值。

4.2.1 存儲結(jié)構(gòu)

• 存儲二維數(shù)組時，存儲二維數(shù)組時，一般有兩種存儲方式；
• 一種是以行序為主序（或先行后列）的順序存儲方式，即從第一行開始存放，一行存放完了接著存放下一行，直到最后一行為止，如BASIC、PASCAL、COBOL、C等程序設計語言中都是以行序為主序的；
• 另一種是以列序為主序（先列后行）的順序存儲方式，即一列一列地存儲，如FORTRAN語言就是采用以列序為主序的存儲分配。

4.2.2 稀疏矩陣

稀疏矩陣（Sparse Matrix）是指矩陣中大多數(shù)元素為零元素的矩陣。

15  0   0   22  0   -15
0   11  3   0   0   0
0   0   0   6   0   0
0   0   0   0   0   0
91  0   0   0   0   0
0   0   0   0   0   0

三元組表

    | i i   v
------------------
1   | 1 1   15
2   | 1 4   22
3   | 1 6   -15
4   | 2 2   11
5   | 2 3   3
6   | 3 4   6
7   | 5 1   91

五、樹與二叉樹

典型的非線性結(jié)構(gòu)。

• 線性結(jié)構(gòu)中結(jié)點具有唯一前趨和唯一后繼的關系，而非線性結(jié)構(gòu)中結(jié)點之間的關系不再具有這種唯一性；
• 樹形結(jié)構(gòu)中結(jié)點間的關系是前趨唯一而后繼不唯一，即元素之間是一對多的關系；
• 在圖結(jié)構(gòu)中結(jié)點之間的關系是前趨、后繼均不唯一，因此也就無所謂前趨、后繼了

5.1 樹的基本概念

• 樹（Tree）是n（n≥0）個結(jié)點的有限集合
• 當n=0時，稱這棵樹為空樹；
• 當n>0時，該集合滿足以下條件：
  （1）有且只有一個特殊的結(jié)點稱為樹的根（root），根結(jié)點沒有直接前趨結(jié)點，但有零個或多個直接后繼結(jié)點；（這里的前趨、后繼暫時沿用線性表中的概念，在樹中，前趨、后繼其實是另外的術語）。
  （2）除根結(jié)點之外的其余n-1個結(jié)點被分成m（m>0）個互不相交的集合T1, T2,…, Tm，其中每一個集合Ti（1≤i≤m）本身又是一棵樹。樹T1, T2, …, Tm稱為根結(jié)點的子樹；
• 樹的二元組的形式：T=(D, R)
  其中，D為樹T中結(jié)點的集合，R為樹中結(jié)點之間關系的集合。
• 當樹T為空樹時，即D=Φ；
• 當樹T不為空樹時，有：D={Root}∪DF其中，Root為樹T的根結(jié)點，DF為樹T的根Root的子樹集合；

術語：
（1）結(jié)點：包含一個數(shù)據(jù)元素及若干指向其他結(jié)點的分支信息的數(shù)據(jù)結(jié)構(gòu)。
（2）結(jié)點的度：結(jié)點所擁有的子樹的個數(shù)稱為該結(jié)點的度。
（3）葉子結(jié)點：度為0的結(jié)點稱為葉子結(jié)點，或者稱為終端結(jié)點。
（4）分支結(jié)點：度不為0的結(jié)點稱為分支結(jié)點，或者稱為非終端結(jié)點。一棵樹的結(jié)點除葉子結(jié)點外，其余的結(jié)點都是分支結(jié)點。
（5）孩子結(jié)點、雙親結(jié)點、兄弟結(jié)點：樹中一個結(jié)點的子樹的根結(jié)點稱為這個結(jié)點的孩子結(jié)點，這個結(jié)點稱為它孩子結(jié)點的雙親結(jié)點。具有同一個雙親結(jié)點的孩子結(jié)點互稱為兄弟結(jié)點。
（6）路徑、路徑長度：設n1, n2, …, nk為一棵樹的結(jié)點序列，若結(jié)點ni是ni+1的雙親結(jié)點（1≤i <k），則把n1, n2, …, nk稱為一條由n1至nk的路徑。這條路徑的長度是k-1。
（7）祖先、子孫：在樹中，如果有一條路徑從結(jié)點M到結(jié)點N，那么M就稱為N的
（8）結(jié)點的層次：規(guī)定樹的根結(jié)點的層數(shù)為1，其余結(jié)點的層數(shù)等于它的雙親結(jié)點的層數(shù)加1。
（9）樹的深度（高度）：樹中所有結(jié)點的層次的最大數(shù)稱為樹的深度。（10）樹的度：樹中所有結(jié)點的度的最大值稱為該樹的度。
（11）有序樹和無序樹：如果一棵樹中結(jié)點的各子樹從左到右是有次序的，即若交換了某結(jié)點各子樹的相對位置，則構(gòu)成不同的樹，稱這棵樹為有序樹；反之，則稱為無序樹。
（12）森林：m（m≥0）棵不相交的樹的集合稱為森林。自然界中樹和森林是不同的概念，但在數(shù)據(jù)結(jié)構(gòu)中，樹和森林只有很小的差別。任何一棵樹，刪去根結(jié)點就變成了森林；反之，給森林增加一個統(tǒng)一的根結(jié)點，森林就變成了一棵樹。

操作：

• 初始化
• 獲取根節(jié)點
• 獲取父節(jié)點
• 獲取兄弟節(jié)點
• 插入節(jié)點
• 刪除節(jié)點
• 遍歷樹中的所有節(jié)點

5.2 二叉樹

每個結(jié)點只能含有0、1或2個孩子結(jié)點，而且其孩子結(jié)點有左右之分的樹。

5.2.1 二叉樹的五種形態(tài)

• 空二叉樹
• 只有根節(jié)點的二叉樹
• 只有左子二叉樹的二叉樹
• 只有右子二叉樹的二叉樹
• 左、右子二叉樹都存在的二叉樹

5.2.2 概念

• 滿二叉樹
  如果所有分支結(jié)點都存在左子樹和右子樹，并且所有葉子結(jié)點都在同一層上，這樣的一棵二叉樹稱為滿二叉樹。
• 完全二叉樹
  完全二叉樹的特點是：葉子結(jié)點只能出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點集中在樹的左部。
• 二叉樹性質(zhì)
  （1）性質(zhì)1
  一棵非空二叉樹的第i層上最多有2i-1個結(jié)點（i≥1）。
  （2）性質(zhì)2
  一棵深度為k的二叉樹中，最多具有2k-1個結(jié)點。
  （3）性質(zhì)3
  對于一棵非空的二叉樹，如果葉子結(jié)點數(shù)為n0，度數(shù)為2的結(jié)點數(shù)為n2，則有：n0=n2+1。
  （4）性質(zhì)4
  具有n個結(jié)點的完全二叉樹的深度[log 2 n] + 1（[]符號表示取整）。
  （5）性質(zhì)5
  對于具有n個結(jié)點的完全二叉樹，如果按照從上至下和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點從1開始順序編號，則對于任意的編號為i的結(jié)點，有：
  a：如果i > 1，則該結(jié)點i的雙親結(jié)點的編號為[插圖]；如果i=1，則該結(jié)點是根結(jié)點，無雙親結(jié)點。
  b：如果2i≤n，則該結(jié)點i的左孩子結(jié)點的編號為2i；如果2i >n，則該結(jié)點i無左孩子。
  c：如果2i+ 1≤n，則該結(jié)點i的右孩子結(jié)點的編號為2i+1；如果2i+ 1>n，則該結(jié)點i無右孩子。

5.2.3 二叉樹的存儲結(jié)構(gòu)

• 順序存儲結(jié)構(gòu)
  用一組連續(xù)的存儲單元存放二叉樹中的結(jié)點。
  完全二叉樹和滿二叉樹采用順序存儲的話，可以利用數(shù)組元素的下標值確定結(jié)點在二叉樹中的位置及結(jié)點之間的關系。
• 鏈式存儲結(jié)構(gòu)
  二叉鏈表存儲。鏈表中每個結(jié)點由三個域組成，除了數(shù)據(jù)域外，還有兩個指針域，分別用來給出該結(jié)點左孩子和右孩子所在的鏈結(jié)點的存儲地址。

typedef int deat_type
typedef struct node{
    deat_type data;
    struct node *l_child;
    struct node *r_child;
}node_t;

三叉鏈表存儲：每個結(jié)點由四個域組成，具體結(jié)構(gòu)為：其中，data、lchild及rchild三個域的意義同二叉鏈表結(jié)構(gòu)；parent域為指向該結(jié)點雙親結(jié)點的指針。

typedef int deat_type
typedef struct node{
    deat_type data;
    struct node *l_child;   //指向左子節(jié)點
    struct node *r_child;   //指向有子節(jié)點
    struct node *parent;    //指向父節(jié)點
}node_t;

5.2.4 二叉樹的基本操作

• 建立空二叉樹
• 由根節(jié)點和左右子二叉樹合成新的二叉樹
• 插入左二叉樹
• 插入右二叉樹
• 刪除左二叉樹
• 刪除有二叉樹
• 查找節(jié)點
• 遍歷二叉樹的節(jié)點

5.2.5 二叉樹的遍歷

• 二叉樹的遍歷是指按照某種順序訪問二叉樹中的每個結(jié)點，使每個結(jié)點被訪問一次且僅被訪問一次。
• 若以D、L、R分別表示訪問根結(jié)點、遍歷根結(jié)點的左子樹、遍歷根結(jié)點的右子樹，則二叉樹的遍歷方式有六種：DLR、LDR、LRD、DRL、RDL和RLD。- - 由于左右具有對稱性，因此可以限定先左后右，則只有前三種方式，即DLR（稱為前序遍歷或先序遍歷）、LDR（稱為中序遍歷）和LRD（稱為后序遍歷）。

5.2.6 先序遍歷（DLR）及其算法

訪問過程
（1）訪問根結(jié)點；
（2）先序遍歷根結(jié)點的左子樹；
（3）先序遍歷根結(jié)點的右子樹
可見這個過程包含遞歸形式。例子：

//二叉樹測試
#include <stdio.h>
#include <stdlib.h>
//二叉鏈表
typedef int data_type;
typedef struct node{
    data_type data;
    struct node *l_child;
    struct node *r_child;
}node_t;
//創(chuàng)建根節(jié)點
node_t *node_creat_root(void)
{
    node_t *ret = (node_t*)malloc(sizeof(node_t));
    ret->l_child = NULL;
    ret->r_child = NULL;
    return ret;
}
//向節(jié)點插入左節(jié)點
node_t *tree_insert_l(node_t *node_p)
{
    node_t *l = (node_t *)malloc(sizeof(node_t));
    l->l_child = NULL;
    l->r_child = NULL;
    node_p->l_child = l;
    return l;
}
//向節(jié)點插入左節(jié)點
node_t *tree_insert_r(node_t *node_p)
{
    node_t *r = (node_t *)malloc(sizeof(node_t));
    r->l_child = NULL;
    r->r_child = NULL;
    node_p->r_child = r;
    return r;
}
//先序遍歷二叉樹節(jié)點，打印數(shù)據(jù)（用遞歸方法比較合適）
void tree_scan_dlr(node_t *root)
{
    printf("%c\n", root->data);
    if(root->l_child != NULL)
    {
        tree_scan_dlr(root->l_child);
    }
    
    if(root->r_child != NULL)
    {
        tree_scan_dlr(root->r_child);
    }
}
int main()  
{     
    node_t *tree_p;
    tree_p = node_creat_root();
    tree_p->data = 'a';
    node_t *l = tree_insert_l(tree_p);
    l->data = 'b';
    node_t *r = tree_insert_r(tree_p);
    r->data = 'c';
    node_t *n1 = tree_insert_l(l);
    n1->data = 'd';
    node_t *n2 = tree_insert_r(l);
    n2->data = 'e';
    node_t *n3 = tree_insert_l(r);
    n3->data = 'f';
    node_t *n4 = tree_insert_r(r);
    n4->data = 'g';
    tree_scan_dlr(tree_p);  
    return 0;    
}  

也有非遞歸先序遍歷的方式（通過“輔助?！钡乃枷雽崿F(xiàn)）

5.2.6 中序遍歷（LDR）及其算法

中序遍歷（LDR）的遞歸過程為：若二叉樹為空，遍歷結(jié)束。否則：
（1）中序遍歷根結(jié)點的左子樹；
（2）訪問根結(jié)點；
（3）中序遍歷根結(jié)點的右子樹。

5.2.7 后續(xù)遍歷（LRD）及其算法

后序遍歷（LRD）的遞歸過程為：若二叉樹為空，遍歷結(jié)束。否則：
（1）后序遍歷根結(jié)點的左子樹；
（2）后序遍歷根結(jié)點的右子樹；
（3）訪問根結(jié)點。

5.2.8 層次遍歷

所謂二叉樹的層次遍歷，是指從二叉樹的第一層（根結(jié)點）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點逐個訪問。
算法實現(xiàn)：
二叉樹以二叉鏈表存儲，一維數(shù)組用以實現(xiàn)隊列。
注意應用隊列的頭和尾的移動。

5.2.9 二叉樹的其他操作

• 查找元素
• 統(tǒng)計葉子結(jié)點個數(shù)
• 求二叉樹的深度

5.3 樹與森林

5.3.1 樹的表示方法

樹的存儲方式有順序存儲、鏈式存儲，表示的方法也有多種：
（1）雙親表示法
樹中的每個結(jié)點（除根結(jié)點外）都有唯一的一個雙親結(jié)點，根據(jù)這一特性，可用一組連續(xù)的存儲空間（一維數(shù)組）存儲樹中的各個結(jié)點，數(shù)組中的一個元素表示樹中的一個結(jié)點，數(shù)組元素為結(jié)構(gòu)體類型，其中包括結(jié)點本身的信息及該結(jié)點的雙親結(jié)點在數(shù)組中的序號，樹的這種存儲方法稱為雙親表示法。
（2）孩子表示法

（3）孩子兄弟表示法

5.3.2 樹、二叉樹和森林的轉(zhuǎn)換

將一棵樹轉(zhuǎn)換為二叉樹的方法是：
（1）樹中所有相鄰兄弟之間加一條連線；
（2）對樹中的每個結(jié)點，只保留它與第一個孩子結(jié)點之間的連線，刪去它與其他孩子結(jié)點之間的連線；
（3）以樹的根結(jié)點為軸心，將整棵樹順時針轉(zhuǎn)動一定的角度，使之結(jié)構(gòu)層次分明。

【待續(xù)：森林轉(zhuǎn)換為二叉樹、二叉樹轉(zhuǎn)換為樹和森林】

5.3.3 樹遍歷

先根遍歷：
（1）訪問根結(jié)點；
（2） 按照從左到右的順序先根遍歷根結(jié)點的每一棵子樹。
后根遍歷：
（1） 按照從左到右的順序后根遍歷根結(jié)點的每一棵子樹；
（2） 訪問根結(jié)點。

5.3.4 森林的遍歷

前序遍歷：
（1）0 訪問森林中第一棵樹的根結(jié)點；
（2） 前序遍歷第一棵樹的根結(jié)點的子樹；
（3） 前序遍歷去掉第一棵樹后的子森林。
中序遍歷：
（1）0 中序遍歷第一棵樹的根結(jié)點的子樹；
（2）訪問森林中第一棵樹的根結(jié)點；
（3） 中序遍歷去掉第一棵樹后的子森林。

5.4 哈夫曼樹（最優(yōu)二叉樹）

• 最優(yōu)二叉樹也稱哈夫曼（Huffman）樹，是指對于一組帶有確定權(quán)值的葉子結(jié)點，構(gòu)造的具有最小帶權(quán)路徑長度的二叉樹；
• 權(quán)值是指一個與特定結(jié)點相關的數(shù)值。
• 對權(quán)值和節(jié)點路徑長度乘積進行累加，得到的和為最小值。
• 帶權(quán)路徑長度（Weighted Path Length）
• 思想：根據(jù)哈夫曼樹的定義，一棵二叉樹要使其WPL值最小，必須使權(quán)值越大的葉子結(jié)點越靠近根結(jié)點，而權(quán)值越小的葉子結(jié)點越遠離根結(jié)點。

5.4.1 哈夫曼樹的構(gòu)造方法

（1）由給定的n個權(quán)值{w1, w2, …, wn}構(gòu)造n棵只有一個葉子結(jié)點的二叉樹，從而得到一個二叉樹的集合F={T1, T2, …, Tn}；
（2）在F中選取根結(jié)點的權(quán)值最小和次小的兩棵二叉樹作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新的二叉樹根結(jié)點的權(quán)值為其左、右子樹根結(jié)點權(quán)值之和；
（3）在集合F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到集合F中；
（4）重復（2）、（3）兩步，當F中只剩下一棵二叉樹時，這棵二叉樹便是所要建立的哈夫曼樹。

5.4.2 哈夫曼樹的構(gòu)造算法

【待續(xù)】

5.4.3 哈夫曼數(shù)的編碼

利用哈夫曼樹來構(gòu)造編碼方案，就是哈夫曼樹的典型應用。

六、圖

圖（Graph）是由非空的頂點集合和一個描述頂點之間的關系——邊（或者弧）的集合組成的。

6.1 圖的基本概念

6.1.1 術語

（1）無向圖：在一個圖中，如果任意兩個頂點構(gòu)成的偶對（vi, vj）∈E是無序的，即頂點之間的連線是沒有方向的，則稱該圖為無向圖。如圖6.1所示是一個無向圖G1。
（2）有向圖：在一個圖中，如果任意兩個頂點構(gòu)成的偶對<vi, vj>∈E是有序的（有序?qū)Τ３Ｓ眉饫ㄌ枴?lt; >”表示），即頂點之間的連線是有方向的，則稱該圖為有向圖。
（3）頂點、邊、弧、弧頭、弧尾：在圖中，數(shù)據(jù)元素vi稱為頂點（Vertex）；(vi,vj)表示在頂點vi和頂點vj之間有一條直接連線。如果是在無向圖中，則稱這條連線為邊；如果是在有向圖中，一般稱這條連線為弧。邊用頂點的無序偶對(vi, vj)來表示，稱頂點vi和頂點vj互為鄰接點，邊(vi, vj)依附于頂點vi與頂點vj；弧用頂點的有序偶對<vi, vj>來表示，有序偶對的第一個結(jié)點vi被稱為始點（或弧尾），在圖中就是不帶箭頭的一端；有序偶對的第二個結(jié)點vj被稱為終點（或弧頭），在圖中就是帶箭頭的一端。
（4）無向完全圖：在一個無向圖中，如果任意兩頂點都有一條直接邊相連接，則稱該圖為無向完全圖。可以證明，在一個含有n個頂點的無向完全圖中，有n(n-1)/2條邊。
（5）有向完全圖：在一個有向圖中，如果任意兩頂點之間都有方向互為相反的兩條弧相連接，則稱該圖為有向完全圖。在一個含有n個頂點的有向完全圖中，有n(n-1)條邊。
（6）頂點的度、入度、出度：頂點的度（Degree）是指依附于某頂點v的邊數(shù)，通常記為TD (v)。在有向圖中，要區(qū)別頂點的入度與出度的概念。頂點v的入度是指以頂點v為終點的弧的數(shù)目，記為ID(v)；頂點v出度是指以頂點v為始點的弧的數(shù)目，記為OD(v)。有TD (v)=ID (v)＋OD (v)。
可以證明，對于具有n個頂點、e條邊的無向圖，頂點vi的度TD(vi)與頂點的個數(shù)及邊的數(shù)目滿足關系：

圖片.png

（8）路徑、路徑長度：頂點vp到頂點vq之間的路徑（Path）是指頂點序列vp, vi1,vi2, …, vim, vq。其中，(vp, vi1), (vi1, vi2), …, (vim, vq)分別為圖中的邊。路徑上邊的數(shù)目稱為路徑長度。圖6.1所示的無向圖G1中，v1→v4→v3→v5與v1→v2→v5是從頂點v1到頂點v5的兩條路徑，其路徑長度分別為3和2。
（9）簡單路徑、回路、簡單回路：序列中頂點不重復出現(xiàn)的路徑稱為簡單路徑。在圖6.1中，前面提到的v1到v5的兩條路徑都為簡單路徑。路徑中第一個頂點與最后一個頂點相同的路徑稱為回路或環(huán)（Cycle）。除第一個頂點與最后一個頂點之外，其他頂點不重復出現(xiàn)的回路稱為簡單回路，或者簡單環(huán)。如圖6.2中的v1→v3→v4→v1。
（10）子圖：對于圖G=(V, E)，G′=(V′, E′)，若存在V′是V的子集、E′是E的子集，則稱圖G′是G的一個子圖。圖6.4給出了圖6.2(G2)和圖6.1(G1)的兩個子圖G′和G″。
（11）連通、連通圖、連通分量：在無向圖中，如果從一個頂點vi到另一個頂點vj(i≠j)存在路徑，則稱頂點vi和vj是連通的。如果圖中任意兩個頂點都是連通的，則稱該圖是連通圖。無向圖的極大連通子圖稱為連通分量，極大連通子圖是指在保證連通與子圖的條件下，包含原圖中所有的頂點與邊。
（12）強連通圖、強連通分量：對于有向圖來說，若圖中任意一對頂點vi和vj(i≠j)均存在從一個頂點vi到另一個頂點vj和從vj到vi的路徑，則稱該有向圖是強連通圖。有向圖的極大強連通子圖稱為強連通分量，極大強連通子圖的含義同上。圖6.2中有兩個強連通分量，分別是{v1, v3, v4}和{v2}，如圖6.6所示。
（13）生成樹：所謂連通圖G的生成樹，是G的包含其全部n個頂點的一個極小連通子圖，所謂極小連通子圖是指在包含所有頂點且保證連通的前提下盡可能少地包含原圖中的邊。圖6.4（b）中的G″給出了圖6.1中G1的一棵生成樹。生成樹必定包含且僅包含連通圖G的n-1條邊。在生成樹中添加任意一條屬于原圖中的邊必定會產(chǎn)生回路，因為新添加的邊使其所依附的兩個頂點之間有了第二條路徑。若生成樹中減少任意一條邊，則必然成為非連通的。
（14）生成森林：在非連通圖中，由每個連通分量都可得到一個極小連通子圖，即一棵生成樹。這些連通分量的生成樹就組成了一個非連通圖的生成森林。

6.1.2 圖的操作

（1）CreatGraph(G)：輸入圖G的頂點和邊，建立圖G的存儲。（2）DestroyGraph(G)：釋放圖G占用的存儲空間。
（3）GetVex(G, v)：在圖G中找到頂點v，并返回頂點v的相關信息。（4）PutVex(G, v, value)：在圖G中找到頂點v，并將value值賦給頂點v。
（5）InsertVex(G, v)：在圖G中增添新頂點v。
（6）DeleteVex(G, v)：在圖G中，刪除頂點v及所有和頂點v相關聯(lián)的邊或弧。
（7）InsertArc(G, v, w)：在圖G中增添一條從頂點v到頂點w的邊或弧。
（8）DeleteArc(G, v, w)：在圖G中刪除一條從頂點v到頂點w的邊或弧。
（9）DFSTraverse(G, v)：在圖G中，從頂點v出發(fā)深度優(yōu)先遍歷圖G。
（10）BFSTtaverse(G, v)：在圖G中，從頂點v出發(fā)廣度優(yōu)先遍歷圖G。在一個圖中，頂點是沒有先后次序的，但當采用某一種確定的存儲方式存儲后，存儲結(jié)構(gòu)中頂點的存儲次序構(gòu)成了頂點之間的相對次序，這里用頂點在圖中的位置表示該頂點的存儲順序；同樣的道理，對一個頂點的所有鄰接點，采用該頂點的第i個鄰接點表示與該頂點相鄰接的某個頂點的存儲順序，在這種意義下，圖還有以下的基本操作。
（11）LocateVex(G, u)：在圖G中找到頂點u，返回該頂點在圖中位置。（12）FirstAdjVex(G, v)：在圖G中，返回v的第一個鄰接點。若頂點在G中沒有鄰接頂點，則返回“空”。（13）NextAdjVex(G, v, w)：在圖G中，返回v的（相對于w的）下一個鄰接頂點。若w是v的最后一個鄰接點，則返回“空”。

6.2 圖的存儲結(jié)構(gòu)

6.2.1 鄰接矩陣

• 所謂鄰接矩陣（Adjacency Matrix）的存儲結(jié)構(gòu)，就是用一維數(shù)組存儲圖中頂點的信息，用矩陣表示圖中各頂點之間的鄰接關系。
• 用矩陣表示圖中各頂點之間的鄰接關系。假設圖G=(V, E)有n個確定的頂點，即V={v0, v1, …, vn-1}，則表示G中各頂點相鄰關系的矩陣為一個n×n的矩陣，矩陣元素下標i、j代表點，元素值用1表示連接，0標志未連接。

特點：
（1）無向圖的鄰接矩陣一定是一個對稱矩陣。因此，在具體存放鄰接矩陣時只需存放上（或下）三角矩陣的元素即可。
（2）對于無向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個數(shù)正好是第i個頂點的度TD(vi)。
（3）對于有向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個數(shù)正好是第i個頂點的出度OD(vi)（或入度ID(vi)）。
（4）用鄰接矩陣方法存儲圖，很容易確定圖中任意兩個頂點之間是否有邊相連；但是，要確定圖中有多少條邊，則必須按行、按列對每個元素進行檢測，所花費的時間代價很大。這是用鄰接矩陣存儲圖的局限性。

6.2.2 鄰接表

鄰接表（Adjacency List）是圖的一種順序存儲與鏈式存儲結(jié)合的存儲方法。鄰接表表示法類似于樹的孩子鏈表表示法。就是對于圖G中的每個頂點vi，將所有鄰接于vi的頂點vj鏈成一個單鏈表，這個單鏈表就稱為頂點vi的鄰接表，再將所有頂點的鄰接表表頭放到數(shù)組中，就構(gòu)成了圖的鄰接表

• 一種是頂點表的結(jié)點結(jié)構(gòu)，它由頂點域（vertex）和指向第一條鄰接邊的指針域（firstedge）構(gòu)成；
• 另一種是邊表（即鄰接表）結(jié)點，它由鄰接點域（adjvex）和指向下一條鄰接邊的指針域（next）構(gòu)成；
• 對于網(wǎng)的邊表需再增設一個存儲邊上信息（如權(quán)值等）的域（info）。

在鄰接表上容易找到任意頂點的第一個鄰接點和下一個鄰接點，但要判定任意兩個頂點（vi和vj）之間是否有邊或弧相連，則需查找第i個或第j個鏈表，因此，不如鄰接矩陣方便。

6.3 圖的遍歷

圖的遍歷是指從圖中的任意頂點出發(fā)，對圖中的所有頂點訪問一次且只訪問一次。

6.3.1 深度優(yōu)先搜索（Depth-First Search，DFS）

類似于樹的先根遍歷，是樹的先根遍歷的推廣。

• 假設初始狀態(tài)是圖中所有頂點未曾被訪問，則深度優(yōu)先搜索可從圖中某個頂點v出發(fā)，訪問此頂點；
• 然后依次從v的未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點都被訪問到；
• 若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作為起始點；
• 重復上述過程，直至圖中所有頂點都被訪問到為止。

6.3.2 廣度優(yōu)先搜索（Breadth-First Search，BFS）

類似于樹的按層次遍歷的過程。

• 假設從圖中某頂點v出發(fā)，在訪問了v之后依次訪問v的各個未曾訪問過的鄰接點；
• 然后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到；
• 若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作為起始點，重復上述過程，直至圖中所有頂點都被訪問到為止；
• 換句話說，廣度優(yōu)先搜索遍歷圖的過程是以v為起始點，由近至遠，依次訪問和v有路徑相通且路徑長度為1, 2, …的頂點。

6.4 圖的應用

6.4.1 最小生成樹

如果無向連通圖是一個網(wǎng)，那么，它的所有生成樹中必有一棵生成樹的邊的權(quán)值總和最小，稱這樣一棵生成樹為最小代價生成樹（Minimum Cost SpanningTree），簡稱最小生成樹（MST）。一棵生成樹的代價就是樹中所有邊的代價之和。

構(gòu)造最小生成樹的Prim算法和Kruskal算法
【待續(xù)】

6.4.2 最短路徑

在網(wǎng)中求點A到點B的所有路徑中邊的權(quán)值之和最短的那一條路徑，這條路徑就是兩點之間的最短路徑
【待續(xù)】

6.4.3 拓撲排序

• 一個無環(huán)的有向圖稱為有向無環(huán)圖（Directed Acycline Graph，DAG）。
• 有向無環(huán)圖是描述工程或系統(tǒng)進程的有效工具。

七、查找

（1）關鍵碼

• 關鍵碼（Key）是數(shù)據(jù)元素（記錄）中某個項或組合項的值，可以用它標識一個數(shù)據(jù)元素（記錄）；
• 能唯一確定一個數(shù)據(jù)元素（記錄）的關鍵碼稱為主關鍵碼；
• 不能唯一確定一個數(shù)據(jù)元素（記錄）的關鍵碼稱為次關鍵碼。
  （2）查找表
• 具有同一類型（屬性）的數(shù)據(jù)元素（記錄）組成的集合稱為查找表。
• 靜態(tài)查找表：僅對查找表進行前兩種所謂的“查找”操作，而不能被改變的表；
• 動態(tài) 查找表：對查找表除進行“查找”操作外，可能還要向表中插入數(shù)據(jù)元素或刪除表中數(shù)據(jù)元素，因而動態(tài)查找表在查找過程中可以被改變。
  （3）查找
  按給定的某個值kx，在查找表中查找關鍵碼為給定值kx的數(shù)據(jù)元素（記錄）。
  （4）平均查找長度ASL
  定義：在查找成功時，平均查找長度ASL是指為確定數(shù)據(jù)元素在表中的位置所進行的關鍵碼比較次數(shù)的期望值

7.2 靜態(tài)表查找

7.2.1 靜態(tài)表查找結(jié)構(gòu)

靜態(tài)查找表是數(shù)據(jù)元素的線性表，可以是基于數(shù)組的順序存儲或以線性鏈表存儲。

7.2.2 順序查找

順序查找又稱線性查找，是最基本的查找方法之一。其查找過程為：從表的一端開始，向另一端逐個將其關鍵碼與給定值kx進行比較，若相等，則查找成功，并給出數(shù)據(jù)元素在表中的位置；若整個表檢測完，仍未找到與kx相同的關鍵碼，則查找失敗，給出失敗信息。

7.2.3 有序表查找

有序表是表中數(shù)據(jù)元素按關鍵碼升序或降序排列。對于有序表，若按順序存儲結(jié)構(gòu)存儲，可以用折半查找來實現(xiàn)查找操作。

7.2.4 分塊查找

分塊查找又稱索引順序查找，是對順序查找的一種改進。分塊查找要求將查找表分成若干個子表，并對子表建立索引表，查找表的每一個子表由索引表中的索引項確定。

7.3 動態(tài)表查找

二叉排序樹就是一種常見的動態(tài)查找表

7.3.1 二叉排序樹定義

二叉排序樹（Binary Sort Tree）或者是一棵空二叉樹，或者是具有下列性質(zhì)的二叉樹。
（1）若左子樹不空，則左子樹上所有結(jié)點的關鍵碼值均小于根結(jié)點的關鍵碼值；若右子樹不空，則右子樹上所有結(jié)點的關鍵碼值均大于根結(jié)點的關鍵碼值。
（2）左、右子樹也都是二叉排序樹。
左子節(jié)點鍵值 < 父節(jié)點鍵值 < 右子節(jié)點鍵值

7.3.1 二叉排序樹查找算法

7.3.1 二叉排序樹構(gòu)造和插入

7.4 哈希表

建立關鍵碼與數(shù)據(jù)元素間的一一對應關系，通過這個關系，能很快地由關鍵碼值得到對應的數(shù)據(jù)元素位置。而哈希方法就是試圖建立這樣的對應關系。

選取某個函數(shù)，依該函數(shù)按關鍵碼計算元素的存儲位置，并按此存放；查找時，由同一個函數(shù)對給定值kx計算地址，將kx與地址單元中元素關鍵碼進行比較，確定查找是否成功，這就是哈希（Hash）方法（又稱為散列法、雜湊法或關鍵字地址計算法）；哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希（Hash）函數(shù)（散列函數(shù)）。

7.4.1 常用的哈希函數(shù)構(gòu)造方法

【待續(xù)】

7.4.2 處理沖突的方法

【待續(xù)】

7.4.4 哈希表的查找算法

【待續(xù)】

7.4.4 哈希表的性能分析

8 排序