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

第1章 概要
1.1 本書的主要內(nèi)容
1.2 面向?qū)ο蟮脑O(shè)計(jì)
1.3 對象分級與設(shè)計(jì)方法
1.4 需要了解的C＋＋特性
1.5 本書是如何組織的？
第2章 算法分析
2.1 一個(gè)細(xì)化的計(jì)算機(jī)模型
2.1.1 基本公理
2.1.2 例1：算術(shù)級數(shù)求和
2.1.3 數(shù)組下標(biāo)操作
2.1.4 例2：霍納（Horner）法則
2.1.5 分析遞歸函數(shù)
2.1.6 例3：找出數(shù)組中最大元素
2.1.7 平均運(yùn)行時(shí)間
2.1.8 關(guān)于調(diào)和數(shù)
2.1.9 最佳情況與最差情況的運(yùn)行時(shí)間
2.1.10 最后的公理
2.2 一個(gè)簡化的計(jì)算機(jī)模型
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：冪計(jì)算
2.2.6 例4：再三求幾何級數(shù)之和
習(xí)題
設(shè)計(jì)項(xiàng)目
第3章 漸近表示法
3.1 漸近上界——大O表示法
3.1.1 一個(gè)簡單的例子
3.1.2 大O表示法中的錯(cuò)誤與陷阱
3.1.3 大O的特性
3.1.4 多項(xiàng)式
3.1.5 對數(shù)
3.1.6 緊湊大O界
3.1.7 大O表示法中更多的錯(cuò)誤與陷階
3.1.8 常用的大O表達(dá)式
3.2 漸近下界——表示法
3.2.1 一個(gè)簡單的例子
3.2.2 再次關(guān)于多項(xiàng)式
3.3 更多的表示法——及小o表示法
3.4 算法漸近分析
3.4.1 運(yùn)行時(shí)間分析的大O規(guī)則
3.4.2 例1：求級數(shù)的前項(xiàng)和
3.4.3 例2：Fibonacci數(shù)
3.4.4 例3：桶式排序
3.4.5 現(xiàn)實(shí)檢查
3.4.6 檢查你的分析
習(xí)題
設(shè)計(jì)項(xiàng)目
第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ù)組下標(biāo)操作符
4.1.7 數(shù)組大小的重調(diào)
4.2 單鏈表
4.2.1 鏈表的實(shí)現(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ù)組下標(biāo)計(jì)算
4.3.2 二維數(shù)組的實(shí)現(xiàn)
4.3.3 C＋＋中多維數(shù)組的下標(biāo)
4.3.4 例：規(guī)范矩陣相乘
習(xí)題
設(shè)計(jì)項(xiàng)目
第5章 數(shù)據(jù)類型與抽象
5.1 抽象數(shù)據(jù)類型
5.2 設(shè)計(jì)模式
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 可搜索容器
習(xí)題
設(shè)計(jì)項(xiàng)目
第6章 棧、隊(duì)列及雙端隊(duì)列
6.1 棧
6.1.1 棧的數(shù)組表示法
6.1.2 棧的鏈表表示法
6.1.3 應(yīng)用
6.2 隊(duì)列
6.2.1 隊(duì)列的數(shù)組表示法
6.2.2 隊(duì)列的鏈表表示法
6.2.3 應(yīng)用
6.3 雙端隊(duì)列
6.3.1 雙端隊(duì)列的數(shù)組表示法
6.3.2 雙端隊(duì)列的鏈表表示法
6.3.3 雙向鏈表及循環(huán)鏈表
習(xí)題
設(shè)計(jì)項(xiàng)目
第7章 有序線性表與排序表
7.1 有序線性表
7.1.1 有序線性表的數(shù)組表示法
7.1.2 有序線性表的鏈表表示法
7.1.3 比較ListASArray和ListASLinkedList
7.1.4 應(yīng)用
7.2 排序表
7.2.1 排序表的數(shù)組表示法
7.2.2 排序表的鏈表表示法
7.2.3 比較SortedListAsArray和SortedListAsLinkedList
7.2.4 應(yīng)用
習(xí)題
設(shè)計(jì)項(xiàng)目
第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ù)的實(shí)現(xiàn)
8.3.1 整型關(guān)鍵字
8.3.2 浮點(diǎn)型關(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 鏈?zhǔn)椒稚⒈?br />8.5.2 平均情況分析
8.6 使用開地址法的分散表
8.6.1 線性探查
8.6.2 二次探查
8.6.3 雙散列法
8.6.4 開地址法的實(shí)現(xiàn)
8.6.5 平均情況分析
8.7 應(yīng)用
習(xí)題
設(shè)計(jì)項(xiàng)目
第9章 樹
9.1 基礎(chǔ)
9.2 N叉樹
9.3 二叉樹
9.4 樹的遍歷
9.5 表達(dá)式樹
9.6 樹的實(shí)現(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 應(yīng)用
習(xí)題
設(shè)計(jì)項(xiàng)目
第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 查找樹的實(shí)現(xiàn)
10.4.1 二叉查找樹
10.4.2 在二叉查找樹中插入數(shù)據(jù)項(xiàng)
10.4.3 從二叉查找樹中刪除數(shù)據(jù)項(xiàng)
10.5 AVL查找樹
10.5.1 AVL樹的實(shí)現(xiàn)
10.5.2 在AVL樹中插入數(shù)據(jù)項(xiàng)
10.5.3 從AVL樹中刪除數(shù)據(jù)項(xiàng)
10.6 M路查找樹
10.6.1 M路查找樹的實(shí)現(xiàn)
10.6.2 在M路查找樹中查找數(shù)據(jù)項(xiàng)
10.6.3 在M路查找樹中插入數(shù)據(jù)項(xiàng)
10.6.4 從M路查找樹中刪除數(shù)據(jù)項(xiàng)
10.7 B樹
10.7.1 B樹的實(shí)現(xiàn)
10.7.2 在B樹中插入數(shù)據(jù)項(xiàng)
10.7.3 從B樹中刪除數(shù)據(jù)項(xiàng)
10.8 應(yīng)用
習(xí)題
設(shè)計(jì)項(xiàng)目
第11章 堆和優(yōu)先隊(duì)列
11.1 基礎(chǔ)知識
11.2 二叉堆
11.2.1 完全樹
11.2.2 二叉堆的實(shí)現(xiàn)
11.2.3 在二叉堆中插入數(shù)據(jù)項(xiàng)
11.2.4 從二叉堆中刪除數(shù)據(jù)項(xiàng)
11.3 左翼堆
11.3.1 左翼樹
11.3.2 左翼堆的實(shí)現(xiàn)
11.3.3 左翼堆的合并
11.3.4 在左翼堆中插入數(shù)據(jù)項(xiàng)
11.3.5 從左翼堆中刪除數(shù)據(jù)項(xiàng)
11.4 二項(xiàng)隊(duì)列
11.4.1 二項(xiàng)樹
11.4.2 二項(xiàng)隊(duì)列
11.4.3 實(shí)現(xiàn)
11.4.4 二項(xiàng)隊(duì)列的合并
11.4.5 在二項(xiàng)隊(duì)列中插入數(shù)據(jù)項(xiàng)
11.4.6 從二項(xiàng)隊(duì)列中刪除數(shù)據(jù)項(xiàng)
11.5 應(yīng)用
11.5.1 離散事件模擬
11.5.2 實(shí)現(xiàn)
習(xí)題
設(shè)計(jì)項(xiàng)目
第12章 集合、多重集和分區(qū)
12.1 基礎(chǔ)知識
12.1.1 集合的實(shí)現(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 應(yīng)用
習(xí)題
設(shè)計(jì)項(xiàng)目
第13章 動態(tài)存儲分配：另一種堆
13.1 基礎(chǔ)
13.1.1 C＋＋ Magic
13.1.2 堆
13.2 單鏈自由存儲器
13.2.1 實(shí)現(xiàn)
13.3 雙鏈自由存儲器
13.3.1 實(shí)現(xiàn)
13.4 伙伴存儲管理系統(tǒng)
13.4.1 實(shí)現(xiàn)
13.5 應(yīng)用
13.5.1 實(shí)現(xiàn)
習(xí)題
設(shè)計(jì)項(xiàng)目
第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 分治算法的運(yùn)行時(shí)間
14.3.5 例4：矩陣相乘
14.4 自底向上算法：動態(tài)程序設(shè)計(jì)
14.4.1 例1：廣義Fibonacci數(shù)
14.4.2 例2：求解二項(xiàng)式系數(shù)
14.4.3 應(yīng)用：排版問題
14.5 隨機(jī)化算法
14.5.1 產(chǎn)生隨機(jī)數(shù)
14.5.2 隨機(jī)變量
14.5.3 蒙特卡羅法
14.5.4 模擬退火法
習(xí)題
設(shè)計(jì)項(xiàng)目
第15章 排序算法和排序器
15.1 基礎(chǔ)知識
15.2 排序和排序器
15.3 插入排序
15.3.1 直接插入排序
15.3.2 平均運(yùn)行時(shí)間
15.3.3 二分法插入排序
15.4 交換排序
15.4.1 冒泡排序
15.4.2 快速排序
15.4.3 運(yùn)行時(shí)間分析
15.4.4 平均運(yùn)行時(shí)間
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 算法性能分析
習(xí)題
設(shè)計(jì)項(xiàng)目
第16章 圖和圖算法
16.1 基礎(chǔ)知道
16.1.1 圖的表示法
16.2 圖的實(shí)現(xiàn)
16.2.1 頂點(diǎn)的實(shí)現(xiàn)
16.2.3 抽象圖和有向圖
16.2.4 無向圖的實(shí)現(xiàn)
16.2.5 邊帶權(quán)圖和頂點(diǎn)帶權(quán)圖
16.2.6 圖表示法的比較
16.3 圖的遍歷
16.3.1 深度優(yōu)先遍歷
16.3.2 廣度優(yōu)先遍歷
16.3.3 拓?fù)渑判?br />16.3.4 圖遍歷的應(yīng)用：檢查圖的回路及連通性
16.4 最短路徑算法
16.4.1 單源最短路徑
16.4.2 每對頂點(diǎn)間的最短路徑
16.5 最小支撐樹
16.5.1 Prim算法
16.5.2 Kruskal算法
16.6 應(yīng)用：關(guān)鍵路徑分析
習(xí)題
設(shè)計(jì)項(xiàng)目
附錄A C＋＋與面向?qū)ο缶幊?br />附錄B 類層次圖
附錄C 字符碼
參考答案