前言
第一篇 基本能力的編程實驗
第1章 簡單計算的編程實驗
1.1 改進程序書寫風格的實驗範例
1.2 正確處理多組測試數據的實驗範例
1.3 提高實數精度的實驗範例
1.4 使用二分法提高計算時效的實驗範例
1.5 相關題庫
第2章 簡單模擬的編程實驗
2.1 直敘式模擬的實驗範例
2.2 篩選法模擬的實驗範例
2.3 構造法模擬的實驗範例
2.4 相關題庫
第3章 簡單遞歸的編程實驗
3.1 計算遞歸函數的實驗範例
3.2 用遞歸算法求問題解的實驗範例
3.3 求解遞歸數據的實驗範例
3.4 相關題庫
本篇小結
第二篇 線性數據結構的編程實驗
第4章 應用直接存取類線性表編程
4.1 數組應用一：日期計算的實驗範例
4.2 數組應用二：高精度運算的實驗範例
4.3 數組應用三：多項式表示與處理的實驗範例
4.4 數組應用四：數值矩陣運算的實驗範例
4.5 字符串處理一：串的存儲結構的實驗範例
4.6 字符串處理二：串模式匹配的實驗範例
4.7 相關題庫
第5章 應用順序存取類線性表編程
5.1 順序表應用的實驗範例
5.2 棧應用的實驗範例
5.3 隊列應用的實驗範例
5.4 相關題庫
第6章 應用廣義索引類線性表編程
6.1 使用詞典解題的實驗範例
6.2 使用散列表與散列方法解題的實驗範例
6.3 相關題庫
第7章 應用線性表排序編程
7.1 利用STL中自帶的排序功能編程的實驗範例
7.2 應用排序算法編程的實驗範例
7.3 相關題庫
本篇小結
第三篇 層次類非線性表的編程實驗
第8章 采用樹結構的非線性表編程
8.1 用樹的遍歷求解層次性問題的實驗範例
8.2 用樹結構支持並查集的實驗範例
8.3 用樹狀數組統計子樹權和的實驗範例
8.4 相關題庫
第9章 應用二叉樹的基本概念編程
9.1 普通有序樹轉化為二叉樹的實驗範例
9.2 計算二叉樹路徑的實驗範例
9.3 通過遍歷確定二叉樹結構的實驗範例
9.4 相關題庫
第10章 應用經典二叉樹編程
10.1 二叉搜索樹的實驗範例
10.2 二叉堆的實驗範例
10.3 哈夫曼樹的實驗範例
10.4 相關題庫
本篇小結
第四篇 群聚類非線性表的編程實驗
第11章 應用圖的遍歷算法編程
11.1 BFS算法的實驗範例
11.2 DFS算法的實驗範例
11.3 拓撲排序的實驗範例
11.4 計算無向圖的連通性的實驗範例
11.5 相關題庫
第12章 應用最小生成樹算法編程
12.1 Kruskal算法的實驗範例
12.2 Prim算法的實驗範例
12.3 相關題庫
第13章 應用最佳路徑算法編程
13.1 Warshall算法和Floyed-Warshall算法的實驗範例
13.2 Dijkstra算法的實驗範例
13.3 Bellman-Ford算法的實驗範例
13.4 SPFA算法的實驗範例
13.5 相關題庫
第14章 應用特殊圖的經典算法編程
14.1 二分圖匹配的實驗範例
14.2 計算網絡最大流的實驗範例
14.3 相關題庫
本篇小結

我們長期從事數據結構教學和競賽培訓，教學實踐使我們萌發了對數據結構課程的教學模式進行改革的想法：
1）在課程中需要增加思維方式和解題策略的引導，引導學生思考各類數據結構的本質特征是什麼；面對當前問題為什麼要采用這樣的數據結構而不宜采用那樣的數據結構；當有多個數據結構可用時，怎樣權衡時間復雜度、空間復雜度、編程復雜度和思維復雜度四個因素，尋找最合時宜的數據結構，將“知識導向”與“智慧導向”真正結合起來。
2）在課程中需要引入案例教學，通過模擬或者重現現實生活中的一些場景，讓學生置身問題情境之中，通過思考、討論和上機編程來進行學習。傳統教學將數據結構“束之高閣”，在理論教學和筆試上兜來兜去，可能會使學生渾然不知數據結構在現實生活中究竟派什麼用處，懵懵懂懂，最終失去了學習的意義。“紙上得來終覺淺，絕知此事要躬行”。案例教學則是一種以問題和動手編程驅動學習的方式：將知識置於問題情境和實踐過程之中，變枯燥乏味為生動活潑。學生拿到試題後，先進行審題，然後溫習或查閱各種他認為必要的數據結構知識，這無形中激發了他們的求知欲望，加深了他們對知識真諦的理解。捕捉到相關的理論知識後，學生還要經過縝密思考和動手編程，使之變為解決問題的程序方案。這個“認識-實踐-再認識-再實踐”的過程，應視為知識理解上的一種提高，知識學習與應用能力間的一種轉變和升華。
基於上述想法，我們近年來開設了“數據結構實驗”課程，並將ACM國際大學生程序設計競賽和其他程序設計競賽中的典型試題分門別類，精選了其中204道試題，翻譯後作為學習數據結構知識的實驗案例。這些試題不僅為相關知識創設了豐富有趣的問題背景，而且在相關網站上都有試題的在線測試。學生不僅可以帶著問題學習數據結構，而且所編程序的正確性和效率也可以通過相關網站上的測試繫統得到實時檢驗，達到“學以致用”的目的。
本書試題的在線測試地址主要有：
在線評測繫統 簡稱 網址
北京大學在線評測繫統 POJ http://poj.org/
浙江大學在線評測繫統 ZOJ http://acm.zju.edu.cn/onlinejudge/
UVA在線評測繫統 UVA http://uva.onlinejudge.org/
http://livearchive.onlinejudge.org/
Ural在線評測繫統 Ural http://acm.timus.ru/
SGU在線評測繫統 SGU http://acm.sgu.ru/
本書按照數據結構的知識結構和循序漸進的原則，共分四大篇（基本能力的編程實驗、線性數據結構的編程實驗、層次類非線性表的編程實驗、群聚類非線性表的編程實驗）14個章節。每個章節為相關數據結構知識提供了大量的實驗範例，並且建立了相關的試題庫，其中實驗範例68道，題庫試題136道。每個實驗範例不僅有知識要點闡述和詳盡的試題解析，還列出了寫有詳細注釋的參考程序；題庫中的所有試題無論難易，都有清晰的提示。教師既可以將實驗範例作為開設數據結構實驗課程的教材，也可以從相關題庫中挑選數據結構實驗課程的作業、考題或指導ACM集訓活動的培訓資料。每道題都注明了試題來源和在線測試網址，考慮到網站更新給讀者學習帶來不便的可能情況，本書還附帶了存儲所有試題的英文原版描述和大部分試題的測試數據等資料的光盤。我們之所以這樣做，就是力圖構建一個盡可能豐富、實用和長效的數據結構實驗課程資源庫。
需要說明的是，本書是在復旦大學ACM集訓隊長期活動的基礎上積累而成的。阿拉法特·居來提、姚哲雲、張昊等同學精心編寫了所有程序，每道程序都通過了嚴格的測試驗證，其中一些程序經多次修改，精益求精。這些同學為本書的出版付出了辛勤的勞動，作出了不可或缺的貢獻。在此，向他們表示由衷的感激。另外，衷心感謝復旦大學計算機學院2006、2007、2008級同學在使用本書講義過程中提出的寶貴意見和建議。
由於時間和水平所限，書中肯定夾雜了不少缺點和錯誤，表述不當和筆誤更是在所難免，熱忱歡迎學術界同仁和讀者賜正。如果你在閱讀中發現了問題，請通過書信或電子郵件告訴我們，以便及時整理成勘誤表放在本書的專門網站上，供廣大讀者查詢更正。我們更期望讀者對本書提出建設性意見，以便再版時改進。我們的聯繫方式是：
通信地址：上海市邯鄲路220號復旦大學計算機科學技術學院 吳永輝
郵編：200433