本書共分三個部分。第一部分從第1章到第4章，旨在復習C++程序設計的概念以及程序性能的分析和測量方法。第二部分從第5章到第16章，研究數(shù)據(jù)結構，包括線性表、數(shù)組和矩陣、棧、隊列、字典、二叉樹、優(yōu)先級隊列、競賽樹、搜索樹和圖等。第三部分從第17章到第21章，研究常用算法，包括貪婪算法、分而治之算法、動態(tài)規(guī)劃、回溯算法和分枝定界算法。本書有800多道練習題和50多個應用實例。內(nèi)容廣博，組織合理，論述清晰，循序漸進，而且對程序性能的分析和測量系統(tǒng)入微。
DataStructures，Algorithms，andApplicationsinC++，SecondEdition對數(shù)據(jù)結構和算法的研究是計算機科學和工程的基礎。精通這方面的知識，對開發(fā)能夠有效利用計算機資源的程序是必不可少的。因此，所有計算機科學和工程專業(yè)都有一門或幾門課程專門用來講授這方面的內(nèi)容。一般來說，第一門程序設計課程介紹數(shù)據(jù)結構和算法的基礎知識（數(shù)據(jù)結構的棧和隊列，算法的排序和矩陣運算）。第二門程序設計課程介紹數(shù)據(jù)結構和算法的系統(tǒng)知識。隨后，可以對數(shù)據(jù)結構和算法進行深入的研究，這通常需要一門或兩門課程。
計算機科學和工程的本科專業(yè)課程過多，已經(jīng)迫使很多高等院校進行課程整合。例如，在佛羅里達大學，給本科生只開設一學期的數(shù)據(jù)結構和算法的課程。在學習本課程之前，要求學生已經(jīng)學過一學期的Java程序設計和離散數(shù)學。
本書既可以用于兩門或更多的專門研究數(shù)據(jù)結構和算法的課程，也可以用于相關的一門綜合課程。全書共分三個部分。第一部分從第1章到第4章，旨在復習C++程序設計的概念以及程序性能的分析和測量方法。對于熟悉C語言程序設計的學生，通過學習第1章應該能夠過渡到C++。第1章雖然不是C++的入門知識，但是依然包含了C++的一些基本概念，這些概念常令學生感到困惑，如參數(shù)傳遞、模板函數(shù)、動態(tài)存儲分配、遞歸、類、繼承、異常的拋出和捕捉。第2章和第3章復習了程序性能的分析和測量方法——操作計數(shù)、執(zhí)行步數(shù)和漸近符號（大O、Ω、Θ，小o）。第4章復習了程序性能的實驗測量方法，還簡要地討論了高速緩沖存儲器對運行時間測量的影響問題。第2章通過程序性能分析方法的應用，深入研究了在程序設計入門課程中遇到的典型的基礎性算法：簡單的排序算法（冒泡排序、選擇排序、插入排序和計數(shù)排序），順序搜索，利用Horner法則進行多項式求值，矩陣運算（矩陣相加、矩陣轉置、矩陣相乘）。第3章研究了二分搜索算法。盡管第2章到第4章的主要目的是學習程序性能的分析和測量方法，但是也讓學生精通了一組基本算法。
本書第二部分從第5章到第16章，深入研究了數(shù)據(jù)結構。第5章和第6章分別研究了數(shù)據(jù)的數(shù)組描述方法和指針（或鏈式）描述方法，構建起數(shù)據(jù)結構研究的框架。這兩章用這兩種數(shù)據(jù)描述方法來創(chuàng)建C++類，以描述線性表數(shù)據(jù)結構。我們通過實驗數(shù)據(jù)對不同的數(shù)據(jù)描述方法在描述線性表時的性能進行了比較。第二部分從第7章以后都是應用第5章和第6章的描述方法來描述其他的數(shù)據(jù)結構，如數(shù)組和矩陣（第7章）、棧（第8章）、隊列（第9章）、字典（第10、14和15章）、二叉樹（第11章）、優(yōu)先級隊列（第12章）、競賽樹（第15章）和圖（第16章）。
本書在處理數(shù)據(jù)結構時，試圖做到與C++標準模板庫（STL）所使用的結構在相似性或同一性上保持兼容。例如，第5章的線性表數(shù)據(jù)結構便是按照STL的類vector的模式而建立的。本書通篇都利用了STL的函數(shù)，諸如copy、min和max，學生由此會熟悉這些函數(shù)。
本書第三部分從第17章到第21章，研究常用的算法設計方法。這些方法有貪婪算法（第17章）、分而治之算法（第18章）、動態(tài)規(guī)劃（第19章）、回溯算法（第20章）和分支定界算法（第21章）。另外還包括兩種下限的證明（最小最大問題和排序問題）（18.4節(jié)）、機器調度的近似算法（12.6.2節(jié)）、箱子裝載算法（13.5節(jié)）和0/1背包問題（17.3.2節(jié)）。12.6.2節(jié)還簡略地介紹了NP-復雜問題。
本書的一個特色是強調應用。書中的每一種數(shù)據(jù)結構和算法設計都通過多個應用實例來演示。通常每一章的最后一節(jié)都針對本章介紹的數(shù)據(jù)結構或設計方法給出具體的應用。很多時候，在一章的前面幾節(jié)也包含一些應用實例。這些應用實例涉及多個方面——排序（冒泡排序、選擇排序、插入排序、計數(shù)排序、堆排序、歸并排序、快速排序、箱子排序、基數(shù)排序和拓撲排序）；矩陣運算（矩陣加法、矩陣轉置、矩陣乘法）；電路設計自動化（搜索電路網(wǎng)組、電路布線、元件折疊、開關盒布線、設置信號放大器、交叉分布、電路板排列）；壓縮編碼（LZW壓縮、霍夫曼編碼）；計算幾何（凸包和最近點對）；仿真（工廠仿真）；圖像處理（圖元標注）；趣味數(shù)學（漢諾塔、殘缺棋盤、迷宮老鼠）；調度（LPT調度）；優(yōu)化（裝箱問題、貨箱裝載、0/1背包、矩陣乘法鏈）；統(tǒng)計（直方圖、尋找最大值和最小值、尋找第k個最小值）；圖論（生成樹、圖元、最短路徑、最大完備子圖、二分覆蓋和旅行商）。研究這些應用實例不需要學生具有相關領域的預備知識，因為本書包含了這些知識，而且這些知識會提高學生的學習興趣。
我們希望通過把實際應用與數(shù)據(jù)結構和算法設計方法的基礎研究緊密結合，能夠激發(fā)學生更大的專業(yè)興趣。學生通過完成本書和本書網(wǎng)站的800多道練習題，知識將會更加豐富和牢固。
Sartaj Sahni，佛羅里達大學計算機與信息科學工程系杰出教授，歐洲科學院院士，美國電氣和電子工程師協(xié)會（IEEE）、美國計算機協(xié)會（ACM）、美國科學促進會（AAAS）和明尼蘇達超級計算機研究所的成員，坎普爾印度理工學院（ lIT）的杰出校友。Sahni博士獲得1997年IEEE計算機分會的Taylor L Booth教育獎，2003年IEEE計算機分會的W．Wallace McDowell獎和2003年ACM的Karl Karlstrom杰出教育家獎。他目前還擔任ACM《Computing Surveys》期刊的總編輯，還是17個期刊編委會成員。他在坎普爾印度理工學院獲得電子工程學士學位，在康奈爾大學獲得計算機科學碩士和博士學位，發(fā)表過250多篇論文，編寫了1 5本教科書，研究成果所涉及的領域包括有效算法的設計與分析、并行計算、互聯(lián)網(wǎng)、自動化設計和醫(yī)用算法。
Data Structures， Algorithms， and Applications in C++， Second Edition
出版者的話
譯者序
前言
第一部分 預備知識
第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 動態(tài)存儲空間分配
1.4.1 操作符new
1.4.2 一維數(shù)組
1.4.3 異常處理
1.4.4 操作符delete
1.4.5 二維數(shù)組
1.5 自有數(shù)據(jù)類型
1.5.1 類currency
1.5.2 一種不同的描述方法
1.5.3 操作符重載
1.5.4 友元和保護性類成員
1.5.5 增加#ifndef、#define和#endif語句
1.6 異常類illegalParameterValue
1.7 遞歸函數(shù)
1.7.1 遞歸的數(shù)學函數(shù)
1.7.2 歸納
1.7.3 C++遞歸函數(shù)
1.8 標準模板庫
1.9 測試與調試
1.9.1 什么是測試
1.9.2 測試數(shù)據(jù)的設計
1.9.3 調試
1.10 參考及推薦讀物
第2章 程序性能分析
2.1 什么是程序性能
2.2 空間復雜度
2.2.1 空間復雜度的組成
2.2.2 舉例
2.3 時間復雜度
2.3.1 時間復雜度的組成
2.3.2 操作計數(shù)
2.3.3 最好、最壞和平均操作計數(shù)
2.3.4 步數(shù)
第3章 漸近記法
3.1 引言
3.2 漸近記法
3.2.1 大Ο記法
3.2.2 漸近記法Ω和Θ
3.3 漸近數(shù)學（可選）
3.3.1 大O記法
3.3.2 Ω記法
3.3.3 Θ記法
3.3.4 小ο記法
3.3.5 特性
3.4 復雜度分析舉例
3.5 實際復雜度
3.6 參考及推薦讀物
第4章 性能測量
4.1 引言
4.2 選擇實例的大小
4.3 設計測試數(shù)據(jù)
4.4 實驗設計
4.5 高速緩存
4.5.1 簡單計算機模型
4.5.2 緩存未命中對運行時間的影響
4.5.3 矩陣乘法
4.6 參考及推薦讀物
第二部分 數(shù)據(jù)結構
第5章 線性表——數(shù)組描述
5.1 數(shù)據(jù)對象和數(shù)據(jù)結構
5.2 線性表數(shù)據(jù)結構
5.2.1 抽象數(shù)據(jù)類型linearList
5.2.2 抽象類linearList
5.3 數(shù)組描述
5.3.1 描述
5.3.2 變長一維數(shù)組
5.3.3 類arrayList
5.3.4 C++迭代器
5.3.5 arrayList的一個迭代器
5.4 vector的描述
5.5 在一個數(shù)組中實現(xiàn)的多重表
5.6 性能測量
5.7 參考及推薦讀物
第6章 線性表——鏈式描述
6.1 單向鏈表
6.1.1 描述
6.1.2 結構chainNode
6.1.3 類chain
6.1.4 抽象數(shù)據(jù)類型linearList的擴充
6.1.5 類extendedChain
6.1.6 性能測量
6.2 循環(huán)鏈表和頭節(jié)點
6.3 雙向鏈表
6.4 鏈表用到的詞匯表
6.5 應用
6.5.1 箱子排序
6.5.2 基數(shù)排序
6.5.3 凸包
6.5.4 并查集
第7章 數(shù)組和矩陣
7.1 數(shù)組
7.1.1 抽象數(shù)據(jù)類型
7.1.2 C++數(shù)組的索引
7.1.3 行主映射和列主映射
7.1.4 用數(shù)組的數(shù)組來描述
7.1.5 行主描述和列主描述
7.1.6 不規(guī)則二維數(shù)組
7.2 矩陣
7.2.1 定義和操作
7.2.2 類matrix
7.3 特殊矩陣
7.3.1 定義和應用
7.3.2 對角矩陣
7.3.3 三對角矩陣
7.3.4 三角矩陣
7.3.5 對稱矩陣
7.4 稀疏矩陣
7.4.1 基本概念
7.4.2 用單個線性表描述
7.4.3 用多個線性表描述
7.4.4 性能測量
第8章 棧
8.1 定義和應用
8.2 抽象數(shù)據(jù)類型
8.3 數(shù)組描述
8.3.1 作為一個派生類實現(xiàn)
8.3.2 類arrayStack
8.3.3 性能測量
8.4 鏈表描述
8.4.1 類derivedLinkedStack
8.4.2 類linkedStack
8.4.3 性能測量
8.5 應用
8.5.1 括號匹配
8.5.2 漢諾塔
8.5.3 列車車廂重排
8.5.4 開關盒布線
8.5.5 離線等價類問題
8.5.6 迷宮老鼠
8.6 參考及推薦讀物
第9章 隊列
9.1 定義和應用
9.2 抽象數(shù)據(jù)類型
9.3 數(shù)組描述
9.3.1 描述
9.3.2 類arrayQueue
9.4 鏈表描述
9.5 應用
9.5.1 列車車廂重排
9.5.2 電路布線
9.5.3 圖元識別
9.5.4 工廠仿真
9.6 參考及推薦讀物
第10章 跳表和散列
10.1 字典
10.2 抽象數(shù)據(jù)類型
10.3 線性表描述
10.4 跳表表示（可選）
10.4.1 理想情況
10.4.2 插入和刪除
10.4.3 級的分配
10.4.4 結構skipNode
10.4.5 類skipList
10.4.6 skipList方法的復雜度
10.5 散列表描述
10.5.1 理想散列
10.5.2 散列函數(shù)和散列表
10.5.3 線性探查
10.5.4 鏈式散列
10.6 一個應用——文本壓縮
10.6.1 LZW壓縮
10.6.2 LZW壓縮的實現(xiàn)
10.6.3 LZW解壓縮
10.6.4 LZW解壓縮的實現(xiàn)
10.6.5 性能評價
10.7 參考及推薦讀物
第11章 二叉樹和其他樹
11.1 樹
11.2 二叉樹
11.3 二叉樹的特性
11.4 二叉樹的描述
11.4.1 數(shù)組描述
11.4.2 鏈表描述
11.5 二叉樹常用操作
11.6 二叉樹遍歷
11.7 抽象數(shù)據(jù)類型BinaryTree
11.8 類linkedBinaryTree
11.9 應用
11.9.1 設置信號放大器
11.9.2 并查集
11.10 參考及推薦讀物
第12章 優(yōu)先級隊列
12.1 定義和應用
12.2 抽象數(shù)據(jù)類型
12.3 線性表
12.4 堆
12.4.1 定義
12.4.2 大根堆的插入
12.4.3 大根堆的刪除
12.4.4 大根堆的初始化
12.4.5 類maxHeap
12.4.6 堆和STL
12.5 左高樹
12.5.1 高度優(yōu)先與寬度優(yōu)先的最大及最小左高樹
12.5.2 最大HBLT的插入
12.5.3 最大HBLT的刪除
12.5.4 兩棵最大HBLT的合并
12.5.5 初始化
12.5.6 類maxHblt
12.6 應用
12.6.1 堆排序
12.6.2 機器調度
12.6.3 霍夫曼編碼
12.7 參考及推薦讀物
第13章 競賽樹
13.1 贏者樹和應用
13.2 抽象數(shù)據(jù)類型WinnerTree
13.3 贏者樹的實現(xiàn)
13.3.1 表示
13.3.2 贏者樹的初始化
13.3.3 重新組織比賽
13.3.4 類completeWinnerTree
13.4 輸者樹
13.5 應用
13.5.1 用最先適配法求解箱子裝載問題
13.5.2 用相鄰適配法求解箱子裝載問題
13.6 參考及推薦讀物
第14章 搜索樹
14.1 定義
14.1.1 二叉搜索樹
14.1.2 索引二叉搜索樹
14.2 抽象數(shù)據(jù)類型
14.3 二叉搜索樹的操作和實現(xiàn)
14.3.1 類binarySearchTree
14.3.2 搜索
14.3.3 插入
14.3.4 刪除
14.3.5 二叉搜索樹的高度
14.4 帶有相同關鍵字元素的二叉搜索樹
14.5 索引二叉搜索樹
14.6 應用
14.6.1 直方圖
14.6.2 箱子裝載問題的最優(yōu)匹配法
14.6.3 交叉分布
第15章 平衡搜索樹
15.1 AVL樹
15.1.1 定義
15.1.2 AVL樹的高度
15.1.3 AVL樹的描述
15.1.4 AVL搜索樹的搜索
15.1.5 AVL搜索樹的插入
15.1.6 AVL搜索樹的刪除
15.2 紅-黑樹
15.2.1 基本概念
15.2.2 紅-黑樹的描述
15.2.3 紅-黑樹的搜索
15.2.4 紅-黑樹的插入
15.2.5 紅-黑樹的刪除
15.2.6 實現(xiàn)細節(jié)的考慮及復雜性分析
15.3 分裂樹
15.3.1 介紹
15.3.2 分裂樹的操作
15.3.3 折算復雜性
15.4 B-樹
15.4.1 索引順序訪問方法
15.4.2 m叉搜索樹
15.4.3 m階B-樹
15.4.4 B-樹的高度
15.4.5 B-樹的搜索
15.4.6 B-樹的插入
15.4.7 B-樹的刪除
15.4.8 節(jié)點結構
15.5 參考及推薦讀物
第16章 圖
16.1 基本概念
16.2 應用和更多的概念
16.3 特性
16.4 抽象數(shù)據(jù)類型graph
16.5 無權圖的描述
16.5.1 鄰接矩陣
16.5.2 鄰接鏈表
16.5.3 鄰接數(shù)組
16.6 加權圖的描述
16.7 類實現(xiàn)
16.7.1 不同的類
16.7.2 鄰接矩陣類
16.7.3 擴充chain類
16.7.4 鏈表類
16.8 圖的遍歷
16.8.1 廣度優(yōu)先搜索
16.8.2 廣度優(yōu)先搜索的實現(xiàn)
16.8.3 方法graph：：bfs的復雜性分析
16.8.4 深度優(yōu)先搜索
16.8.5 深度優(yōu)先搜索的實現(xiàn)
16.8.6 方法graph：：dfs的復雜性分析
16.9 應用
16.9.1 尋找一條路徑
16.9.2 連通圖及其構成
16.9.3 生成樹
第三部分 算法設計方法
第17章 貪婪算法
17.1 最優(yōu)化問題
17.2 貪婪算法思想
17.3 應用
17.3.1 貨箱裝載
17.3.2 0/1背包問題
17.3.3 拓撲排序
17.3.4 二分覆蓋
17.3.5 單源最短路徑
17.3.6 最小成本生成樹
17.4 參考及推薦讀物
第18章 分而治之
18.1 算法思想
18.2 應用
18.2.1 殘缺棋盤
18.2.2 歸并排序
18.2.3 快速排序
18.2.4 選擇
18.2.5 相距最近的點對
18.3 解遞歸方程
18.4 復雜度的下限
18.4.1 最小最大問題的下限
18.4.2 排序算法的下限
第19章 動態(tài)規(guī)劃
19.1 算法思想
19.2 應用
19.2.1 0/1背包問題
19.2.2 矩陣乘法鏈
19.2.3 所有頂點對之間的最短路徑
19.2.4 帶有負值的單源最短路徑
19.2.5 網(wǎng)組的無交叉子集
19.3 參考及推薦讀物
第20章 回溯法
20.1 算法思想
20.2 應用
20.2.1 貨箱裝載
20.2.2 0/1背包問題
20.2.3 最大完備子圖
20.2.4 旅行商問題
20.2.5 電路板排列
第21章 分支定界
21.1 算法思想
21.2 應用
21.2.1 貨箱裝載
21.2.2 0/1背包問題
21.2.3 最大完備子圖
21.2.4 旅行商問題
21.2.5 電路板排列
書單推薦
