數(shù)據(jù)結構（第3版）

第1章 數(shù)學準備
1．1 數(shù)學歸納法
1．2 數(shù)、冪與對數(shù)
1．3 和與積
1．4 整數(shù)函數(shù)和初等數(shù)論
1．5 排列和階乘
1．6 二項式系數(shù)
1．7 調和數(shù)
1．8 斐波那契數(shù)
小結
推薦讀物與參考文獻
習題
第2章 緒論
2．1 為什么要學習數(shù)據(jù)結構
2．2 數(shù)據(jù)結構概念
2．2．1 數(shù)據(jù)的邏輯結構
2．2．2 數(shù)據(jù)的存儲結構
2．2．3 對數(shù)據(jù)結構的操作
2．2．4 數(shù)據(jù)結構示例
2．3 算法
2．3．1 算法及其特性
2．3．2 算法的描述
2．3．3 算法的評價準則
2．4 算法的正確性證明
2．5 算法分析基礎
2．5．1 算法時間復雜性的分析方法
2．5．2 復雜性函數(shù)的漸近表示
2．5．3 算法時間與空間分析
2．5．4 計算復雜性和算法的效率
小結
推薦讀物與參考文獻
習題
第3章 線性表、堆棧和隊列
3．1 線性表的定義和基本操作
3．2 線性表的順序存儲結構
3．3 線性表的鏈接存儲結構
3．3．1 單鏈表
3．3．2 循環(huán)鏈表
3．3．3 雙向鏈表
3．4 復雜性分析
3．5 堆棧
3．5．1 堆棧的定義和基本操作
3．5．2 順序棧
3．5．3 鏈式棧
3．5．4 順序棧與鏈式棧的比較
3．5．5 堆棧應用——括號匹配
3．5．6 堆棧應用——遞歸
3．6 隊列
3．6．1 隊列的定義和基本操作
3．6．2 順序隊列
3．6．3 鏈式隊列
小結
推薦讀物與參考文獻
習題
第4章 數(shù)組和字符串
4．1 數(shù)組
4．1．1 數(shù)組的存儲和尋址
4．1．2 一維數(shù)組的基本操作
4．2 矩陣
4．2．1 矩陣的數(shù)組表示
4．2．2 特殊矩陣的壓縮存儲
4．2．3 三元組表
4．2．4 十字鏈表
4．3 字符串
4．3．1 字符串的定義與存儲
4．3．2 模式匹配算法
小結
推薦讀物與參考文獻
習題
第5章 樹與二叉樹
5．1 樹的基本概念
5．1．1 樹的定義
5．1．2 樹的相關術語
5．1．3 樹的表示
5．2 二叉樹
5．2．1 二叉樹定義和主要性質
5．2．2 二叉樹順序存儲
5．2．3 二叉樹鏈接存儲
5．2．4 二叉樹遍歷
5．2．5 二叉樹的其他操作
5．2．6 表達式樹
5．3 線索二叉樹
5．3．1 線索二叉樹的概念
5．3．2 線索二叉樹的操作
5．3．3 線索二叉樹的進一步說明
5．4 壓縮與哈夫曼樹
5．4．1 文件編碼
5．4．2 擴充二叉樹
5．4．3 哈夫曼樹和哈夫曼編碼
5．5 樹的存儲和操作
5．5．1 樹與二叉樹的轉換
5．5．2 樹的存儲結構
5．5．3 樹和森林的遍歷
5．5．4 樹的順序表示
5．6 等價類與并查集
5．6．1 等價類
5．6．2 并查集的實現(xiàn)
5．7 分類與決策樹
小結
推薦讀物與參考文獻
習題
第6章 圖
6．1 圖的基本概念
6．2 圖的存儲結構
6．2．1 鄰接矩陣
6．2．2 鄰接表
6．3 圖的遍歷算法
6．3．1 深度優(yōu)先遍歷
6．3．2 廣度優(yōu)先遍歷
6．4 拓撲排序
6．5 關鍵路徑
6．6 最短路徑問題
6．6．1 無權最短路徑問題
6．6．2 正權最短路徑問題
6．6．3 每對頂點之間的最短路徑
6．6．4 滿足約束的最短路徑
6．7 最小支撐樹
6．7．1 普里姆算法
6．7．2 克魯斯卡爾算法
6．8 圖的應用
6．8．1 可及性及傳遞閉包算法
6．8．2 連通分量
6．8．3 圖在網(wǎng)絡分析和信息
檢索中的應用
小結
推薦讀物與參考文獻
習題
第7章 排序
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 基于關鍵詞比較的排序算法分析
7．6．1 平方階排序算法及改進算法
7．6．2 線性對數(shù)階排序算法
7．6．3 分治排序的一般方法
7．6．4 基于關鍵詞比較的排序算法下界
7．7 分布排序
7．8 外排序
7．8．1 外存儲器
7．8．2 磁帶排序
7．8．3 磁盤排序
小結
推薦讀物與參考文獻
習題
第8章 查找
8．1 順序查找
8．1．1 無序表的順序查找
8．1．2 有序表的順序查找
8．2 基于關鍵詞比較的查找
8．2．1 對半查找
8．2．2 一致對半查找
8．2．3 斐波那契查找
8．2．4 插值查找
8．3 二叉查找樹
8．3．1 基本概念和性質
8．3．2 查找、插人和刪除
8．3．3 平均情況時間分析
8．4 最優(yōu)二叉查找樹
8．4．1 訪問頻率
8．4．2 最優(yōu)二叉查找樹
8．4．3 近似最優(yōu)樹的構造
8．5 高度平衡樹
8．5．1 基本概念和性質
8．5．2 查找和插入操作
8．5．3 線性表的平衡樹表示
8．5．4 刪除操作
8．6 B樹
8．6．1 多叉樹
8．6．2 B樹
8．7 數(shù)字查找
8．7．1 檢索結構查找
8．7．2 數(shù)字樹查找
8．8 散列
8．8．1 散列函數(shù)
8．8．2 沖突調節(jié)
8．8．3 刪除
小結
推薦讀物與參考文獻
習題