時(shí)間：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語(yǔ)言的特點(diǎn)是面向過(guò)程，有它的應(yīng)用領(lǐng)域，但也有局限性：在編寫(xiě)某些類(lèi)型的大程序是，沒(méi)有高級(jí)語(yǔ)言快捷和方便。

一、緒論

由來(lái)

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

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

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

1.1 概念

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

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

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

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

1.3 邏輯存儲(chǔ)和物理存儲(chǔ)

• 數(shù)據(jù)的邏輯結(jié)構(gòu)可以看做從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型，它與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)；
• 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)表示（又稱(chēng)映像）稱(chēng)為數(shù)據(jù)的物理結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)方法包括順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。

1.4 算法

1.4.1 特性

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

1.4.2 要求

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

1.4.3 基本操作

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

1.4.4 算法描述

• 自然語(yǔ)言
• 框圖
• 偽代碼
• 高級(jí)程序語(yǔ)言

1.4.5 算法分析

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

（1）時(shí)間復(fù)雜度
同一問(wèn)題的不同的算法，通常的做法是：

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

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

二、線(xiàn)性表

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

三、棧和隊(duì)列

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

3.1 棧

• 棧（Stack）是限制在表的一端進(jìn)行插入和刪除操作的線(xiàn)性表；
• 允許進(jìn)行插入、刪除操作的這一端稱(chēng)為棧頂（Top）；
• 固定端稱(chēng)為棧底；
• 當(dāng)表中沒(méi)有元素時(shí)稱(chēng)為空棧。
• 也稱(chēng)作FILO（First-In Last-Out）表

3.1.1 順序棧

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

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

序號(hào)為0的元素為棧底，top記錄的時(shí)棧頂元素的序號(hào)。
（2）順序棧初始化

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

3.1.2 鏈棧

用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧稱(chēng)為鏈棧。
用單鏈表來(lái)實(shí)現(xiàn)。
應(yīng)用：

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

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

3.1.3 棧與遞歸

例子：

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

3.2 隊(duì)列

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

3.2.1 順序隊(duì)

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

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

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

3.2.2 鏈隊(duì)列

隊(duì)列采用帶頭結(jié)點(diǎn)的鏈表結(jié)構(gòu)

3.3 隊(duì)列的應(yīng)用

• 鍵盤(pán)輸入事件處理

四、串和數(shù)組

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

4.1 串

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

4.1.1 順序存儲(chǔ)結(jié)構(gòu)（定長(zhǎng)）

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

//或者
char s[MAXP_SIZE];

子串的定位操作通常稱(chēng)做串的模式匹配。
基本運(yùn)算：

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

4.1.2 對(duì)分配存儲(chǔ)結(jié)構(gòu)

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

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

4.2 數(shù)組

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

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

• 存儲(chǔ)二維數(shù)組時(shí)，存儲(chǔ)二維數(shù)組時(shí)，一般有兩種存儲(chǔ)方式；
• 一種是以行序?yàn)橹餍颍ɑ蛳刃泻罅校┑捻樞虼鎯?chǔ)方式，即從第一行開(kāi)始存放，一行存放完了接著存放下一行，直到最后一行為止，如BASIC、PASCAL、COBOL、C等程序設(shè)計(jì)語(yǔ)言中都是以行序?yàn)橹餍虻模?/li>
• 另一種是以列序?yàn)橹餍颍ㄏ攘泻笮校┑捻樞虼鎯?chǔ)方式，即一列一列地存儲(chǔ)，如FORTRAN語(yǔ)言就是采用以列序?yàn)橹餍虻拇鎯?chǔ)分配。

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

五、樹(shù)與二叉樹(shù)

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

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

5.1 樹(shù)的基本概念

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

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

操作：

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

5.2 二叉樹(shù)

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

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

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

5.2.2 概念

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

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

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

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

三叉鏈表存儲(chǔ)：每個(gè)結(jié)點(diǎn)由四個(gè)域組成，具體結(jié)構(gòu)為：其中，data、lchild及rchild三個(gè)域的意義同二叉鏈表結(jié)構(gòu)；parent域?yàn)橹赶蛟摻Y(jié)點(diǎn)雙親結(jié)點(diǎn)的指針。

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

5.2.4 二叉樹(shù)的基本操作

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

5.2.5 二叉樹(shù)的遍歷

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

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

訪(fǎng)問(wèn)過(guò)程
（1）訪(fǎng)問(wèn)根結(jié)點(diǎn)；
（2）先序遍歷根結(jié)點(diǎn)的左子樹(shù)；
（3）先序遍歷根結(jié)點(diǎn)的右子樹(shù)
可見(jiàn)這個(gè)過(guò)程包含遞歸形式。例子：

//二叉樹(shù)測(cè)試
#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é)點(diǎn)
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é)點(diǎn)插入左節(jié)點(diǎn)
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é)點(diǎn)插入左節(jié)點(diǎn)
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;
}
//先序遍歷二叉樹(shù)節(jié)點(diǎn)，打印數(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;    
}  

也有非遞歸先序遍歷的方式（通過(guò)“輔助棧”的思想實(shí)現(xiàn)）

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

中序遍歷（LDR）的遞歸過(guò)程為：若二叉樹(shù)為空，遍歷結(jié)束。否則：
（1）中序遍歷根結(jié)點(diǎn)的左子樹(shù)；
（2）訪(fǎng)問(wèn)根結(jié)點(diǎn)；
（3）中序遍歷根結(jié)點(diǎn)的右子樹(shù)。

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

后序遍歷（LRD）的遞歸過(guò)程為：若二叉樹(shù)為空，遍歷結(jié)束。否則：
（1）后序遍歷根結(jié)點(diǎn)的左子樹(shù)；
（2）后序遍歷根結(jié)點(diǎn)的右子樹(shù)；
（3）訪(fǎng)問(wèn)根結(jié)點(diǎn)。

5.2.8 層次遍歷

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

5.2.9 二叉樹(shù)的其他操作

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

5.3 樹(shù)與森林

5.3.1 樹(shù)的表示方法

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

（3）孩子兄弟表示法

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

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

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

5.3.3 樹(shù)遍歷

先根遍歷：
（1）訪(fǎng)問(wèn)根結(jié)點(diǎn)；
（2） 按照從左到右的順序先根遍歷根結(jié)點(diǎn)的每一棵子樹(shù)。
后根遍歷：
（1） 按照從左到右的順序后根遍歷根結(jié)點(diǎn)的每一棵子樹(shù)；
（2） 訪(fǎng)問(wèn)根結(jié)點(diǎn)。

5.3.4 森林的遍歷

前序遍歷：
（1）0 訪(fǎng)問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；
（2） 前序遍歷第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)；
（3） 前序遍歷去掉第一棵樹(shù)后的子森林。
中序遍歷：
（1）0 中序遍歷第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)；
（2）訪(fǎng)問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；
（3） 中序遍歷去掉第一棵樹(shù)后的子森林。

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

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

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

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

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

【待續(xù)】

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

利用哈夫曼樹(shù)來(lái)構(gòu)造編碼方案，就是哈夫曼樹(shù)的典型應(yīng)用。

六、圖

圖（Graph）是由非空的頂點(diǎn)集合和一個(gè)描述頂點(diǎn)之間的關(guān)系——邊（或者弧）的集合組成的。

6.1 圖的基本概念

6.1.1 術(shù)語(yǔ)

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

圖片.png

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

6.1.2 圖的操作

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

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

6.2.1 鄰接矩陣

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

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

6.2.2 鄰接表

鄰接表（Adjacency List）是圖的一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)結(jié)合的存儲(chǔ)方法。鄰接表表示法類(lèi)似于樹(shù)的孩子鏈表表示法。就是對(duì)于圖G中的每個(gè)頂點(diǎn)vi，將所有鄰接于vi的頂點(diǎn)vj鏈成一個(gè)單鏈表，這個(gè)單鏈表就稱(chēng)為頂點(diǎn)vi的鄰接表，再將所有頂點(diǎn)的鄰接表表頭放到數(shù)組中，就構(gòu)成了圖的鄰接表

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

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

6.3 圖的遍歷

圖的遍歷是指從圖中的任意頂點(diǎn)出發(fā)，對(duì)圖中的所有頂點(diǎn)訪(fǎng)問(wèn)一次且只訪(fǎng)問(wèn)一次。

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

類(lèi)似于樹(shù)的先根遍歷，是樹(shù)的先根遍歷的推廣。

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

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

類(lèi)似于樹(shù)的按層次遍歷的過(guò)程。

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

6.4 圖的應(yīng)用

6.4.1 最小生成樹(shù)

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

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

6.4.2 最短路徑

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

6.4.3 拓?fù)渑判?/p>

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

七、查找

（1）關(guān)鍵碼

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

7.2 靜態(tài)表查找

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

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

7.2.2 順序查找

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

7.2.3 有序表查找

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

7.2.4 分塊查找

分塊查找又稱(chēng)索引順序查找，是對(duì)順序查找的一種改進(jìn)。分塊查找要求將查找表分成若干個(gè)子表，并對(duì)子表建立索引表，查找表的每一個(gè)子表由索引表中的索引項(xiàng)確定。

7.3 動(dòng)態(tài)表查找

二叉排序樹(shù)就是一種常見(jiàn)的動(dòng)態(tài)查找表

7.3.1 二叉排序樹(shù)定義

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

7.3.1 二叉排序樹(shù)查找算法

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

7.4 哈希表

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

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

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

【待續(xù)】

7.4.2 處理沖突的方法

【待續(xù)】

7.4.4 哈希表的查找算法

【待續(xù)】

7.4.4 哈希表的性能分析

8 排序