數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)筆記

第一章 緒論

P2 數(shù)據(jù)結(jié)構(gòu)研究

利用計算機(jī)求解問題涉及到兩大核心方法：

l?如何表達(dá)定義要處理的對象（數(shù)據(jù)結(jié)構(gòu)）

l?處理這些對象的步驟（算法）

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

l?線性結(jié)構(gòu)（就是集合，每個數(shù)據(jù)首尾相連，線性表、棧、隊列、串、數(shù)組、廣義表）

l?樹狀結(jié)構(gòu)（一對多，一個子數(shù)據(jù)只能有一個父數(shù)據(jù)）

l?圖狀結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu) ?）

描述非樹脂計算問題的數(shù)學(xué)模型不是數(shù)學(xué)方程，而是數(shù)據(jù)結(jié)構(gòu)

P3-P4 基本概念和術(shù)語

數(shù)據(jù)的分類：數(shù)值型（可運(yùn)算）、非數(shù)值型：文字、圖像等

數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集

數(shù)據(jù)元素/記錄/結(jié)點/頂點：數(shù)據(jù)的基本單位，常常作為一個整體處理，是數(shù)據(jù)對象的子集

數(shù)據(jù)項：構(gòu)成數(shù)據(jù)元素的不可分割的最小單位

數(shù)據(jù)結(jié)構(gòu)：一種或多種帶結(jié)構(gòu)的數(shù)據(jù)元素的集合

數(shù)據(jù)結(jié)構(gòu) = 邏輯結(jié)構(gòu)（抽象） + 存儲結(jié)構(gòu)（實現(xiàn)，物理上如何存儲）

邏輯結(jié)構(gòu)分類（一）：

l?線性結(jié)構(gòu)：收尾相連，只有一個開始節(jié)點和一個終端節(jié)點

l?非線性結(jié)構(gòu)：樹、圖

邏輯結(jié)構(gòu)分類（二）：

l?集合：數(shù)據(jù)元素均獨立

l?線性結(jié)構(gòu)

l?樹狀結(jié)構(gòu)

l?圖狀/網(wǎng)狀結(jié)構(gòu)

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

l?順序存儲結(jié)構(gòu)：依次存儲，數(shù)據(jù)之間的邏輯由儲存位置決定。如數(shù)組。

l?鏈接存儲結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系用指針表示。

l?索引存儲結(jié)構(gòu)：通過索引表（index，就是目錄）找數(shù)據(jù)；一般形式是（關(guān)鍵字，地址）；每個節(jié)點只有一個標(biāo)識；

l?散列存儲結(jié)構(gòu)：根據(jù)節(jié)點的關(guān)鍵字計算出節(jié)點的儲存地址？？？

數(shù)據(jù)類型：一組性質(zhì)相同的值的集合

抽象數(shù)據(jù)類型（ADT）：數(shù)學(xué)模型及其操作，不考慮具體存儲結(jié)構(gòu)即具體實現(xiàn)算法

抽象數(shù)據(jù)類型的表示：（D數(shù)據(jù)對象，S關(guān)系集，P基本操作集）

抽象數(shù)據(jù)類型的定義格式： ??

ADT?抽象數(shù)據(jù)類型名{

DATA

數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>

數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>

Operation

基本操作名1

基本操作：<基本操作的定義>

基本操作名2

初始條件：<初始條件描述>

操作結(jié)果：<操作結(jié)果描述>

} ADT?抽象數(shù)據(jù)類型名

其中：數(shù)據(jù)對象、數(shù)據(jù)關(guān)系用偽代碼描述；

基本操作定義格式為：基本操作名（參數(shù)表） ???????????：為操作提供輸入值，賦值參數(shù)、引用參數(shù)

初始條件：<初始條件描述>??????：執(zhí)行之前要滿足的條件

操作結(jié)果：<操作結(jié)果描述>??????：成功操作完成后，返回的結(jié)果

抽象數(shù)據(jù)類型的一個實例：

ADT Circle{

數(shù)據(jù)對象:D = {t,x,y|r,x,y均為實數(shù)}

數(shù)據(jù)關(guān)系：R = {<r,x,y>|r是半徑,<x,y>為圓心坐標(biāo)}

基本操作：

Circle（&C,r,x,y）

操作結(jié)果：構(gòu)造一個圓

double Area(C)

初始條件：圓已經(jīng)存在

操作結(jié)果：計算面積

} ADT?抽象數(shù)據(jù)類型名

P5 抽象數(shù)據(jù)類型的表示與實現(xiàn)

使用c語言實現(xiàn)一個抽象數(shù)據(jù)的定義：

P6-P9 算法和算法分析

算法的描述：

l?自然語言

l?流程圖：傳統(tǒng)流程圖、NS流程圖

l?偽代碼/類語言：類C語言等

l?程序代碼：C語言、Python等

程序是對算法的具體實現(xiàn)。

算法的特性：

l?有窮性：每一步都要有窮

l?確定性：相同輸入、相同輸出

l?可行性：

l?輸入：有零個或多個輸入

l?輸出：一個或多個輸出

算法設(shè)計的要求：

l?正確性：無語法錯誤、滿足要求、典型/刁難的數(shù)據(jù)輸入后也能得出滿足要求的結(jié)果

l?可讀性：易于找到錯誤

l?穩(wěn)健性：輸入非法數(shù)據(jù)時，可以返回錯誤信息

l?高效性：時間和占用資源低

算法的時間效率：

1)????事后統(tǒng)計：實現(xiàn)算法，測算時間和空間開銷（與軟硬件性能有關(guān)）

2)????事前分析：對消耗資源的估算

算法運(yùn)行時間 = ∑（簡單操作次數(shù)X簡單操作所需時間）

算法運(yùn)行時間 = ∑（ ??語句頻度 ?X 簡單操作所需時間）

如果假設(shè)簡單操作所需時間為單位施加

例：

有算法如下：

【如果不知道一個循環(huán)作為整體執(zhí)行多少次，那么就無法知道該循環(huán)內(nèi)的語句執(zhí)行多少次】

【一個循環(huán)A里的語句a的執(zhí)行次數(shù) = 循環(huán)A的執(zhí)行次數(shù) X 循環(huán)A執(zhí)行一次語句a執(zhí)行的次數(shù)】

為方便比較，只比較數(shù)量級。例如一個算法消耗時間為T1（n）=10n2

若有一個輔助函數(shù)f（n），使得 為一個不等于零的常數(shù)，則有漸進(jìn)時間復(fù)雜自由度

例如，求解矩陣相乘算法消耗時間為 。因為

所以該算法時間復(fù)雜度為

某些情況下，算法基本操作執(zhí)行的次數(shù)因輸入的數(shù)據(jù)集不同而不同。因而有最壞時間復(fù)雜度/平均時間負(fù)責(zé)度/最好時間復(fù)雜度。

時間復(fù)雜自由度的運(yùn)算：

l?加法（順序執(zhí)行）：

l?乘法（程序嵌套）：

漸進(jìn)空間復(fù)雜度：

算法占據(jù)的空間：算法本身占據(jù)的空間（輸入輸出、指令、常量變量）、使用的輔助空間

第六章 圖

P108-P109 圖的基本概念與術(shù)語

定義： ，其中V：數(shù)據(jù)元素（頂點）的有窮非空集合；E：邊的有窮集合。

l?完全圖：任意亮點都有一條邊相連。其中，無向完全圖有 ，有向完全圖有 條邊。

l?稠密圖：邊很少，

l?稠密圖：邊較多

l?網(wǎng)：邊有權(quán)重的圖

l?鄰接：有邊相連的兩個頂點間的關(guān)系。

，兩個頂點互為鄰接點；

， 鄰接到 ， 鄰接于

l?關(guān)聯(lián)（依附）：存在 或 ，冊稱該邊關(guān)聯(lián)與 和

l?頂點的度：一個頂點關(guān)聯(lián)的邊的數(shù)量。度： ；入度： ；出度：

l?路徑：連續(xù)的邊構(gòu)成的頂點序列

l?路徑長度：路徑上邊的數(shù)目或權(quán)重之和

l?回路/環(huán)：第一個頂點和最后一個頂點相同的路徑

l?簡單路徑：除路徑起點和終點相同外，其余頂點均不相同

l?（強(qiáng)）連通圖：任意兩個頂點v，u都存在v到u的路徑

判斷無向圖是否為連通圖，只要沒頂點孤立即可

判斷有向圖是否連接，除了看有無頂點孤立，還要看不相鄰的頂點之間能否順著有向邊連接。

l?子圖：有兩圖 、 ，若存在 、 ，則稱 為 的子圖

l?（強(qiáng)）連通分量：一個圖的極大連通子圖的數(shù)量

l?極小連通子圖：是子圖，而且刪除任意邊，就不再連通

l?生成樹：包含連通圖G所有頂點的極小連通子圖。不能再刪關(guān)系的圖就是數(shù)結(jié)構(gòu)嘛

l?生成森林：對于非連通圖，各個連通分量（極大連通子圖）的生成樹的集合

P111 圖的類型定義

圖的抽象數(shù)據(jù)類型定義：？？？

ADT Graph{

數(shù)據(jù)對象：V，頂點集，具有相同特性的數(shù)據(jù)元素的集合，

數(shù)據(jù)關(guān)系：R，R = {VR}

<V,W>表示從V到W的邊， 定義了邊的信息}

CreateGraph(&G,V,VR)

初始條件:V是圖的頂點集，VR是圖中弧的集合。操作結(jié)果:按V和VR的定義構(gòu)造圖G。

DFSTraverse(G)

初始條件:圖G存在。

操作結(jié)果:對圖進(jìn)行深度優(yōu)先遍歷。

BFSTraverse(G)

初始條件:圖G存在。

操作結(jié)果:對圖進(jìn)行廣度優(yōu)先遍歷。

}ADT Graph

P112 圖的存儲結(jié)構(gòu)-無向圖鄰接矩陣

數(shù)組表示法（鄰接矩陣）

鏈接表示法（鄰接表）

鏈?zhǔn)酱鎯Y(jié)構(gòu)：鄰接表、鄰接多重表、十字鏈表

數(shù)組表示法/鄰接矩陣表示：

有圖 有n個頂點（這里的頂點就是圖譜里的實體）

建立頂點表（記錄頂點信息）：Vexs[n]

建立鄰接矩陣（記錄頂點間關(guān)系）：A.arcs[n][n]

P113 圖的存儲結(jié)構(gòu)-有向圖和網(wǎng)鄰接矩陣

有向圖的鄰接矩陣表示：

網(wǎng)（加權(quán)圖）的鄰接矩陣：

P114 圖的存儲結(jié)構(gòu)-鄰接矩陣創(chuàng)建無向網(wǎng)

▼定義頂點表、鄰接矩陣等

▼輸入頂點信息、初始化鄰接矩陣

▼構(gòu)造鄰接矩陣/輸入關(guān)系信息

P115 圖的存儲結(jié)構(gòu)-鄰接矩陣的優(yōu)缺點

優(yōu)點：

l?直觀、簡單

l?方便檢查任意一對頂點間是否存在邊

l?方便查找任意頂點的所有鄰接點

缺點：

l?不便添加和刪除頂點

l?浪費存儲空間，尤其是稀疏圖的時候

l?統(tǒng)計邊的時候浪費時間，尤其是稀疏圖的時候

P116 圖的存儲結(jié)構(gòu)-鄰接表表示無向圖

▼鄰接表表示無向圖

特點：

l?鄰接表中的邊表不唯一

l?無向圖中，有n個頂點、e條邊，則需要n個頭結(jié)點，2e個表結(jié)點，故空間復(fù)雜度為S（n）=O（n+2e）。適合存儲稀疏圖。

P117 圖的存儲結(jié)構(gòu)-鄰接表表示有向圖

▼鄰接表表示有向圖

特點：

l?頂點 的出度為第i個單鏈表中的節(jié)點個數(shù)

l?頂點 的入度為整個單鏈表鄰接點域值為i-1的節(jié)點個數(shù)

l?有向圖中，有n個頂點、e條邊，則需要n個頭結(jié)點，e個表結(jié)點，故空間復(fù)雜度為S（n）=O（n+e）

P118 圖的存儲結(jié)構(gòu)-建立鄰接表算法

▼定義頂點表

▼定義邊表

▼定義圖

▼某鄰接表表示的圖結(jié)構(gòu)的實例：

P119 圖的存儲結(jié)構(gòu)-鄰接表特點、與鄰接矩陣關(guān)系

鄰接表優(yōu)點：

l?適合稀疏圖，需要空間：無向圖N+2E，有向圖N+2E

l?方便計算無向圖的度

鄰接表缺點：

l?有向圖需要使用鄰接表計算出度，逆鄰接表計算入度

l?不方便判斷任意兩節(jié)點是否存在邊

區(qū)別：

l?鄰接矩陣唯一，鄰接表不唯一

l?鄰接矩陣空間復(fù)雜度為O(n2), 鄰接表空間復(fù)雜度為O(n+e)或O(n+2e)

l?鄰接矩陣多用于稠密圖, 鄰接表多用于稀疏圖

P120 圖的存儲結(jié)構(gòu)-十字鏈表

P121 圖的存儲結(jié)構(gòu)-鄰接多重表

P122-圖的遍歷-深度優(yōu)先思想

深度優(yōu)先Depth_First Search（DFS）

圖遍歷定義：從連通圖中某一頂點出發(fā)，訪問圖中所有頂點，且每個頂點僅被訪問一次

如何避免重復(fù)訪問：

l?設(shè)置輔助數(shù)組visited[n]標(biāo)記每個被訪問過的頂點

l?初始狀態(tài)visited[i] = 0

l?頂點i被訪問后，visited[i] = 1

DFS方法：

l?在訪問圖中某一起始頂點v后，由v出發(fā)，訪問它的任一鄰接頂點w;再從w出發(fā)，訪問與w鄰接但還未被訪問過的頂點w2;

l?然后再從w出發(fā)，進(jìn)行類似的訪問，...

l?如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點都被訪問過的頂點u為止。接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問的鄰接頂點。

l?如果有，則訪問此頂點，之后再從此頂點出發(fā)，進(jìn)行與前述類似的訪問;

l?如果沒有，就再退回一步進(jìn)行搜索。重復(fù)上述過程，直到連通圖中所有頂點都被訪問過為止。

注：退回的時候根據(jù)路徑（路徑數(shù)組/棧）退回

深度優(yōu)先遍歷算法實現(xiàn)-鄰接矩陣

P123 圖的遍歷-深度優(yōu)先-鄰接矩陣實現(xiàn)

P124 圖的遍歷-深度優(yōu)先算法效率

時間復(fù)雜度

適合

鄰接矩陣

O(n2)

稠密圖

鄰接表

O(n+e)？？？

稀疏圖

P125 圖的遍歷-廣度優(yōu)先遍歷及實現(xiàn)

BFS（Breadth First Search）：廣度優(yōu)先遍歷，可以理解為一層一層的搜索

BFS方法：從圖的某一節(jié)點出發(fā)，首先依次訪問該結(jié)點的所有鄰接點，再按這些頂點被訪問的先后次序依次訪問與他們相鄰接的為被訪問的頂點。重復(fù)此過程，直至所有頂點均被訪問為止。

時間復(fù)雜度

適合

鄰接矩陣

O(n2)

稠密圖

鄰接表

O(n+e)？？？

稀疏圖

時間復(fù)雜度

空間復(fù)雜度

DFS

鄰接矩陣O(n2)

鄰接表O(n+e)

O(n)

BFS

P126 圖的應(yīng)用-生成樹及結(jié)構(gòu)

生成樹：包含所有頂點的極小連通子圖。不能再刪關(guān)系的圖就是數(shù)結(jié)構(gòu)嘛

特點：

l?一個圖可有不同的生成樹

l?生成樹的頂點個數(shù)與圖的頂點個數(shù)相同

l?若圖/生成樹有n個節(jié)點，則一定有n-1條邊。反之，不成立。？？？

l?生成樹中再加一條邊（原有圖中的邊），必然形成回路

l?生成樹中任意兩個頂點間的路徑唯一

無向圖的生成樹

l?深度優(yōu)先遍歷樹

l?廣度優(yōu)先遍歷樹

設(shè)圖G=(V,E)是連通圖，當(dāng)從圖中任一項頂點出發(fā)遍歷圖G時，將邊集E(G)分成兩個集合

l?T(G)，遍歷圖所經(jīng)過的邊的集合

l?B(G)，遍歷圖未經(jīng)過的邊的集合

即E(G)=T(G)∪B(G)，顯然，新的子圖G(V,T)是圖G=(V,E)的極小連通子圖和生成樹。

P127 圖的應(yīng)用-最小生成樹及應(yīng)用

最?。ù鷥r）生成樹MST（Minimum Spanning Tree）：給定一個無向網(wǎng)絡(luò)，各邊權(quán)值之和最小的生成樹

最小生成樹不唯一，但是各個最小生成樹的權(quán)值之和一定最小且相等。

典型應(yīng)用：導(dǎo)航（最短路徑規(guī)劃）、建立通訊網(wǎng)絡(luò)

P128 圖的應(yīng)用-最小生成樹MST性質(zhì)

MST性質(zhì)：若邊（u，v）是一條具有最小權(quán)值的邊，則必然存在一個包含邊（u，v）的最小生成樹

MST性質(zhì)的意義在于，在生成樹的構(gòu)造過程中，可將網(wǎng)的頂點分為

l?頂點集合U：落入生成樹內(nèi)的頂點

l?頂點集合V-U：未落入生成樹內(nèi)的頂點

則接下來應(yīng)在連通U和V-U的邊中選擇權(quán)值最小的邊。

P129 圖的應(yīng)用-最小生成樹Prim算法

算法思想：

P130 圖的應(yīng)用-最小生成樹Kruskal算法

如何判斷加邊的時候，是否形成環(huán)呢

算法

普里姆算法

克魯斯卡爾算法

算法思想

選擇點

選擇邊

時間復(fù)雜度

適用范圍

稠密圖

稀疏圖

P131 圖的應(yīng)用-最短路徑問題抽象

問題抽象：

描述

算法

單源最短路徑

在有向網(wǎng)中，源點到達(dá)終點的多條路徑中，尋找一條各邊權(quán)值之和最小的路徑

Djikstra（迪杰斯特拉）算法

所有頂點最短路徑

在有向網(wǎng)中，所有頂點之間的最短路徑

Floyd（弗洛伊德）算法

P132 圖的應(yīng)用-最短路徑-Djikstra（迪杰斯特拉）算法

Djikstra（迪杰斯特拉）算法就是在最小生成樹Prim算法的基礎(chǔ)上，增加了操作。

Djikstra（迪杰斯特拉）算法就是在最小生成樹Prim算法的過程中，考慮了各個節(jié)點的最短路徑。

看不懂？？？

P133 圖的應(yīng)用-最短路徑-Floyd（弗洛伊德）算法

方法一：每個頂點執(zhí)行Djikstra（迪杰斯特拉）算法

方法二：？？？講了個啥，看不懂

P134 圖的應(yīng)用-拓?fù)渑判?/span>

DAG圖：有向無環(huán)圖，不是有向樹

DAG網(wǎng)

頂點表示

邊表示

應(yīng)用

AOV網(wǎng)（Activity On Vertex network）

活動

活動之間的優(yōu)先制約關(guān)系

拓?fù)渑判?/p>

AOE網(wǎng)（Activity On Edge network）

活動的開始或結(jié)束

活動

關(guān)鍵路徑

拓?fù)渑判颍篈OV網(wǎng)五回路的情況下，將全部活動（頂點）排序為線性序列（拓?fù)溆行蛐蛄校?/p>

P135 圖的應(yīng)用-關(guān)鍵路徑

AOE網(wǎng)：