數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用：C++語(yǔ)言描述

譯者序
前言
第一部分 預(yù)備知識(shí)
第1章C++程序設(shè)計(jì)
1.1 引言
1.2 函數(shù)與參數(shù)
1.2.1 傳值參數(shù)
1.2.2 模板函數(shù)
1.2.3 引用參數(shù)
1.2.4 常鎮(zhèn)引用參數(shù)
1.2.5 返問(wèn)值
1.2.6 遞歸函數(shù)
1.3 動(dòng)態(tài)存儲(chǔ)分配
1.3.1 操作符new
1.3.2 一維數(shù)組
1.3.3 異常處理
1.3.4操作符delete
1.3.5 二維數(shù)組
1.4 類
1.4.1 類Currency
1.4.2 使用不同的描述方法
1.4.3 操作符重載
1.4.4 引發(fā)異常
1.4.5 友元和保護(hù)共成員
1.4.6 增加＃ifnde和,＃define和＃endif語(yǔ)句
1.5 測(cè)試與調(diào)試
1.5.1 什么是測(cè)試問(wèn)
1.5.2 設(shè)計(jì)測(cè)試數(shù)據(jù)
1.5.3 調(diào)試
1.6 參考及推薦讀物
第 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 執(zhí)行步數(shù)
2.4 漸進(jìn)符號(hào)
2.4.1 大寫符號(hào)
2.4.2 Q符號(hào)
2.4.3 O符號(hào)
2.4.4 小寫O符號(hào)
2.4.5 特性
2.4.6 復(fù)雜性分析舉例
2.5 實(shí)際復(fù)雜性
2.6 性能測(cè)量
2.6.1 選擇實(shí)例的大小
2.6.2 設(shè)計(jì)測(cè)試數(shù)據(jù)
2.6.3 進(jìn)行實(shí)驗(yàn)
2.7 參考及推薦讀物
第二部分 數(shù)據(jù)結(jié)構(gòu)
第 3章數(shù)據(jù)描述
3.1 引言
3.2 線性表
3.3 公式化描述
3.3.1 基本概念
3.3.2 異常類NoMem
3.3.3 操作
3.3.4 評(píng)價(jià)
3.4 鏈表描述
3.4.1 類ChainNode和Chain
3.4.2 操作
3.4.3 擴(kuò)充類Chain
3.4.4 鏈表遍歷器類
3.4.5 循環(huán)鏈表
3.4.6 與公式化描述方法的比較
3.4.7 雙向鏈表
3.4.8 小結(jié)
3.5 間接尋址
3.5.1 基本概念
3.5.2 操作
3.6 模擬指針
3.6.1 Simspace的操作
3.6.2 采用模擬指針的鏈表
3.7 描述方法的比較
3.8 應(yīng)用
3.8.1 箱子排序
3.8.2 基數(shù)排序
3.8.3 等價(jià)類
3.8.4 凸包
3.9 參考及推薦讀物
第4章數(shù)組和矩陣
4.1 數(shù)組
4.1.1 抽象數(shù)據(jù)類型
4.1.2 C++數(shù)組
4.1.3 行主映射和列主映射
4.1.4 類ArraylD
4.1.5 類Array2D
4.2 矩陣
4.2.1 定義和操作
4.2.2 類Matrix
4.3 特殊矩陣
4.3.1 定義和應(yīng)用
4.3.2 對(duì)角矩陣
4.3.3 三對(duì)角矩陣
4.3.4 三角矩陣
4.3.5 對(duì)稱矩陣
4.4 稀疏矩陣
4.4.1 基本概念
4.4.2 數(shù)組描述
4.4.3 鏈表描述
第5章堆錢
5.1 抽象數(shù)據(jù)類型
5.2 派生類和繼承
5.3 公式化描述
5.3I Stack的效率
5.3.2 自定義Stack
5.4 鏈表描述
5.5 應(yīng)用
5.5.1 括號(hào)匹配
5.5.2 漢諾塔
55.3 火車車廂重排
5.5.4 開(kāi)關(guān)盒布線
5.5.5 離線等價(jià)類問(wèn)題
5.5.6 迷宮老鼠
5.6 參考及推薦讀物
第6章隊(duì)列
6.1 抽象數(shù)據(jù)類型
6.2 公式化描述
6.3 鏈表描述
6.4 應(yīng)用
6.4.1 火車車廂重排
6.4.2 電路布線
6.4.3 識(shí)別圖元
6.4.4 工廠仿真
6.5 參考及推薦讀物
第7章跳表和散列
7.1 字典
7.2節(jié)線性表描述
7.3 跳表描述
7.3.1 理想情況
7.3.2 插入和刪除
7.3.3 級(jí)的分配
7.3.4 類skipNode
7.3.5 類SkipLISt
7.3.6 復(fù)雜性
7.4 散殞表描述
7.4.1 理想散列
7.4.2 線性開(kāi)型尋址散到
7.4.3 鏈大散列
7.5 應(yīng)用——文本壓縮
7.5.1 LZW壓縮
7.5.2 LZW壓縮的實(shí)現(xiàn)
7.5.3 LZW解壓縮
7.5.4 LZW解壓縮的實(shí)現(xiàn)
7.6 參考及推薦讀物
第8章二叉樹(shù)和其他樹(shù)
8.1 樹(shù)
8.2 二叉樹(shù)
8.3 二叉樹(shù)的特性
8.4 二叉樹(shù)描述
8.4.1 公式化描述
8.4.2 鏈表描述
8.5 二叉樹(shù)常用操作
8.6 二叉樹(shù)遍歷
8.7 抽象數(shù)據(jù)類型BlnaryTree
8.8 類BinaryTree
8.9 抽象數(shù)據(jù)類型及類的擴(kuò)充
8.9.1 輸出
8.9.2 刪除
8.9.3 計(jì)算高度
8.9.4 統(tǒng)計(jì)節(jié)點(diǎn)數(shù)
8.10 應(yīng)用
8.10.1 設(shè)置信號(hào)放大器
8.10.2 在線等價(jià)類
8.11 參考及推薦讀物
第9章優(yōu)先隊(duì)列
9.1 引言
9.2 線性表
9.3 堆
9.3.1 定義
9.3.2 最大堆的插入
9.3.3 最大堆的刪除
9.3.4 最大堆的初始化
9.3.5 類MaxHeap
9.4 左高樹(shù)
9.4.1 高度與寬度優(yōu)先的最大及最小左高樹(shù)
9.4.2 最大HBLT的插入
9.4.3 最大HBLT的刪除
9.4.4 合并兩棵最大HBLT
9.4.5 初始化最大HBLT
9.4.6 類MaxHBLT
9.5 應(yīng)用
9.5.1 堆排序
9.5.2 機(jī)器調(diào)度
9.5.3 霍夫曼編碼
9.6 參考及推薦讀物
第10章競(jìng)賽樹(shù)
10.1 引言
10.2 抽象數(shù)據(jù)類型WinnerTree
10.3 類WnnerTree
10.3.1 定義
10.3.2 類定義
10.3.3 構(gòu)造函數(shù)析構(gòu)國(guó)數(shù)及Wuuer函數(shù)
10.3.4 初始化贏者樹(shù)
10.3.5 重新組織比賽
10.4 輸者樹(shù)
10.5 應(yīng)用
10.5.1 用最先匹配法求解箱子裝載問(wèn)題
10.5.2 用相鄰匹配法求解箱子裝載問(wèn)題
第11章搜索樹(shù)
11.1 二叉搜索樹(shù)
11.1.1 基本概念
11.1.2 抽象數(shù)據(jù)類型BSTree和IndexedBSTree
11.1.3 類BSTree
11.1.4 搜索
11.1.5 插入
11.1.6 刪除
11.1.7 類DBSTree
11.1.8 二叉搜索樹(shù)的高度
11.2 AVL樹(shù)
11.2.1 基本概念
11.2.2 AVL樹(shù)的高度
11.2.3 AVL樹(shù)的描述
11.2.4 AVL搜索樹(shù)的搜索
11.2.5 AVL搜索樹(shù)的插入
11.2.6 AVL搜索樹(shù)的刪除
11.3 紅一黑樹(shù)
11.3.1 基本概念
11.3.2 紅一黑樹(shù)的描述
11.3.3 紅一黑樹(shù)的搜索
11.3.4 紅一黑樹(shù)的插入
11.3.5 紅一黑樹(shù)的刪除
11.3.6 實(shí)現(xiàn)細(xì)節(jié)的考慮及復(fù)雜性分析
11.4 B一樹(shù)
11.4.1 索引順序訪問(wèn)方法
11.4.2 m叉搜索樹(shù)
11.4.3 m序B一樹(shù)
11.4.4 B一樹(shù)的高度
11.4.5 B一樹(shù)的搜索
11.4.6 B一樹(shù)的插入
11.4.7 B一樹(shù)的刪除
11.4.8 節(jié)點(diǎn)結(jié)構(gòu)
11.5 應(yīng)用
11.5.1 直方圖
11.5.2 用最優(yōu)匹配法求解箱子裝載問(wèn)題
11.5.3 交叉分布
11.6 參考及推薦讀物
第12章圖
12.1 基本概念
12.2 應(yīng)用
12.3有盡有特性
12.4 抽象數(shù)據(jù)類型GraPh和DlgraPh
12.5 無(wú)向圖和有向圖的描述
12.5.1 鄰接矩陣
12.5.2 鄰接壓縮表
12.5.3 鄰接鏈表
12.6 網(wǎng)絡(luò)描述
12.7 類定義
12.7.1 不同的類
12.7.2 鄰接矩陣類
12.7.3 擴(kuò)充Chain類
12.7.4 類LinkedBase
12.7.5 鏈接類
12.8 圖的遍歷
12.8.1 基本概念
12.8.2 鄰接矩陣的遍歷函數(shù)
12.8.3 鄰接鏈表的遍歷函數(shù)
12.9 語(yǔ)言特性
12.9.1 虛函數(shù)和多態(tài)性
12.9.2 純虛函數(shù)和抽象類
12.9.3 虛基類
12.9.4 抽象類和抽象數(shù)據(jù)類型
12.10 圖的搜索算法
12.10.1寬度優(yōu)先搜索
12.10.2 類Network
12.10.3 BFS的實(shí)現(xiàn)
12.10.4 BFS的復(fù)雜性分析
12.10.5 深度優(yōu)先搜索
12.11 應(yīng)用
12.11.1 尋找路徑
12.11.2 連通圖及其構(gòu)件
12.11.3生成樹(shù)
第三部分 算法設(shè)計(jì)方法
第13章 貪婪算法
13.1 最優(yōu)化問(wèn)題
13.2 算法思想
13.3 應(yīng)用
13.3.1 貨箱裝船
13.3.2 0/昔背包問(wèn)題
13.3.3 拓?fù)渑判?br />13.3.4 二分覆蓋
13.3.5 單源最短路徑
13.3.6 最小耗費(fèi)生成樹(shù)
13.4 參考及推薦讀物
第 14章分而治之算法
14.1 算法思想
14.2 應(yīng)用
14.2.1 殘缺棋盤
14.2.2 歸并排序
14.2.3 快速排序
14.2.4 選擇
14.2.5距離最近的點(diǎn)對(duì)
14.3 解遞歸方程
14.4 復(fù)雜性的下限
14.4.1 最小最大問(wèn)題的下限
14.4.2 排序算法的下限
第 15章動(dòng)態(tài)規(guī)劃
15.1 算法思想
15.2 應(yīng)用
15.2.1 0/l背包問(wèn)題
15.2.2 圖像壓縮
15.2.3 矩陣乘法鏈
15.2.4 最短路徑
15.2.5 網(wǎng)絡(luò)的無(wú)交叉子集
15.2.6 元件折疊
15.3 參考及推薦讀物
第 16章回溯
16.1 算法思想
16.2 應(yīng)用
16.2.1 貨箱裝船
16.2.2 0/1背包問(wèn)題
16.2.3 最大完備子圖
16.2.4 旅行商問(wèn)題
16.2.5 電路板排列
第17章分枝定界
17.1 算法思想
17.2 應(yīng)用
17.2.1 貨箱裝船
17.2.2 0/1背包問(wèn)題
17.2.3 最大完備子圖
17.2.4 旅行商問(wèn)題
17.2.5 電路板排列