數(shù)據(jù)結(jié)構(gòu)C和C++語言描述（第2版）

第1章 數(shù)據(jù)結(jié)構(gòu)入門
1.1 信息和涵義
1.1.1 二進(jìn)制整數(shù)和十進(jìn)制整數(shù)
1.1.2 實數(shù)
1.1.3 字符串
1.1.4 硬件和軟件
1.1.5 實現(xiàn)的概念
1.1.6 示例
1.1.7 抽象數(shù)據(jù)類型
1.1.8 序列的值定義
1.1.9 變長字符串的ADT表示
1.1.10 C的數(shù)據(jù)類型
1.1.11 C中的指針
1.1.12 C中的數(shù)據(jù)結(jié)構(gòu)
1.1.13 練習(xí)1
1.2 C中的數(shù)組
1.2.1 數(shù)組的抽象數(shù)據(jù)類型定義
1.2.2 使用一維數(shù)組
1.2.3 一維數(shù)組的實現(xiàn)
1.2.4 將數(shù)組作為參數(shù)
1.2.5 C中的字符串
1.2.6 字符串操作
1.2.7 二維數(shù)組
1.2.8 多維數(shù)組
1.2.9 練習(xí)2
1.3 C中的結(jié)構(gòu)
1.3.1 結(jié)構(gòu)的實現(xiàn)
1.3.2 聯(lián)合（Union）
1.3.3 聯(lián)合的實現(xiàn)
1.3.4 結(jié)構(gòu)參數(shù)
1.3.5 表示其他數(shù)據(jù)結(jié)構(gòu)
1.3.6 有理數(shù)
1.3.7 內(nèi)存的分配和變量的作用域
1.3.8 練習(xí)3
1.4 C＋＋中的類
1.4.1 Rational類
1.4.2 Rational類的使用
1.3 方法的實現(xiàn)
1.4.4 重載
1.4.5 繼承
1.4.6 構(gòu)造函數(shù)
1.4.7 練習(xí)4
第2章 堆棧
2.1 定義和示例
2.1.1 基本操作
2.1.2 示例
2.1.3 堆棧的抽象數(shù)據(jù)類型定義
2.1.4 練習(xí)1
2.2 用C描述堆棧
2.2.1 pop操作的實現(xiàn)
2.2.2 測試異常情況
2.2.3 實現(xiàn)push操作
2.2.4 練習(xí)2
2.3 示例：中綴、后綴和前綴
2.3.1 基本定義和示例
2.3.2 后綴表達(dá)式的計算
2.3.3 計算后綴表達(dá)式的程序
2.3.4 程序的局限性
2.3.5 中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式
2.3.6 將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的程序
2.3.7 用C＋＋模板實現(xiàn)的堆棧
2.3.8 練習(xí)3
第3章 遞歸
3.1 遞歸定義和遞歸過程
3.1.1 階乘函數(shù)
3.1.2 自然數(shù)的乘法
3.1.3 斐波納契數(shù)列
3.1.4 對分查找
3.1.5 遞歸定義或算法的特點
3.1.6 練習(xí)1
3.2 C中的遞歸
3.2.1 用C實現(xiàn)階乘
3.2.2 用C實現(xiàn)斐波納契數(shù)列
3.2.3 用C實現(xiàn)對分查找
3.2.4 遞歸鏈
3.2.5 代數(shù)表達(dá)式的遞歸定義
3.2.6 練習(xí)2
3.3 編寫遞歸程序
3.3.1 漢諾塔問題
3.3.2 使用遞歸將前綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式
3.3.3 練習(xí)3
3.4 遞歸的模擬
3.4.1 從函數(shù)中返回
3.4.2 遞歸函數(shù)的實現(xiàn)
3.4.3 階乘的模擬
3.4.4 優(yōu)化模擬例程
3.4.5 消除goto語句
3.4.6 模擬漢諾塔問題
3.4.7 練習(xí)4
3.5 遞歸的效率
第4章 隊列和鏈表
4.1 隊列及其順序表示
4.1.1 隊列的抽象數(shù)據(jù)類型定義
4.1.2 隊列的C語言實現(xiàn)
4.1.3 insert操作
4.1.4 優(yōu)先隊列
4.1.5 用數(shù)組實現(xiàn)的優(yōu)先隊列
4.1.6 練習(xí)1
4.2 鏈表
4.2.1 從鏈表中插入和刪除結(jié)點
4.2.2 堆棧的鏈表實現(xiàn)
4.2.3 getnode和freenode操作
4.2.4 隊列的鏈表實現(xiàn)
4.2.5 鏈表數(shù)據(jù)結(jié)構(gòu)
4.2.6 鏈表操作的例子
4.2.7 優(yōu)先隊列的鏈表實現(xiàn)
4.2.8 頭結(jié)點
4.2.9 練習(xí)2
4.3 C中的鏈表
4.3.1 鏈表的數(shù)組實現(xiàn)
4.3.2 數(shù)組實現(xiàn)的局限性
4.3.3 動態(tài)變量的分配和釋放
4.3.4 使用動態(tài)變量實現(xiàn)的鏈表
4.3.5 用鏈表實現(xiàn)的隊列
4.3.6 C中鏈表操作的例子
4.3.7 非整數(shù)鏈表和非齊次鏈表
4.3.8 數(shù)組實現(xiàn)和動態(tài)實現(xiàn)鏈表的比較
4.3.9 頭結(jié)點的實現(xiàn)
4.3.10 練習(xí)3
4.4 示例：用鏈表進(jìn)行模擬
4.4.1 模擬進(jìn)程
4.4.2 數(shù)據(jù)結(jié)構(gòu)
4.4.3 模擬程序
4.4.4 練習(xí)4
4.5 其他鏈表結(jié)構(gòu)
4.5.1 循環(huán)鏈表
4.5.2 用循環(huán)錠表表示堆棧
4.5.3 用循環(huán)鏈表表示隊列
4.5.4 循環(huán)鏈表的基本操作
4.5.5 約瑟夫問題
4.5.6 頭結(jié)點
4.5.7 使用循環(huán)鏈表實現(xiàn)長正整數(shù)的加法
4.5.8 雙向鏈表
4.5.9 使用雙向鏈表實現(xiàn)長整數(shù)的加法
4.5.10 練習(xí)5
4.6 C＋＋中的鏈表
第5章 樹
5.1 一叉樹
5.1.1 二叉樹中的操作
5.1.2 二叉樹的應(yīng)用
5.1.3 練習(xí)1
5.2 二叉樹的表示
5.2.1 二叉樹的結(jié)點表示
5.2.2 內(nèi)部結(jié)點和外部結(jié)點
5.2.3 二叉樹的隱式數(shù)組表示
5.2.4 選擇一個二叉樹表示
5.2.5 二叉樹遍歷的C語言表示
5.2.6 線索化二叉樹
5.2.7 使用father字段的通歷
5.2.8 異構(gòu)二叉樹
5.2.9 練習(xí)2
5.3 示例：哈夫曼算法
5.3.1 哈夫曼算法
5.3.2 C程序
5.3.3 練習(xí)3
5.4 將表表示為二叉樹
5.4.1 尋找第k個元素
5.4.2 刪除元素
5.4.3 用C語言實現(xiàn)用樹表示的表
5.4.4 構(gòu)建一個用樹表示的表
5.4.5 回顧約瑟夫問題
5.4.6 練習(xí)4
5.5 樹及其應(yīng)用
5.5.1 樹的C語言表示
5.5.2 樹的遍歷
5.5.3 用樹來表示廣義表達(dá)式
5.5.4 對表達(dá)式樹求值
5.5.5 構(gòu)建樹
5.5.6 練習(xí)5
5.6 示例：游戲樹
第6章 排序
6.1 背景
6.1.1 效率方面的考慮
6.1.2 符號O
6.1.3 排序的效率
6.1.4 練習(xí)1
6.2 交換排序
6.2.1 冒泡排序
6.2.2 快速排序
6.2.3 快速排序的效率
6.2.4 練習(xí)2
6.3 選擇排序以及樹排序
6.3.1 直接選擇排序
6.3.2 二叉樹排序
6.3.3 堆排序
6.3.4 作為優(yōu)先級隊列的堆
6.3.5 使用堆進(jìn)行排序
6.3.6 堆排序的過程
6.3.7 練習(xí)3
6.4 插入排序
6.4.1 簡單插入
6.4.2 希爾排序
6.4.3 地址計算排序
6.4.4 練習(xí)4
6.5 歸并排序以及基數(shù)排序
6.5.1 歸并排序
6.5.2 Cook-Kim算法
6.5.3 基數(shù)排序
6.5.4 練習(xí)5
第7章 搜索
7.1 基本搜索技術(shù)
7.1.1 作為抽象數(shù)據(jù)類型的目錄
7.1.2 算法符號
7.1.3 順序搜索
7.1.4 順序搜索的效率
7.1.5 重新排序鏈表以最大化搜索效率
7.1.6 在有序表中進(jìn)行搜索
7.1.7 使用索引的順序搜索
7.1.8 二叉樹搜索
7.1.9 插值搜索
7.1.10 練習(xí)1
7.2 樹搜索
7.2.1 在二叉搜索樹中插入元素
7.2.2 在二叉搜索樹中刪除元素
7.2.3 二叉搜索樹操作的效率
7.2.4 不均勻的二叉搜索樹的效率
7.2.5 最佳搜索樹
7.2.6 平衡二叉樹
7.2.7 練習(xí)2
7.3 廣義搜索樹
7.3.1 多路搜索樹
7.3.2 在多路樹中進(jìn)行搜索
7.3.3 實現(xiàn)多路樹
7.3.4 遍歷多路樹
7.3.5 在多路搜索樹中進(jìn)行插入
7.3.6 B樹
7.3.7 B樹插入算法
7.3.8 計算father和index
7.3.9 在多路搜索樹中進(jìn)行刪除
7.3.10 多路搜索樹的效率
7.3.11 改進(jìn)B樹
7.3.12 B樹
7.3.13 數(shù)字搜索樹
7.3.14 Trie
7.3.15 練習(xí)3
7.4 散列
7.4.1 使用開放尋址來解決散列沖突
7.4.2 從散列表刪除項
7.4.3 再散列方法的效率
7.4.4 散列表重新排序
7.4.5 Brent方法
7.4.6 二叉樹散列
7.4.7 通過額外的存儲空間來獲得改進(jìn)
7.4.8 聯(lián)合散列
7.4.9 單獨鏈地址法
7.4.10 在外部存儲器中進(jìn)行散列
7.4.11 分離方法
7.4.12 動態(tài)散列以及可擴(kuò)展散列
7.4.13 線性散列
7.4.14 選擇散列函數(shù)
7.4.15 理想的散列函數(shù)
7.4.16 散列函數(shù)的通用類
7.4.17 練習(xí)4
第8章 圖及其應(yīng)用
8.1 圖
8.1.1 圖的應(yīng)用
8.1.2 圖的C語言表示
8.1.3 傳遞閉包
8.1.4 Warshall算法
8.1.5 最短路徑算法
8.1.6 練習(xí)1
8.2 流問題
8.2.1 改進(jìn)流函數(shù)
8.2.2 示例
8.2.3 算法和程序
8.2.4 練習(xí)2
8.3 圖的鏈接表示
8.3.1 再訪Dijkstra算法
8.3.2 組織圖結(jié)點集合
8.3.3 調(diào)度的應(yīng)用
8.3.4 C程序
8.3.5 練習(xí)3
8.4 圖的遍歷以及生成森林
8.4.1 圖的遍歷方法
8.4.2 生成森林
8.4.3 無向圖以及它們的遍歷
8.4.4 深度優(yōu)先遍歷
8.4.5 深度優(yōu)先遍歷的應(yīng)用
8.4.6 深度優(yōu)先通歷的效率
8.4.7 廣度優(yōu)先遍歷
8.4.8 最小生成樹
8.4.9 Kruskal算法
8.4.10 Round-Robin算法
8.4.11 練習(xí)4
第9章 存儲管理
9.1 廣義表
9.1.1 修改表的操作
9.1.2 示例
9.1.3 表的鏈表表示
9.1.4 表的表示
9.1.5 crlist操作
9.1.6 表頭的用法
9.1.7 釋放表結(jié)點
9.1.8 C中的廣義表
9.1.9 編程語言和表
9.1.10 練習(xí)1
9.2 自動表管理
9.2.1 引用計數(shù)方法
9.2.2 無用信息收集
9.2.3 無用信息收集的算法
9.2.4 收集和壓縮
9.2.5 無用信息收集的變種
9.2.6 練習(xí)2
9.3 動態(tài)存儲管理
9.3.1 存儲塊的壓縮
9.3.2 首次匹配、最佳匹配和最差匹配
9.3.3 首次匹配方法的改進(jìn)
9.3.4 釋放存儲塊
9.3.5 邊界標(biāo)簽方法
9.3.6 Buddy System
9.3.7 其他的Buddy System
9.3.8 練習(xí)3