圖書簡介
數據結構（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.2k後繼問題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
