數據結構與算法（第4版）

第1章 緒論
1.1 數據結構的研究對象
1.2 數據結構發(fā)展概況
1.3 抽象數據型
1.3.1 抽象數據型的定義
1.3.2 數據類型、數據結構和抽象數據型
1.3.3 多層次抽象技術
1.3.4 抽象數據型的優(yōu)點
1.4 算法及其復雜性
1.4.1 算法與程序
1.4.2 算法的復雜性及其表示
1.4.3 最壞、最好和平均情況分析
1.4.4 時間復雜性分析的基本方法
1.5 逐步求精的程序設計方法
1.5.1 如何求解問題
1.5.2 算法的逐步求精
1.6 關于描述語言
1.6.1 結構體類型說明
1.6.2 輸入／輸出
1.6.3 動態(tài)存儲分配
1.6.4 引用類型參數
1.6.5 其他
習題
第2章 線性表
2.1 線性表的抽象數據型
2.2 線性表的實現
2.2.1 線性表的數組實現
2.2.2 線性表的指針實現
2.2.3 線性表的游標實現
2.2.4 雙向鏈接表
2.2.5 環(huán)形鏈表
2.2.6 多項式的代數運算
2.3 棧
2.3.1 棧的數組實現
2.3.2 棧的指針實現
2.3.3 棧和遞歸過程
2.3.4 棧的應用
2.4 隊列
2.4.1 隊列的指針實現
2.4.2 隊列的循環(huán)數組實現
2.4.3 隊列的應用
2.5 串
2.5.1 串的抽象數據型
2.5.2 串的表示
2.5.3 模式匹配算法
2.6 數組
2.6.1 數組的抽象數據型
2.6.2 數組的表示
2.7 廣義表
習題
第3章 樹
3.1 基本術語
3.2 二叉樹
3.2.1 二叉樹的定義及遍歷
3.2.2 二叉樹的性質
3.2.3 二叉樹的抽象數據型
3.2.4 二叉樹的表示
3.2.5 二叉樹的復制
3.3 堆
3.4 選擇樹
3.5 樹
3.5.1 樹的抽象數據型
3.5.2 樹的表示
3.6 森林和二叉樹間的轉換
3.7 樹的應用
3.7.1 集合的樹結構表示
3.7.2 判定樹
3.7.3 哈夫曼樹
3.7.4 表達式求值
習題
第4章 圖
4.1 基本定義
4.2 圖的表示
4.2.1 鄰接矩陣
4.2.2 鄰接表
4.3 圖的搜索
4.3.1 深度優(yōu)先搜索與深度優(yōu)先編號
4.3.2 廣度優(yōu)先搜索與廣度優(yōu)先編號
4.4 圖與樹的聯系
4.4.1 深度優(yōu)先生成森林和廣度優(yōu)先生成森林
4.4.2 無向圖與開放樹的聯系
4.4.3 最小生成樹
4.5 無向圖的雙連通性
4.5.1 無向圖的雙連通分量
4.5.2 求關節(jié)點
4.6 搜索產生的邊
4.7 強連通性
4.8 拓撲排序
4.8.1 無環(huán)路有向圖
4.8.2 拓撲排序算法
4.9 關鍵路徑
4.1 0單源最短路徑
4.1 l每一對頂點之間的最短路徑
4.1 1.1 Floyd算法
4.1 1.2 Warshau算法
4.1 1.3 求有向圖的中心點
4.1 2求有向圖的基本環(huán)路
習題
第5章 查找
5.1 線性查找
5.2 折半查找
5.3 分塊查找
5.4 二叉查找樹
5.5 AVL樹
5.6 B一樹與B樹
5.6.1 B一樹及其性質
5.6.2 B一樹的插入操作
5.6.3 B一樹的刪除操作
5.6.4 B樹
5.7 Trie樹
5.7.1 Trie樹的定義
5.7.2 Trie樹的查找操作
5.7.3 采樣策略
5.7.4 Trie樹的插入操作
5.7.5 Trie樹的刪除操作
5.8 散列法
5.8.1 內散列表
5.8.2 散列函數
5.8.3 沖突的處理
5.8.4 外散列表
習題
第6章 排序
6.1 簡單的排序算法
6.1.1 氣泡排序
6.1.2 插入排序
6.1.3 選擇排序
6.2 快速排序
6.3 歸并排序
6.4 堆排序
6.5 基數排序
6.6 詞典排序
6.7 求第K個最小元素
習題
第7章 文件與外部排序
7.1 文件及文件操作
7.1.1 文件的有關概念
7.1.2 文件操作
7.2 文件組織
7.2.1 順序式文件
7.2.2 索引文件
7.2.3 散列文件
7.2.4 鏈接式文件和多重鏈表文件
7.2.5 倒排文件
7.3 磁盤文件的歸并排序
7.3.1 K路歸并
7.3.2 并行操作的緩沖區(qū)處理
7.3.3 初始歸并段的生成
7.4 磁帶文件的歸并排序
7.4.1 平衡歸并排序
7.4.2 多階段歸并排序
習題
第8章 算法設計方法
8.1 遞歸方程的求解
8.1.1 與遞歸方程解有關的兩個問題
8.1.2 猜解法
8.1.3 迭代法
8.1.4 一類遞歸方程的展開式與通解
8.2 分治法
8.2.1 基本思想
8.2.2 整數乘法
8.2.3 求兩個矩陣的乘積
8.2.4 平衡
8.3 貪心法
8.3.1 基本思想
8.3.2 背包問題
8.4 動態(tài)規(guī)劃
8.4.1 基本思想
8.4.2 矩陣連乘問題
8.4.3 聯賽勝負概率問題
8.5 回溯法
8.5.1 基本思想
8.5.2 單詞匹配問題
8.5.3 回溯算法與解法空間的組織
8.5.4 8皇后問題
8.6 分枝限界法
8.6.1 基本思想
8.6.2 0-1背包問題
8.6.3 旅行商問題
習題
參考文獻