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

數(shù)據(jù)

數(shù)據(jù)：人類氛驮、動(dòng)物贷盲、植物...
數(shù)據(jù)對(duì)象：人類
數(shù)據(jù)元素：一個(gè)人
數(shù)據(jù)項(xiàng)：眼、耳觉吭、鼻...(數(shù)據(jù)不可分割的最小單位)

Snip20170718_13.png

結(jié)構(gòu)

邏輯結(jié)構(gòu)：集合結(jié)構(gòu)宜鸯、線性結(jié)構(gòu)憔古、樹(shù)形結(jié)構(gòu)、圖形結(jié)構(gòu)
物理結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)淋袖、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

Snip20170718_14.png

抽象數(shù)據(jù)結(jié)構(gòu)類型

Snip20170718_12.png

第二章 算法

示例

Snip20170718_15.png

算法效率的度量 -- 時(shí)間復(fù)雜度

時(shí)間復(fù)雜度：T(n) = O(f(n))
T(n):執(zhí)行次數(shù)
n:問(wèn)題規(guī)模
f(n):
測(cè)定運(yùn)行時(shí)間最可靠的方法就是計(jì)算對(duì)運(yùn)行時(shí)間有消耗的基本操作的執(zhí)行次數(shù)投放。運(yùn)行時(shí)間和這個(gè)成正比。

常數(shù)階 O(1)

線性階 O(n)

Snip20170718_16.png

對(duì)數(shù)階 O(log n)

Snip20170718_19.png

平方階 O(n2)

Snip20170718_21.png

心得：以是否存在循環(huán)和循環(huán)嵌套情況來(lái)判斷時(shí)間復(fù)雜度

平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度

常見(jiàn)時(shí)間復(fù)雜度

Snip20170718_20.png

算法效率的度量 -- 空間復(fù)雜度

空間復(fù)雜度:S(n) = O(f(n))

第三章 線性表

Snip20170718_41.png

線性表：零個(gè)或多個(gè)數(shù)據(jù)元素的有限序列

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

Snip20170718_27.png

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

存取性能為O(1),這種稱為隨機(jī)存儲(chǔ)結(jié)構(gòu)

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

插入刪除性能為O(n)

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

結(jié)點(diǎn)：數(shù)據(jù)域+指針域
指針域
數(shù)據(jù)域
單鏈表
頭指針
頭結(jié)點(diǎn)：空的數(shù)據(jù)域+頭指針（非必要）

Snip20170718_31.png

Snip20170718_30.png

單鏈表的讀取

O(n)

單鏈表的插入與刪除

O(1)

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

“頭插法”

Snip20170718_32.png

“尾插法”

Snip20170718_36.png

單鏈表的整表刪除

靜態(tài)鏈表

靜態(tài)鏈表：數(shù)組描述的鏈表

Snip20170718_38.png

循環(huán)鏈表

循環(huán)鏈表

Snip20170718_39.png

雙向鏈表

Snip20170718_40.png

第四章 棧與隊(duì)列

Snip20170718_48.png

棧：僅在表尾進(jìn)行插入和刪除操作的線性表
進(jìn)棧：壓棧适贸、入棧
出棧：彈棧

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

Snip20170718_42.png

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

棧的結(jié)構(gòu)定義
入棧
出棧

兩棧共享空間

Snip20170718_43.png

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

把棧頂放在單鏈表的頭部，不需要頭結(jié)點(diǎn)
進(jìn)棧
出棧

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

斐波拉切數(shù)列：前面兩項(xiàng)相鄰之和構(gòu)成后一項(xiàng) （1 2 3 5 8 ...）
遞歸 ：自己調(diào)用自己

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

Snip20170718_46.png

中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式規(guī)則：

Snip20170718_44.png

后綴表達(dá)式計(jì)算規(guī)則：

Snip20170718_45.png

隊(duì)列

隊(duì)列：只允許在一端進(jìn)行插入操作涝桅，另一端進(jìn)行刪除操作的線性表

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

Snip20170718_47.png

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

隊(duì)列的鏈?zhǔn)酱鎯?chǔ)

第五章 串（字符串）

Snip20170718_49.png

主串
子串
空格串
ASCII編碼

Snip20170718_50.png

串的比較

串的順序和鏈?zhǔn)酱鎯?chǔ)

串的模式匹配 -- 樸素的算法

太低效了

串的模式匹配 -- KMP算法

第六章 樹(shù)

樹(shù)
根
空樹(shù)
子樹(shù)
結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹(shù)數(shù)
葉結(jié)點(diǎn)拜姿、終端結(jié)點(diǎn)：度為0
分支結(jié)點(diǎn)、非終端結(jié)點(diǎn)：度不為0 （分支結(jié)點(diǎn)=根節(jié)點(diǎn)+內(nèi)部結(jié)點(diǎn)）
結(jié)點(diǎn)的層次
樹(shù)的深度冯遂、樹(shù)的高度
有序樹(shù)蕊肥、無(wú)序樹(shù)
森林

Snip20170719_52.png

樹(shù)的抽象結(jié)構(gòu)類型

Snip20170719_53.png

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

雙親表示法:記錄父節(jié)點(diǎn)
孩子表示法：記錄所有的孩子；改進(jìn)版雙親孩子表示法

Snip20170719_55.png

孩子兄弟表示法：記錄第一個(gè)孩子和右兄弟

二叉樹(shù)

二叉樹(shù)

Snip20170719_56.png

特殊二叉樹(shù)

斜樹(shù)
滿二叉樹(shù)

Snip20170719_58.png

完全二叉樹(shù):與滿二叉樹(shù)位置編號(hào)相同蛤肌，只不過(guò)不滿

Snip20170719_59.png

二叉樹(shù)性質(zhì)

1-5

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

順序存儲(chǔ)一般只用于完全二叉樹(shù)

二叉樹(shù)存儲(chǔ)結(jié)構(gòu)--鏈?zhǔn)酱鎯?chǔ)

Snip20170719_60.png

遍歷二叉樹(shù)--前序

Snip20170719_61.png

算法實(shí)現(xiàn)：

Snip20170719_65.png

遍歷二叉樹(shù)--中序

Snip20170719_62.png

算法實(shí)現(xiàn)：

Snip20170719_66.png

遍歷二叉樹(shù)--后序

Snip20170719_63.png

算法實(shí)現(xiàn)：

Snip20170719_67.png

遍歷二叉樹(shù)--層序遍歷

Snip20170719_64.png

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

Snip20170719_68.png

前序：從根節(jié)點(diǎn)開(kāi)始壁却，先遍歷左子樹(shù)，再遍歷右子樹(shù)
中序：從“左下角"開(kāi)始, 中 --> 右
后序：從“左下角"開(kāi)始裸准，右 --> 中

線索二叉樹(shù)

樹(shù)展东、森林與二叉樹(shù)轉(zhuǎn)換

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

赫夫曼編碼：最基本的壓縮編碼方法

第七章 圖

圖：頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通常表示為：G（V,E）炒俱，其中G表示為一個(gè)圖盐肃，V表示頂點(diǎn)集合爪膊，G表示邊的集合
頂點(diǎn)：和線性表、樹(shù)不同砸王，圖中不可以沒(méi)有頂點(diǎn)
邊：
無(wú)向圖：

Snip20170725_80.png

完全無(wú)向圖：

Snip20170725_84.png

有向圖
有向邊 弧 弧頭 弧尾

Snip20170725_82.png

稀疏圖：
稠密圖：
權(quán)：

Snip20170725_85.png

網(wǎng)：
子圖：

第八章 查找

第九章 排序