【中國直郵】I READING愛閱讀 電腦科學叢書·資料結構、演算法與應用:C++語言描述(原書第2版)

編輯推薦

是享有盛譽的資料結構教科書的第2版。
它完整​​地包含了基本資料結構的內容，是CS2課程的理想用書。

內容簡介

《資料結構、演算法與應用－C++語言描述》是享有盛譽的資料結構教科書的第2版。它完整​​地包含了基本資料結構的內容，是CS2課程的理想用書。作者SartajSahni透過循循善誘的講解、直觀具體的討論和基於現實的應用，讓讀者輕鬆、愉快地學習。新版書著重利用標準範本庫(STL)，把書中發展的資料結構與演算法與對應的STL實作方法相互關聯。本書也增加了許多新的實例和練習題。
書中的應用實例是它的特色。 Sahni博士為每一個資料結構和演算法都提供了若干個應用實例，涉及排序、壓縮編碼和影像處理等多個面向。這些實例把概念和應用結合在一起，使理論與實踐統一，從而讓概念容易理解，使學生增加學習動機和興趣。
《電腦科學叢書·資料結構、演算法與應用：C++語言描述（原書第2版）》所採用的實用教學方法，不僅充實了理論概念，而且大量的習題讓學生有了實踐機會（書中有800多道練習題，包括理解題和簡單的程式設計題和工程設計題）。除此之外，本書的配套網站上包含書中的所有程式、範例資料、運行結果、部分練習的解答和帶有結果的範例測驗。

作者簡介

Sartaj Sahni ，佛羅裡達大學電腦與資訊科學工程系傑出教授，歐洲科學院院士，美國電機與電子工程師協會（IEEE）、美國電腦協會（ACM）、美國科學促進會（AAAS）和明尼蘇達超級電腦研究所的成員，坎普爾印度理工學院（ lIT）的傑出校友。 Sahni博士獲得1997年IEEE電腦分會的Taylor L Booth教育獎，2003年IEEE電腦分會的W． Wallace McDowell獎和2003年ACM的Karl Karlstrom傑出教育家獎。他目前也擔任ACM《Computing Surveys》期刊的總編輯，也是17位期刊編委會成員。他在坎普爾印度理工學院獲得電子工程學士學位，在康乃爾大學獲得電腦科學碩士和博士學位，並發表過250多篇論文，編寫了1 5本教科書，研究成果所涉及的領域包括有效演算法的設計與分析、平行計算、互聯網、自動化設計和醫用演算法。

目錄

Data Structures， Algorithms， and Applications in C++， Second Edition
出版者的話
譯者序
前言
第一部分預備知識
第1章C++回顧
1.1 引言
1.2 函數與參數
1.2.1 傳值參數
1.2.2 模板函數
1.2.3 引用參數
1.2.4 常數引用參數
1.2.5 返回值
1.2.6 重載函數
1.3 異常
1.3.1 拋出異常
1.3.2 處理異常
1.4 動態儲存空間分配
1.4.1 操作符new
1.4.2 一維數組
1.4.3 異常處理
1.4.4 操作符delete
1.4.5 二維數組
1.5 自有資料類型
1.5.1 類別currency
1.5.2 一種不同的描述方法
1.5.3 操作符重載
1.5.4 友元和保護性類別成員
1.5.5 增加#ifndef、#define和#endif語句
1.6 異常類illegalParameterValue
1.7 遞歸函數
1.7.1 遞歸的數學函數
1.7.2 歸納
1.7.3 C++遞迴函數
1.8 標準範本庫
1.9 測試與調試
1.9.1 什麼是測試
1.9.2 測試資料的設計
1.9.3 調試
1.10 參考及推薦讀物
第2章程序性能分析
2.1 什麼是程式效能
2.2 空間複雜度
2.2.1 空間複雜度的組成
2.2.2 舉例
2.3 時間複雜度
2.3.1 時間複雜度的組成
2.3.2 操作計數
2.3.3 最好、最壞和平均操作計數
2.3.4 步數
第3章漸近記法
3.1 引言
3.2 漸近記法
3.2.1 大Ο記法
3.2.2 漸近記法Ω和Θ
3.3 漸近數學（可選）
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 設計測試數據
4.4 實驗設計
4.5 高速緩存
4.5.1 簡單電腦模型
4.5.2 快取未命中對運行時間的影響
4.5.3 矩陣乘法
4.6 參考及推薦讀物

第二部分資料結構
第5章線性表—數組描述
5.1 資料對象和資料結構
5.2 線性表資料結構
5.2.1 抽象資料型態linearList
5.2.2 抽象類別linearList
5.3 數組描述
5.3.1 描述
5.3.2 變長一維數組
5.3.3 類別arrayList
5.3.4 C++迭代器
5.3.5 arrayList的迭代器
5.4 vector的描述
5.5 在一個陣列中實現的多重表
5.6 性能測量
5.7 參考及推薦讀物
第6章線性表—鍊式描述
6.1 單向鍊錶
6.1.1 描述
6.1.2 結構chainNode
6.1.3 類chain
6.1.4 抽象資料型態linearList的擴充
6.1.5 類extendedChain
6.1.6 性能測量
6.2 循環鍊錶和頭節點
6.3 雙向鍊錶
6.4 鍊錶用到的詞彙表
6.5 應用
6.5.1 箱子排序
6.5.2 基數排序
6.5.3 凸包
6.5.4 並查集
第7章數組和矩陣
7.1 數組
7.1.1 抽象資料類型
7.1.2 C++數組的索引
7.1.3 行主映射與列主映射
7.1.4 用陣列的陣列來描述
7.1.5 行主描述與列主描述
7.1.6 不規則二維數組
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 抽象資料類型
8.3 數組描述
8.3.1 作為一個派生類別實現
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 抽象資料類型
9.3 數組描述
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 抽象資料類型
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 散列函數和散列表
10.5.3 線性探查
10.5.4 鍊式散列
10.6 一個應用－文字壓縮
10.6.1 LZW壓縮
10.6.2 LZW壓縮的實現
10.6.3 LZW解壓縮
10.6.4 LZW解壓縮的實現
10.6.5 性能評價
10.7 參考及推薦讀物
第11章二元樹和其他樹
11.1 樹
11.2 二元樹
11.3 二元樹的特性
11.4 二元樹的描述
11.4.1 數組描述
11.4.2 鍊錶描述
11.5 二元樹常用操作
11.6 二元樹遍歷
11.7 抽象資料型別BinaryTree
11.8 類linkedBinaryTree
11.9 應用
11.9.1 設定訊號放大器
11.9.2 並查集
11.10 參考及推薦讀物
第12章優先權隊列
12.1 定義與應用
12.2 抽象資料類型
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 高度優先與寬度優先的最大及最小左高樹
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 抽象資料類型WinnerTree
13.3 贏家樹的實現
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 抽象資料類型
14.3 二元搜尋樹的操作與實現
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 箱子裝載問題的最適匹配法
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 實現細節的考量及複雜性分析
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 節點結構
15.5 參考及推薦讀物
第16章圖
16.1 基本概念
16.2 應用和更多的概念
16.3 特性
16.4 抽象資料型態graph
16.5 無權圖的描述
16.5.1 鄰接矩陣
16.5.2 鄰接鍊錶
16.5.3 鄰接數組
16.6 加權圖的描述
16.7 類實現
16.7.1 不同的類
16.7.2 鄰接矩陣類
16.7.3 擴充chain類
16.7.4 鍊錶類
16.8 圖的遍歷
16.8.1 廣度優先搜索
16.8.2 廣度優先搜尋的實現
16.8.3 方法graph：：bfs的複雜性分析
16.8.4 深度優先搜索
16.8.5 深度優先搜尋的實現
16.8.6 方法graph：：dfs的複雜性分析
16.9 應用
16.9.1 尋找一條路徑
16.9.2 連通圖及其構成
16.9.3 生成樹

第三部分演算法設計方法
第17章貪婪演算法
17.1 最優化問題
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章動態規劃
19.1 算法思想
19.2 應用
19.2.1 0/1背包問題
19.2.2 矩陣乘法鏈
19.2.3 所有頂點對之間的最短路徑
19.2.4 帶有負值的單源最短路徑
19.2.5 網組的無交叉子集
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 電路板排列

前言/序言

DataStructures，Algorithms，andApplicationsinC++，SecondEdition對資料結構和演算法的研究是電腦科學和工程的基礎。精通這方面的知識，對開發能夠有效利用電腦資源的程式是必不可少的。因此，所有電腦科學和工程專業都有一門或幾門課程專門用來講授這方面的內容。一般來說，第一門程式設計課程介紹資料結構和演算法的基礎知識（資料結構的堆疊和佇列，演算法的排序和矩陣運算）。第二門程式設計課程介紹資料結構和演算法的系統知識。隨後，可以對資料結構和演算法進行深入的研究，這通常需要一門或兩門課程。
電腦科學和工程的本科專業課程過多，已經迫使許多高等院校進行課程整合。例如，在佛羅裡達大學，給本科生只開設一學期的資料結構和演算法的課程。在學習本課程之前，請學生已經學過一學期的Java程式設計和離散數學。
本書既可以用於兩門或更多的專門研究資料結構和演算法的課程，也可以用於相關的綜合課程。全書共分三個部分。第一部分從第1章到第4章，旨在複習C++程式設計的概念以及程式效能的分析和測量方法。對於熟悉C語言程式設計的學生，透過學習第1章應該能夠過渡到C++。第1章雖然不是C++的入門知識，但依然包含了C++的一些基本概念，這些概念常令學生感到困惑，如參數傳遞、模板函數、動態存儲分配、遞歸、類別、繼承、異常的拋出和捕捉。第2章和第3章複習了程式性能的分析和測量方法－操作計數、執行步數和漸近符號（大O、Ω、Θ，小o）。第4章複習了程式效能的實驗測量方法，也簡要地討論了高速緩衝記憶體對運行時間測量的影響問題。第2章透過程式效能分析方法的應用，深入研究了在程式設計入門課程中遇到的典型的基礎性演算法：簡單的排序演算法（冒泡排序、選擇排序、插入排序和計數排序），順序搜尋，利用Horner法則進行多項式求值，矩陣運算（矩陣相加、矩陣轉置、矩陣相乘）。第3章研究了二分搜尋演算法。儘管第2章到第4章的主要目的是學習程式表現的分析和測量方法，但也讓學生精通了一組基本演算法。
本書第二部分從第5章到第16章，深入研究了資料結構。第5章和第6章分別研究了資料的陣列描述方法和指標（或稱鍊式）描述方法，建構起資料結構研究的架構。這兩章用這兩種資料描述方法來建立C++類，以描述線性表資料結構。我們透過實驗數據對不同的數據描述方法在描述線性表時的性能進行了比較。第二部分從第7章以後都是應用第5章和第6章的描述方法來描述其他的資料結構，如陣列和矩陣（第7章）、堆疊（第8章）、佇列（第9章）、字典（第10、14和15章）、二元樹（第11章）、優先權隊列（第12章）、競賽樹（第15章）和圖（第16章）。
本書在處理資料結構時，試圖做到與C++標準範本庫（STL）所使用的結構在相似性或同一性上保持相容。例如，第5章的線性表資料結構便是依照STL的類別vector的模式而建立的。本書通篇都利用了STL的函數，諸如copy、min和max，學生由此會熟悉這些函數。
本書第三部分從第17章到第21章，研究常用的演算法設計方法。這些方法有貪婪演算法（第17章）、分而治之演算法（第18章）、動態規劃（第19章）、回溯演算法（第20章）和分支定界演算法（第21章）。另外還包括兩種​​下限的證明（最小最大問題和排序問題）（18.4節）、機器調度的近似演算法（12.6.2節）、箱子裝載演算法（13.5節）和0/1背包問題（17.3.2節）。 12.6.2節也簡略介紹了NP-複雜問題。
本書的一個特色是強調應用。書中的每一種資料結構和演算法設計都透過多個應用實例來演示。通常每一章的最後一節都針對本章所介紹的資料結構或設計方法給予具體的應用。很多時候，在一章的前面幾節也包含一些應用實例。這些應用實例涉及多個面向－排序（冒泡排序、選擇排序、插入排序、計數排序、堆排序、歸併排序、快速排序、箱子排序、基數排序和拓樸排序）；矩陣運算（矩陣加法、矩陣轉置、矩陣乘法）；電路設計自動化（搜尋電路網組、電路佈線、元件折疊、開關盒佈線、設定訊號放大器、交叉分佈、電路板排列）；壓縮編碼（LZW壓縮、霍夫曼編碼）；計算幾何（凸包和最近點對）；模擬（工廠模擬）；影像處理（圖元標註）；趣味數學（漢諾塔、殘缺棋盤、迷宮老鼠）；調度（LPT調度）；最佳化（裝箱問題、貨箱裝載、0/1背包、矩陣乘法鏈）；統計（直方圖、尋找最大值和最小值、尋找第k個最小值）；圖論（生成樹、圖元、最短路徑、最大完備子圖、二分覆蓋和旅行商）。研究這些應用實例不需要學生具有相關領域的預備知識，因為本書包含了這些知識，而這些知識會提高學生的學習興趣。
我們希望透過把實際應用與資料結構和演算法設計方法的基礎研究緊密結合，能夠激發學生更大的專業興趣。學生透過完成本書和本書網站的800多道練習題，知識將會更加豐富和牢固。