内容簡介
本書是國家級雙語教學示範課程《數據結構》的配套教材，根據教育部高等學校計算機科學與技術教學指導委員會制定的《高等學校計算機科學與技術專業發展戰略研究報告暨專業規範》編寫。全書每章均以數據的邏輯結構、存儲結構和相應的算法實現為主線，并對算法的運算效率進行分析。全書分為8章，涵蓋了各種常見數據結構。第1章主要介紹數據結構和算法分析的基本概念，第2～6章主要介紹典型的線性結構、樹型結構和圖型結構，第7～8章分别介紹查找和排序操作。
另外，每章後面附有習題和上機實驗内容，上機實驗提供了完整的、可運行的程序上機實驗供讀者參考，以加深讀者對所學知識的理解和應用。
本書既可作為高等院校計算機及相關專業數據結構課程的教學用書，也可作為從事計算機工程與應用的廣大讀者的參考書。
該書是國家級雙語教學示範課程配套教材，以基本數據結構和算法設計策略為知識單元，系統地介紹了數據結構的知識與應用、計算機算法的設計與分析方法，主要内容包括線性表、樹、圖和廣義表、算法設計策略以及查找與排序算法等。《數據結構與算法》注重理論與實踐相結合，内容深入淺出，可以作為高等院校計算機學科相關專業的教材或參考書，同時對計算機科技工作者也有參考價值。
作品目錄
第1章
緒論 1
1.1 數據及其邏輯結構 1
1.1.1 基本概念 1
1.1.2 邏輯結構 2
1.2 數據結構 2
1.2.1 什麼是數據結構 2
1.2.2 數據結構的二元組描述 3
1.2.3 數據結構和數據類型 4
1.3 存儲實現與運算實現 4
1.3.1 順序存儲結構 4
1.3.2 鍊式存儲結構 5
1.3.3 索引存儲結構 6
1.3.4 散列存儲結構 6
1.3.5 運算實現 7
1.3.6 進一步讨論 8
1.4 算法描述和算法分析 8
1.4.1 什麼是算法 8
1.4.2 算法描述 9
1.4.3 算法分析 11
1.5 網絡教輔資源 14
1.6 小結 14
練習一 15
第2章
線性表 19
2.1 線性表的基本概念 19
2.2 線性表的順序表示和實現 21
2.3 線性表的鍊接表示和實現 26
2.3.1 線性表的鍊式存儲原理 27
2.3.2 線性表的鍊式存儲算法實現 27
2.3.3 算法效率分析 32
2.4 循環鍊表和雙鍊表 32
2.4.1 循環鍊表 32
2.4.2 雙向鍊表 33
2.5 線性表的應用舉例 35
2.5.1 問題的提出 35
2.5.2 分析問題 36
2.5.3 算法實現 36
2.5.4 程序 39
2.6 小結 44
練習二 45
第3章
棧和隊列 54
3.1 棧 54
3.1.1 棧的定義 54
3.1.2 棧的基本運算 54
3.1.3 棧的順序存儲結構 55
3.1.4 棧的鍊式存儲結構 58
3.1.5 棧的應用 60
3.2 隊列 63
3.2.1 隊列的定義 63
3.2.2 隊列的基本運算 63
3.2.3 隊列的順序存儲結構 64
3.2.4 隊列的鍊式存儲結構 68
3.2.5 隊列的應用 72
3.3 小結 74
練習三 75
第4章
串和數組 79
4.1 串的基本概念 79
4.2 串的基本操作和串的存儲結構 80
4.2.1 串的基本操作 80
4.2.2 串的靜态順序存儲結構 81
4.2.3 串的動态順序存儲結構 87
4.2.4 串的鍊式存儲結構 91
4.3 數組的定義和運算 92
4.4 數組的順序存儲結構 92
4.5 特殊矩陣的壓縮存儲 94
4.5.1 特殊矩陣 95
4.5.2 稀疏矩陣 96
4.6 小結 103
練習四 104
第5章
樹和二叉樹 110
5.1 樹的概念與定義 110
5.1.1 樹的定義 110
5.1.2 樹的基本操作 111
5.2 二叉樹的性質和存儲結構 111
5.2.1 二叉樹的定義與基本操作 111
5.2.2 二叉樹的性質 112
5.2.3 二叉樹的存儲結構 114
5.3 二叉樹的遍曆與線索化 116
5.3.1 二叉樹的遍曆 116
5.3.2 二叉樹的非遞歸遍曆 119
5.3.3 樹的唯一性問題 120
5.3.4 二叉樹遍曆的應用 121
5.3.5 線索二叉樹 124
5.4 樹、森林和二叉樹的關系 126
5.4.1 樹的存儲結構 127
5.4.2 樹、森林與二叉樹的相互轉換 129
5.4.3 樹與森林的遍曆 132
5.5 哈夫曼樹及其應用 133
5.5.1 哈夫曼樹的定義 133
5.5.2 哈夫曼樹的構造 134
5.5.3 哈夫曼編碼 135
5.6 小結 137
練習五 139
第6章
圖 146
6.1 圖的定義及理論 146
6.2 圖的存儲結構及算法實現 149
6.2.1 圖的基本運算的抽象 149
6.2.2 數組表示法 150
6.2.3 鄰接表表示 154
6.2.4 十字鍊表表示 160
6.3 圖的算法實現 162
6.3.1 圖的遍曆算法 162
6.3.2 圖的連通性 166
6.4 圖的應用 167
6.4.1 圖的最小生成樹 167
6.4.2 最短路徑 171
6.4.3 任意頂點最短路徑 175
6.5 小結 176
練習六 177
第7章
查找表 183
7.1 查找表的基本概念 183
7.2 靜态查找表 184
7.2.1 順序查找 184
7.2.2 折半查找 187
7.2.3 分塊查找 190
7.3 動态查找表 192
7.3.1 二叉排序樹 192
7.3.2 平衡二叉樹 199
7.4 哈希表 200
7.4.1 哈希表的基本概念 201
7.4.2 哈希函數的構造方法 202
7.4.3 處理哈希沖突的方法 206
7.5 小結 209
練習七 210
第8章
内部排序 217
8.1 排序的基本概念 217
8.1.1 排序 217
8.1.2 内部排序和外部排序 218
8.1.3 排序算法評價 218
8.1.4 排序算法的穩定性 218
8.1.5 待排序記錄序列的存儲結構 218
8.2 直接插入排序和希爾排序 218
8.2.1 直接插入排序 219
8.2.2 折半查找插入排序 222
8.2.3 希爾排序 223
8.3 選擇排序和堆排序 225
8.3.1 選擇排序 226
8.3.2 堆排序 227
8.4 冒泡排序和快速排序 229
8.4.1 冒泡排序 229
8.4.2 快速排序 231
8.5 歸并排序 235
8.6 基數排序 236
8.6.1 基本思想 236
8.6.2 基數排序過程與算法 237
8.7 各種内部排序方法的比較讨論 241
8.8 外部排序 243
8.8.1 外部存儲系統 243
8.8.2 外部排序面臨的問題 246
8.8.3 外部排序的基本過程 246
8.9 小結 247
練習八 248
