Data Structures， Algorithms， and Applications in C++， Second Edition
出版者的話(huà)
譯者序
前言
第一部分 預(yù)備知識(shí)
第1章 C++回顧
1.1 引言
1.2 函數(shù)與參數(shù)
1.2.1 傳值參數(shù)
1.2.2 模板函數(shù)
1.2.3 引用參數(shù)
1.2.4 常量引用參數(shù)
1.2.5 返回值
1.2.6 重載函數(shù)
1.3 異常
1.3.1 拋出異常
1.3.2 處理異常
1.4 動(dòng)態(tài)存儲(chǔ)空間分配
1.4.1 操作符new
1.4.2 一維數(shù)組
1.4.3 異常處理
1.4.4 操作符delete
1.4.5 二維數(shù)組
1.5 自有數(shù)據(jù)類(lèi)型
1.5.1 類(lèi)currency
1.5.2 一種不同的描述方法
1.5.3 操作符重載
1.5.4 友元和保護(hù)性類(lèi)成員
1.5.5 增加#ifndef、#define和#endif語(yǔ)句
1.6 異常類(lèi)illegalParameterValue
1.7 遞歸函數(shù)
1.7.1 遞歸的數(shù)學(xué)函數(shù)
1.7.2 歸納
1.7.3 C++遞歸函數(shù)
1.8 標(biāo)準(zhǔn)模板庫(kù)
1.9 測(cè)試與調(diào)試
1.9.1 什么是測(cè)試
1.9.2 測(cè)試數(shù)據(jù)的設(shè)計(jì)
1.9.3 調(diào)試
1.10 參考及推薦讀物
第2章 程序性能分析
2.1 什么是程序性能
2.2 空間復(fù)雜度
2.2.1 空間復(fù)雜度的組成
2.2.2 舉例
2.3 時(shí)間復(fù)雜度
2.3.1 時(shí)間復(fù)雜度的組成
2.3.2 操作計(jì)數(shù)
2.3.3 最好、最壞和平均操作計(jì)數(shù)
2.3.4 步數(shù)
第3章 漸近記法
3.1 引言
3.2 漸近記法
3.2.1 大Ο記法
3.2.2 漸近記法Ω和Θ
3.3 漸近數(shù)學(xué)（可選）
3.3.1 大O記法
3.3.2 Ω記法
3.3.3 Θ記法
3.3.4 小ο記法
3.3.5 特性
3.4 復(fù)雜度分析舉例
3.5 實(shí)際復(fù)雜度
3.6 參考及推薦讀物
第4章 性能測(cè)量
4.1 引言
4.2 選擇實(shí)例的大小
4.3 設(shè)計(jì)測(cè)試數(shù)據(jù)
4.4 實(shí)驗(yàn)設(shè)計(jì)
4.5 高速緩存
4.5.1 簡(jiǎn)單計(jì)算機(jī)模型
4.5.2 緩存未命中對(duì)運(yùn)行時(shí)間的影響
4.5.3 矩陣乘法
4.6 參考及推薦讀物


第二部分 數(shù)據(jù)結(jié)構(gòu)
第5章 線(xiàn)性表——數(shù)組描述
5.1 數(shù)據(jù)對(duì)象和數(shù)據(jù)結(jié)構(gòu)
5.2 線(xiàn)性表數(shù)據(jù)結(jié)構(gòu)
5.2.1 抽象數(shù)據(jù)類(lèi)型linearList 
5.2.2 抽象類(lèi)linearList
5.3 數(shù)組描述
5.3.1 描述
5.3.2 變長(zhǎng)一維數(shù)組
5.3.3 類(lèi)arrayList
5.3.4 C++迭代器
5.3.5 arrayList的一個(gè)迭代器
5.4 vector的描述
5.5 在一個(gè)數(shù)組中實(shí)現(xiàn)的多重表
5.6 性能測(cè)量
5.7 參考及推薦讀物
第6章 線(xiàn)性表——鏈?zhǔn)矫枋?br /> 6.1 單向鏈表
6.1.1 描述
6.1.2 結(jié)構(gòu)chainNode
6.1.3 類(lèi)chain
6.1.4 抽象數(shù)據(jù)類(lèi)型linearList的擴(kuò)充
6.1.5 類(lèi)extendedChain
6.1.6 性能測(cè)量
6.2 循環(huán)鏈表和頭節(jié)點(diǎn)
6.3 雙向鏈表
6.4 鏈表用到的詞匯表
6.5 應(yīng)用
6.5.1 箱子排序
6.5.2 基數(shù)排序
6.5.3 凸包
6.5.4 并查集
第7章 數(shù)組和矩陣
7.1 數(shù)組
7.1.1 抽象數(shù)據(jù)類(lèi)型
7.1.2 C++數(shù)組的索引
7.1.3 行主映射和列主映射
7.1.4 用數(shù)組的數(shù)組來(lái)描述
7.1.5 行主描述和列主描述
7.1.6 不規(guī)則二維數(shù)組
7.2 矩陣
7.2.1 定義和操作
7.2.2 類(lèi)matrix
7.3 特殊矩陣
7.3.1 定義和應(yīng)用
7.3.2 對(duì)角矩陣
7.3.3 三對(duì)角矩陣
7.3.4 三角矩陣
7.3.5 對(duì)稱(chēng)矩陣
7.4 稀疏矩陣
7.4.1 基本概念
7.4.2 用單個(gè)線(xiàn)性表描述
7.4.3 用多個(gè)線(xiàn)性表描述
7.4.4 性能測(cè)量
第8章 棧
8.1 定義和應(yīng)用
8.2 抽象數(shù)據(jù)類(lèi)型
8.3 數(shù)組描述
8.3.1 作為一個(gè)派生類(lèi)實(shí)現(xiàn)
8.3.2 類(lèi)arrayStack
8.3.3 性能測(cè)量
8.4 鏈表描述
8.4.1 類(lèi)derivedLinkedStack
8.4.2 類(lèi)linkedStack
8.4.3 性能測(cè)量
8.5 應(yīng)用
8.5.1 括號(hào)匹配
8.5.2 漢諾塔
8.5.3 列車(chē)車(chē)廂重排
8.5.4 開(kāi)關(guān)盒布線(xiàn)
8.5.5 離線(xiàn)等價(jià)類(lèi)問(wèn)題
8.5.6 迷宮老鼠
8.6 參考及推薦讀物
第9章 隊(duì)列
9.1 定義和應(yīng)用
9.2 抽象數(shù)據(jù)類(lèi)型
9.3 數(shù)組描述
9.3.1 描述
9.3.2 類(lèi)arrayQueue
9.4 鏈表描述
9.5 應(yīng)用
9.5.1 列車(chē)車(chē)廂重排
9.5.2 電路布線(xiàn)
9.5.3 圖元識(shí)別
9.5.4 工廠(chǎng)仿真
9.6 參考及推薦讀物
第10章 跳表和散列
10.1 字典
10.2 抽象數(shù)據(jù)類(lèi)型
10.3 線(xiàn)性表描述
10.4 跳表表示（可選）
10.4.1 理想情況
10.4.2 插入和刪除
10.4.3 級(jí)的分配
10.4.4 結(jié)構(gòu)skipNode
10.4.5 類(lèi)skipList
10.4.6 skipList方法的復(fù)雜度
10.5 散列表描述
10.5.1 理想散列
10.5.2 散列函數(shù)和散列表
10.5.3 線(xiàn)性探查
10.5.4 鏈?zhǔn)缴⒘?br /> 10.6 一個(gè)應(yīng)用——文本壓縮
10.6.1 LZW壓縮
10.6.2 LZW壓縮的實(shí)現(xiàn)
10.6.3 LZW解壓縮
10.6.4 LZW解壓縮的實(shí)現(xiàn)
10.6.5 性能評(píng)價(jià)
10.7 參考及推薦讀物
第11章 二叉樹(shù)和其他樹(shù)
11.1 樹(shù)
11.2 二叉樹(shù)
11.3 二叉樹(shù)的特性
11.4 二叉樹(shù)的描述
11.4.1 數(shù)組描述
11.4.2 鏈表描述
11.5 二叉樹(shù)常用操作
11.6 二叉樹(shù)遍歷
11.7 抽象數(shù)據(jù)類(lèi)型BinaryTree
11.8 類(lèi)linkedBinaryTree
11.9 應(yīng)用
11.9.1 設(shè)置信號(hào)放大器
11.9.2 并查集
11.10 參考及推薦讀物
第12章 優(yōu)先級(jí)隊(duì)列
12.1 定義和應(yīng)用
12.2 抽象數(shù)據(jù)類(lèi)型
12.3 線(xiàn)性表
12.4 堆
12.4.1 定義
12.4.2 大根堆的插入
12.4.3 大根堆的刪除
12.4.4 大根堆的初始化
12.4.5 類(lèi)maxHeap
12.4.6 堆和STL
12.5 左高樹(shù)
12.5.1 高度優(yōu)先與寬度優(yōu)先的最大及最小左高樹(shù)
12.5.2 最大HBLT的插入
12.5.3 最大HBLT的刪除
12.5.4 兩棵最大HBLT的合并
12.5.5 初始化
12.5.6 類(lèi)maxHblt
12.6 應(yīng)用
12.6.1 堆排序
12.6.2 機(jī)器調(diào)度
12.6.3 霍夫曼編碼
12.7 參考及推薦讀物
第13章 競(jìng)賽樹(shù)
13.1 贏者樹(shù)和應(yīng)用
13.2 抽象數(shù)據(jù)類(lèi)型WinnerTree
13.3 贏者樹(shù)的實(shí)現(xiàn)
13.3.1 表示
13.3.2 贏者樹(shù)的初始化
13.3.3 重新組織比賽
13.3.4 類(lèi)completeWinnerTree
13.4 輸者樹(shù)
13.5 應(yīng)用
13.5.1 用最先適配法求解箱子裝載問(wèn)題
13.5.2 用相鄰適配法求解箱子裝載問(wèn)題
13.6 參考及推薦讀物
第14章 搜索樹(shù)
14.1 定義
14.1.1 二叉搜索樹(shù)
14.1.2 索引二叉搜索樹(shù)
14.2 抽象數(shù)據(jù)類(lèi)型
14.3 二叉搜索樹(shù)的操作和實(shí)現(xiàn)
14.3.1 類(lèi)binarySearchTree
14.3.2 搜索
14.3.3 插入
14.3.4 刪除
14.3.5 二叉搜索樹(shù)的高度
14.4 帶有相同關(guān)鍵字元素的二叉搜索樹(shù)
14.5 索引二叉搜索樹(shù)
14.6 應(yīng)用
14.6.1 直方圖
14.6.2 箱子裝載問(wèn)題的最優(yōu)匹配法
14.6.3 交叉分布
第15章 平衡搜索樹(shù)
15.1 AVL樹(shù)
15.1.1 定義
15.1.2 AVL樹(shù)的高度
15.1.3 AVL樹(shù)的描述
15.1.4 AVL搜索樹(shù)的搜索
15.1.5 AVL搜索樹(shù)的插入
15.1.6 AVL搜索樹(shù)的刪除
15.2 紅-黑樹(shù)
15.2.1 基本概念
15.2.2 紅-黑樹(shù)的描述
15.2.3 紅-黑樹(shù)的搜索
15.2.4 紅-黑樹(shù)的插入
15.2.5 紅-黑樹(shù)的刪除
15.2.6 實(shí)現(xiàn)細(xì)節(jié)的考慮及復(fù)雜性分析
15.3 分裂樹(shù)
15.3.1 介紹
15.3.2 分裂樹(shù)的操作
15.3.3 折算復(fù)雜性
15.4 B-樹(shù)
15.4.1 索引順序訪(fǎng)問(wèn)方法
15.4.2 m叉搜索樹(shù)
15.4.3 m階B-樹(shù)
15.4.4 B-樹(shù)的高度
15.4.5 B-樹(shù)的搜索
15.4.6 B-樹(shù)的插入
15.4.7 B-樹(shù)的刪除
15.4.8 節(jié)點(diǎn)結(jié)構(gòu)
15.5 參考及推薦讀物
第16章 圖
16.1 基本概念
16.2 應(yīng)用和更多的概念
16.3 特性
16.4 抽象數(shù)據(jù)類(lèi)型graph
16.5 無(wú)權(quán)圖的描述
16.5.1 鄰接矩陣
16.5.2 鄰接鏈表
16.5.3 鄰接數(shù)組
16.6 加權(quán)圖的描述
16.7 類(lèi)實(shí)現(xiàn)
16.7.1 不同的類(lèi)
16.7.2 鄰接矩陣類(lèi)
16.7.3 擴(kuò)充chain類(lèi)
16.7.4 鏈表類(lèi)
16.8 圖的遍歷
16.8.1 廣度優(yōu)先搜索
16.8.2 廣度優(yōu)先搜索的實(shí)現(xiàn)
16.8.3 方法graph：：bfs的復(fù)雜性分析
16.8.4 深度優(yōu)先搜索
16.8.5 深度優(yōu)先搜索的實(shí)現(xiàn)
16.8.6 方法graph：：dfs的復(fù)雜性分析
16.9 應(yīng)用
16.9.1 尋找一條路徑
16.9.2 連通圖及其構(gòu)成
16.9.3 生成樹(shù)


第三部分 算法設(shè)計(jì)方法
第17章 貪婪算法
17.1 最優(yōu)化問(wèn)題
17.2 貪婪算法思想
17.3 應(yīng)用
17.3.1 貨箱裝載
17.3.2 0/1背包問(wèn)題
17.3.3 拓?fù)渑判?br /> 17.3.4 二分覆蓋
17.3.5 單源最短路徑
17.3.6 最小成本生成樹(shù)
17.4 參考及推薦讀物
第18章 分而治之
18.1 算法思想
18.2 應(yīng)用
18.2.1 殘缺棋盤(pán)
18.2.2 歸并排序
18.2.3 快速排序
18.2.4 選擇
18.2.5 相距最近的點(diǎn)對(duì)
18.3 解遞歸方程
18.4 復(fù)雜度的下限
18.4.1 最小最大問(wèn)題的下限
18.4.2 排序算法的下限
第19章 動(dòng)態(tài)規(guī)劃
19.1 算法思想
19.2 應(yīng)用
19.2.1 0/1背包問(wèn)題
19.2.2 矩陣乘法鏈
19.2.3 所有頂點(diǎn)對(duì)之間的最短路徑
19.2.4 帶有負(fù)值的單源最短路徑
19.2.5 網(wǎng)組的無(wú)交叉子集
19.3 參考及推薦讀物
第20章 回溯法
20.1 算法思想
20.2 應(yīng)用
20.2.1 貨箱裝載
20.2.2 0/1背包問(wèn)題
20.2.3 最大完備子圖
20.2.4 旅行商問(wèn)題
20.2.5 電路板排列
第21章 分支定界
21.1 算法思想
21.2 應(yīng)用
21.2.1 貨箱裝載
21.2.2 0/1背包問(wèn)題
21.2.3 最大完備子圖
21.2.4 旅行商問(wèn)題
21.2.5 電路板排列