數(shù)據(jù)結(jié)構(gòu)（C語言描述 修訂版）

第1章 引論
　1.1 算法及其復雜性的概念
　1.1.1 算法與程序
　1.1.2 算法復雜性的概念
　1.1.3 算法復雜性的漸近性態(tài)
　1.2 算法的表達與數(shù)據(jù)表示
　1.2.1 問題求解
　1.2.2 表達算法的抽象機制
　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)存儲分配
　1.6 遞歸
　1.6.1 遞歸的基本概念
　1.6.2 間接遞歸
　本章小結(jié)
　習題1
　算法實驗1
　算法實驗題1.1 哥德巴赫猜想問題
　算法實驗題1.2 連續(xù)整數(shù)和問題
第2章 表
　2.1 表的基本概念
　2.2 用數(shù)組實現(xiàn)表
　2.3 用指針實現(xiàn)表
　2.4 用間接尋址方法實現(xiàn)表
　2.5 用游標實現(xiàn)表
　2.6 循環(huán)鏈表
　2.7 雙鏈表
　2.8 表的搜索游標
　2.8.1 用數(shù)組實現(xiàn)表的搜索游標
　2.8.2 單循環(huán)鏈表的搜索游標
　2.9 應用舉例——Josephus排列問題
　本章小結(jié)
　習題2
　算法實驗2
　算法實驗題2.1 向量分類問題
　算法實驗題2.2 條形圖輪廓問題
第3章 棧
　3.1 棧的基本概念
　3.2 用數(shù)組實現(xiàn)棧
　3.3 用指針實現(xiàn)棧
　3.4 應用舉例——等價類劃分問題
　本章小結(jié)
　習題3
　算法實驗3
　算法實驗題3.1 車皮編序問題
　算法實驗題3.2 單柱Hanoi塔問題
　算法實驗題3.3 多棧模擬問題
　算法實驗題3.4 親兄弟問題
第4章 隊列
　4.1 隊列的基本概念
　4.2 用指針實現(xiàn)隊列
　4.3 用循環(huán)數(shù)組實現(xiàn)隊列
　4.4 應用舉例——電路布線問題
　本章小結(jié)
　習題4
　算法實驗4
　算法實驗題4.1 組隊列問題
　算法實驗題4.2 雙棧隊列問題
　算法實驗題4.3 猴子分桃問題
　算法實驗題4.4 逆序表問題
第5章 排序與選擇
　5.1 簡單排序算法
　5.1.1 冒泡排序
　5.1.2 插入排序
　5.1.3 選擇排序
　5.1.4 簡單排序算法的計算復雜性
　5.2 快速排序算法
　5.2.1 算法基本思想及實現(xiàn)
　5.2.2 算法的性能
　5.2.3 隨機快速排序算法
　5.2.4 非遞歸快速排序算法
　5.2.5 三數(shù)取中劃分算法
　5.2.6 三劃分快速排序算法
　5.3 合并排序算法
　5.3.1 算法基本思想及實現(xiàn)
　5.3.2 對基本算法的改進
　5.3.3 自底向上的合并排序算法
　5.3.4 自然合并排序
　5.3.5 鏈表結(jié)構(gòu)的合并排序算法
　5.4 線性時間排序算法
　5.4.1 計數(shù)排序
　5.4.2 桶排序
　5.5 中位數(shù)與第k小元素
　5.5.1 平均情況下的線性時間選擇算法
　5.5.2 最壞情況下的線性時間選擇算法
　5.6 應用舉例——帶權(quán)中位數(shù)問題
　本章小結(jié)
　習題5
　算法實驗5
　算法實驗題5.1 交換排序問題
　算法實驗題5.2 DNA排序問題
　算法實驗題5.3 輸油管道問題
　算法實驗題5.4 最優(yōu)服務次序問題
第6章 樹
　6.1 樹的定義
　6.2 樹的遍歷
　6.3 樹的表示法
　6.3.1 父結(jié)點數(shù)組表示法
　6.3.2 兒子鏈表表示法
　6.3.3 左兒子右兄弟表示法
　6.4 二叉樹的基本概念
　6.5 二叉樹的運算
　6.6 二叉樹的實現(xiàn)
　6.6.1 二叉樹的順序存儲結(jié)構(gòu)
　6.6.2 二叉樹的結(jié)點度表示法
　6.6.3 用指針實現(xiàn)二叉樹
　6.7 線索二叉樹
　6.8 應用舉例——信號增強裝置布局問題
　本章小結(jié)
　習題6
　算法實驗6
　算法實驗題6.1 層序列表問題
　算法實驗題6.2 最近公共祖先問題
　算法實驗題6.3 子樹問題
　算法實驗題6.4 同構(gòu)二叉樹問題
　算法實驗題6.5 后序中序遍歷問題
第7章 圖
　7.1 圖的基本概念
　7.2 抽象數(shù)據(jù)類型ADT圖
　7.3 圖的表示法
　7.3.1 鄰接矩陣表示法
　7.3.2 鄰接表表示法
　7.3.3 緊縮鄰接表
　7.4 用鄰接矩陣實現(xiàn)圖
　7.4.1 用鄰接矩陣實現(xiàn)賦權(quán)有向圖
　7.4.2 用鄰接矩陣實現(xiàn)賦權(quán)無向圖
　7.4.3 用鄰接矩陣實現(xiàn)有向圖
　7.4.4 用鄰接矩陣實現(xiàn)無向圖
　7.5 用鄰接表實現(xiàn)圖
　7.5.1 用鄰接表實現(xiàn)有向圖
　7.5.2 用鄰接表實現(xiàn)無向圖
　7.5.3 用鄰接表實現(xiàn)賦權(quán)有向圖
　7.5.4 用鄰接表實現(xiàn)賦權(quán)無向圖
　7.6 圖的遍歷
　7.6.1 廣度優(yōu)先搜索
　7.6.2 深度優(yōu)先搜索
　7.7 最短路徑
　7.7.1 單源最短路徑
　7.7.2 Bellman-Ford最短路徑算法
　7.7.3 所有頂點對之間的最短路徑
　7.8 無圈有向圖DAG
　7.8.1 拓撲排序
　7.8.2 DAG的最短路徑
　7.8.3 DAG的最長路徑
　7.8.4 DAG所有頂點對之間的最短路徑
　7.9 最小支撐樹
　7.9.1 最小支撐樹性質(zhì)
　7.9.2 Prim算法
　7.9.3 Kruskal算法
　7.10 圖匹配
　7.11 應用舉例——差分約束系統(tǒng)
　本章小結(jié)
　習題7
　算法實驗7
　算法實驗題7.1 圖的二著色問題
　算法實驗題7.2 賦權(quán)有向圖中心問題
　算法實驗題7.3 最長簡單路徑問題
　算法實驗題7.4 計算機網(wǎng)絡問題
　算法實驗題7.5 差分約束問題
　算法實驗題7.6 有截止時間的工作排序問題
第8章 集合
　8.1 以集合為基礎的抽象數(shù)據(jù)類型
　8.1.1 集合的定義和記號
　8.1.2 定義在集合上的基本運算
　8.2 用位向量實現(xiàn)集合
　8.3 用鏈表實現(xiàn)集合
　8.4 應用舉例——Eratosthenes篩法
　本章小結(jié)
　習題8
　算法實驗8
　算法實驗題8.1 半數(shù)集問題
第9章 符號表
　9.1 實現(xiàn)符號表的簡單方法
　9.2 用散列表實現(xiàn)符號表
　9.2.1 開散列
　9.2.2 閉散列
　9.2.3 散列函數(shù)及其效率
　9.2.4 閉散列的重新散列技術(shù)
　9.3 應用舉例——字符串頻率統(tǒng)計問題
　本章小結(jié)
　習題9
　算法實驗9
　算法實驗題9.1 偽隨機排列問題
　算法實驗題9.2 字符串散列問題
　算法實驗題9.3 英文文本分析問題
　算法實驗題9.4 最長模式串問題
第10章 字典
　10.1 字典的定義
　10.2 用數(shù)組實現(xiàn)字典
　10.3 用二叉搜索樹實現(xiàn)字典
　10.4 AVL樹
　10.4.1 AVL樹的定義和性質(zhì)
　10.4.2 旋轉(zhuǎn)變換
　10.4.3 AVL樹的插入運算
　10.4.4 AVL樹的刪除運算
　10.5 應用舉例——條形圖統(tǒng)計問題
　本章小結(jié)
　習題10
　算法實驗10
　算法實驗題10.1 裝箱問題
　算法實驗題10.2 電路板連線問題
　算法實驗題10.3 辭典問題
第11章 優(yōu)先隊列
　11.1 優(yōu)先隊列的定義
　11.2 用字典實現(xiàn)優(yōu)先隊列
　11.3 優(yōu)先級樹和堆
　11.4 用數(shù)組實現(xiàn)堆
　11.5 可并優(yōu)先隊列
　11.5.1 左偏樹的定義
　11.5.2 用左偏樹實現(xiàn)可并優(yōu)先隊列
　11.6 應用舉例——哈夫曼編碼
　本章小結(jié)
　習題11
　算法實驗11
　算法實驗題11.1 多機調(diào)度問題
　算法實驗題11.2 整數(shù)字典問題
　算法實驗題11.3 最小權(quán)語言問題
　算法實驗題11.4 二叉搜索堆問題
第12章 并查集
　12.1 并查集的定義及其簡單實現(xiàn)
　12.2 用父結(jié)點數(shù)組實現(xiàn)并查集
　12.3 應用舉例——離線最小值問題
　本章小結(jié)
　習題12
　算法實驗12
　算法實驗題12.1 二進制方程問題
　算法實驗題12.2 網(wǎng)絡連通問題
　算法實驗題12.3 朋友問題
　算法實驗題12.4 無向圖的連通分支問題
參考文獻