數(shù)據(jù)結(jié)構(gòu)與算法分析（Java版）

第一部分 預(yù)備知識
第1章 數(shù)據(jù)結(jié)構(gòu)和算法
1.1 數(shù)據(jù)結(jié)構(gòu)的原則
1.1.1 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的必要性
1.1.2 代價與效益
1.1.3 本書的目的
1.2 抽象數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)
1.3 問題、算法和程序
1.4 算法的效率
1.5 深入學(xué)習(xí)導(dǎo)讀
1.6 習(xí)題
第2章 數(shù)學(xué)預(yù)備知識
2.1 集合
2.2 常用數(shù)學(xué)術(shù)語
2.3 對數(shù)
2.4 遞歸
2.5 級數(shù)求和與遞歸
2.6 數(shù)學(xué)證明方法
2.6.1 反證法
2.6.2 數(shù)學(xué)歸納法
2.7 評估
2.8 深入學(xué)習(xí)導(dǎo)讀
2.9 習(xí)題
第3章 算法分析
3.1 概述
3.2 最佳、最差和平均情況
3.3 換一臺更快的計算機(jī)，還是換一種更快的算法
3.4 漸進(jìn)分析
3.4.1 上限
3.4.2 下限
3.4.3 表示法
3.4.4 化簡法則
3.5 程序運(yùn)行時間的計算
3.6 問題的分析
3.7 多參數(shù)問題
3.8 空間代價
3.9 實際操作中的一些因素
3.10 深入學(xué)習(xí)導(dǎo)讀
3.11 習(xí)題
3.12 項目設(shè)計
第二部分 基本數(shù)據(jù)結(jié)構(gòu)
第4章 線性表、棧和隊列
4.1 線性表
4.1.1 順序表的表示法
4.1.2 鏈表
4.1.3 線性表實現(xiàn)方法的比較
4.1.4 元素的表示
4.1.5 雙鏈表
4.1.6 循環(huán)鏈表
4.2 棧
4.2.1 順序棧
4.2.2 鏈?zhǔn)綏?br />4.2.3 順序棧與鏈?zhǔn)綏５谋容^
4.2.4 遞歸的實現(xiàn)
4.3 隊列
4.3.1 順序隊列
4.3.2 鏈?zhǔn)疥犃?br />4.3.3 順序隊列與鏈?zhǔn)疥犃械谋容^
4.4 習(xí)題
4.5 項目設(shè)計
第5章 二叉樹
5.1 定義及主要特性
5.1.1 滿二叉樹定理
5.1.2 二叉樹的抽象數(shù)據(jù)類型
5.2 周游二叉樹
5.3 二叉樹的實現(xiàn)
5.3.1 使用指針實現(xiàn)二叉樹
5.3.2 空間開銷
5.3.3 使用數(shù)組實現(xiàn)完全二叉樹
5.4 Huffman編碼樹
5.4.1 建立Huffman編碼樹
5.4.2 Huffman編碼及其用法
5.5 二叉檢索樹
5.6 堆與優(yōu)先隊列
5.7 深入學(xué)習(xí)導(dǎo)讀
5.8 習(xí)題
5.9 項目設(shè)計
第6章 樹
6.1 樹的定義與術(shù)語
6.1.1 樹結(jié)點的ADT(抽象數(shù)據(jù)類型)
6.1.2 樹的周游
6.2 父指針表示法
6.3 樹的實現(xiàn)
6.3.1 子結(jié)點表表示法
6.3.2 左子結(jié)點／右兄弟結(jié)點表示法
6.3.3 動態(tài)結(jié)點表示法
6.3.4 動態(tài)"左子結(jié)點／右兄弟結(jié)點"表示法
6.4 K叉樹
6.5 樹州順序表示法
6.6 深入學(xué)習(xí)導(dǎo)讀
6.7 習(xí)題
6.8 項目設(shè)計
第7章 圖
7.1 術(shù)語和表示法
7.2 圖的實現(xiàn)
7.3 圖的周游
7.3.1 深度優(yōu)先搜索
7.3.2 廣度優(yōu)先搜索
7.3.3 拓?fù)渑判?br />7.4 最短路徑問題
7.4.1 單源最短路徑
7.4.2 每對頂點間的最短路徑
7.5 最小支撐樹
7.5.1 Prim算法
7.5.2 Kmskal算法
7.6 深入學(xué)習(xí)導(dǎo)讀
7.7 習(xí)題
7.8 項目設(shè)計
第三部分 排序和檢索
第8章 內(nèi)排序
8.1 排序的術(shù)語及記號
8.2 三種代價為(n2)的排序方法
8.2.1 插入排序
8.2.2 起泡排序
8.2.3 選擇排序
8.2.4 交換排序算法的時間代價
8.3 Shell排序
8.4 快速排序
8.5 歸并排序
8.6 堆排序
8.7 分配排序和基數(shù)排序
8.8 對各種排序算法的實驗比較
8.9 排序問題的下限
8.10 深入學(xué)習(xí)導(dǎo)讀
8.11 習(xí)題
8.12 項目設(shè)計
第9章 文件管理和外排序
9.1 主存儲器和輔助存儲器
9.2 磁盤和磁帶驅(qū)動器
9.2.1 磁盤訪問的代價
9.2.2 磁帶
9.3 緩沖區(qū)和緩沖池
9.4 程序員的文件視圖
9.5 外部排序
9.6 外部排序的簡單方法
9.7 置換選擇排序
9.8 多路歸并
9.9 深入學(xué)習(xí)導(dǎo)讀
9.10 習(xí)題
9.11 項目設(shè)計
第10章 檢索
10.1 檢索已排序的數(shù)組
10.2 自組織線性表
10.3 集合的檢索
10.4 散列方法
10.4.1 散列函數(shù)
10.4.2 開散列方法
10.4.3 閉散列方法
10.5 深入學(xué)習(xí)導(dǎo)讀
10.6 習(xí)題
10.7 項目設(shè)計
第11章 索引技術(shù)
11.1 線性索引
11.2 ISAM
11.3 樹形索引
11.4 2-3樹
11.5 B樹
11.5.1 B+樹
11.5.2 B樹分析
11.6 深入學(xué)習(xí)導(dǎo)讀
11.7 習(xí)題
11.8 項目設(shè)計
第四部分 應(yīng)用與高級話題
第12章 線性表和數(shù)組高級技術(shù)
12.1 跳躍表
12.2 廣義表
12.3 矩陣的表示方法
12.4 存儲管理
12.4.1 動態(tài)存儲分配
12.4.2 失敗處理策略和無用單元收集
12.5 深入學(xué)習(xí)導(dǎo)讀
12.6 習(xí)題
12.7 項目設(shè)計
第13章 高級樹形結(jié)構(gòu)
13.1 Trie結(jié)構(gòu)
13.2 伸展樹
13.3 空間數(shù)據(jù)結(jié)構(gòu)
13.3.1 k-d樹
13.3.2 PR四分樹
13.3.3 其他空間數(shù)據(jù)結(jié)構(gòu)
13.4 深入學(xué)習(xí)導(dǎo)讀
13.5 習(xí)題
13.6 項目設(shè)計
第14章 分析技術(shù)
14.1 求和技術(shù)
14.2 遞歸關(guān)系
14.2.1 估計上下限
14.2.2 擴(kuò)展遞歸
14.2.3 分治法遞歸
14.2.4 快速排序平均情況分析
14.3 均攤分析
14.4 深入學(xué)習(xí)導(dǎo)讀
14.5 習(xí)題
14.6 項目設(shè)計
第15章 計算的限制
15.1 簡介
15.2 歸約
15.3 難解問題
15.3.1 NP完全性
15.3.2 繞過NP完全性問題
15.4 不可解問題
15.4.1 不可數(shù)性
15.4.2 停機(jī)問題的不可解性
15.4.3 確定程序行為是不可解的
15.5 深入學(xué)習(xí)導(dǎo)讀
15.6 習(xí)題
15.7 項目設(shè)計
附錄A C和Pasca1程序員的Java導(dǎo)引
A.1 例1：線性表的接口
A.2 例2：基于數(shù)組的線性表實現(xiàn)
A.3 例3：鏈表的實現(xiàn)
參考文獻(xiàn)