數據結構編程實驗

內容介紹

本書以知識體系結構和思維方式兩個方面作為主線,分成四大篇14章介紹了基本能力的編程實驗(基礎)、線性數據結構的編程實驗(線性表)、層次類非線性表的編程實驗(樹)以及群聚類非線性表的編程實驗(圖),並將“排序”和“搜尋”的內容融合到相關章節中。每章節由實驗範例和題庫兩個部分組成,試題全部選自ACM國際大學生程式設計競賽和其他程式設計競賽,共204題,並給出了試題來源和線上測試地址。每個實驗範例不僅有詳盡的知識要點闡述和試題解析,而且列出了寫有詳細注釋的參考程式;而題庫中的所有試題無論難易,都有清晰的提示。本書還附帶了存儲所有試題的英文原版描述和大部分試題的測試數據等資料的光碟。
本書的實驗範例部分可以作為程式設計語言和數據結構的實驗教材,供大學教學使用;題庫部分則可以作為計算機專業學生的研修資料和程式設計競賽的培訓教材。

作者介紹

吳永輝,博士,復旦大學計算機科學與工程系副教授,ACM-ICPC中國賽區指導委員會(ACM-ICPC Council China)成員,復旦大學ACM程式設計競賽隊教練。作者自2001年起連續帶隊進入ACM-ICPC世界總決賽,並取得過世界第6名的佳績。他的主要研究方向為資料庫,在《計算機研究與發展》、《軟體學報》以及重大學術會議上發表過多篇論文,參與翻譯出版了《數據通信與網路》和《數據通信、計算機網路與開放系統》。
王建德,著名的信息學奧林匹克競賽金牌教練,國務院特殊津貼專家,中學特級教師。他所輔導的學生在國際奧林匹克信息學競賽(IOI)中獲7金、3銀、2銅的優異成績,先後出版了24本關於程式設計和算法的學術專著,其中《實用算法的分析與程式設計》廣受好評,長期以來是國內各類程式設計競賽的必備教程。

作品目錄

前言
第一篇 基本能力的編程實驗
第1章 簡單計算的編程實驗 2
1.1 改進程式書寫風格的實驗範例 2
1.2 正確處理多組測試數據的實驗範例 4
1.3 提高實數精度的實驗範例 7
1.4 使用二分法提高計算時效的實驗範例 8
1.5 相關題庫 13
第2章 簡單模擬的編程實驗 23
2.1 直敘式模擬的實驗範例 23
2.2 篩選法模擬的實驗範例 26
2.3 構造法模擬的實驗範例 28
2.4 相關題庫 30
第3章 簡單遞歸的編程實驗 36
3.1 計算遞歸函式的實驗範例 36
3.2 用遞歸算法求問題解的實驗範例 37
3.3 求解遞歸數據的實驗範例 40
3.4 相關題庫 42
本篇小結 46
第二篇 線性數據結構的編程實驗
第4章 套用直接存取類線性表編程 48
4.1 數組套用一:日期計算的實驗
範例 48
4.2 數組套用二:高精度運算的實驗範例 54
4.3 數組套用三:多項式表示與處理的實驗範例 60
4.4 數組套用四:數值矩陣運算的實驗範例 65
4.5 字元串處理一:串的存儲結構的實驗範例 70
4.6 字元串處理二:串模式匹配的實驗範例 71
4.7 相關題庫 77
第5章 套用順序存取類線性表編程 112
5.1 順序表套用的實驗範例 112
5.2 棧套用的實驗範例 118
5.3 佇列套用的實驗範例 124
5.4 相關題庫 134
第6章 套用廣義索引類線性表編程 141
6.1 使用詞典解題的實驗範例 141
6.2 使用散列表與散列方法解題的實驗範例 148
6.3 相關題庫 154
第7章 套用線性表排序編程 160
7.1 利用STL中自帶的排序功能編程的實驗範例 160
7.2 套用排序算法編程的實驗範例 166
7.3 相關題庫 169
本篇小結 190
第三篇 層次類非線性表的編程實驗
第8章 採用樹結構的非線性表編程 192
8.1 用樹的遍歷求解層次性問題的實驗範例 192
8.2 用樹結構支持並查集的實驗範例 201
8.3 用樹狀數組統計子樹權和的實驗範例 207
8.4 相關題庫 211
第9章 套用二叉樹的基本概念編程 231
9.1 普通有序樹轉化為二叉樹的實驗範例 231
9.2 計算二叉樹路徑的實驗範例 234
9.3 通過遍歷確定二叉樹結構的實驗範例 237
9.4 相關題庫 239
第10章 套用經典二叉樹編程 243
10.1 二叉搜尋樹的實驗範例 243
10.2 二叉堆的實驗範例 248
10.3 哈夫曼樹的實驗範例 259
10.4 相關題庫 262
本篇小結 275
第四篇 群聚類非線性表的編程實驗
第11章 套用圖的遍歷算法編程 278
11.1 BFS算法的實驗範例 278
11.2 DFS算法的實驗範例 282
11.3 拓撲排序的實驗範例 285
11.4 計算無向圖的連通性的實驗範例 291
11.5 相關題庫 299
第12章 套用最小生成樹算法編程 327
12.1 Kruskal算法的實驗範例 327
12.2 Prim算法的實驗範例 330
12.3 相關題庫 333
第13章 套用最佳路徑算法編程 341
13.1 Warshall算法和Floyed-Warshall算法的實驗範例 341
13.2 Dijkstra算法的實驗範例 347
13.3 Bellman-Ford算法的實驗範例 351
13.4 SPFA算法的實驗範例 356
13.5 相關題庫 360
第14章 套用特殊圖的經典算法編程 368
14.1 二分圖匹配的實驗範例 368
14.2 計算網路最大流的實驗範例 371
14.3 相關題庫 385
本篇小結 396

相關詞條

熱門詞條

聯絡我們