數據結構編程實驗（簡體書）

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

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

《數據結構編程實驗:大學程序設計課程與競賽訓練教材(附光盤)》編輯推薦：204道試題全部從ACM國際大學生程序設計競賽和其他程序設計競賽中精選而出，并給出詳盡試題解析。由淺入深、循序漸進地引入基本能力、線性表、樹、圖的編程實驗，同時注重從思維方式上歷練讀者的編程能力。

前言
我們長期從事數據結構教學和競賽培訓，教學實踐使我們萌發了對數據結構課程的教學模式進行改革的想法：
1）在課程中需要增加思維方式和解題策略的引導，引導學生思考各類數據結構的本質特征是什么；面對當前問題為什么要采用這樣的數據結構而不宜采用那樣的數據結構；當有多個數據結構可用時，怎樣權衡時間復雜度、空間復雜度、編程復雜度和思維復雜度四個因素，尋找最合時宜的數據結構，將“知識導向”與“智慧導向”真正結合起來。
2）在課程中需要引入案例教學，通過模擬或者重現現實生活中的一些場景，讓學生置身問題情境之中，通過思考、討論和上機編程來進行學習。傳統教學將數據結構“束之高閣”，在理論教學和筆試上兜來兜去，可能會使學生渾然不知數據結構在現實生活中究竟派什么用處，懵懵懂懂，最終失去了學習的意義。“紙上得來終覺淺，絕知此事要躬行”。案例教學則是一種以問題和動手編程驅動學習的方式：將知識置于問題情境和實踐過程之中，變枯燥乏味為生動活潑。學生拿到試題後，先進行審題，然後溫習或查閱各種他認為必要的數據結構知識，這無形中激發了他們的求知欲望，加深了他們對知識真諦的理解。捕捉到相關的理論知識後，學生還要經過縝密思考和動手編程，使之變為解決問題的程序方案。這個“認識-實踐-再認識-再實踐”的過程，應視為知識理解上的一種提高，知識學習與應用能力間的一種轉變和升華。
基于上述想法，我們近年來開設了“數據結構實驗”課程，并將ACM國際大學生程序設計競賽和其他程序設計競賽中的典型試題分門別類，精選了其中204道試題，翻譯後作為學習數據結構知識的實驗案例。這些試題不僅為相關知識創設了豐富有趣的問題背景，而且在相關網站上都有試題的在線測試。學生不僅可以帶著問題學習數據結構，而且所編程序的正確性和效率也可以通過相關網站上的測試系統得到實時檢驗，達到“學以致用”的目的。
……

前言
第一篇 基本能力的編程實驗
第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

3.2用遞歸算法求問題解的實驗范例
如果問題給出了初始狀態、目標狀態，且擴展子狀態的規則和約束條件同一的話，則可以使用遞歸算法找出一個由初始狀態至目標狀態的求解方案。使用遞歸算法需要注意幾個問題：
怎樣將求解過程中每一步的狀況組合成值參或局部變量，以便回溯時能恢復遞歸前的狀態。若這些參數的存儲量大（例如數組）且初始值需由主程序傳入，為避免內存溢出，則必須將其設為全局變量，且回溯前需恢復其遞歸前的值。
確定邊界條件，即程序在什么情況下不再遞歸下去。
確定搜索的范圍和約束條件，即在當前狀態未達邊界的情況下，在什么范圍內擴展子狀態，這些子狀態應滿足什么條件方可繼續遞歸下去。
上述遞歸算法簡稱回溯法。實際上這種方法與第四篇中圖的深度優先搜索本質上是一致的，只不過深度優先搜索一般用于現成的顯式圖，而回溯法一般用于遞歸問題的求解，兩者都是采用縱深搜索的遞歸策略。
【3.2.1Red and Black】
有一個矩形房間，覆蓋正方形瓷磚。每塊瓷磚涂成了紅色或黑色。一名男子站在黑色的瓷磚上，由此出發，可以移到四個相鄰瓷磚之一，但他不能移動到紅磚上，只能移動到黑磚上。編寫一個程序，計算他通過重復上述移動所能經過的黑磚數。
輸入
輸入包含多個數據集。一個數據集開頭行包含兩個正整數W和H，W和H分別表示矩形房間的列數和行數，且都不超20。
每個數據集有H行，其中每行包含W個字符。每個字符的含義如下所示：
'. '—黑磚；
'#'—紅磚；
'@'—男子（每個數據集僅出現一次）。
兩個0表示輸入結束。
輸出
對每個數據集，程序應該輸出一行，包含男子從初始瓷磚出發可到達的瓷磚數。