數據結構與算法分析

《數據結構與算法分析》是2007年人民郵電出版社出版的一本圖書，作者是Mark Allen Weiss。

基本介紹

• 書名：數據結構與算法分析
• 作者：Mark Allen Weiss
• 原版名稱：Data Structures and Algorithm Analysis
• ISBN：9787115139238
• 定價：49.00元
• 出版社：人民郵電出版社
• 出版時間：2007年
• 開本：16開

圖書簡介

《數據結構與算法分析C++描述>（第3版）是數據結構和算法分析的經典教材，書中使用主流的程式設計語言C++作為具體的實現語言。書的內容包括表、棧、佇列、樹、散列表、優先佇列、排序、不相交集算法、圖論算法、算法分析、算法設計、攤還分析、查找樹算法、k-d樹和配對堆等。

內容簡介

《數據結構與算法分析C++描述》(第3版)適合作為計算機相關專業本科生的數據結構課程和研究生算法分析課程的教材。本科生的數據結構課程可以使用本書第1章～第9章，多學時課程還可以講解第10章；研究生算法分析課程可以使用第6章～第12章。

作品目錄

第1章　引論

1.1　本書討論的內容

1.2　數學知識複習

1.2.1　指數

1.2.2　對數

1.2.3　級數

1.2.4　模運算

1.2.5　證明方法

1.3　遞歸的簡單介紹

1.4　C++類

1.4.1　基本class語法

1.4.2　特別的構造函式語法與訪問函式

1.4.3　接口與實現的分離

1.4.4　vector和string

1.5　C++細節

1.5.1　指針

1.5.2　參數傳遞

1.5.3　返回值傳遞

1.5.4　引用變數

1.5.5　三大函式：析構函式、複製構造函式和operator=

1.5.6　C風格的數組和字元串

1.6　模板

1.6.1　函式模板

1.6.2　類模板

1.6.3　Object、Comparable和例子

1.6.4　函式對象

1.6.5　類模板的分離編譯

1.7　使用矩陣

1.7.1　數據成員、構造函式和基本訪問函式

1.7.2　operator[]

1.7.3　析構函式、複製賦值和複製構造函式

小結

練習

參考文獻

第2章　算法分析

2.1　數學基礎

2.2　模型

2.3　要分析的問題

2.4　運行時間計算

2.4.1　一個簡單的例子

2.4.2　一般法則

2.4.3　最大子序列和問題的解

2.4.4　運行時間中的對數

2.4.5　檢驗你的分析

2.4.6　分析結果的準確性

小結

練習

參考文獻

第3章　表、棧和佇列

3.1　抽象數據類型(ADT)

3.2　表ADT

3.2.1　表的簡單數組實現

3.2.2　簡單鍊表

3.3　STL中的向量和表

3.3.1　疊代器

3.3.2　示例：對表使用erase

3.3.3　const_iterator

3.4　向量的實現

3.5　表的實現

3.6　棧ADT

3.6.1　棧模型

3.6.2　棧的實現

3.6.3　套用

3.7　佇列ADT

3.7.1　佇列模型

3.7.2　佇列的數組實現

3.7.3　佇列的套用

小結

練習

第4章　樹

4.1　預備知識

4.1.1　樹的實現

4.1.2　樹的遍歷及套用

4.2　二叉樹

4.2.1　實現

4.2.2　一個例子——表達式樹

4.3　查找樹ADT——二叉查找樹

4.3.1　contains

4.3.2　findMin和findMax

4.3.3　insert

4.3.4　remove

4.3.5　析構函式和複製賦值操作符

4.3.6　平均情況分析

4.4　AVL樹

4.4.1　單旋轉

4.4.2　雙旋轉

4.5　伸展樹

4.5.1　一個簡單的想法(不能直接使用)

4.5.2　伸展

4.6　樹的遍歷

4.7　B樹

4.8　標準庫中的set和map

4.8.1　set

4.8.2　map

4.8.3　set和map的實現

4.8.4　使用幾個map的例子

小結

練習

參考文獻

第5章　散列

5.1　基本思想

5.2　散列函式

5.3　分離連結法

5.4　不使用鍊表的散列表

5.4.1　線性探測

5.4.2　平方探測

5.4.3　雙散列

5.5　再散列

5.6　標準庫中的散列表

5.7　可擴散列

小結

練習

參考文獻

第6章　優先佇列(堆)

6.1　模型

6.2　一些簡單的實現

6.3　二叉堆

6.3.1　結構性質

6.3.2　堆序性質

6.3.3　基本的堆操作

6.3.4　堆的其他操作

6.4　優先佇列的套用

6.4.1　選擇問題

6.4.2　事件模擬

6.5　d堆

6.6　左式堆

6.6.1　左式堆性質

6.6.2　左式堆操作

6.7　斜堆

6.8　二項佇列

6.8.1　二項佇列結構

6.8.2　二項佇列操作

6.8.3　二項佇列的實現

6.9　標準庫中的優先佇列

小結

練習

參考文獻

第7章　排序

7.1　預備知識

7.2　插入排序

7.2.1　算法

7.2.2　插入排序的STL實現

7.2.3　插入排序的分析

7.3　一些簡單排序算法的下界

7.4　謝爾排序

7.5　堆排序

7.6　歸併排序

7.7　快速排序

7.7.1　選取樞紐元

7.7.2　分割策略

7.7.3　小數組

7.7.4　實際的快速排序例程

7.7.5　快速排序的分析

7.7.6　選擇問題的線性期望時間算法

7.8　間接排序

7.8.1　vector<Comparable*>不運行

7.8.2　智慧型指針類

7.8.3　重載operator<

7.8.4　使用“*”解引用指針

7.8.5　重載類型轉換操作符

7.8.6　隨處可見的隱式類型轉換

7.8.7　雙向隱式類型轉換會導致歧義

7.8.8　指針減法是合法的

7.9　排序算法的一般下界

7.10　桶排序

7.11　外部排序

7.11.1　為什麼需要新算法

7.11.2　外部排序模型

7.11.3　簡單算法

7.11.4　多路合併

7.11.5　多相合併

7.11.6　替換選擇

小結

練習

參考文獻

第8章　不相交集類

8.1　等價關係

8.2　動態等價性問題

8.3　基本數據結構

8.4　靈巧求並算法

8.5　路徑壓縮

8.6　按秩求並和路徑壓縮的最壞情形

8.7　一個套用

小結

練習

參考文獻

第9章　圖論算法

9.1　若干定義

9.2　拓撲排序

9.3　最短路徑算法

9.3.1　無權最短路徑

9.3.2　Dijkstra算法

9.3.3　具有負邊值的圖

9.3.4　無環圖

9.3.5　所有頂點對的最短路徑

9.3.6　最短路徑舉例

9.4　網路流問題

9.5　最小生成樹

9.5.1　Prim算法

9.5.2　Kruskal算法

9.6　深度優先搜尋的套用

9.6.1　無向圖

9.6.2　雙連通性

9.6.3　歐拉迴路

9.6.4　有向圖

9.6.5　查找強分支

9.7　NP完全性介紹

9.7.1　難與易

9.7.2　NP類

9.7.3　NP完全問題

小結

練習

參考文獻

第10章　算法設計技巧

10.1　貪心算法

10.1.1　一個簡單的調度問題

10.1.2　赫夫曼編碼

10.1.3　近似裝箱問題

10.2　分治算法

10.2.1　分治算法的運行時間

10.2.2　最近點問題

10.2.3　選擇問題

10.2.4　一些算術問題的理論改進

10.3　動態規劃

10.3.1　用表代替遞歸

10.3.2　矩陣乘法的順序安排

10.3.3　最優二叉查找樹

10.3.4　所有點對最短路徑

10.4　隨機化算法

10.4.1　隨機數生成器

10.4.2　跳躍表

10.4.3　素性測試

10.5　回溯算法

10.5.1　公路收費點重建問題

10.5.2　博弈

小結

練習

參考文獻

第11章　攤還分析

11.1　一個無關的智力問題

11.2　二項佇列

11.3　斜堆

11.4　斐波那契堆

11.4.1　切除左式堆中的結點

11.4.2　二項佇列的懶惰合併

11.4.3　斐波那契堆操作

11.4.4　時間界的證明

11.5　伸展樹

小結

練習

參考文獻

第12章　高級數據結構及其實現

12.1　自頂向下伸展樹

12.2　紅黑樹

12.2.1　自底向上插入

12.2.2　自頂向下紅黑樹

12.2.3　自頂向下刪除

12.3　確定性跳躍表

12.4　AA樹

12.5　treap樹

12.6　k-d樹

12.7　配對堆

小結

練習

參考文獻

附錄　類模板的分離編譯

索引

作者簡介

MarkAllenWeiss，1987年在普林斯頓大學獲得計算機科學博士學位，師從著名算法大師RobertSedgewick，現任美國佛羅里達國際大學計算與信息科學學院教授。他曾經擔任全美AP（AdvancedPlacement）考試計算機學科委員會的主席（2000-2004）。他的主要研究方向是數據結構，算法和教育學。