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

第1章 基礎(chǔ)
1.1 什么是數(shù)據(jù)結(jié)構(gòu)
1.2 程序性能分析
1.2.1 程序性能的衡量標準
1.2.2 程序的事后測試
1.2.3 時間復雜性的計算方法
1.2.4 空間復雜性的計算方法
1.2.5 計算復雜性的表示方法
1.2.6 兩種代價計算方法的比較
1.3 從抽象數(shù)據(jù)類型到C＋＋語言描述
1.4 C＋＋基礎(chǔ)知識
1.4.1 C＋＋中的類和對象
1.4.2 C＋＋的輸入和輸出
1.4.3 C＋＋中的變量和常量
1.4.4 C＋＋中的函數(shù)
1.4.5 C＋＋中的動態(tài)存儲分配
1.4.6 C＋＋中的繼承
1.4.7 C＋＋中的多態(tài)性
1.4.8 其他
1.5 進階導讀
習題
第2章 線性表
2.1 線性表及其基本運算
2.1.1 線性表的定義與特點
2.1.2 線性表的基本運算
2.2 數(shù)組
2.2.1 數(shù)組的定義和特點
2.2.2 數(shù)組的類定義
2.2.3 數(shù)組的順序存儲方式
2.2.4 稀疏矩陣
2.3 線性表的順序表示——順序表
2.3.1 順序表的定義和特點
2.3.2 順序表類定義
2.3.3 順序表的插入
2.3.4 順序表的刪除
2.3.5 順序表的應(yīng)用實例——用順序存儲的線性表表示多項式
2.4 線性表的鏈式表示——鏈表
2.4.1 線性鏈表的邏輯結(jié)構(gòu)與建立
2.4.2 線性鏈表的類定義
2.4.3 線性鏈表的插入與刪除
2.4.4 線性鏈表的應(yīng)用實例——用線性鏈表表示多項式
2.4.5 幾種變形的線性鏈表
2.4.6 雙向鏈表
2.5 進階導讀
習題
第3章 串
3.1 串的定義
3.2 串的邏輯結(jié)構(gòu)和基本操作
3.3 串的存儲結(jié)構(gòu)
3.3.1 串的數(shù)組存儲表示
3.3.2 串的塊鏈存儲表示
3.4 串的實現(xiàn)
3.4.1 串的自定義類
3.4.2 串的實現(xiàn)
3.5 串的模式匹配算法
3.5.1 BF算法
3.5.2 KR算法
3.5.3 KMP算法
3.5.4 BM算法
3.6 進階導讀
習題
第4章 棧和隊列
4.1 棧
4.1.1 棧的基本操作
4.1.2 用數(shù)組實現(xiàn)棧
4.1.3 用鏈表實現(xiàn)棧
4.1.4 棧的應(yīng)用實例
4.2 隊列
4.2.1 用數(shù)組實現(xiàn)隊列
4.2.2 循環(huán)隊列
4.2.3 雙向隊列
4.2.4 用鏈表實現(xiàn)隊列
4.2.5 隊列的應(yīng)用舉例
4.3 進階導讀
習題
第5章 遞歸和廣義表
5.1 遞歸的概念
5.2 遞歸轉(zhuǎn)化為非遞歸
5.3 廣義表
5.3.1 廣義表的概念與存儲結(jié)構(gòu)
5.3.2 廣義表遞歸算法的實現(xiàn)
5.4 進階導讀
習題
第6章 樹、二叉樹和森林
6.1 基本概念
6.2 樹的存儲結(jié)構(gòu)
6.3 樹的線性表示
6.4 樹的遍歷
6.5 二叉樹
6.6 二叉樹的存儲表示
6.7 二叉樹的各種遍歷
6.8 線索化二叉樹
6.9 堆
6.10 計算二叉樹的數(shù)目
6.11 二叉樹的應(yīng)用：霍夫曼樹和霍夫曼編碼
6.12 進階導讀
習題
第7章 查找與索引
7.1 查找與索引的概念
7.2 基于順序表的查找
7.2.1 順序表
7.2.2 順序查找
7.2.3 有序順序表上的查找操作
7.3 二叉查找樹
7.3.1 二叉查找樹的結(jié)構(gòu)
7.3.2 二叉查找樹上的查找
7.3.3 基于二叉查找樹的遍歷
7.3.4 最優(yōu)二叉查找樹
7.3.5 動態(tài)二叉查找樹
7.4 B－樹和B＋樹
7.4.1 B－樹的結(jié)構(gòu)
7.4.2 B－樹的查詢
7.4.3 B－樹的插入
7.4.4 B－樹的刪除
7.4.5 B＋樹
7.5 Trie樹
7.5.1 Trie樹的定義
7.5.2 Trie樹的查找
7.5.3 Trie樹的插入和刪除
7.6 Hash查找
7.6.1 Hash函數(shù)
7.6.2 解決沖突的方法
7.6.3 Hash查找的討論
7.7 進階導讀
習題
第8章 圖
8.1 圖的基本概念
8.2 圖的存儲結(jié)構(gòu)
8.2.1 鄰接矩陣
8.2.2 鄰接表
8.3 圖的遍歷與求圖的連通分量
8.3.1 深度優(yōu)先查找法
8.3.2 廣度優(yōu)先查找法
8.3.3 求圖的連通分量
8.4 生成樹與最?。ù鷥r）生成樹
8.4.1 普里姆（Prim）算法
8.4.2 克魯斯卡爾（Kruskal）算法
8.5 最短路徑
8.5.1 求某個頂點到其他頂點的最短路徑
8.5.2 求一對頂點之間的最短路徑
8.5.3 傳遞閉包
8.6 拓撲排序
8.7 關(guān)鍵路徑
8.8 進階導讀
習題
第9章 排序
9.1 問題定義
9.2 基本排序方法
9.2.1 插入排序
9.2.2 冒泡排序
9.2.3 選擇排序
9.3 歸并排序
9.4 快速排序
9.4.1 基本算法
9.4.2 性能
9.4.3 快速排序的一些改進策略
9.4.4 重復值
9.5 堆排序
9.5.1 堆及其基本操作
9.5.2 堆排序
9.6 希爾排序
9.7 基數(shù)排序
9.8 內(nèi)部排序方法的比較
9.9 進階導讀——中的sort（）函數(shù)
習題
第10章 外部排序
10.1 外部存儲設(shè)備
10.1.1 磁帶存儲設(shè)備
10.1.2 磁盤存儲設(shè)備
10.2 外排序的基本過程
10.3 磁盤文件的外排序方法
10.4 磁帶文件的外排序方法
10.4.1 平衡合并排序
10.4.2 多階段合并排序
10.5 進階導讀
習題