程序設(shè)計(jì)中實(shí)用的數(shù)據(jù)結(jié)構(gòu)

定　價(jià)：￥59.00

作　者：	王建德，吳永輝著
出版社：	人民郵電出版社
叢編項(xiàng)：
標(biāo)　簽：	計(jì)算機(jī)理論

購(gòu)買這本書(shū)可以去

ISBN：	9787115268655	出版時(shí)間：	2012-01-01	包裝：	平裝
開(kāi)本：	16開(kāi)	頁(yè)數(shù)：	369	字?jǐn)?shù)：

內(nèi)容簡(jiǎn)介

　　本書(shū)對(duì)近年來(lái)程序設(shè)計(jì)教育和競(jìng)賽培訓(xùn)活動(dòng)中涌現(xiàn)的許多實(shí)用的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)方法進(jìn)行了全面總結(jié)，通過(guò)深入的分析和生動(dòng)的實(shí)例引導(dǎo)讀者尋找問(wèn)題中各對(duì)象之間的關(guān)系，確定數(shù)學(xué)模型所使用的邏輯結(jié)構(gòu)；實(shí)現(xiàn)對(duì)各個(gè)對(duì)象的操作，即確定數(shù)據(jù)所采用的存儲(chǔ)結(jié)構(gòu)；將數(shù)據(jù)類型與定義在該類型上的運(yùn)算融于一體，為面向?qū)ο蟮某绦蛟O(shè)計(jì)方法奠定基礎(chǔ)。本書(shū)既是大學(xué)計(jì)算機(jī)專業(yè)數(shù)據(jù)結(jié)構(gòu)課程和算法設(shè)計(jì)課程的優(yōu)秀參考書(shū)，也是大中學(xué)生程序設(shè)計(jì)競(jìng)賽不可多得的培訓(xùn)教材。本書(shū)特色按照數(shù)據(jù)結(jié)構(gòu)的知識(shí)體系，全書(shū)分為“線性表”、“樹(shù)型問(wèn)題”和“圖型問(wèn)題”三篇，介紹了幾十種存儲(chǔ)方式和相應(yīng)的算法。介紹了許多實(shí)用的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)方法，同時(shí)引導(dǎo)讀者盡可能采用“揚(yáng)長(zhǎng)避短”的選擇原則和“取長(zhǎng)補(bǔ)短”的結(jié)合方法，選擇有利于提升算法效率的數(shù)據(jù)結(jié)構(gòu)。對(duì)每個(gè)比較難懂的概念都舉實(shí)例加以說(shuō)明，對(duì)每個(gè)比較抽象的定理都有具體的應(yīng)用例證幫助理解，對(duì)每個(gè)經(jīng)典算法都有清晰的程序流程給予示范。此外，還大量運(yùn)用圖表，使得概念、定理和算法的由來(lái)變得具體、形象和直觀。書(shū)中采用了一種結(jié)構(gòu)清晰、移植性強(qiáng)且貼近自然語(yǔ)言表述的類程序設(shè)計(jì)語(yǔ)言。只要讀者具備Pascal和C等任一種語(yǔ)言的基礎(chǔ)，就可以比較輕松地讀懂其語(yǔ)義。

作者簡(jiǎn)介

　　王建德國(guó)務(wù)院特殊津貼專家、上海師范大學(xué)特聘教授、控江中學(xué)特級(jí)教師。他輔導(dǎo)學(xué)生在國(guó)際奧林匹克信息學(xué)競(jìng)賽（IOI）中獲8金、4銀、2銅，先后出版了《新編實(shí)用算法分析與程序設(shè)計(jì)》和《程序設(shè)計(jì)中常用的計(jì)算思維方式》等多本廣受好評(píng)的圖書(shū)，這些圖書(shū)長(zhǎng)期以來(lái)是國(guó)內(nèi)各類程序設(shè)計(jì)競(jìng)賽的必備教程。吳永輝博士，復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)與工程系副教授，ACM-ICPC中國(guó)賽區(qū)指導(dǎo)委員會(huì)成員，復(fù)旦大學(xué)ACM程序設(shè)計(jì)競(jìng)賽隊(duì)教練。自2001年起連續(xù)帶隊(duì)進(jìn)入ACM-ICPC世界總決賽，并取得過(guò)世界第六名的佳績(jī)。主要研究方向?yàn)閿?shù)據(jù)庫(kù)，在《計(jì)算機(jī)研究與發(fā)展》、《軟件學(xué)報(bào)》以及重大學(xué)術(shù)會(huì)議上發(fā)表過(guò)多篇論文，參與翻譯的著作有《數(shù)據(jù)通信與網(wǎng)絡(luò)》和《數(shù)據(jù)通信、計(jì)算機(jī)網(wǎng)絡(luò)與開(kāi)放系統(tǒng)》。

圖書(shū)目錄

上篇討論線性表
第1 章數(shù)組　　 3
1.1 數(shù)組的基本概念　　 3
1.1.1 數(shù)組是一種順序存儲(chǔ)結(jié)構(gòu)　　 3
1.1.2 數(shù)組是程序設(shè)計(jì)中使用頻率最高的數(shù)據(jù)類型　　 4
1.2 優(yōu)化數(shù)組的存儲(chǔ)方式　　 6
1.2.1 規(guī)則矩陣的壓縮存儲(chǔ)　　 6
1.2.2 稀疏矩陣的壓縮存儲(chǔ)　　 7
1.2.3 01 矩陣的壓縮存儲(chǔ)　　11
1.3 排序與順序統(tǒng)計(jì)　　 14
1.3.1 排序的基本概念　　 14
1.3.2 計(jì)數(shù)排序與貪心策略　　 15
1.3.3 采用“二分”策略的排序方法　　 21
1.3.4 順序統(tǒng)計(jì)的基本方法　　 28
第2 章鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)　　 34
2.1 鏈表的基本概念　　 34
2.1.1 單鏈表　　 34
2.1.2 循環(huán)鏈表　　 35
2.1.3 雙向鏈表　　 35
2.2 鏈表的基本運(yùn)算　　 35
2.2.1 構(gòu)建單鏈表　　 36
2.2.2 插入操作　　 36
2.2.3 刪除操作　　 36
2.2.4 讀取操作　　 36
2.3 鏈表的應(yīng)用　　 37
第3 章兩種存取方式特殊的線性表　　 43
3.1 “后進(jìn)先出”的棧　　 43
3.1.1 棧的基本運(yùn)算　　43
3.1.2 棧的應(yīng)用　　44
3.2 “先進(jìn)先出”的隊(duì)列　　52
3.2.1 隊(duì)列的基本運(yùn)算　　52
3.2.2 隊(duì)列的應(yīng)用　　54
第4 章散列技術(shù)　　59
4.1 散列表　　59
4.2 散列函數(shù)的設(shè)計(jì)　　59
4.3 消除沖突的基本方法　　61
4.3.1 使用開(kāi)放尋址法消除沖突　　61
4.3.2 使用分離鏈接法消除沖突　　67
第5 章后綴數(shù)組　　71
5.1 后綴數(shù)組的基本概念　　71
5.2 采用倍增算法求解rank 數(shù)組　　73
5.3 利用rank 數(shù)組計(jì)算最長(zhǎng)公共前綴　　74
5.3.1 計(jì)算最長(zhǎng)公共前綴是一個(gè)典型的RMQ 問(wèn)題　　75
5.3.2 計(jì)算最長(zhǎng)公共前綴的基本方法　　75
5.4 后綴數(shù)組的應(yīng)用　　78
5.4.1 利用后綴數(shù)組處理單個(gè)字符串　　78
5.4.2 兩個(gè)字符串的公共子串問(wèn)題　　87
5.4.3 多個(gè)字符串共享子串的問(wèn)題　　90
上篇小結(jié)　　97
中篇討論樹(shù)型問(wèn)題
第6 章樹(shù)的基本概念和遍歷規(guī)則　　101
6.1 樹(shù)的遞歸定義　　101
6.2 節(jié)點(diǎn)的分類　　101
6.3 有關(guān)度的定義　　 101
6.4 樹(shù)的深度（高度）　　 102
6.5 森林　　 102
6.6 有序樹(shù)和無(wú)序樹(shù)　　 102
6.7 樹(shù)的表示方法　　 103
6.8 樹(shù)的遍歷規(guī)則　　 103
6.8.1 先根次序遍歷樹(shù)　　 103
6.8.2 后根次序遍歷樹(shù)　　 104
第7 章樹(shù)的存儲(chǔ)結(jié)構(gòu)　　105
7.1 采用數(shù)組存儲(chǔ)入邊信息　　 105
7.1.1 存儲(chǔ)無(wú)權(quán)樹(shù)的入邊信息　　 105
7.1.2 存儲(chǔ)加權(quán)樹(shù)的入邊信息　　 106
7.2 采用數(shù)組存儲(chǔ)所有兒子的地址信息　　 108
7.2.1 采用整數(shù)存儲(chǔ)兒子的數(shù)組下標(biāo)　　 108
7.2.2 采用指針存儲(chǔ)兒子的地址　　 109
7.3 采用鄰接表存儲(chǔ)出邊信息　　 110
7.3.1 采用數(shù)組存儲(chǔ)方式的鄰接表　　 110
7.3.2 采用單鏈表存儲(chǔ)方式的鄰接表　　 114
7.4 無(wú)根樹(shù)的一般存儲(chǔ)方式　　 116
第8 章二叉樹(shù)　　123
8.1 二叉樹(shù)的基本概念和存儲(chǔ)結(jié)構(gòu)　　 123
8.1.1 二叉樹(shù)的基本概念　　 123
8.1.2 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)　　 125
8.2 將普通有序樹(shù)和森林轉(zhuǎn)換成對(duì)應(yīng)的二叉樹(shù)　　128
8.2.1 將普通有序樹(shù)轉(zhuǎn)換成對(duì)應(yīng)的二叉樹(shù)　　 128
8.2.2 將普通有序樹(shù)組成的森林轉(zhuǎn)換成對(duì)應(yīng)的二叉樹(shù)　　 129
8.3 二叉樹(shù)的遍歷　　 130
8.3.1 前序遍歷　　 130
8.3.2 中序遍歷　　 130
8.3.3 后序遍歷　　 131
8.3.4 由兩種遍歷確定二叉樹(shù)結(jié)構(gòu)　　 133
第9 章并查集　　135
9.1 并查集的基本概念　　 135
9.2 查找元素所在樹(shù)的根節(jié)點(diǎn)并進(jìn)行路徑壓縮　　 137
9.3 合并兩個(gè)元素所在的集合　　138
第10 章堆　　143
10.1 二叉堆的概念　　 143
10.2 在插入或刪除節(jié)點(diǎn)時(shí)維護(hù)堆性質(zhì)　　 144
10.2.1 插入節(jié)點(diǎn)　　 144
10.2.2 刪除最小值元素　　 144
10.3 建堆　　 145
10.4 堆排序　　 146
第11 章最優(yōu)二叉樹(shù)　　 154
11.1 最優(yōu)二叉樹(shù)的基本概念　　 154
11.2 構(gòu)造最優(yōu)二叉樹(shù)　　 155
第12 章線段樹(shù)　　160
12.1 線段樹(shù)的基本概念　　 160
12.1.1 用于區(qū)間運(yùn)算的線段樹(shù)　　 160
12.1.2 用于數(shù)據(jù)統(tǒng)計(jì)的線段樹(shù)　　 161
12.1.3 線段樹(shù)的數(shù)據(jù)結(jié)構(gòu)　　 162
12.2 線段樹(shù)的基本操作　　 162
12.2.1 建立線段樹(shù)　　 162
12.2.2 在區(qū)間內(nèi)插入線段或數(shù)據(jù)　　 163
12.2.3 刪除區(qū)間內(nèi)的線段或數(shù)據(jù)　　 164
12.2.4 計(jì)算區(qū)間內(nèi)的線段或數(shù)據(jù)狀態(tài)　　 165
12.3 線段樹(shù)在靜態(tài)統(tǒng)計(jì)問(wèn)題上的應(yīng)用　　 165
12.4 線段樹(shù)在動(dòng)態(tài)統(tǒng)計(jì)問(wèn)題上的應(yīng)用　　 168
第13 章二叉查找樹(shù)　　 176
13.1 二叉排序樹(shù)　　 176
13.1.1 二叉排序樹(shù)的基本概念　　 176
13.1.2 二叉排序樹(shù)的基本操作　　 177
13.2 靜態(tài)二叉排序樹(shù)　　 180
13.2.1 靜態(tài)二叉排序樹(shù)的特征　　 180
13.2.2 靜態(tài)二叉排序樹(shù)的構(gòu)造方法　　 180
13.2.3 在靜態(tài)二叉排序樹(shù)上進(jìn)行數(shù)據(jù)統(tǒng)計(jì)　　　 181
13.3 子樹(shù)大小平衡樹(shù)（SBT）　　 186
13.3.1 SBT 的性質(zhì)　　 186
13.3.2 旋轉(zhuǎn)　　 186
13.3.3 動(dòng)態(tài)維護(hù)SBT 的平衡特性　　 191
13.3.4 SBT 的基本操作　　 196
中篇小結(jié)　　 205
下篇討論圖型問(wèn)題
第14 章圖的基本概念及其存儲(chǔ)結(jié)構(gòu)　　 209
14.1 圖的基本概念　　 209
14.2 圖的簡(jiǎn)單分類　　 211
14.2.1 無(wú)向圖和有向圖　　 212
14.2.2 無(wú)權(quán)圖和加權(quán)圖　　 212
14.2.3 稀疏圖和稠密圖　　 212
14.2.4 完全圖和補(bǔ)圖　　 212
14.2.5 樹(shù)和森林　　 213
14.2.6 圖的生成樹(shù)和生成森林　　 213
14.2.7 平面圖　　 214
14.2.8 二分圖　　 214
14.2.9 相交圖和區(qū)間圖　　 214
14.3 圖的存儲(chǔ)結(jié)構(gòu)　　 215
14.3.1 存儲(chǔ)節(jié)點(diǎn)間相鄰關(guān)系的相鄰矩陣　　 215
14.3.2 存儲(chǔ)邊信息的3 種數(shù)據(jù)結(jié)構(gòu)　　 217
第15 章圖的遍歷及其應(yīng)用　　 220
15.1 廣度優(yōu)先遍歷（BFS 算法）　　 220
15.1.1 BFS 算法的基本概念　　 220
15.1.2 BFS 算法的應(yīng)用　　 222
15.2 深度優(yōu)先遍歷（DFS 算法）　　 233
15.2.1 DFS 的基本概念　　 233
15.2.2 在DFS 遍歷過(guò)程中記錄節(jié)點(diǎn)顏色變化的時(shí)間　　 239
15.2.3 根據(jù)節(jié)點(diǎn)顏色對(duì)邊進(jìn)行分類　　 240
15.2.4 分析DFS 森林的結(jié)構(gòu)　　 242
15.2.5 使用DFS 算法進(jìn)行拓?fù)渑判颉　?244
15.2.6 使用DFS 算法計(jì)算歐拉回路　　 248
第16 章有向圖的強(qiáng)連通分量和傳遞閉包　　255
16.1 判定仙人掌圖　　255
16.2 計(jì)算強(qiáng)連通分量　　259
16.3 傳遞閉包的應(yīng)用　　266
第17 章無(wú)向圖的連通性分析　　271
17.1 計(jì)算節(jié)點(diǎn)的low 函數(shù)　　271
17.2 計(jì)算連通圖的割點(diǎn)和橋　　272
17.2.1 計(jì)算連通圖的割點(diǎn)　　272
17.2.2 計(jì)算連通圖的橋　　273
17.3 計(jì)算雙連通子圖　　275
17.4 分析連通圖的連通程度　　276
17.4.1 連通圖的頂連通度　　277
17.4.2 連通圖的邊連通度　　278
第18 章最小生成樹(shù)　　279
18.1 基本概念　　279
18.2 最小生成樹(shù)的應(yīng)用價(jià)值　　279
18.3 最小生成樹(shù)的計(jì)算策略　　281
18.4 計(jì)算最小生成樹(shù)的兩種算法　　281
18.4.1 Kruskal 算法　　282
18.4.2 Prim 算法　　283
18.5 最小生成樹(shù)算法的應(yīng)用實(shí)例　　285
第19 章加權(quán)圖的單源最短路徑問(wèn)題　　293
19.1 基本概念　　293
19.1.1 單源算法是高效解決所有最短路徑問(wèn)題的基礎(chǔ)　　293
19.1.2 負(fù)權(quán)回路影響單源最短路徑的計(jì)算　　294
19.1.3 松弛技術(shù)是單源算法的核心　　295
19.2 求解單源最短路徑問(wèn)題的3 種算法　　296
19.2.1 Dijkstra 算法　　296
19.2.2 Bellman-Ford 算法　　298
19.2.3 SPFA 算法　　299
19.3 單源最短路徑算法的應(yīng)用實(shí)例　　301
第20 章二分圖的匹配問(wèn)題　　310
20.1 基本概念　　310
20.1.1 圖的匹配概念　　 310
20.1.2 二分圖的概念和判定方法　　 311
20.2 計(jì)算無(wú)權(quán)二分圖的最大匹配　　 315
20.2.1 匈牙利算法的基本思路　　316
20.2.2 匈牙利算法的基本流程　　316
20.2.3 匈牙利算法的應(yīng)用實(shí)例　　317
20.3 計(jì)算帶權(quán)二分圖的最佳匹配　　 320
20.3.1 最佳匹配的概念　　 320
20.3.2 KM算法的基本思路　　 321
20.3.3 KM算法的基本流程和應(yīng)用實(shí)例　　 323
第21 章最大流問(wèn)題　　327
21.1 基本概念　　 327
21.2 在可增廣路徑的基礎(chǔ)上計(jì)算最大流　　 329
21.2.1 可增廣路徑的基本概念　　 329
21.2.2 基于最大流定理上的最大流算法　　 334
21.3 按層次計(jì)算最大流的Dinic 算法　　 334
21.3.1 Dinic 算法的基本思路　　 334
21.3.2 Dinic 算法的基本流程　　 335
21.4 利用最大流最小割定理解題　　 339
21.4.1 割的概念　　 339
21.4.2 最小割的計(jì)算方法和應(yīng)用實(shí)例　　 340
21.5 計(jì)算多源多匯網(wǎng)絡(luò)的可行流　　 346
21.6 網(wǎng)絡(luò)增加容量下界因素后的流量計(jì)算問(wèn)題　　 348
21.6.1 求容量有上下界的網(wǎng)絡(luò)的最大流　　 348
21.6.2 求容量有上下界的網(wǎng)絡(luò)的最小流　　 353
21.7 網(wǎng)絡(luò)增加費(fèi)用因素后的流量計(jì)算問(wèn)題　　 358
21.7.1 計(jì)算最小費(fèi)用最大流　　 359
21.7.2 計(jì)算容量有上下界的網(wǎng)絡(luò)的最小費(fèi)用最小流　　 364
下篇小結(jié)　　 370