數據結構

數據結構（STL框架）

普通高等教育“十一五”國家級規劃教材、國家精品課程主講教材

作者：王曉東

定價：34.80元

印次：1-2

ISBN：9787302203933

出版日期：2009.09.01

印刷日期：2011.01.17

本書以ACM和IEEE/CS Computing Curricula 2005課程體系以及教育部計算機科學與技術教學指導委員會發布的“高等學校計算機科學與技術本科專業規範”中制定的關於數據結構和演演算法設計與分析的知識結構和體系為依據，以基本數據結構和抽象數據類型為知識單元而編寫。本書一個明顯的特色是在STL (Standard Template Library）框架下描述數據結構的設計思想和實現方法，使讀者循序漸進地理解數據抽象，面向對象設計方法和泛型演演算法設計三位一體的面向高層次的現代化軟體設計風格。全書共分16章，涵蓋 CC2005 課程體系中有關演演算法與數據結構、知識結構和體系的重要內容，包括演演算法與數據結構引論、向量、雙端隊列、表、棧和隊列、排序與選擇、樹、二叉搜索樹、平衡搜索樹、集合、映射、堆與優先隊列、散列、並查集、圖與相關演演算法。

本書可作為高等學校計算機、電子信息、信息與計算科學、信息管理與信息系統等專業數據結構課程教材，也適合工程技術人員和自學者學習參考。

第1章 演演算法與數據結構引論1

1.1 演演算法及其複雜性的概念1

1.1.1 演演算法與程序1

1.1.2 演演算法複雜性的概念1

1.1.3 演演算法複雜性的漸近性態2

1.2 數據結構與抽象數據類型3

1.3 用C++描述數據結構與演演算法4

1.3.1 指針和引用4

1.3.2 函數與參數傳遞4

1.3.3 C++的類5

1.3.4 類的對象6

1.3.5 模板6

1.3.6 動態存儲分配7

1.4 遞歸8

1.5 標準模板庫STL與泛型演演算法9

1.5.1 STL概述9

1.5.2 容器10

1.5.3 迭代器10

1.5.4 泛型演演算法11

1.5.5 函數對象14

1.6 應用舉例19

1.6.1 用C++的類實現抽象數據類型19

1.6.2 順序搜索與二分搜索演演算法的設計與分析23

1.6.3 遞歸演演算法的設計與分析25

習題126

數據結構與演演算法實驗127

數據結構與演演算法實驗題1.1 實係數復變多項式問題27

數據結構與演演算法實驗題1.2 平面幾何問題28

數據結構與演演算法實驗題1.3 m進位數問題29

第2章 向量30

2.1 向量的基本概念30

2.2 抽象數據類型向量30

2.3 向量的迭代器30

2.4 向量的實現方法31

2.5 矩陣與多維向量35

2.6 高精度整數36

2.7 應用舉例47

2.7.1 搜索公共元素問題47

2.7.2 同色方塊識別問題48

2.7.3 全排列問題49

習題249

數據結構與演演算法實驗250

數據結構與演演算法實驗題2.1 前綴與後綴和問題50

數據結構與演演算法實驗題2.2投票選舉問題50

數據結構與演演算法實驗題2.3穩定婚姻問題51

數據結構與演演算法實驗題2.4凸多邊形的三角剖分問題52

目錄數據結構(STL框架)第3章雙端隊列53

3.1雙端隊列的基本概念53

3.2抽象數據類型雙端隊列53

3.3雙端隊列的實現方法54

3.4雙端隊列的迭代器60

3.5應用舉例62

3.5.1雙端隊列的簡單應用62

3.5.2簡單多邊形的凸殼問題63

習題365

數據結構與演演算法實驗365

數據結構與演演算法實驗題3.1排隊購票問題65

數據結構與演演算法實驗題3.2循環向量的極值問題66

第4章線性表68

4.1表的基本概念68

4.2用數組實現表69

4.3用指針實現表73

4.3.1用指針實現單鏈表的方法73

4.3.2單鏈表的迭代器75

4.4用間接定址方法實現表79

4.4.1間接定址方法的基本思想79

4.4.2間接定址表的迭代器82

4.5用游標實現表84

4.5.1用游標實現表的基本思想84

4.5.2游標實現的表的迭代器89

4.6循環鏈表90

4.6.1實現單循環鏈表的基本思想90

4.6.2單循環鏈表的迭代器92

4.7雙鏈表94

4.7.1實現雙向循環鏈表的基本思想94

4.7.2雙向循環鏈表的迭代器97

4.8應用舉例101

4.8.1多項式函數101

4.8.2Josephus排列問題106

習題4107

數據結構與演演算法實驗4108

數據結構與演演算法實驗題4.1實係數一元多項式問題108

數據結構與演演算法實驗題4.2Josephus排列問題1109

數據結構與演演算法實驗題4.3向量分類問題110

數據結構與演演算法實驗題4.4條形圖輪廓問題110

數據結構與演演算法實驗題4.5Josephus排列問題2111

第5章棧113

5.1棧的基本概念113

5.2棧的實現方法114

5.3應用舉例115

5.3.1等價類劃分問題115

5.3.2模擬遞歸問題117

5.3.3電路板布線問題119

習題5121

數據結構與演演算法實驗5121

數據結構與演演算法實驗題5.1車皮編序問題121

數據結構與演演算法實驗題5.2單柱Hanoi塔問題122

數據結構與演演算法實驗題5.3多棧模擬問題123

數據結構與演演算法實驗題5.4親兄弟問題124

第6章隊列125

6.1隊列的基本概念125

6.2隊列的實現方法125

6.3應用舉例126

6.3.1最優電路布線問題126

6.3.2和諧簡訊問題129

習題6130

數據結構與演演算法實驗6130

數據結構與演演算法實驗題6.1組隊列問題130

數據結構與演演算法實驗題6.2雙棧隊列問題131

數據結構與演演算法實驗題6.3猴子分桃問題132

數據結構與演演算法實驗題6.4逆序表問題132

第7章排序與選擇134

7.1簡單排序演演算法134

7.1.1冒泡排序演演算法134

7.1.2插入排序演演算法135

7.1.3選擇排序演演算法136

7.1.4簡單排序演演算法的計算複雜性136

7.2快速排序演演算法137

7.2.1演演算法基本思想及實現137

7.2.2演演算法性能分析139

7.2.3隨機快速排序演演算法139

7.3合併排序演演算法140

7.3.1演演算法基本思想及實現140

7.3.2消除遞歸141

7.3.3自然合併排序演演算法141

7.4鏈表排序與索引排序演演算法142

7.4.1鏈表排序演演算法142

7.4.2索引排序演演算法149

7.5線性時間排序演演算法151

7.5.1計數排序演演算法151

7.5.2桶排序演演算法152

7.6中位數與第k小元素152

7.6.1平均情況下的線性時間選擇演演算法153

7.6.2最壞情況下的線性時間選擇演演算法154

7.7泛型排序演演算法156

7.7.1排序演演算法的泛化方法156

7.7.2泛型合併排序演演算法158

7.7.3泛型快速排序演演算法159

7.7.4泛型選擇演演算法160

7.8應用舉例161

7.8.1區間覆蓋問題161

7.8.2輸油管道問題161

習題7162

數據結構與演演算法實驗7163

數據結構與演演算法實驗題7.1交換排序問題163

數據結構與演演算法實驗題7.2DNA排序問題163

數據結構與演演算法實驗題7.3郵局選址問題164

數據結構與演演算法實驗題7.4最優服務次序問題165

第8章樹166

8.1樹的定義166

8.2樹的遍歷168

8.3樹的表示法170

8.3.1父結點數組表示法170

8.3.2兒子鏈表表示法170

8.3.3左兒子右兄弟表示法171

8.4二叉樹的基本概念171

8.5二叉樹的運算173

8.6二叉樹的實現174

8.6.1二叉樹的順序存儲結構174

8.6.2二叉樹的結點度表示法175

8.6.3用指針實現二叉樹176

8.7線索二叉樹179

8.8應用舉例--信號增強裝置布局問題181

習題8184

數據結構與演演算法實驗8185

數據結構與演演算法實驗題8.1層序列表問題185

數據結構與演演算法實驗題8.2最近公共祖先問題186

數據結構與演演算法實驗題8.3子樹問題187

數據結構與演演算法實驗題8.4同構二叉樹問題187

數據結構與演演算法實驗題8.5後序中序遍歷問題188

第9章二叉搜索樹189

9.1有序集與二叉搜索樹189

9.1.1抽象數據類型字典189

9.1.2用數組實現字典189

9.1.3二叉搜索樹的基本概念190

9.2實現二叉搜索樹190

9.3二叉搜索樹的迭代器199

9.4二叉搜索樹的效率205

9.5應用舉例--條形圖統計問題207

習題9209

數據結構與演演算法實驗9209

數據結構與演演算法實驗題9.1裝箱問題209

數據結構與演演算法實驗題9.2電路板連線問題210

數據結構與演演算法實驗題9.3字典問題211

第10章平衡搜索樹212

10.1紅黑樹212

10.1.1紅黑樹的定義和性質212

10.1.2旋轉變換213

10.1.3紅黑樹的插入運算與重平衡216

10.1.4紅黑樹的刪除運算與重平衡218

10.2AVL樹223

10.2.1AVL樹的定義和性質223

10.2.2AVL樹的插入運算與重平衡224

10.2.3AVL樹的刪除運算與重平衡226

10.3應用舉例229

10.3.1條形圖統計問題229

10.3.2動態選擇問題230

10.3.3Josephus排列問題232

習題10233

數據結構與演演算法實驗10234

數據結構與演演算法實驗題10.1逆序計數問題234

數據結構與演演算法實驗題10.2k後繼問題234

數據結構與演演算法實驗題10.3圓內相交弦問題235

數據結構與演演算法實驗題10.4最小間隙問題236

數據結構與演演算法實驗題10.5圖形周長問題237

數據結構與演演算法實驗題10.6動態選擇問題237

第11章集合239

11.1集合的基本概念239

11.2用位向量實現集合240

11.3用平衡二叉搜索樹實現集合246

11.3.1直接應用紅黑樹實現集合246

11.3.2平衡二叉搜索樹的泛化247

11.3.3符合STL標準的集合252

11.4多重集合254

11.5泛型集合運算256

11.6應用舉例259

11.6.1Eratosthenes篩法259

11.6.2子集和問題260

11.6.3拼寫檢查問題260

11.6.4軟體產品資料庫問題261

習題11262

數據結構與演演算法實驗11263

數據結構與演演算法實驗題11.1半數集問題263

數據結構與演演算法實驗題11.2賬單支付問題263

數據結構與演演算法實驗題11.3張貼海報問題264

數據結構與演演算法實驗題11.4三色棋遊戲問題265

第12章映射266

12.1映射的基本概念266

12.2用平衡二叉搜索樹實現映射266

12.2.1二叉搜索樹的進一步泛化266

12.2.2符合STL標準的映射272

12.3多重映射274

12.4應用舉例275

12.4.1種群分佈統計問題275

12.4.2電子字典問題276

習題12278

數據結構與演演算法實驗12278

數據結構與演演算法實驗題12.1工作薪酬問題278

數據結構與演演算法實驗題12.2撲克遊戲智能分析問題279

數據結構與演演算法實驗題12.3最優行駛路線問題280

數據結構與演演算法實驗題12.4庫存調整問題281

數據結構與演演算法實驗題12.5雙字元字頻分析問題282

數據結構與演演算法實驗題12.6英文辭彙分析問題283

第13章散列285

13.1符號表285

13.2開散列286

13.3閉散列292

13.4散列函數的效率297

13.5重新散列298

13.6散列集299

13.6.1用散列表實現集合299

13.6.2用散列表實現多重集合300

13.7散列映射301

13.7.1開散列表的泛化301

13.7.2用散列表實現映射307

13.7.3用散列表實現多重映射308

13.8應用舉例309

13.8.1字元串頻率統計問題309

13.8.2拼寫檢查問題310

13.8.3種群分佈統計問題311

13.8.4電子字典問題312

習題13313

數據結構與演演算法實驗13313

數據結構與演演算法實驗題13.1偽隨機排列問題313

數據結構與演演算法實驗題13.2字元串散列問題314

數據結構與演演算法實驗題13.3英文文本分析問題314

數據結構與演演算法實驗題13.4最長模式串問題315

第14章堆與優先隊列316

14.1優先隊列的基本概念316

14.2優先順序樹和堆316

14.3堆的順序存儲方式317

14.4堆的有關演演算法318

14.5堆的泛型演演算法323

14.6用堆實現優先隊列326

14.7可並優先隊列327

14.7.1左偏樹的定義327

14.7.2用左偏樹實現可並優先隊列328

14.7.3泛化左偏樹331

14.8應用舉例332

14.8.1優先隊列的比較模式332

14.8.2哈夫曼編碼問題334

14.8.3活動安排問題337

習題14338

數據結構與演演算法實驗14338

數據結構與演演算法實驗題14.1區間相交問題338

數據結構與演演算法實驗題14.2整數字典問題338

數據結構與演演算法實驗題14.3最小權語言問題339

數據結構與演演算法實驗題14.4二叉搜索堆問題339

數據結構與演演算法實驗題14.5區間覆蓋問題340

數據結構與演演算法實驗題14.6批作業調度問題341

第15章並查集342

15.1並查集的基本概念342

15.2用父結點向量實現並查集343

15.3應用舉例--離線最小值問題346

習題15347

數據結構與演演算法實驗15348

數據結構與演演算法實驗題15.1二進位方程問題348

數據結構與演演算法實驗題15.2網路連通問題349

數據結構與演演算法實驗題15.3朋友問題349

數據結構與演演算法實驗題15.4等價類劃分問題350

第16章圖352

16.1圖的基本概念352

16.2抽象數據類型圖355

16.3圖的表示法355

16.3.1鄰接矩陣表示法355

16.3.2鄰接表表示法356

16.3.3緊縮鄰接表356

16.4用鄰接矩陣實現圖357

16.4.1用鄰接矩陣實現圖的方法357

16.4.2鄰接矩陣圖的頂點迭代器359