數(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í)數(shù)
1.1.3 字符串
1.1.4 硬件和軟件
1.1.5 實(shí)現(xiàn)的概念
1.1.6 示例
1.1.7 抽象數(shù)據(jù)類型
1.1.8 序列的值定義
1.1.9 變長(zhǎng)字符串的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ù)組的實(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)的實(shí)現(xiàn)
1.3.2 聯(lián)合（Union）
1.3.3 聯(lián)合的實(shí)現(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 方法的實(shí)現(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操作的實(shí)現(xiàn)
2.2.2 測(cè)試異常情況
2.2.3 實(shí)現(xiàn)push操作
2.2.4 練習(xí)2
2.3 示例：中綴、后綴和前綴
2.3.1 基本定義和示例
2.3.2 后綴表達(dá)式的計(jì)算
2.3.3 計(jì)算后綴表達(dá)式的程序
2.3.4 程序的局限性
2.3.5 中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式
2.3.6 將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的程序
2.3.7 用C＋＋模板實(shí)現(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 對(duì)分查找
3.1.5 遞歸定義或算法的特點(diǎn)
3.1.6 練習(xí)1
3.2 C中的遞歸
3.2.1 用C實(shí)現(xiàn)階乘
3.2.2 用C實(shí)現(xiàn)斐波納契數(shù)列
3.2.3 用C實(shí)現(xiàn)對(duì)分查找
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ù)的實(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章 隊(duì)列和鏈表
4.1 隊(duì)列及其順序表示
4.1.1 隊(duì)列的抽象數(shù)據(jù)類型定義
4.1.2 隊(duì)列的C語言實(shí)現(xiàn)
4.1.3 insert操作
4.1.4 優(yōu)先隊(duì)列
4.1.5 用數(shù)組實(shí)現(xiàn)的優(yōu)先隊(duì)列
4.1.6 練習(xí)1
4.2 鏈表
4.2.1 從鏈表中插入和刪除結(jié)點(diǎn)
4.2.2 堆棧的鏈表實(shí)現(xiàn)
4.2.3 getnode和freenode操作
4.2.4 隊(duì)列的鏈表實(shí)現(xiàn)
4.2.5 鏈表數(shù)據(jù)結(jié)構(gòu)
4.2.6 鏈表操作的例子
4.2.7 優(yōu)先隊(duì)列的鏈表實(shí)現(xiàn)
4.2.8 頭結(jié)點(diǎn)
4.2.9 練習(xí)2
4.3 C中的鏈表
4.3.1 鏈表的數(shù)組實(shí)現(xiàn)
4.3.2 數(shù)組實(shí)現(xiàn)的局限性
4.3.3 動(dòng)態(tài)變量的分配和釋放
4.3.4 使用動(dòng)態(tài)變量實(shí)現(xiàn)的鏈表
4.3.5 用鏈表實(shí)現(xiàn)的隊(duì)列
4.3.6 C中鏈表操作的例子
4.3.7 非整數(shù)鏈表和非齊次鏈表
4.3.8 數(shù)組實(shí)現(xiàn)和動(dòng)態(tài)實(shí)現(xiàn)鏈表的比較
4.3.9 頭結(jié)點(diǎn)的實(shí)現(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)鏈表表示隊(duì)列
4.5.4 循環(huán)鏈表的基本操作
4.5.5 約瑟夫問題
4.5.6 頭結(jié)點(diǎn)
4.5.7 使用循環(huán)鏈表實(shí)現(xiàn)長(zhǎng)正整數(shù)的加法
4.5.8 雙向鏈表
4.5.9 使用雙向鏈表實(shí)現(xiàn)長(zhǎng)整數(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é)點(diǎn)表示
5.2.2 內(nèi)部結(jié)點(diǎn)和外部結(jié)點(diǎn)
5.2.3 二叉樹的隱式數(shù)組表示
5.2.4 選擇一個(gè)二叉樹表示
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個(gè)元素
5.4.2 刪除元素
5.4.3 用C語言實(shí)現(xiàn)用樹表示的表
5.4.4 構(gòu)建一個(gè)用樹表示的表
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 對(duì)表達(dá)式樹求值
5.5.5 構(gòu)建樹
5.5.6 練習(xí)5
5.6 示例：游戲樹
第6章 排序
6.1 背景
6.1.1 效率方面的考慮
6.1.2 符號(hào)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)先級(jí)隊(duì)列的堆
6.3.5 使用堆進(jìn)行排序
6.3.6 堆排序的過程
6.3.7 練習(xí)3
6.4 插入排序
6.4.1 簡(jiǎn)單插入
6.4.2 希爾排序
6.4.3 地址計(jì)算排序
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 算法符號(hào)
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 實(shí)現(xiàn)多路樹
7.3.4 遍歷多路樹
7.3.5 在多路搜索樹中進(jìn)行插入
7.3.6 B樹
7.3.7 B樹插入算法
7.3.8 計(jì)算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 從散列表刪除項(xiàng)
7.4.3 再散列方法的效率
7.4.4 散列表重新排序
7.4.5 Brent方法
7.4.6 二叉樹散列
7.4.7 通過額外的存儲(chǔ)空間來獲得改進(jìn)
7.4.8 聯(lián)合散列
7.4.9 單獨(dú)鏈地址法
7.4.10 在外部存儲(chǔ)器中進(jìn)行散列
7.4.11 分離方法
7.4.12 動(dòng)態(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é)點(diǎn)集合
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章 存儲(chǔ)管理
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é)點(diǎn)
9.1.8 C中的廣義表
9.1.9 編程語言和表
9.1.10 練習(xí)1
9.2 自動(dòng)表管理
9.2.1 引用計(jì)數(shù)方法
9.2.2 無用信息收集
9.2.3 無用信息收集的算法
9.2.4 收集和壓縮
9.2.5 無用信息收集的變種
9.2.6 練習(xí)2
9.3 動(dòng)態(tài)存儲(chǔ)管理
9.3.1 存儲(chǔ)塊的壓縮
9.3.2 首次匹配、最佳匹配和最差匹配
9.3.3 首次匹配方法的改進(jìn)
9.3.4 釋放存儲(chǔ)塊
9.3.5 邊界標(biāo)簽方法
9.3.6 Buddy System
9.3.7 其他的Buddy System
9.3.8 練習(xí)3