程式設計中實用的數據結構

程式設計中實用的數據結構

《程式設計中實用的數據結構》是人民郵電出版社2014年出版的一部書。 該書按照數據結構知識的分類,以線性表、樹型問題和圖型問題為基本構件,介紹了幾十種存儲方式和相應算法,同時深入淺出地分析和證明了每一種存儲方式和算法的套用場合和效率,引導讀者儘可能選擇有利於提升算法效率的數據結構。

內容簡介

《程式設計中實用的數據結構》既可以作為大專院校計算機專業數據結構或算法類課程的教材,亦可以作為大學生和中學生程式設計競賽活動的培訓教程,還可以作為計算機軟體研發的參考資料。

作者簡介

王建德 國務院特殊津貼專家、上海師範大學特聘教授、控江中學特級教師。他輔導學生在國際奧林匹克信息學競賽(IOI)中獲8金、4銀、2銅,先後出版了《新編實 用算法分析與程式設計》和《程式設計中常用的計算思維方式》等多本廣受好評的圖書,這些圖書長期以來是國內各類程式設計競賽的必備教程。

吳 永輝 博士,復旦大學計算機科學與工程系副教授,ACM-ICPC中國賽區指導委員會成員,復旦大學ACM程式設計競賽隊教練。自2001年起連續帶隊進入 ACM-ICPC世界總決賽,並取得過世界第六名的佳績。主要研究方向為資料庫,在《計算機研究與發展》、《軟體學報》以及重大學術會議上發表過多篇論 文,參與翻譯的著作有《數據通信與網路》和《數據通信、計算機網路與開放系統》。

圖書目錄

《程式設計中實用的數據結構》

上篇 討論線性表

第1 章 數組  3

1.1 數組的基本概念  3

1.1.1 數組是一種順序存儲結構  3

1.1.2 數組是程式設計中使用頻率最高的數據類型  4

1.2 最佳化數組的存儲方式  6

1.2.1 規則矩陣的壓縮存儲  6

1.2.2 稀疏矩陣的壓縮存儲  7

1.2.3 01 矩陣的壓縮存儲 11

1.3 排序與順序統計  14

1.3.1 排序的基本概念  14

1.3.2 計數排序與貪心策略  15

1.3.3 採用“二分”策略的排序方法  21

1.3.4 順序統計的基本方法  28

第2 章 鏈式存儲結構  34

2.1 鍊表的基本概念  34

2.1.1 單鍊表  34

2.1.2 循環鍊表  35

2.1.3 雙向鍊表  35

.2.2 鍊表的基本運算  35

2.2.1 構建單鍊表  36

2.2.2 插入操作  36

2.2.3 刪除操作  36

2.2.4 讀取操作  36

2.3 鍊表的套用  37

第3 章 兩種存取方式特殊的線性表  43

3.1 “後進先出”的棧  43

3.1.1 棧的基本運算 43

3.1.2 棧的套用 44

3.2 “先進先出”的佇列 52

3.2.1 佇列的基本運算 52

3.2.2 佇列的套用 54

第4 章 散列技術 59

4.1 散列表 59

4.2 散列函式的設計 59

4.3 消除衝突的基本方法 61

4.3.1 使用開放定址法消除衝突 61

4.3.2 使用分離連結法消除衝突 67

第5 章 後綴數組 71

5.1 後綴數組的基本概念 71

5.2 採用倍增算法求解rank 數組 73

5.3 利用rank 數組計算最長公共前綴 74

5.3.1 計算最長公共前綴是一個典型的rmq 問題 75

5.3.2 計算最長公共前綴的基本方法 75

5.4 後綴數組的套用 78

5.4.1 利用後綴數組處理單個字元串 78

5.4.2 兩個字元串的公共子串問題 87

5.4.3 多個字元串共享子串的問題 90

上篇 小結 97

中篇 討論樹型問題

第6 章 樹的基本概念和遍歷規則 101

6.1 樹的遞歸定義 101

6.2 節點的分類 101

6.3 有關度的定義  101

6.4 樹的深度(高度)  102

6.5 森林  102

6.6 有序樹和無序樹  102

6.7 樹的表示方法  103

6.8 樹的遍歷規則  103

6.8.1 先根次序遍歷樹  103

6.8.2 後根次序遍歷樹  104

第7 章 樹的存儲結構 105

7.1 採用數組存儲入邊信息  105

7.1.1 存儲無權樹的入邊信息  105

7.1.2 存儲加權樹的入邊信息  106

7.2 採用數組存儲所有兒子的地址信息  108

7.2.1 採用整數存儲兒子的數組下標  108

7.2.2 採用指針存儲兒子的地址  109

7.3 採用鄰接表存儲出邊信息  110

7.3.1 採用數組存儲方式的鄰接表  110

7.3.2 採用單鍊表存儲方式的鄰接表  114

7.4 無根樹的一般存儲方式  116

第8 章 二叉樹 123

8.1 二叉樹的基本概念和存儲結構  123

8.1.1 二叉樹的基本概念  123

8.1.2 二叉樹的存儲結構  125

8.2 將普通有序樹和森林轉換成對應的二叉樹 128

8.2.1 將普通有序樹轉換成對應的二叉樹  128

8.2.2 將普通有序樹組成的森林轉換成對應的二叉樹  129

8.3 二叉樹的遍歷  130

8.3.1 前序遍歷  130

8.3.2 中序遍歷  130

8.3.3 後序遍歷  131

8.3.4 由兩種遍歷確定二叉樹結構  133

第9 章 並查集 135

9.1 並查集的基本概念  135

9.2 查找元素所在樹的根節點並進行路徑壓縮  137

9.3 合併兩個元素所在的集合 138

第10 章 堆 143

10.1 二叉堆的概念  143

10.2 在插入或刪除節點時維護堆性質  144

10.2.1 插入節點  144

10.2.2 刪除最小值元素  144

10.3 建堆  145

10.4 堆排序  146

第11 章 最優二叉樹  154

11.1 最優二叉樹的基本概念  154

11.2 構造最優二叉樹  155

第12 章 線段樹 160

12.1 線段樹的基本概念  160

12.1.1 用於區間運算的線段樹  160

12.1.2 用於數據統計的線段樹  161

12.1.3 線段樹的數據結構  162

12.2 線段樹的基本操作  162

12.2.1 建立線段樹  162

12.2.2 在區間內插入線段或數據  163

12.2.3 刪除區間內的線段或數據  164

12.2.4 計算區間內的線段或數據狀態  165

12.3 線段樹在靜態統計問題上的套用  165

12.4 線段樹在動態統計問題上的套用  168

第13 章 二叉查找樹  176

13.1 二叉排序樹  176

13.1.1 二叉排序樹的基本概念  176

13.1.2 二叉排序樹的基本操作  177

13.2 靜態二叉排序樹  180

13.2.1 靜態二叉排序樹的特徵  180

13.2.2 靜態二叉排序樹的構造方法  180

13.2.3 在靜態二叉排序樹上進行數據統計  181

13.3 子樹大小平衡樹(sbt)   186

13.3.1 sbt 的性質  186

13.3.2 旋轉  186

13.3.3 動態維護sbt 的平衡特性  191

13.3.4 sbt 的基本操作  196

中篇 小結  205

下篇 討論圖型問題

第14 章 圖的基本概念及其存儲結構  209

14.1 圖的基本概念  209

14.2 圖的簡單分類  211

14.2.1 無向圖和有向圖  212

14.2.2 無權圖和加權圖  212

14.2.3 稀疏圖和稠密圖  212

14.2.4 完全圖和補圖  212

14.2.5 樹和森林  213

14.2.6 圖的生成樹和生成森林  213

14.2.7 平面圖  214

14.2.8 二分圖  214

14.2.9 相交圖和區間圖  214

14.3 圖的存儲結構  215

14.3.1 存儲節點間相鄰關係的相鄰矩陣  215

14.3.2 存儲邊信息的3 種數據結構  217

第15 章 圖的遍歷及其套用  220

15.1 廣度優先遍歷(bfs 算法)   220

15.1.1 bfs 算法的基本概念  220

15.1.2 bfs 算法的套用  222

15.2 深度優先遍歷(dfs 算法)   233

15.2.1 dfs 的基本概念  233

15.2.2 在dfs 遍歷過程中記錄節點顏色變化的時間  239

15.2.3 根據節點顏色對邊進行分類  240

15.2.4 分析dfs 森林的結構  242

15.2.5 使用dfs 算法進行拓撲排序  244

15.2.6 使用dfs 算法計算歐拉迴路  248

第16 章 有向圖的強連通分量和傳遞閉包 255

16.1 判定仙人掌圖 255

16.2 計算強連通分量 259

16.3 傳遞閉包的套用 266

第17 章 無向圖的連通性分析 271

17.1 計算節點的low 函式 271

17.2 計算連通圖的割點和橋 272

17.2.1 計算連通圖的割點 272

17.2.2 計算連通圖的橋 273

17.3 計算雙連通子圖 275

17.4 分析連通圖的連通程度 276

17.4.1 連通圖的頂連通度 277

17.4.2 連通圖的邊連通度 278

第18 章 最小生成樹 279

18.1 基本概念 279

18.2 最小生成樹的套用價值 279

18.3 最小生成樹的計算策略 281

18.4 計算最小生成樹的兩種算法 281

18.4.1 kruskal 算法 282

18.4.2 prim 算法 283

18.5 最小生成樹算法的套用實例 285

第19 章 加權圖的單源最短路徑問題 293

19.1 基本概念 293

19.1.1 單源算法是高效解決所有最短路徑問題的基礎 293

19.1.2 負權迴路影響單源最短路徑的計算 294

19.1.3 鬆弛技術是單源算法的核心 295

19.2 求解單源最短路徑問題的3 種算法 296

19.2.1 dijkstra 算法 296

19.2.2 bellman-ford 算法 298

19.2.3 spfa 算法 299

19.3 單源最短路徑算法的套用實例 301

第20 章 二分圖的匹配問題 310

20.1 基本概念 310

20.1.1 圖的匹配概念  310

20.1.2 二分圖的概念和判定方法  311

20.2 計算無權二分圖的最大匹配  315

20.2.1 匈牙利算法的基本思路 316

20.2.2 匈牙利算法的基本流程 316

20.2.3 匈牙利算法的套用實例 317

20.3 計算帶權二分圖的最佳匹配  320

20.3.1 最佳匹配的概念  320

20.3.2 km算法的基本思路  321

20.3.3 km算法的基本流程和套用實例  323

第21 章 最大流問題 327

21.1 基本概念  327

21.2 在可增廣路徑的基礎上計算最大流  329

21.2.1 可增廣路徑的基本概念  329

21.2.2 基於最大流定理上的最大流算法  334

21.3 按層次計算最大流的dinic 算法  334

21.3.1 dinic 算法的基本思路  334

21.3.2 dinic 算法的基本流程  335

21.4 利用最大流最小割定理解題  339

21.4.1 割的概念  339

21.4.2 最小割的計算方法和套用實例  340

21.5 計算多源多匯網路的可行流  346

21.6 網路增加容量下界因素後的流量計算問題  348

21.6.1 求容量有上下界的網路的最大流  348

21.6.2 求容量有上下界的網路的最小流  353

21.7 網路增加費用因素後的流量計算問題  358

21.7.1 計算最小費用最大流  359

21.7.2 計算容量有上下界的網路的最小費用最小流  364

下篇 小結  370

相關詞條

熱門詞條

聯絡我們