數(shù)據(jù)結(jié)構(gòu)與算法

第1章 引論
1.1 算法及其復(fù)雜性的概念
1.1.1 算法與程序
1.1.2 算法復(fù)雜性的概念
1.1.3 算法復(fù)雜性的漸近性態(tài)
1.2 算法的表達(dá)與數(shù)據(jù)表示
1.2.1 問題求解
1.2.2 表達(dá)算法的抽象機(jī)制
1.3 抽象數(shù)據(jù)類型
1.3.1 抽象數(shù)據(jù)類型的基本概念
1.3.2 使用抽象數(shù)據(jù)類型的好處
1.4 數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型
1.5 用C語言描述數(shù)據(jù)結(jié)構(gòu)與算法
1.5.1 變量和指針
1.5.2 函數(shù)與參數(shù)傳遞
1.5.3 結(jié)構(gòu)
1.5.4 動態(tài)存儲分配
本章小結(jié)
習(xí)題
第2章 表
2.1 ADT表
2.2 用數(shù)組實(shí)現(xiàn)表
2.3 用指針實(shí)現(xiàn)表
2.4 用間接尋址方法實(shí)現(xiàn)表
2.5 用游標(biāo)實(shí)現(xiàn)表
2.6 循環(huán)鏈表
2.7 雙鏈表
2.8 表的搜索游標(biāo)
2.8.1 用數(shù)組實(shí)現(xiàn)表的搜索游標(biāo)
2.8.2 單循環(huán)鏈表的搜索游標(biāo)
2.9 應(yīng)用
本章小結(jié)
習(xí)題
第3章 棧
3.1 ADT棧
3.2 用數(shù)組實(shí)現(xiàn)棧
3.3 用指針實(shí)現(xiàn)棧
3.4 應(yīng)用
本章小結(jié)
習(xí)題
第4章 隊(duì)列
4.1 ADT隊(duì)列
4.2 用指針實(shí)現(xiàn)隊(duì)列
4.3 用循環(huán)數(shù)組實(shí)現(xiàn)隊(duì)列
4.4 應(yīng)用
本章小結(jié)
習(xí)題
第5章 遞歸
5.1 遞歸的概念
5.2 遞歸程序設(shè)計
5.2.1 分治與遞歸
5.2.2 動態(tài)規(guī)劃
5.2.3 回溯與遞歸
5.3 模擬遞歸
5.4 應(yīng)用
本章小結(jié)
習(xí)題
第6章 排序與選擇
6.1 簡單排序算法
6.1.1 冒泡排序
6.1.2 插入排序
6.1.3 選擇排序
6.1.4 簡單排序算法的計算復(fù)雜性
6.2 快速排序算法
6.2.1 算法基本思想及實(shí)現(xiàn)
6.2.2 算法的性能
6.2.3 隨機(jī)快速排序算法
6.2.4 非遞歸快速排序算法
6.2.5 三數(shù)取中劃分算法
6.2.6 三劃分快速排序算法
6.3 合并排序算法
6.3.1 算法基本思想及實(shí)現(xiàn)
6.3.2 對基本算法的改進(jìn)
6.3.3 自底向上的合并排序算法
6.3.4 自然合并排序
6.3.5 鏈表結(jié)構(gòu)的合并排序算法
6.4 線性時間排序算法
6.4.1 計數(shù)排序
6.4.2 桶排序
6.5 中位數(shù)與第k小元素
6.5.1 平均情況下的線性時間選擇算法
6.5.2 最壞情況下的線性時間選擇算法
6.6 應(yīng)用
本章小結(jié)
習(xí)題
第7章 樹
7.1 樹的定義
7.2 樹的遍歷
7.3 樹的表示法
7.3.1 父結(jié)點(diǎn)數(shù)組表示法
7.3.2 兒子鏈表表示法
7.3.3 左兒子右兄弟表示法
7.4 二叉樹
7.5 ADT二叉樹
7.6 二叉樹的實(shí)現(xiàn)
7.6.1 二叉樹的順序存儲結(jié)構(gòu)
7.6.2 二叉樹的結(jié)點(diǎn)度表示法
7.6.3 用指針實(shí)現(xiàn)二叉樹
7.7 線索二叉樹
7.8 應(yīng)用
本章小結(jié)
習(xí)題
第8章 集合
8.1 以集合為基礎(chǔ)的抽象數(shù)據(jù)類型
8.1.1 集合的定義和記號
8.1.2 定義在集合上的基本運(yùn)算
8.2 用位向量實(shí)現(xiàn)集合
8.3 用鏈表實(shí)現(xiàn)集合
8.4 應(yīng)用
本章小結(jié)
習(xí)題
第9章 符號表
9.1 實(shí)現(xiàn)符號表的簡單方法
9.2 用散列表實(shí)現(xiàn)符號表
9.2.1 開散列
9.2.2 閉散列
9.2.3 散列函數(shù)及其效率
9.2.4 閉散列的重新散列技術(shù)
9.3 應(yīng)用
本章小結(jié)
習(xí)題
第10章 字典
10.1 字典的定義
10.2 用數(shù)組實(shí)現(xiàn)字典
10.3 用二叉搜索樹實(shí)現(xiàn)字典
10.4 AVL樹
10.4.1 AVL樹的定義和性質(zhì)
10.4.2 旋轉(zhuǎn)變換
10.4.3 AVL樹的插入運(yùn)算
10.4.4 AVL樹的刪除運(yùn)算
10.5 應(yīng)用
本章小結(jié)
習(xí)題
第11章 優(yōu)先隊(duì)列
11.1 優(yōu)先隊(duì)列的定義
11.2 用字典實(shí)現(xiàn)優(yōu)先隊(duì)列
11.3 優(yōu)先級樹和堆
11.4 用數(shù)組實(shí)現(xiàn)堆
11.5 可并優(yōu)先隊(duì)列
11.5.1 左偏樹的定義
11.5.2 用左偏樹實(shí)現(xiàn)呵并優(yōu)先隊(duì)列
11.6 應(yīng)用
本章小結(jié)
習(xí)題
第12章 并查集
12.1 并查集的定義及其簡單實(shí)現(xiàn)
12.2 用父親數(shù)組實(shí)現(xiàn)并查集
12.3 應(yīng)用
本章小結(jié)
習(xí)題
第13章 圖
13.1 圖的基本概念
13.2 抽象數(shù)據(jù)類型ADT圖
13.3 圖的表示法
13.3.1 鄰接矩陣表示法
13.3.2 鄰接表表示法
13.3.3 緊縮鄰接表
13.4 用鄰接矩陣實(shí)現(xiàn)圖
13.4.1 用鄰接矩陣實(shí)現(xiàn)賦權(quán)有向圖
13.4.2 閑鄰接矩陣實(shí)現(xiàn)賦權(quán)無向圖
13.4.3 用鄰接矩陣實(shí)現(xiàn)有向圖
13.4.4 用鄰接矩陣實(shí)現(xiàn)無向圖
13.5 用鄰接表實(shí)現(xiàn)圖
13.5.1 用鄰接表實(shí)現(xiàn)有向圖
13.5.2 用鄰接表實(shí)現(xiàn)無向圖
13.5.3 用鄰接表實(shí)現(xiàn)賦權(quán)有向圖
13.5.4 用鄰接表實(shí)現(xiàn)賦權(quán)無向圖
13.6 圖的遍歷
13.6.1 廣度優(yōu)先搜索
13.6.2 深度優(yōu)先搜索
13.7 最短路徑
13.7.1 單源最短路徑
13.7.2 所有頂點(diǎn)對之間的最短路徑
13.8 最小支撐樹
13.8.1 最小支撐樹性質(zhì)
13.8.2 Prim算法
13.8.3 Kruskal算法
13.9 圖匹配
本章小結(jié)
習(xí)題
參考文獻(xiàn)