內容簡介

本實驗指導教程是配合計算機及相關專業的“數據結構”課程而編寫的。在內容編排方面，按照循序漸進、由淺入深的順序設計、選取案例。全書共分兩個部分：第一部分為“數據結構實驗”；第二部分為“數據結構課程設計”。

第一部分(包括第1～8章)針對每個知識點，首先給出明確的要求，隨后設計基礎實驗，特別是前幾章在基礎實驗之后，設計了若干應用案例。這樣有利于學生明確知識點在應用中如何使用，消除迷茫感、增強學習興趣。

第二部分(即第9章)是課程設計，介紹在一個項目中如何選擇和使用多種基本的數據結構，介紹如何有效地將它們融合在一起，解決實際的復雜應用問題。

本書可作為高等院校計算機及相關專業數據結構課程的實驗教材。

前    言

　　

　　數據結構是計算機及相關專業中一門重要的專業基礎課程。用計算機解決實際問題時，就要涉及數據的表示及數據的處理，而這正是數據結構課程的主要研究對象。通過對數據結構知識內容的學習，可以為后續課程，尤其是軟件方面的課程打下堅實的基礎，同時，也提供了必要的技能訓練。此課程的學習質量將直接影響計算機軟件系列課程的學習效果，因此，數據結構課程在計算機專業中具有舉足輕重的作用。

　　根據我們多年的教學經驗，認為學生學習數據結構的主要困難在于解題。學生在解題中經常會出現錯誤，原因在于實踐能力不足。

　　要學好數據結構，僅僅通過課堂教學或自學獲取理論知識是遠遠不夠的，還必須加強實際動手能力的訓練。只有通過實驗課調試和運行已有的各種典型算法和已編寫的程序，從成功和失敗的經驗中得到鍛煉，才能熟練掌握和運用理論知識解決軟件開發中的實際問題，達到學以致用的目的。

　　本實驗指導教程是配合計算機及相關專業數據結構課程而編寫的。本書在內容編排方面，按照循序漸進、由淺入深的順序設計、選取案例。根據教學內容，針對學生的實際情況，本書在內容編排上共分兩個部分。第一部分為"數據結構實驗"；第二部分為"數據結構課程設計"。

　　第一部分(包括第1～8章)針對每個知識點，首先給出明確的要求，隨后設計基礎實驗，特別是前幾章在基礎實驗之后，設計了若干應用案例。這樣有利于學生明確知識點在應用中如何使用，消除學生的迷茫感、增強學生的學習興趣。

　　第二部分(即第9章)是課程設計，介紹在一個項目中如何選擇和使用多種基本數據結構，介紹如何有效地將它們融合在一起解決實際的復雜應用問題。這有利于學生更深層次地掌握數據結構原理及其應用范圍和過程。

　　本書具有以下特點。

　　(1) 基于案例驅動的教學內容設計。在實驗案例的選擇方面，不僅有針對知識點的基礎案例，而且有對應的應用案例，從而使學生能夠消除畏難情緒。我們在該實驗教材的編寫過程中，選擇案例時由淺入深并精心設計了應用案例，以確保應用的完整性。

　　(2) 提供大量的源代碼和開發案例。在該實驗教材的編寫中，摒棄了偽代碼的描述，全部采用C語言源代碼，這些源代碼都是經過調試并且在教學過程中已經應用的，學生可以直接分析和模仿。同時，在重要的章節，都提供了較為深入的設計案例，例如多項式的運算、括號匹配判斷系統、迷宮求解系統、最短路徑求解等，為學生提供了更為深入的源碼討論和模仿的機會，極大地提高了教材的全面性、深入性和綜合性。

　　(3) 提供典型的課程設計內容。為了更好地提高學生的專業技能訓練水平以及提高學生的學習興趣，在本書的編寫過程中，編寫成員根據自己多年教學的積累，整理出了適合計算機專業學生實際情況的課程設計題目，并提供了相應的解決思路和源代碼，為學生提供了很好的學習機會和訓練機會。

　　本書提供案例程序的源代碼(可運行)，并贈送C++版案例實驗教程。讀者可以從清華大學出版社的網站下載。 

　　本書可作為高等院校計算機及相關專業數據結構課程的實驗教材。

　　由于編者水平有限，錯誤和不當之處在所難免，希望讀者批評指正。 

　　

編  者

 

　　

目錄

第1章  順序表 1

實驗1  順序表的實現 2

　1．實驗目的 2

　2．實驗內容 2

　3．算法設計 2

　4．程序實現 3

　5．運行程序 5

實驗2  順序表的應用--集合運算 5

　1．實驗目的 5

　2．實驗內容 5

　3．算法設計 5

　4．程序實現 6

　5．運行程序 8

實驗3  順序表的應用--回文數猜想 8

　1．問題描述 8

　2．基本要求 8

　3．算法設計 8

　4．程序實現 9

　5．運行程序 10

第2章  鏈表 11

實驗1  單鏈表的實現 12

　1．實驗目的 12

　2．實驗內容 12

　3．算法設計 12

　4．程序實現 13

　5．運行程序 15

實驗2  單鏈表的應用--約瑟夫問題 16

　1．問題描述 16

　2．基本要求 16

　3．算法設計 16

　4．程序實現 16

　5．運行程序 17

實驗3  單鏈表的應用--多項式求和 18

　1．問題描述 18

　2．基本要求 18

　3．算法設計 18

　4．實現程序 18

　5．運行程序 21

第3章  棧 23

實驗1  順序棧的實現 24

　1．實驗目的 24

　2．實驗內容 24

　3．算法設計 24

　4．程序實現 25

　5．運行程序 26

實驗2  鏈棧的實現 26

　1．實驗目的 26

　2．實驗內容 26

　3．算法設計 27

　4．程序實現 27

　5．程序運行 28

實驗3  棧的應用--數制轉換 28

　1．問題描述 28

　2．基本要求 28

　3．算法設計 29

　4．程序實現 29

　5．運行程序 30

實驗4  棧的應用--括號匹配問題 30

　1．問題描述 30

　2．基本要求 30

　3．算法設計 30

　4．程序實現 30

　5．運行程序 31

實驗5  棧的應用--表達式求值 32

　1．問題描述 32

　2．基本要求 32

　3．算法設計 32

　4．程序實現 32

　5．運行程序 34

第4章  隊列 35

實驗1  循環隊列的實現 36

　1．實驗目的 36

　2．實驗內容 36

　3．算法設計 36

　4．程序實現 37

　5．運行程序 38

實驗2  鏈隊列的實現 39

　1．實驗目的 39

　2．實驗內容 39

　3．算法設計 39

　4．程序實現 39

　5．運行程序 41

實驗3  隊列的應用--優先隊列 41

　1．問題描述 41

　2．基本要求 41

　3．算法設計 41

　4．實現程序 42

　5．運行程序 44

實驗4  隊列的應用--雙端隊列 45

　1．問題描述 45

　2．基本要求 45

　3．算法設計 45

　4．程序實現 45

　5．運行程序 48

第5章  二叉樹 49

實驗1  二叉樹的建立 50

　1．實驗目的 50

　2．實驗內容 50

　3．算法設計 50

　4．程序實現 51

　5．運行程序 51

實驗2  二叉樹的遍歷 52

　1．實驗目的 52

　2．實驗內容 52

　3．算法設計 52

　4．程序實現 53

　5．運行程序 55

實驗3  二叉樹的高度、節點數、葉子

節點數 55

　1．實驗目的 55

　2．實驗內容 55

　3．算法設計 55

　4．程序實現 55

　5．運行程序 57

實驗4  堆 57

　1．問題描述 57

　2．基本要求 57

　3．算法設計 57

　4．程序實現 58

　5．運行程序 60

第6章  圖 61

實驗1  圖的鄰接矩陣表示 62

　1．實驗目的 62

　2．實驗內容 62

　3．實現提示 62

　4．程序實現 62

　5．運行程序 64

實驗2  圖的鄰接表表示 64

　1．實驗目的 64

　2．實驗內容 64

　3．實現提示 64

　4．程序實現 64

　5．運行程序 66

實驗3  圖的深度優先搜索 67

　1．問題描述 67

　2．基本要求 67

　3．實現提示 67

　4．程序實現 67

　5．運行程序 69

第7章  排序 71

實驗1  冒泡排序 72

　1．實驗目的 72

　2. 實驗內容 72

　3．實現提示 72

　4．程序實現 73

　5．運行程序 74

實驗2  插入排序、選擇排序 74

　1．實驗目的 74

　2．實驗內容 74

　3．實現提示 75

　4．程序實現 75

　5．運行程序 76

實驗3  歸并排序 76

　1．實驗目的 76

　2．實驗內容 76

　3．實現提示 76

　4．實現程序 76

　5．運行程序 78

實驗4  快速排序 78

　1．實驗目的 78

　2．實驗內容 79

　3．實現提示 79

　4．程序實現 79

　5．運行程序 80

實驗5  堆排序 81

　1．實驗目的 81

　2．實驗內容 81

　3．實現提示 81

　4．程序實現 81

　5．運行程序 82

第8章  查找 83

實驗1  折半查找 84

　1．實驗目的 84

　2．實驗內容 84

　3．實現提示 84

　4．程序實現 85

　5．運行程序 86

實驗2  二叉排序樹查找 87

　1．實驗目的 87

　2．實驗內容 87

　3．實現提示 87

　4．程序實現 87

　5．運行程序 89

實驗3  哈希查找 89

　1．實驗目的 89

　2．實驗內容 89

　3．實現提示 90

　4．程序實現 90

　5．運行程序 91

第9章  課程設計 93

問題1  學生成績管理 94

　1．問題描述 94

　2．任務要求 94

　3．程序實現 95

　4．運行結果 98

問題2  數據庫管理系統 98

　1．問題描述 98

　2．任務要求 98

　3．分析與實現 99

　4．程序實現 101

　5．運行結果 116

問題3  馬踏棋盤 117

　1．問題描述 117

　2．任務要求 117

　3．分析與實現 117

　4．運行結果 120

問題4  停車場管理 121

　1．問題描述 121

　2．任務要求 121

　3．分析與實現 122

　4．運行結果 126

問題5  大整數計算器 126

　1．問題描述 126

　2. 任務要求 127

　3．分析與實現 127

　4．運行結果 132

 

問題6  魔方陣 132

　1．問題描述 132

　2．任務要求 133

　3．分析與實現 133

　4．運行結果 134

問題7  本科生導師制問題 134

　1．問題描述 134

　2．任務要求 135

　3．分析與實現 135

　4．運行結果 144

問題8  電文的編碼和譯碼 145

　1．問題描述 145

　2．任務要求 145

　3．分析與實現 145

　4．運行結果 148

問題9  家族關系查詢系統 149

　1．問題描述 149

　2．任務要求 149

　3．分析與實現 149

　4．運行結果 161

問題10  地鐵建設問題 162

　1．問題描述 162

　2．任務要求 162

　3．分析與實現 162

　4．運行結果 165

問題11  校園導航 165

　1．問題描述 165

　2．任務要求 165

　3．分析與實現 166

　4．運行結果 169

參考文獻 170