數(shù)據(jù)結(jié)構(gòu)（第2版）

第一章 緒論
1.1 為什么要學習數(shù)據(jù)結(jié)構(gòu)
1.2 數(shù)據(jù)結(jié)構(gòu)概念
1.2.1 數(shù)據(jù)的邏輯結(jié)構(gòu)
1.2.2 數(shù)據(jù)的存儲結(jié)構(gòu)
1.2.3 對數(shù)據(jù)結(jié)構(gòu)的操作
1.2.4 數(shù)據(jù)結(jié)構(gòu)示例
1.3 算法
1.3.1 算法及其特性
1.3.2 算法的描述
1.3.3 算法的評價準則
1.4 算法的正確性證明
1.5 算法分析基礎(chǔ)
1.5.1 算法時間復雜性的分析方法
1.5.2 復雜性函數(shù)的漸近表示
1.5.3 算法時間與空間分析
1.5.4 計算復雜性和算法的效率
小結(jié)
參考文獻與推薦讀物
習題
第二章 線性表、堆棧和隊列
2.1 線性表的定義和基本操作
2.2 線性表的順序存儲結(jié)構(gòu)
2.3 線性表的鏈接存儲結(jié)構(gòu)
2.3.1 單鏈表
2.3.2 循環(huán)鏈表
2.3.3 雙向鏈表
2.4 復雜性分析
2.5 堆棧
2.5.1 堆棧的定義和基本操作
2.5.2 順序棧
2.5.3 鏈式棧
2.5.4 順序棧與鏈式棧的比較
2.5.5 堆棧應用——括號匹配
2.6 隊列
2.6.1 隊列的定義和基本操作
2.6.2 順序隊列
2.6.3 鏈式隊列
2.6.4 順序隊列與鏈式隊列的比較
2.6.5 隊列與堆棧的擴展
小結(jié)
參考文獻與推薦讀物
習題
第三章 數(shù)組和字符串
3.1 數(shù)組
3.1.1 數(shù)組的存儲和尋址
3.1.2 一維數(shù)組類
3.2 矩陣
3.2.1 矩陣類
3.2.2 特殊矩陣
3.2.3 三元組表
3.2.4 十字鏈表
3.3 字符串
3.3.1 字符串的定義與字符串類
3.3.2 模式匹配算法
小結(jié)
參考文獻與推薦讀物
習題
第四章 樹
4.1 樹的基本概念
4.1.1 樹的定義
4.1.2 樹的相關(guān)術(shù)語
4.2 二叉樹
4.2.1 二叉樹定義和主要性質(zhì)
4.2.2 二叉樹順序存儲
4.2.3 二叉樹鏈接存儲
4.2.4 二叉樹遍歷
4.2.5 創(chuàng)建二叉樹
4.2.6 復制二叉樹
4.3 線索二叉樹
4.3.1 線索二叉樹定義
4.3.2 線索二叉樹存儲
4.3.3 線索二叉樹基本算法
4.4 樹和森林
4.4.1 樹與二叉樹的轉(zhuǎn)換
4.4.2 樹的順序存儲
4.4.3 樹的鏈接存儲
4.4.4 樹和森林的遍歷
4.5 壓縮與哈夫曼樹
4.5.1 文件編碼
4.5.2 擴充二叉樹
4.5.3 哈夫曼樹和哈夫曼編碼
4.6 應用
4.6.1 表達式求值
4.6.2 分類與決策樹
小結(jié)
參考文獻與推薦讀物
習題
第五章 圖
5.1 圖的基本概念
5.2 圖的存儲結(jié)構(gòu)與類定義
5.2.1 存儲結(jié)構(gòu)
5.2.2 Graph類
5.3 圖的遍歷算法
5.3.1 深度優(yōu)先遍歷
5.3.2 廣度優(yōu)先遍歷
5.4 拓撲排序
5.5 關(guān)鍵路徑
5.6 最短路徑問題
5.6.1 無權(quán)最短路徑問題
5.6.2 正權(quán)最短路徑問題
5.6.3 每對頂點之間的最短路徑
5.7 最小支撐樹
5.7.1 普里姆算法
5.7.2 克魯斯卡爾算法
5.8 圖的應用
5.8.1 可及性與Warshall算法
5.8.2 連通分量
5.8.3 圖在網(wǎng)絡分析和信息檢索
中的應用
小結(jié)
參考文獻與推薦讀物
習題
第六章 遞歸
6.1 遞歸的定義
6.2 基本遞歸過程
6.3 遞歸過程實現(xiàn)與堆棧
6.4 遞歸法求解問題
6.4.1 委員會問題
6.4.2 回溯
6.5 遞歸的效率
小結(jié)
參考文獻與推薦讀物
習題
第七章 排序
7.1 排序問題的基本概念
7.2 插入排序
7.2.1 直接插入排序
7.2.2 Shell排序
7.3 交換排序
7.3.1 冒泡排序
7.3.2 快速排序
7.4 選擇排序
7.4.1 直接選擇排序
7.4.2 堆排序
7.5 合并排序
7.6 基于關(guān)鍵詞比較的排序算法分析
7.6.1 平方階排序算法及改進算法
7.6.2 線性對數(shù)階排序算法
7.6.3 分治排序的一般方法
7.6.4 基于關(guān)鍵詞比較的排序算法下界
7.7 分布排序
7.7.1 基數(shù)分布
7.7.2 值分布
7.8 外排序
7.8.1 外存儲器
7.8.2 磁帶排序
7.8.3 磁盤排序
小結(jié)
參考文獻與推薦讀物
習題
第八章 查找
8.1 順序查找
8.1.1 無序表的順序查找
8.1.2 有序表的順序查找
8.2 基于關(guān)鍵詞比較的查找
8.2.1 對半查找
8.2.2 一致對半查找
8.2.3 斐波那契查找
8.2.4 插值查找
8.3 二叉查找樹
8.3.1 基本概念和性質(zhì)
8.3.2 查找、插入和刪除
8.3.3 平均情況時間分析
8.4 最優(yōu)二叉查找樹
8.4.1 訪問頻率
8.4.2 最優(yōu)二叉查找樹
8.4.3 近似最優(yōu)樹的構(gòu)造
8.5 平衡樹
8.5.1 高度平衡樹
8.5.2 重量平衡樹
8.6 紅黑樹
8.6.1 紅黑樹的性質(zhì)
8.6.2 旋轉(zhuǎn)
8.6.3 插入
8.6.4 刪除
8.7 B樹及其變形樹
8.7.1 多又樹
8.7.2 B樹
8.7.3 B樹變形樹
8.8 數(shù)字查找
8.8.1 檢索結(jié)構(gòu)查找
8.8.2 數(shù)字樹查找
8.9 散列
8.9.1 散列函數(shù)
8.9.2 沖突調(diào)節(jié)
8.9.3 刪除
8.9.4 重量平衡樹的應用——按位置查找
小結(jié)
參考文獻與推薦讀物
習題
第九章 內(nèi)存管理
9.1 概述
9.2 均勻大小記錄的分配和回收算法
9.2.1 記錄分配算法
9.2.2 訪問計數(shù)器法
9.2.3 廢料收集方法
9.3 不同大小記錄的分配和回收算法
9.3.1 查找分配策略
9.3.2 邊界標識法
9.3.3 壓縮分配
9.4 伙伴系統(tǒng)
9.4.1 伙伴系統(tǒng)概述
9.4.2 分配記錄和釋放記錄算法
小結(jié)
參考文獻與推薦讀物
習題
第10章 文件
10.1 文件的基本概念
10.1.1 文件及其分類
10.1.2 文件的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)
10.2 順序文件
10.2.1 順序無序文件
10.2.2 順序有序文件
10.2.3 增補文件
10.3 散列文件
10.3.1 散列文件
10.3.2 可擴充的散列文件
10.4 索引文件
10.4.1 動態(tài)索引結(jié)構(gòu)和靜態(tài)索引結(jié)構(gòu)
10.4.2 ISAM文件
10.4.3 VSAM文件
10.5 多關(guān)鍵字文件
10.5.1 多重鏈表文件
10.5.2 倒排文件
小結(jié)
參考文獻與推薦讀物
習題
第11章 隨機數(shù)
11.1 生成隨機數(shù)
11.1.1 均勻分布隨機數(shù)
11.1.2 其他分布隨機數(shù)
11.2 隨機數(shù)檢驗
11.2.1 一般檢驗方法
11.2.2 經(jīng)驗檢驗方法
11.3 隨機排列與隨機組合
11.3.1 隨機排列
11.3.2 隨機組合
11.4 應用
11.4.1 隨機算法
11.4.2 使用隨機數(shù)的快速排序算法
小結(jié)
參考文獻與推薦讀物
習題
附錄
附錄1 各章算法的C++實現(xiàn)
附錄2 習題參考答案或解題思路