數(shù)據(jù)結(jié)構(gòu)與算法：面向?qū)ο蟮腃++設(shè)計模式

第1章 概要
1.1 本書的主要內(nèi)容
1.2 面向?qū)ο蟮脑O(shè)計
1.3 對象分級與設(shè)計方法
1.4 需要了解的C＋＋特性
1.5 本書是如何組織的？
第2章 算法分析
2.1 一個細化的計算機模型
2.1.1 基本公理
2.1.2 例1：算術(shù)級數(shù)求和
2.1.3 數(shù)組下標操作
2.1.4 例2：霍納（Horner）法則
2.1.5 分析遞歸函數(shù)
2.1.6 例3：找出數(shù)組中最大元素
2.1.7 平均運行時間
2.1.8 關(guān)于調(diào)和數(shù)
2.1.9 最佳情況與最差情況的運行時間
2.1.10 最后的公理
2.2 一個簡化的計算機模型
2.2.1 例1：求幾何級數(shù)之和
2.2.2 關(guān)于算術(shù)級數(shù)求和
2.2.3 例2：再次求幾何級數(shù)之和
2.2.4 關(guān)于幾何級數(shù)求和
2.2.5 例3：冪計算
2.2.6 例4：再三求幾何級數(shù)之和
習題
設(shè)計項目
第3章 漸近表示法
3.1 漸近上界——大O表示法
3.1.1 一個簡單的例子
3.1.2 大O表示法中的錯誤與陷阱
3.1.3 大O的特性
3.1.4 多項式
3.1.5 對數(shù)
3.1.6 緊湊大O界
3.1.7 大O表示法中更多的錯誤與陷階
3.1.8 常用的大O表達式
3.2 漸近下界——表示法
3.2.1 一個簡單的例子
3.2.2 再次關(guān)于多項式
3.3 更多的表示法——及小o表示法
3.4 算法漸近分析
3.4.1 運行時間分析的大O規(guī)則
3.4.2 例1：求級數(shù)的前項和
3.4.3 例2：Fibonacci數(shù)
3.4.4 例3：桶式排序
3.4.5 現(xiàn)實檢查
3.4.6 檢查你的分析
習題
設(shè)計項目
第4章 基本數(shù)據(jù)結(jié)構(gòu)
4.1 動態(tài)數(shù)組
4.1.1 缺省構(gòu)造函數(shù)
4.1.2 數(shù)組構(gòu)造函數(shù)
4.1.3 備份構(gòu)造函數(shù)
4.1.4 析構(gòu)函數(shù)
4.1.5 數(shù)組成員函數(shù)
4.1.6 數(shù)組下標操作符
4.1.7 數(shù)組大小的重調(diào)
4.2 單鏈表
4.2.1 鏈表的實現(xiàn)
4.2.2 鏈表元素
4.2.3 缺省構(gòu)造函數(shù)
4.2.4 析構(gòu)函數(shù)與Purge成員函數(shù)
4.2.5 存取器
4.2.6 First與Last函數(shù)
4.2.7 前插
4.2.8 添加
4.2.9 備份構(gòu)造函數(shù)與賦值操作符
4.2.10 析取函數(shù)
4.2.11 InsertAfter與InsertBefore函數(shù)
4.3 多維數(shù)組
4.3.1 數(shù)組下標計算
4.3.2 二維數(shù)組的實現(xiàn)
4.3.3 C＋＋中多維數(shù)組的下標
4.3.4 例：規(guī)范矩陣相乘
習題
設(shè)計項目
第5章 數(shù)據(jù)類型與抽象
5.1 抽象數(shù)據(jù)類型
5.2 設(shè)計模式
5.2.1 類層次
5.2.2 對象
5.2.3 NullObject單元集類
5.2.4 內(nèi)嵌類型的對象包裝
5.2.5 容器
5.2.6 訪問者
5.2.7 迭代器
5.2.8 NullIterator類
5.2.9 直接存儲與間接存儲
5.2.10 被包含對象的所有權(quán)
5.2.11 關(guān)聯(lián)
5.2.12 可搜索容器
習題
設(shè)計項目
第6章 棧、隊列及雙端隊列
6.1 棧
6.1.1 棧的數(shù)組表示法
6.1.2 棧的鏈表表示法
6.1.3 應用
6.2 隊列
6.2.1 隊列的數(shù)組表示法
6.2.2 隊列的鏈表表示法
6.2.3 應用
6.3 雙端隊列
6.3.1 雙端隊列的數(shù)組表示法
6.3.2 雙端隊列的鏈表表示法
6.3.3 雙向鏈表及循環(huán)鏈表
習題
設(shè)計項目
第7章 有序線性表與排序表
7.1 有序線性表
7.1.1 有序線性表的數(shù)組表示法
7.1.2 有序線性表的鏈表表示法
7.1.3 比較ListASArray和ListASLinkedList
7.1.4 應用
7.2 排序表
7.2.1 排序表的數(shù)組表示法
7.2.2 排序表的鏈表表示法
7.2.3 比較SortedListAsArray和SortedListAsLinkedList
7.2.4 應用
習題
設(shè)計項目
第8章 散列、哈希表及分散表
8.1 散列的基本知識
8.1.1 關(guān)鍵字和散列函數(shù)
8.2 散列法
8.2.1 相除散列法
8.2.2 平方取中散列法
8.2.3 相乘散列法
8.2.4 Fibonacci散列法
8.3 散列函數(shù)的實現(xiàn)
8.3.1 整型關(guān)鍵字
8.3.2 浮點型關(guān)鍵字
8.3.3 字符串關(guān)鍵字
8.3.4 散列對象
8.3.5 散列容器
8.3.6 使用關(guān)聯(lián)
8.4 哈希表
8.4.1 拉鏈法
8.4.2 平均情況分析
8.5 分散表
8.5.1 鏈式分散表
8.5.2 平均情況分析
8.6 使用開地址法的分散表
8.6.1 線性探查
8.6.2 二次探查
8.6.3 雙散列法
8.6.4 開地址法的實現(xiàn)
8.6.5 平均情況分析
8.7 應用
習題
設(shè)計項目
第9章 樹
9.1 基礎(chǔ)
9.2 N叉樹
9.3 二叉樹
9.4 樹的遍歷
9.5 表達式樹
9.6 樹的實現(xiàn)
9.6.1 樹的遍歷
9.6.2 樹迭代器
9.6.3 廣義樹
9.6.4 N叉樹
9.6.5 二叉樹
9.6.6 二叉樹的遍歷
9.6.7 樹的比較
9.6.8 應用
習題
設(shè)計項目
第10章 查找樹
10.1 基礎(chǔ)知識
10.1.1 M路查找樹
10.1.2 二叉查找樹
10.2 搜索查找樹
10.2.1 搜索M路查找樹
10.2.2 搜索二叉樹
10.3 平均情況分析
10.3.1 搜索成功
10.3.2 遞歸關(guān)系的求解——拓展遞歸法
10.3.3 搜索失敗
10.3.4 查找樹的遍歷
10.4 查找樹的實現(xiàn)
10.4.1 二叉查找樹
10.4.2 在二叉查找樹中插入數(shù)據(jù)項
10.4.3 從二叉查找樹中刪除數(shù)據(jù)項
10.5 AVL查找樹
10.5.1 AVL樹的實現(xiàn)
10.5.2 在AVL樹中插入數(shù)據(jù)項
10.5.3 從AVL樹中刪除數(shù)據(jù)項
10.6 M路查找樹
10.6.1 M路查找樹的實現(xiàn)
10.6.2 在M路查找樹中查找數(shù)據(jù)項
10.6.3 在M路查找樹中插入數(shù)據(jù)項
10.6.4 從M路查找樹中刪除數(shù)據(jù)項
10.7 B樹
10.7.1 B樹的實現(xiàn)
10.7.2 在B樹中插入數(shù)據(jù)項
10.7.3 從B樹中刪除數(shù)據(jù)項
10.8 應用
習題
設(shè)計項目
第11章 堆和優(yōu)先隊列
11.1 基礎(chǔ)知識
11.2 二叉堆
11.2.1 完全樹
11.2.2 二叉堆的實現(xiàn)
11.2.3 在二叉堆中插入數(shù)據(jù)項
11.2.4 從二叉堆中刪除數(shù)據(jù)項
11.3 左翼堆
11.3.1 左翼樹
11.3.2 左翼堆的實現(xiàn)
11.3.3 左翼堆的合并
11.3.4 在左翼堆中插入數(shù)據(jù)項
11.3.5 從左翼堆中刪除數(shù)據(jù)項
11.4 二項隊列
11.4.1 二項樹
11.4.2 二項隊列
11.4.3 實現(xiàn)
11.4.4 二項隊列的合并
11.4.5 在二項隊列中插入數(shù)據(jù)項
11.4.6 從二項隊列中刪除數(shù)據(jù)項
11.5 應用
11.5.1 離散事件模擬
11.5.2 實現(xiàn)
習題
設(shè)計項目
第12章 集合、多重集和分區(qū)
12.1 基礎(chǔ)知識
12.1.1 集合的實現(xiàn)
12.2 數(shù)組和位矢量集合
12.2.1 位矢量集合
12.3 多重集
12.3.1 多重集的數(shù)組表示法
12.3.2 多重集的鏈表表示法
12.4 分區(qū)
12.4.1 用森林表示分區(qū)
12.4.2 折疊查找
12.4.3 按大小合并
12.4.4 按高度或?qū)犹柡喜?br />12.5 應用
習題
設(shè)計項目
第13章 動態(tài)存儲分配：另一種堆
13.1 基礎(chǔ)
13.1.1 C＋＋ Magic
13.1.2 堆
13.2 單鏈自由存儲器
13.2.1 實現(xiàn)
13.3 雙鏈自由存儲器
13.3.1 實現(xiàn)
13.4 伙伴存儲管理系統(tǒng)
13.4.1 實現(xiàn)
13.5 應用
13.5.1 實現(xiàn)
習題
設(shè)計項目
第14章 算法模式和問題求解
14.1 蠻干算法和貪心算法
14.1.1 例1：數(shù)錢
14.1.2 例2：0／1背包問題
14.2 回溯算法
14.2.1 例1：平衡稱
14.2.2 解空間的表示
14.2.3 抽象回溯求解程序
14.2.4 分支界限求解程序
14.2.5 例2：再次分析0／1背包問題
14.3 自頂向下算法：分治算法
14.3.1 例1：二分法查找
14.3.2 例2：求解Fibonacci數(shù)
14.3.3 例3：歸并排序
14.3.4 分治算法的運行時間
14.3.5 例4：矩陣相乘
14.4 自底向上算法：動態(tài)程序設(shè)計
14.4.1 例1：廣義Fibonacci數(shù)
14.4.2 例2：求解二項式系數(shù)
14.4.3 應用：排版問題
14.5 隨機化算法
14.5.1 產(chǎn)生隨機數(shù)
14.5.2 隨機變量
14.5.3 蒙特卡羅法
14.5.4 模擬退火法
習題
設(shè)計項目
第15章 排序算法和排序器
15.1 基礎(chǔ)知識
15.2 排序和排序器
15.3 插入排序
15.3.1 直接插入排序
15.3.2 平均運行時間
15.3.3 二分法插入排序
15.4 交換排序
15.4.1 冒泡排序
15.4.2 快速排序
15.4.3 運行時間分析
15.4.4 平均運行時間
15.4.5 軸值的選擇
15.5 選擇排序
15.5.1 直接選擇排序
15.5.2 堆排序
15.5.3 堆的建立
15.6 歸并排序
15.7 排序算法的下界
15.8 分配排序
15.8.1 桶式排序
15.8.2 基數(shù)排序
15.9 算法性能分析
習題
設(shè)計項目
第16章 圖和圖算法
16.1 基礎(chǔ)知道
16.1.1 圖的表示法
16.2 圖的實現(xiàn)
16.2.1 頂點的實現(xiàn)
16.2.3 抽象圖和有向圖
16.2.4 無向圖的實現(xiàn)
16.2.5 邊帶權(quán)圖和頂點帶權(quán)圖
16.2.6 圖表示法的比較
16.3 圖的遍歷
16.3.1 深度優(yōu)先遍歷
16.3.2 廣度優(yōu)先遍歷
16.3.3 拓撲排序
16.3.4 圖遍歷的應用：檢查圖的回路及連通性
16.4 最短路徑算法
16.4.1 單源最短路徑
16.4.2 每對頂點間的最短路徑
16.5 最小支撐樹
16.5.1 Prim算法
16.5.2 Kruskal算法
16.6 應用：關(guān)鍵路徑分析
習題
設(shè)計項目
附錄A C＋＋與面向?qū)ο缶幊?br />附錄B 類層次圖
附錄C 字符碼
參考答案