大話數(shù)據(jù)結(jié)構(gòu)

前言

• 人們無(wú)法理解他們沒(méi)有經(jīng)歷過(guò)的事情。--尼采
• 吸引學(xué)生的注意力，比較好的辦法是從他們比較熟知的知識(shí)開始。
• A picture is worth a thousand words.(一圖值千言) --諺語(yǔ)
• 挫折感是很強(qiáng)烈的
• 涉及到比較復(fù)雜的算法知識(shí)，需要讀者有一定的數(shù)學(xué)修養(yǎng)和邏輯思維能力，否則可能書籍的后半部分閱讀起來(lái)會(huì)比較吃力。
• 《如何閱讀一本書》，閱讀越主動(dòng)，效果越好。
• “最淡的墨水也勝于最強(qiáng)的記憶！”，筆記減緩閱讀的速度，有助于大腦學(xué)習(xí)。

第一章 數(shù)據(jù)結(jié)構(gòu)緒論

1.1 開場(chǎng)白

1.2 你數(shù)據(jù)結(jié)構(gòu)怎么學(xué)的？

1.3 數(shù)據(jù)結(jié)構(gòu)起源

1.4 基本概念和術(shù)語(yǔ)

1.4.1 數(shù)據(jù)

數(shù)值數(shù)據(jù)、字符數(shù)據(jù)（包括聲音、視頻等）

1.4.2 數(shù)據(jù)元素

組成數(shù)據(jù)的、有一定意義的基本單位，也稱為記錄

1.4.3 數(shù)據(jù)項(xiàng)

數(shù)據(jù)不可分割的最小單位

1.4.4 數(shù)據(jù)對(duì)象

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

1.4.5 數(shù)據(jù)結(jié)構(gòu)

是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合

1.5 邏輯結(jié)構(gòu)與物理結(jié)構(gòu)

1.5.1 邏輯結(jié)構(gòu)

數(shù)據(jù)對(duì)象中數(shù)據(jù)元素之間的相互關(guān)系

1.集合結(jié)構(gòu)

數(shù)據(jù)元素同屬于一個(gè)集合，沒(méi)有其他關(guān)系，平等關(guān)系

2.線性結(jié)構(gòu)

數(shù)據(jù)元素是一對(duì)一關(guān)系

3.樹形結(jié)構(gòu)

數(shù)據(jù)元素之間存在一對(duì)多的層次關(guān)系

4.圖形結(jié)構(gòu)

數(shù)據(jù)元素是多對(duì)多的關(guān)系

1.5.2 物理結(jié)構(gòu)

也叫存儲(chǔ)結(jié)構(gòu)
是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)形式
兩種形式：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)

1.順序存儲(chǔ)結(jié)構(gòu)

把數(shù)據(jù)元素存放在地址連續(xù)的存儲(chǔ)單元里
邏輯關(guān)系=物理關(guān)系

2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

數(shù)據(jù)元素存放在任意的存儲(chǔ)單元
引入指針存放數(shù)據(jù)元素的位置

邏輯結(jié)構(gòu)是面向問(wèn)題的，而物理結(jié)構(gòu)就是面向計(jì)算機(jī)的，其基本的目標(biāo)就是將數(shù)據(jù)及其邏輯關(guān)系存儲(chǔ)到計(jì)算機(jī)的內(nèi)存中。

1.6 抽象數(shù)據(jù)類型

1.6.1 數(shù)據(jù)類型

指一組數(shù)值相同的值的集合及定義在此集合上的一些操作的總稱
C語(yǔ)言中數(shù)據(jù)類型：

• 原子類型：不可分解的基本類型
• 結(jié)構(gòu)類型：可分解

抽象是指抽取出事物具有的普遍性的本質(zhì)。抽象是一種思考問(wèn)題的方式，它隱藏細(xì)節(jié)，只保留實(shí)現(xiàn)目標(biāo)所必需的信息。

1.6.2 抽象數(shù)據(jù)類型

是指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作

1.7 總結(jié)回顧

1.8 結(jié)尾語(yǔ)

第2章 算法

2.1 開場(chǎng)白

2.2 數(shù)據(jù)結(jié)構(gòu)與算法關(guān)系

梁山伯與祝英臺(tái)、羅密歐與朱麗葉

2.3 兩種算法的比較

高斯：求1+2+3+...+100的值的傳統(tǒng)算法和高效算法

2.4 算法定義

2.5 算法的特性

輸入、輸出、有窮性、確定性和可行性

2.5.1 輸入輸出

2.5.2 有窮性

2.5.3 確定性

無(wú)歧義

2.5.4 可行性

2.6 算法設(shè)計(jì)的要求

2.6.1 正確性

2.6.2 可讀性

2.6.3 健壯性

2.6.4 時(shí)間效率高和存儲(chǔ)量低

2.7 算法效率的度量方法

2.7.1 事后統(tǒng)計(jì)方法

缺點(diǎn)很多，不科學(xué)，不準(zhǔn)確，基本不用

2.7.2 事前分析估算方法

每天打游戲與每天學(xué)習(xí)的差別

2.8 函數(shù)的漸進(jìn)增長(zhǎng)

判斷一個(gè)算法的效率時(shí)，函數(shù)中的常數(shù)和其他次要項(xiàng)常?？梢院雎?，而更應(yīng)該關(guān)注主項(xiàng)（最高階項(xiàng)）的階數(shù)

2.9 算法時(shí)間復(fù)雜度

2.9.1 算法時(shí)間復(fù)雜度定義

2.9.2 推導(dǎo)大O階方法

2.9.3 常數(shù)階

O(1)

2.9.4 線性階

O(n)

2.9.5 對(duì)數(shù)階

O(㏒n)

2.9.6 平方階

O(n2)

2.10 常見的時(shí)間復(fù)雜度

2.11 最壞情況與平均情況

2.12 算法空間復(fù)雜度

不是討論重點(diǎn)，時(shí)間復(fù)雜度才是重點(diǎn)。

2.13 總結(jié)回顧

2.14 結(jié)尾語(yǔ)

愚公移山固然可敬，但發(fā)明炸藥和推土機(jī)，可能更加實(shí)在和聰明。

第3章 線性表

0個(gè)或多個(gè)數(shù)據(jù)元素的有限序列

3.1 開場(chǎng)白

幼兒園的小朋友按次序排隊(duì)一樣

3.2 線性表的定義

前驅(qū)元素、后繼元素
空表

3.3 線性表的抽象數(shù)據(jù)類型

基本操作：創(chuàng)建、初始化、置空、讀表、查表、求長(zhǎng)、插入、刪除等
及各種基本操作的組合

3.4 線性表的順序存儲(chǔ)結(jié)構(gòu)

3.4.1 順序存儲(chǔ)定義

用一段地址連續(xù)的存儲(chǔ)單元一次存儲(chǔ)線性表的數(shù)據(jù)元素

3.4.2 順序存儲(chǔ)方式

起始位置、最大長(zhǎng)度、當(dāng)前長(zhǎng)度

3.4.3 數(shù)據(jù)長(zhǎng)度與線性表長(zhǎng)度區(qū)別

3.4.4 地址計(jì)算方法

存儲(chǔ)單元的編號(hào)成為地址
線性表時(shí)間復(fù)雜度為O(1)
隨機(jī)存取結(jié)構(gòu)

3.5 順序存儲(chǔ)結(jié)構(gòu)的插入和刪除

3.5.1 獲得元素操作

3.5.2 插入操作

插入位置之后的元素統(tǒng)一后移一個(gè)單位，注意越界問(wèn)題

3.5.3 刪除操作

插入和刪除操作的時(shí)間復(fù)雜度都是O(n)

3.5.4 線性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)

3.6 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

3.6.1 順序存儲(chǔ)結(jié)構(gòu)不足的解決辦法

3.6.2 線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)定義

任意的存儲(chǔ)單元
數(shù)據(jù)域、指針域組成一個(gè)結(jié)點(diǎn)
單鏈表：結(jié)點(diǎn)中只有一個(gè)指針域
頭結(jié)點(diǎn)

3.6.3 頭指針和頭結(jié)點(diǎn)的異同

頭結(jié)點(diǎn)不一定會(huì)有
頭指針一定會(huì)有

3.6.4 線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)代碼描述

3.7 單鏈表的讀取

必須從頭開始找

3.8 單鏈表的插入與刪除

3.8.1 單鏈表的插入

事先判斷插入位置是否存在

3.8.2 單鏈表的刪除

事先判斷刪除位置是否存在
插入和刪除的時(shí)間復(fù)雜度均為O(n)

3.9 單鏈表的整表創(chuàng)建

頭插法、尾插法

3.10 單鏈表的整表刪除

3.11 單鏈表結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)

• 存儲(chǔ)分配方式
• 時(shí)間性能
• 空間性能

3.12 靜態(tài)鏈表

用數(shù)組描述的鏈表叫做靜態(tài)鏈表
應(yīng)用場(chǎng)景：為沒(méi)有指針的高級(jí)語(yǔ)言設(shè)計(jì)的一種單鏈表能力

3.12.1 靜態(tài)鏈表的插入操作

3.12.2 靜態(tài)鏈表的刪除操作

3.12.3 靜態(tài)鏈表的優(yōu)缺點(diǎn)

3.13 循環(huán)鏈表

3.14 雙向鏈表

新增指向前驅(qū)結(jié)點(diǎn)的指針域
用空間來(lái)?yè)Q時(shí)間

3.15 總結(jié)回顧

線性表的順序結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是其他數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，很重要

3.16 結(jié)尾語(yǔ)

• 魚塘的人工魚和河中的野魚
• 舒適環(huán)境很難培養(yǎng)出堅(jiān)強(qiáng)品格，被安排好的人生，也很難做出偉大事業(yè)。
• 不怕苦，吃苦半輩子，怕吃苦，吃苦一輩子。

第4章 棧與隊(duì)列

棧：僅在表尾進(jìn)行插入和刪除操作
隊(duì)列：只允許在一端進(jìn)行插入，另一端進(jìn)行刪除

4.1 開場(chǎng)白

左輪手槍與彈夾式手槍

4.2 棧的定義

4.2.1棧的定義

棧頂：允許插入和刪除的一端
棧底
后進(jìn)先出 LIFO結(jié)構(gòu)

4.2.2 進(jìn)棧出棧變化形式

4.3 棧的抽象數(shù)據(jù)類型

4.4 棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)

4.4.1 棧的順序存儲(chǔ)結(jié)構(gòu)

棧底：下標(biāo)為0的一端
類比游標(biāo)卡尺

4.4.2 棧的順序存儲(chǔ)結(jié)構(gòu)--進(jìn)棧操作

4.4.3 棧的順序存儲(chǔ)結(jié)構(gòu)--出棧操作

4.5 兩棧共享空間

4.6 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)

4.6.1 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

鏈棧

4.6.2 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)--進(jìn)棧操作

4.6.2 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)--出棧操作

進(jìn)棧、出棧的時(shí)間復(fù)雜度均為O(1)

4.7 棧的作用

簡(jiǎn)化程序設(shè)計(jì)
類比用腳走路和乘坐交通工具
很多高級(jí)語(yǔ)言都有對(duì)棧結(jié)構(gòu)的封裝

4.8 棧的應(yīng)用--遞歸

4.8.1 斐波那契數(shù)列實(shí)現(xiàn)

兔子繁殖問(wèn)題
數(shù)學(xué)模型

4.8.2 遞歸定義

直接調(diào)用自己或通過(guò)一系列的調(diào)用語(yǔ)句間接地調(diào)用自己的函數(shù)
遞歸會(huì)建立函數(shù)副本，消耗時(shí)間和內(nèi)存

4.9 棧的應(yīng)用--四則運(yùn)算表達(dá)式求值

4.9.1 后綴（逆波蘭）表示法定義

四則運(yùn)算表達(dá)式的一種新的顯示方式，巧妙地解決了程序四則運(yùn)算的難題，所有的符號(hào)都是在要運(yùn)算數(shù)字的后面出現(xiàn)

4.9.2 后綴表達(dá)式計(jì)算結(jié)果

遇到數(shù)字就進(jìn)棧，遇到符號(hào)，就將處于棧頂?shù)膬蓚€(gè)數(shù)字出棧進(jìn)行運(yùn)算，運(yùn)算結(jié)果進(jìn)棧

4.9.3 中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式

標(biāo)準(zhǔn)四則運(yùn)算表達(dá)式即中綴表達(dá)式

4.10 隊(duì)列的定義

先進(jìn)先出的線性表，F(xiàn)IFO
隊(duì)尾：允許插入
隊(duì)頭：允許刪除

4.11 隊(duì)列的抽象數(shù)據(jù)類型

是一種特殊的線性表

4.12 循環(huán)隊(duì)列

4.12.1 隊(duì)列順序存儲(chǔ)的不足

入隊(duì)列操作，時(shí)間復(fù)雜度為O(1)
出隊(duì)列操作，時(shí)間復(fù)雜度為O(n)
假溢出：內(nèi)存利用率不高
front指針：指向隊(duì)頭元素
rear指針：指向隊(duì)尾元素的下一個(gè)位置

4.12.2 循環(huán)隊(duì)列定義

頭尾相接的順序存儲(chǔ)結(jié)構(gòu)的隊(duì)列

4.13 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)

簡(jiǎn)稱鏈隊(duì)列

4.13.1 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)--入隊(duì)操作

入隊(duì)：鏈表尾部插入結(jié)點(diǎn)

4.13.2 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)--出隊(duì)操作

出隊(duì)：頭結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)出隊(duì)，將頭結(jié)點(diǎn)的后繼改為它后面的結(jié)點(diǎn)

4.14 總結(jié)回顧

棧和隊(duì)列都是特殊的線性表，只不過(guò)對(duì)插入和刪除操作做了限制。
棧：

• 順序棧（兩棧共享空間的實(shí)現(xiàn)）
• 鏈棧
  隊(duì)列：
• 順序隊(duì)列（循環(huán)隊(duì)列的實(shí)現(xiàn)）
• 鏈隊(duì)列

4.15 結(jié)尾語(yǔ)

第5章 串

由零個(gè)或多個(gè)字符組成的有限序列，又叫字符串

5.1 開場(chǎng)白

5.2 串的定義

早期計(jì)算機(jī)主要做一些計(jì)算工作，后來(lái)在計(jì)算機(jī)上作非數(shù)值處理的工作越來(lái)越多，就不得不引入對(duì)字符的處理。
空串用“”或希臘字母Φ表示
空格串、子串與主串

5.3 串的比較

通過(guò)組成串的字符之間的編碼來(lái)進(jìn)行的，而字符的編碼指的是字符在對(duì)應(yīng)字符集中的序號(hào)。
標(biāo)準(zhǔn)ASCII編碼：7位二進(jìn)制數(shù)表示一個(gè)字符，總共128個(gè)，后來(lái)拓展到8位二進(jìn)制數(shù)，可以表示256個(gè)字符。
Unicode編碼：常用的是由16位二進(jìn)制數(shù)表示一個(gè)字符，約65萬(wàn)多個(gè)字符，足夠表示世界上所有語(yǔ)言的所有字符，為了和ASCII兼容，前256個(gè)字符和ASCII碼完全相同。
類比查字典

5.4 串的抽象數(shù)據(jù)類型

串的基本操作和線性表的基本操作有很大區(qū)別，線性表關(guān)注的是單個(gè)元素的操作，串更多的是查找子串位子、得到指定位置子串、替換子串等操作。

5.5 串的存儲(chǔ)結(jié)構(gòu)

5.5.1 串的順序存儲(chǔ)結(jié)構(gòu)

容易越界

5.5.2 串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

為了避免浪費(fèi)內(nèi)存空間，可以在一個(gè)結(jié)點(diǎn)存放多個(gè)字符

5.6 樸素的模式匹配算法

子串的定位操作通常稱做串的模式匹配。
對(duì)主串的每一個(gè)字符作為子串開頭，與要匹配的字符串進(jìn)行匹配，對(duì)子串做大循環(huán)，每個(gè)字符開頭做T的長(zhǎng)度的小循環(huán)，直到匹配成功或全部遍歷完成為止。
太過(guò)低效。

5.7 KMP模式匹配算法

以三個(gè)研究過(guò)該算法的前輩的名字縮寫命名。

5.7.1 KMP模式匹配算法原理

5.7.2 next數(shù)組值推導(dǎo)

5.7.3 KMP模式匹配算法實(shí)現(xiàn)

KMP算法僅當(dāng)模式與子串之間存在許多“部分匹配”的情況下才體現(xiàn)出它的優(yōu)勢(shì)，否則兩者差異并不明顯。

KMP模式匹配算法改進(jìn)

5.7.4 KMP模式匹配算法改進(jìn)

5.7.5 nextval數(shù)組值推導(dǎo)

5.8 總結(jié)回顧

5.9 結(jié)尾語(yǔ)

第6章 樹

空樹
根
根的子樹

6.1 開場(chǎng)白

6.2 樹的定義

線性結(jié)構(gòu)：一對(duì)一
樹形結(jié)構(gòu)：一對(duì)多
根節(jié)點(diǎn)是唯一的
子樹個(gè)數(shù)沒(méi)有限制，但它們一定是互不相交的

6.2.1 結(jié)點(diǎn)分類

結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹數(shù)
葉結(jié)點(diǎn)或終端結(jié)點(diǎn)：度為0
非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)：度不為0
內(nèi)部結(jié)點(diǎn)：除根節(jié)點(diǎn)之外的分支結(jié)點(diǎn)
樹的度：樹內(nèi)各結(jié)點(diǎn)的度的最大值

6.2.2 結(jié)點(diǎn)間的關(guān)系

孩子
雙親
兄弟
祖先
子孫

6.2.3 樹的其他相關(guān)概念

結(jié)點(diǎn)的層次
堂兄弟
樹的深度或高度
森林：m棵互不相交的樹的集合

6.3 樹的抽象數(shù)據(jù)類型

6.4 樹的存儲(chǔ)結(jié)構(gòu)

6.4.1 雙親表示法

每個(gè)結(jié)點(diǎn)中，附設(shè)一個(gè)指示器指示其雙親結(jié)點(diǎn)到鏈表中的位置

6.4.2 孩子表示法

每個(gè)結(jié)點(diǎn)有多個(gè)指針域，其中每個(gè)指針指向一棵子樹的根結(jié)點(diǎn)，也叫做多重鏈表表示法。

6.4.3 孩子兄弟表示法

6.5 二叉樹的定義

左子樹和右子樹

6.5.1 二叉樹的特點(diǎn)

• 每個(gè)結(jié)點(diǎn)最多有兩棵子樹
• 左子樹和右子樹是有順序的，次序不能任意顛倒
• 即使結(jié)點(diǎn)只有一棵子樹，也要區(qū)分它是左子樹還是右子樹

6.5.2 特殊二叉樹

1.斜樹：左斜樹、右斜樹
2.滿二叉樹：最完美、最平衡的二叉樹
3.完全二叉樹：滿二叉樹一定是一棵完全二叉樹，但完全二叉樹不一定是滿二叉樹

6.6 二叉樹的性質(zhì)

6.6.1 二叉樹性質(zhì)1

6.6.2 二叉樹性質(zhì)2

6.6.3 二叉樹性質(zhì)3

6.6.4 二叉樹性質(zhì)4

6.6.5 二叉樹性質(zhì)5

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

6.7.1 二叉樹順序存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)一般只用于完全二叉樹

6.7.2 二叉鏈表

data：數(shù)據(jù)域
lchild：左孩子指針域
rchild：右孩子指針域

6.8 遍歷二叉樹

6.8.1 二叉樹遍歷原理

訪問(wèn)
次序

6.8.2 二叉樹遍歷方法

1.前序遍歷
2.中序遍歷
3.后序遍歷
4.層序遍歷

6.8.3 前序遍歷算法

6.8.4 中序遍歷算法

6.8.5 后序遍歷算法

6.8.6 推導(dǎo)遍歷結(jié)果

• 已知前序遍歷序列和中序遍歷序列，可以唯一確定一棵二叉樹
• 已知后序遍歷序列和中序遍歷序列，可以唯一確定一棵二叉樹

6.9 二叉樹的建立

擴(kuò)展二叉樹

6.10 線索二叉樹

6.10.1 線索二叉樹原理

指向前驅(qū)和后繼的指針?lè)Q為線索，加上線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹就稱為線索二叉樹。
線索二叉樹等于是把一棵二叉樹轉(zhuǎn)變成了一個(gè)雙向鏈表。
對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過(guò)程稱作是線索化。
ltag、rtag區(qū)分是指向孩子還是指向前驅(qū)或后繼的。

6.10.2 線索二叉樹結(jié)構(gòu)實(shí)現(xiàn)

線索化的實(shí)質(zhì)就是將二叉樹鏈表中的空指針改為指向前驅(qū)或后繼的線索。所以線索化的過(guò)程就是在遍歷的過(guò)程中修改空指針的過(guò)程。
如果所用的二叉樹需經(jīng)常遍歷或查找結(jié)點(diǎn)時(shí)需要某種遍歷序列中的前驅(qū)和后繼，那么采用線索二叉鏈表的存儲(chǔ)結(jié)構(gòu)是很不錯(cuò)的。

6.11 樹、森林與二叉樹的轉(zhuǎn)換

6.11.1 樹轉(zhuǎn)換為二叉樹

6.11.2 森林轉(zhuǎn)換為二叉樹

6.11.3 二叉樹轉(zhuǎn)換為樹

6.11.4 二叉樹轉(zhuǎn)換為森林

判斷一棵二叉樹能夠轉(zhuǎn)換成一棵樹還是森林的標(biāo)準(zhǔn)：只要看這棵二叉樹的根節(jié)點(diǎn)有沒(méi)有右孩子，有就是森林，沒(méi)有就是一棵樹。

6.11.5 樹與森林的遍歷

6.12 赫夫曼樹及其應(yīng)用

6.12.1 赫夫曼樹

壓縮文件：重新編碼
赫夫曼編碼
成績(jī)?cè)u(píng)級(jí)算法的優(yōu)化

6.12.2 赫夫曼樹定義與原理

路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支
路徑長(zhǎng)度：路徑上的分支數(shù)目
樹的路徑長(zhǎng)度：從樹根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和
赫夫曼樹：帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹稱為赫夫曼樹，也稱為最優(yōu)二叉樹。
尋找最優(yōu)二叉樹的步驟。

6.12.3 赫夫曼編碼

解決遠(yuǎn)距離通信（主要是電報(bào)）的數(shù)據(jù)傳輸?shù)淖顑?yōu)化問(wèn)題

6.13 總結(jié)回顧

需要在理解的基礎(chǔ)上去記憶。
二叉樹的遍歷，前序、中序、后序以及層序遍歷都是需要熟練掌握的。

6.14 結(jié)尾語(yǔ)

第7章 圖

7.1 開場(chǎng)白

7.2 圖的定義

線性表：線性關(guān)系
樹形結(jié)構(gòu)：類比人類族譜，一對(duì)多
圖：更復(fù)雜，結(jié)點(diǎn)之間的關(guān)系可以是任意的

元素：線性表中的單位
結(jié)點(diǎn)：樹中的數(shù)據(jù)元素
頂點(diǎn)：圖中的數(shù)據(jù)元素

線性關(guān)系：線性表中相鄰元素之間的關(guān)系
層次關(guān)系：樹結(jié)構(gòu)中，相鄰兩層結(jié)點(diǎn)的關(guān)系
邊：圖中任意兩個(gè)頂點(diǎn)之間都可能有關(guān)系，頂點(diǎn)之間的邏輯關(guān)系用邊表示

7.2.1 各種圖的定義

無(wú)向邊：頂點(diǎn)之間的邊沒(méi)有方向
無(wú)序偶對(duì)
無(wú)向圖
無(wú)向完全圖

有向邊：也稱為弧
弧頭、弧尾
有向圖
有向完全圖
簡(jiǎn)單圖

稀疏圖、稠密圖

權(quán)：與圖或弧相關(guān)的數(shù)
網(wǎng)：帶權(quán)的圖

子圖

7.2.2 圖的頂點(diǎn)與邊間關(guān)系

互為鄰接點(diǎn)（有向圖）
鄰接到、鄰接自（無(wú)向圖）

頂點(diǎn)的度：和頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目（有向圖）
入度、出度、度=入度+出度（有向圖）

頂點(diǎn)序列：一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的所有路徑
路徑長(zhǎng)度：邊或弧的數(shù)目

回路或環(huán)：首尾頂點(diǎn)相同的路徑
簡(jiǎn)單路徑、簡(jiǎn)單回路、簡(jiǎn)單環(huán)

7.2.3 連通圖相關(guān)術(shù)語(yǔ)

連通圖（無(wú)向圖）
連通分量（無(wú)向圖）

強(qiáng)連通圖（有向圖）
強(qiáng)連通分量（有向圖）

有向樹

7.2.4 圖的定義與術(shù)語(yǔ)總結(jié)

7.3 圖的抽象數(shù)據(jù)類型

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

圖的存儲(chǔ)結(jié)構(gòu)更復(fù)雜。不能用順序存儲(chǔ)結(jié)構(gòu)來(lái)表示，也不推薦多重鏈表的方式，會(huì)造成很多存儲(chǔ)單元的浪費(fèi)，或者操作的不便。

7.4.1 鄰接矩陣

頂點(diǎn)：一維數(shù)組存儲(chǔ)
邊或?。憾S數(shù)組存儲(chǔ)
鄰接矩陣：一維+二維

無(wú)向圖的邊數(shù)組是一個(gè)對(duì)稱矩陣。

網(wǎng)的鄰接矩陣，需要包含權(quán)值信息。

7.4.2 鄰接表

鄰接矩陣的缺點(diǎn)：邊數(shù)較少（稀疏圖）時(shí)，會(huì)極大浪費(fèi)存儲(chǔ)空間。
鄰接表：數(shù)組和鏈表相結(jié)合的存儲(chǔ)方式稱為鄰接表。

邊表（無(wú)向圖）
弧尾的出邊表（有向圖）

統(tǒng)計(jì)頂點(diǎn)的出度：鄰接表很清晰
統(tǒng)計(jì)頂點(diǎn)的入度：逆鄰接表

網(wǎng)的鄰接表：邊表結(jié)點(diǎn)中新增weight數(shù)據(jù)域

7.4.3 十字鏈表

正向思維、逆向思維、整合思維
同時(shí)統(tǒng)計(jì)出度和入度：鄰接表+逆鄰接表=十字鏈表

7.4.4 鄰接多重表

為了簡(jiǎn)化無(wú)向圖的邊操作

7.4.5 邊集數(shù)組

關(guān)注的是邊的集合，查找度效率太低。

7.5 圖的遍歷

7.5.1 深度優(yōu)先遍歷

也稱深度優(yōu)先搜索，簡(jiǎn)稱DFS.
走迷宮策略。

7.5.2 廣度優(yōu)先遍歷

也稱廣度優(yōu)先搜索，簡(jiǎn)稱BFS.

深度與廣度算法在時(shí)間復(fù)雜度上是一樣的，不同之處在于對(duì)頂點(diǎn)訪問(wèn)的順序不同。

7.6 最小生成樹

構(gòu)造連通網(wǎng)的最小代價(jià)生成樹稱為最小生成樹。

7.6.1 普里姆算法

7.6.2 克魯斯卡爾算法

7.7 最短路徑

網(wǎng)圖最短路徑：權(quán)值之和最少的路徑，源點(diǎn)、終點(diǎn)。
人腦是用來(lái)創(chuàng)造而不是做枯燥復(fù)雜的計(jì)算的。

7.7.1 迪杰斯特拉算法

解決了從某個(gè)源頭到其余各頂點(diǎn)的最短路徑問(wèn)題。

7.7.2 弗洛伊德算法

所有頂點(diǎn)至所有頂點(diǎn)的最短路徑問(wèn)題可以選擇弗洛伊德算法。

7.8 拓?fù)渑判?/h3>

7.8.1 拓?fù)渑判蚪榻B

AOV網(wǎng)：表示工程，用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)之間的優(yōu)先關(guān)系的有向圖。
對(duì)一個(gè)有向圖構(gòu)造拓?fù)湫蛄械倪^(guò)程。

7.8.2 拓?fù)渑判蛩惴?/h4>

入度域

7.9 關(guān)鍵路徑

AOE網(wǎng)：表示工程，用頂點(diǎn)表示事件，用有向邊表示活動(dòng)，用邊上的權(quán)值表示活動(dòng)的持續(xù)時(shí)間的帶權(quán)有向圖。
路徑長(zhǎng)度
關(guān)鍵路徑、關(guān)鍵活動(dòng)

7.9.1 關(guān)鍵路徑算法原理

7.9.2 關(guān)鍵路徑算法

存在多條關(guān)鍵路徑的有向無(wú)環(huán)圖，只提高一條關(guān)鍵路徑上的關(guān)鍵活動(dòng)的速度并不能導(dǎo)致整個(gè)工程縮短工期，而必須同時(shí)在幾條關(guān)鍵路徑上提高活動(dòng)的速度。
就像僅僅有事業(yè)的成功，而沒(méi)有健康的身體以及快樂(lè)的生活，壓根談不上幸福的人生。

7.10 總結(jié)回顧

7.11 結(jié)尾語(yǔ)

第8章 查找

8.1 開場(chǎng)白

搜索引擎：網(wǎng)絡(luò)蜘蛛
關(guān)鍵字的云端之旅

8.2 查找概論

• 查找表
• 關(guān)鍵字（鍵值）、關(guān)鍵碼
• 主關(guān)鍵字、主關(guān)鍵碼
• 次關(guān)鍵字、次關(guān)鍵碼
  查找方式
• 靜態(tài)查找表：只查詢檢索
• 動(dòng)態(tài)查找表：查找過(guò)程中同時(shí)插入或刪除

8.3 順序表查找

順序查找（線性查找）

8.3.1 順序表查找算法

循環(huán)查找

8.3.2 順序表查找優(yōu)化

哨兵
參考：順序表查找優(yōu)化（哨兵元素的重要作用）

8.4 有序表查找

有序排序
時(shí)間復(fù)雜度:O(n)

8.4.1 折半查找

• 猜數(shù)字游戲
• 折半查找又稱二分查找
• 前提：關(guān)鍵碼有序
• 時(shí)間復(fù)雜度:O(㏒n)

8.4.2 插值查找

• 翻字典時(shí)有意識(shí)的往前或往后翻。
• 數(shù)學(xué)推導(dǎo)過(guò)程
• 核心是插值的計(jì)算公式：與最大最小記錄的關(guān)鍵字比較后的查找方法

8.4.3 斐波那契查找

• 黃金分割原理
• 折半查找是進(jìn)行加法和除法運(yùn)算
• 插值查找是進(jìn)行復(fù)雜的四則運(yùn)算
• 斐波那契查找只是最簡(jiǎn)單的加減法運(yùn)算
• 海量數(shù)據(jù)的查找過(guò)程中，細(xì)微差別也可能會(huì)影響查找效率
• 三種查找本質(zhì)上是分隔點(diǎn)的選擇不同，各有優(yōu)劣

8.5 線性索引查找

• 實(shí)際上，考慮時(shí)間代價(jià)，很多數(shù)據(jù)都不是關(guān)鍵字有序的。
• 索引：加快查找速度而設(shè)計(jì)的一種數(shù)據(jù)結(jié)構(gòu)。關(guān)鍵字與對(duì)應(yīng)的記錄相關(guān)聯(lián)的過(guò)程。
• 線性索引、樹形索引、多級(jí)索引
• 線性索引（索引表）：稠密索引、分塊索引、倒排索引

8.5.1 稠密索引

• 本子記錄家中所有物品的位置，本子就是索引
• 稠密索引的索引表一定是按照關(guān)鍵碼有序的排列
• 缺點(diǎn)：數(shù)據(jù)集非常大時(shí)，索引表規(guī)模很大，性能下降

8.5.2 分塊索引

• 類比圖書館的圖書分類體系
• 先分塊再建立索引，減少索引項(xiàng)的個(gè)數(shù)
• 塊內(nèi)無(wú)序、塊內(nèi)有序
• 分塊索引在兼顧了對(duì)細(xì)分塊不需要有序的情況下，大大增加了整體查找的速度，所以普遍被用于數(shù)據(jù)庫(kù)表查找等技術(shù)中。

8.5.3 倒排索引

• 搜索引擎的高效查找

8.6 二叉排序樹

• 老虎追趕問(wèn)題。
• 所謂優(yōu)勢(shì)只不過(guò)是比別人多深入思考一點(diǎn)而已。
• 提高查找和插入刪除關(guān)鍵字的速度

8.6.1 二叉排序樹查找操作

8.6.2 二叉排序樹插入操作

8.6.3 二叉排序樹刪除操作

8.6.4 二叉排序樹總結(jié)

• 查找性能取決于二叉排序樹的形狀
• 最好是構(gòu)建一棵平衡的二叉排序樹

8.7 平衡二叉樹(AVL樹)

• 每一個(gè)節(jié)點(diǎn)的左子樹和右子樹的高度差至多為1
• 平衡因子：結(jié)點(diǎn)左子樹減去右子樹深度，-1、0或1
• 前提必須是一棵二叉排序樹

8.7.1 平衡二叉樹實(shí)現(xiàn)原理

• 不停旋轉(zhuǎn)，左旋或右旋
• 一旦有不平衡的情況，馬上處理

8.7.2 平衡二叉樹實(shí)現(xiàn)算法

• 把不平衡消滅在萌芽

8.8 多路查找樹（B樹）

• 語(yǔ)言是溝通的工具，文字是記錄存證的工具，而文字化的過(guò)程，又可以讓思考徹底沉淀，善于使用文字的人，通常是深沉而嚴(yán)謹(jǐn)?shù)摹?/li>
• 內(nèi)存由硅制的存儲(chǔ)芯片組成，每個(gè)存儲(chǔ)單位代價(jià)都要比磁存儲(chǔ)技術(shù)昂貴兩個(gè)數(shù)量級(jí)
• 之前討論的數(shù)據(jù)結(jié)構(gòu)，考慮的都是內(nèi)存中的運(yùn)算時(shí)間復(fù)雜度
• 涉及到外部存儲(chǔ)設(shè)備，時(shí)間復(fù)雜度的計(jì)算就會(huì)發(fā)生變化，考慮對(duì)外部設(shè)備的訪問(wèn)時(shí)間
• 多路查找樹，其每一個(gè)節(jié)點(diǎn)的孩子數(shù)可以多于兩個(gè)，且每一個(gè)結(jié)點(diǎn)處可以存儲(chǔ)多個(gè)元素

8.8.1 2-3樹

• 多路查找樹：每一個(gè)結(jié)點(diǎn)都具有兩個(gè)或三個(gè)孩子
• 2結(jié)點(diǎn)：1個(gè)元素+（2個(gè)孩子或0個(gè)孩子）
• 3結(jié)點(diǎn)：一大一小2個(gè)元素+（3個(gè)孩子或0個(gè)孩子）
• 所有葉子都在同一層次
• 2-3樹的插入實(shí)現(xiàn)
• 2-3樹的刪除實(shí)現(xiàn)

8.8.2 2-3-4樹

• 4結(jié)點(diǎn)：小中大3個(gè)元素+（4個(gè)孩子或沒(méi)有孩子）

8.8.3 B樹

• 是一種平衡的多路查找樹
• B樹的階:結(jié)點(diǎn)最大的孩子數(shù)目

8.8.4 B+樹

8.9 散列表查找(哈希表)概述

• 之前的查找方法，“比較”都不可避免

8.9.1 散列表查找定義

• 存儲(chǔ)位置 = f(關(guān)鍵字)
• 散列技術(shù)：在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系f，使得每個(gè)關(guān)鍵字key對(duì)應(yīng)一個(gè)存儲(chǔ)位置f(key)
• 散列函數(shù)(哈希函數(shù))：對(duì)應(yīng)關(guān)系f
• 散列表(哈希表)：采用散列技術(shù)將記錄存儲(chǔ)在一塊連續(xù)的存儲(chǔ)空間，這塊存儲(chǔ)空間的名稱

8.9.2 散列表查找步驟

• 第一步(存儲(chǔ))：每一個(gè)記錄，都需要用同一個(gè)散列函數(shù)計(jì)算出地址再存儲(chǔ)
• 第二步(查找)：通過(guò)同樣的散列函數(shù)計(jì)算記錄的散列地址
• 散列技術(shù)的記錄之間不存在什么邏輯關(guān)系，只與關(guān)鍵字有關(guān)聯(lián)，所以是面向查找的存儲(chǔ)結(jié)構(gòu)
• 優(yōu)點(diǎn)：簡(jiǎn)化了查找的比較過(guò)程，效率極高
• 缺點(diǎn)：不具備很多常規(guī)數(shù)據(jù)結(jié)構(gòu)的能力
• 散列技術(shù)關(guān)鍵：散列函數(shù)的簡(jiǎn)單、均勻、存儲(chǔ)利用率高
• 沖突：key1≠key2 但是f(key1) = f(key2)
• 同義詞：key1和key2
• 沖突不能完全避免，只能盡量減小

8.10 散列函數(shù)的構(gòu)造方法

• 計(jì)算簡(jiǎn)單
• 散列地址分布均勻

8.10.1 直接定址法

• 取關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址

8.10.2 數(shù)字分析法

• 抽?。菏褂藐P(guān)鍵字的一部分來(lái)計(jì)算散列存儲(chǔ)位置

8.10.3 平方取中法

• 不知道關(guān)鍵字的分布，位數(shù)較小

8.10.4 折疊法

8.10.5 除留余數(shù)法

• f(key) = key mod p (p ≦ m)
• 散列表表廠為m，通常p為小于或等于表廠的最小質(zhì)數(shù)，或不包含小于20質(zhì)因子的合數(shù)

8.10.6 隨機(jī)數(shù)法

• f(key) = random(key)

8.11 處理散列沖突的方法

8.11.1 開放定址法

• 線性探測(cè)法
• 堆積：不是同義詞，卻爭(zhēng)奪一個(gè)地址
• 二次探測(cè)法：增加平方運(yùn)算
• 隨機(jī)探測(cè)法：偽隨機(jī)數(shù)、隨機(jī)種子

8.11.2 再散列函數(shù)法

• 多準(zhǔn)備幾個(gè)散列函數(shù)

8.11.3 鏈地址法

• 同義詞子表
• 存在遍歷單鏈表的性能損耗

8.11.4 公共溢出區(qū)法

• 為所有沖突的關(guān)鍵字建立一個(gè)公共的溢出區(qū)來(lái)存放

8.12 散列表查找實(shí)現(xiàn)

8.12.1 散列表查找算法實(shí)現(xiàn)

8.12.2 散列表查找性能分析

• 散列函數(shù)是否均勻
• 處理沖突的方法
• 散列表的裝填因子

8.13 總結(jié)回顧

8.14 結(jié)尾語(yǔ)

第9章 排序

9.1 開場(chǎng)白

9.2 排序的基本概念與分類

• 記錄：數(shù)據(jù)元素
• 依據(jù)：關(guān)鍵字的大小
• 關(guān)鍵字可以是主關(guān)鍵字，也可以是次關(guān)鍵字，甚至是若干記錄的組合
• 多個(gè)關(guān)鍵字的排序最終都可以轉(zhuǎn)化為單個(gè)關(guān)鍵字的排序

9.2.1 排序的穩(wěn)定性

• 關(guān)鍵字相同時(shí)，排序后前后順序是否變化

9.2.2 內(nèi)排序與外排序

• 內(nèi)排序：記錄個(gè)數(shù)少，排序時(shí)全放在內(nèi)存中
• 外排序：記錄個(gè)數(shù)太多，排序時(shí)需要在內(nèi)外存之間多次交換數(shù)據(jù)

內(nèi)排序算法的性能：

• 時(shí)間性能：排序往往屬于系統(tǒng)的核心功能，比較和移動(dòng)操作要盡可能的少
• 輔助空間
• 算法的復(fù)雜性：算法本身的復(fù)雜度

內(nèi)排序常用方法：

• 插入排序
• 交換排序
• 選擇排序
• 歸并排序

簡(jiǎn)單算法：

• 冒泡排序
• 簡(jiǎn)單選擇排序
• 直接插入排序

改進(jìn)算法：

• 希爾排序
• 堆排序
• 歸并排序
• 快速排序

9.2.3 排序用到的結(jié)構(gòu)與函數(shù)

9.3 冒泡排序

9.3.1 最簡(jiǎn)單排序?qū)崿F(xiàn)

• 冒泡基本思想：兩兩比較相鄰記錄的關(guān)鍵字，如果反序則交換，直到?jīng)]有反序的記錄為止
• 最簡(jiǎn)單排序算法效率很低

9.3.2 冒泡排序算法

• 冒泡算法由來(lái)

9.3.3 冒泡算法優(yōu)化

• 避免因已經(jīng)有序的情況下的無(wú)意義循環(huán)判斷

9.3.4 冒泡排序復(fù)雜度分析

9.4 簡(jiǎn)單選擇排序

9.4.1 簡(jiǎn)單選擇排序算法

9.4.2 簡(jiǎn)單選擇排序復(fù)雜度分析

• 時(shí)間復(fù)雜度為O(n2)
• 性能上略優(yōu)于冒泡排序

9.5 直接插入排序

• 類比理牌

9.5.1 直接插入排序算法

9.5.2 直接插入排序復(fù)雜度分析

• 時(shí)間復(fù)雜度為O(n2)
• 性能上優(yōu)于冒泡和簡(jiǎn)單選擇排序

9.6 希爾排序

Ⅸ變6的幾種方法

• 翻轉(zhuǎn)截取
• 加S變?yōu)镾IX
• 加6變?yōu)镮X6
  超越歷史，復(fù)雜度超越O(n2)

9.6.1 希爾排序原理

• 跳躍分割策略：將相距某個(gè)“增量”的記錄組成一個(gè)子序列，保證基本有序

9.6.2 希爾排序算法

• 將相隔某個(gè)“增量”的記錄組成一個(gè)子序列，實(shí)現(xiàn)跳躍式的移動(dòng)

9.6.3 希爾排序復(fù)雜度分析

• 難點(diǎn)是增量的選取
• 并不是一種穩(wěn)定的排序算法

9.7 堆排序

• 堆是特殊的完全二叉樹
• 大頂堆：每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值
• 小頂堆：每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值

9.7.1 堆排序算法

9.7.2 堆排序復(fù)雜度分析

9.8 歸并排序

9.8.1 歸并排序算法

• 歸并：將兩個(gè)或兩個(gè)以上的有虛表組合成一個(gè)新的有序表
• 歸并排序、2路歸并排序

9.8.2 歸并排序復(fù)雜度分析

• 歸并排序是一種比較占用內(nèi)存，但卻效率高且穩(wěn)定的算法

9.8.3 非遞歸實(shí)現(xiàn)歸并排序

• 大量使用遞歸會(huì)造成空間上的性能損耗

9.9 快速排序

• 20世紀(jì)十大算法之一
• 冒泡排序的升級(jí)

9.9.1 快速排序算法

• 基本思想：通過(guò)一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序的目的。

9.9.2 快速排序復(fù)雜度分析

• 由于關(guān)鍵字的比較和交換是跳躍進(jìn)行的，因此，快速排序是一種不穩(wěn)定的排序方法

9.9.3 快速排序優(yōu)化

1.優(yōu)化選取樞軸

• 關(guān)鍵字太大或太小都會(huì)影響性能
• 隨機(jī)選取，全憑運(yùn)氣
• 三數(shù)取中法（小數(shù)組）
• 九數(shù)取中法（很大的數(shù)組）
  2.優(yōu)化不必要的交換
  3.優(yōu)化小數(shù)組時(shí)的排序方案
• 大材小用有時(shí)會(huì)變得反而不好用
• 小數(shù)組排序不需要使用快速排序法，用直接插入排序效果更好
  4.優(yōu)化遞歸操作
• 遞歸會(huì)消耗棧空間
  5.了不起的排序算法
• 至少今天，快速排序在整體性能上，依然是排序算法王者

9.10 總結(jié)回顧

• 目前還沒(méi)有十全十美的排序算法，有優(yōu)點(diǎn)就會(huì)有缺點(diǎn)
• 綜合指標(biāo)：經(jīng)過(guò)優(yōu)化的快速排序是性能最好的排序算法，但是不同的場(chǎng)合我們也應(yīng)該考慮使用不同的算法來(lái)應(yīng)對(duì)它

9.11 結(jié)尾語(yǔ)

• 算法研究者：都是在“似乎不可能”的情況下，逐步提高排序算法的性能
• 不是不可能用四段、三段、一段直線一筆連九點(diǎn)，只是暫時(shí)還沒(méi)有找到方法而已，所有的事情都是可能的，只是我們暫時(shí)還沒(méi)有找到方法而已