《數據結構與算法教程》是朱明方和吳及共同編著的書籍，人民郵電出版社2011年11月出版。
基本介紹
- 書名：數據結構與算法教程
- 作者：朱明方 吳及 編著
- ISBN：978-7-115-25404-7
- 類別：高等學校計算機規劃教材
- 頁數：320
- 定價：39.00 元
- 出版社：人民郵電出版社
- 出版時間：2011年11月
- 裝幀：平裝
- 開本：16
內容提要,作者信息,目 錄,
內容提要
本書可以作為大專院校數據結構課程的教材，也可以作為從事計算機套用開發的科技人員的參考書。本書以清華大學電子係數據結構講義為藍本，主要針對高等院校非計算機專業開設“數據結構”課程的需要而編寫的。全書從套用的角度，重點介紹數據處理中常用的數據結構——線性表、樹與二叉樹、圖，以及基本的數據處理技術——查找和排序方法，同時通過實例把回溯法、分治法、貪心法、動態規劃法等常用的算法設計思想的套用融入其中，把數據結構的介紹和常用算法設計的討論緊密結合，並且輔之以充足的練習題，從而使讀者更具體、更深刻地理解各種常用的數據結構，及它們與算法之間的關係，以達到學以致用的目的。
作者信息
朱明方 清華大學電子工程系教授，原電子工程系網路與人機語音通信研究所副所長，計算機與網路教學實驗室主任，電子工程系教學工作委員會委員。長期從事計算機基礎教學和多媒體信息處理方面的科研工作。參與完成國家及部級的科研項目多項，取得優秀成果；編寫教材10多本，曾獲部級優秀教材一等獎，多次獲清華大學教學優秀成果獎，所編寫的教材得到清華大學“985工程”的支持。
吳及 博士，清華大學電子工程系副教授，博士生導師，清華—訊飛語音技術聯合實驗室主任。從事數據結構與算法方面的教學工作，以及語音識別和多媒體信號處理方面的科研工作，承擔了多項國家863科研項目，發表論文40餘篇。擔任全國人機語音通訊學術會議常設機構委員，並擔任多個國際和全國學術會議程式委員會委員以及多個期刊和學術會議的的審稿人。
目 錄
第1章 緒論 1
1.1 預備知識 1
1.1.1 集合的笛卡兒積 1
1.1.2 二元關係 2
1.1.3 二元關係的基本性質和幾種重要關係 3
1.2 什麼是數據結構 4
1.2.1 從實際問題理解數據結構 4
1.2.2 數據結構所討論的內容 6
1.2.3 如何表示數據結構 9
1.3 抽象數據類型 10
1.3.1 什麼是抽象數據類型 10
1.3.2 抽象數據類型的定義與實現 12
1.4 算法與算法分析 13
1.4.1 什麼是算法 13
1.4.2 算法描述 15
1.4.3 常用的算法設計方法 16
1.4.4 算法分析 21
習題 24
上機練習題 26
第2章 線性表的順序存儲及其運算 27
2.1 線性表的概念 27
2.1.1 什麼是線性表 27
2.1.2 線性表的抽象數據類型 29
2.2 順序表及其運算實現 30
2.2.1 線性表的順序存儲——順序表 30
2.2.2 順序表的基本運算 31
2.2.3 順序表套用例——求子集 36
2.3 棧 36
2.3.1 什麼是棧 37
2.3.2 棧的抽象數據類型 39
2.3.3 順序棧及其運算 39
2.4 棧套用 42
2.4.1 棧在優先權處理中的套用 42
2.4.2 棧與分治法 48
2.4.3 棧與回溯法 50
2.4.4 棧與遞歸 55
2.5 佇列 63
2.5.1 佇列及其抽象數據類型 63
2.5.2 順序佇列及其運算 64
2.5.3 佇列套用例 68
* 2.5.4 優先佇列 72
2.6 數組與特殊矩陣的表示 74
2.6.1 數組的順序存儲 74
2.6.2 規則矩陣的壓縮存儲 76
* 2.6.3 稀疏矩陣的三列二維數組表示——三元組順序表 78
習題 81
上機練習題 82
第3章 鍊表 83
3.1 線性表的鏈式存儲——線性鍊表 83
3.1.1 線性鍊表的結構特點 83
3.1.2 線性鍊表的運算 84
3.2 鏈式棧與鏈式佇列 91
3.2.1 棧的鏈式存儲——鏈式棧 91
3.2.2 佇列的鏈式存儲——鏈式佇列 95
3.3 循環鍊表 98
3.3.1 循環鍊表的結構特點 98
3.3.2 循環鍊表的基本運算 99
3.3.3 鍊表套用例 103
*3.4 多重鍊表 109
3.4.1 多重鍊表結構 109
3.4.2 雙向鍊表 110
*3.5 廣義表 112
3.5.1 什麼是廣義表 113
3.5.2 廣義表的存儲表示 114
3.5.3 廣義表的基本運算 116
習題 120
上機練習題 121
第4章 樹與二叉樹 122
4.1 樹的基本概念 122
4.1.1 什麼是樹 122
4.1.2 樹的性質 127
4.2 二叉樹 128
4.2.1 什麼是二叉樹 128
4.2.2 二叉樹的基本性質 128
4.2.3 二叉樹的抽象數據類型 131
4.2.4 二叉樹的存儲結構 131
4.2.5 二叉樹的遍歷及其他運算 133
* 4.2.6 線索二叉樹 138
4.3 二叉樹套用 141
4.3.1 表達式線性化 141
4.3.2 最優二叉樹 143
4.3.3 二叉搜尋樹 148
4.3.4 堆 154
* 4.3.5 二叉樹與減治法 160
4.4 樹的運算 163
4.4.1 樹的抽象數據類型 163
4.4.2 樹的存儲結構 164
4.4.3 樹的遍歷 165
* 4.4.4 樹的其他運算 167
* 4.5 樹與回溯法 170
4.5.1 問題解的描述——解空間樹 171
4.5.2 回溯法的求解過程分析——遍歷解空間樹 172
4.5.3 回溯法求解問題的形式化描述 174
* 4.6 森林的遍歷 176
4.6.1 森林與二叉樹的轉換 176
4.6.2 森林的遍歷 177
習題 178
上機練習題 179
第5章 圖 180
5.1 圖的基本概念 180
5.1.1 圖的定義和概念 180
5.1.2 圖的抽象數據類型 184
*5.1.3 歐拉路徑 185
5.2 圖的存儲結構 186
5.2.1 圖的鄰接矩陣表示 186
5.2.2 圖的鄰接表表示 189
*5.2.3 圖的其他表示方法 192
5.3 圖的遍歷 195
5.3.1 圖的深度優先遍歷 195
5.3.2 圖的廣度優先遍歷 197
5.3.3 圖遍歷的套用 198
*5.3.4 圖的連通性 200
*5.4 有向圖與有向無環圖 201
5.4.1 有向圖的連通性和傳遞閉包 202
*5.4.2 有向無環圖和拓撲排序 204
*5.4.3 關鍵路徑 207
5.5 最小生成樹 208
5.5.1 圖的生成樹與最小生成樹 209
5.5.2 普里姆(Prim)算法 210
5.5.3 克魯斯卡爾(Kruskal)算法 213
5.5.4 貪心算法 215
5.6 最短路徑問題 218
5.6.1 單源最短路徑 218
5.6.2 全源最短路徑 220
5.6.3 動態規划算法 223
5.7 圖套用例——城市間公路交通網問題 227
5.7.1 問題描述 227
5.7.2 問題求解思路 228
習題 228
上機練習題 230
第6章 查找 231
6.1 線性查找表 231
6.1.1 順序查找 232
6.1.2 折半查找 232
*6.1.3 斐波那契查找 234
6.1.4 線性查找表的性能比較 234
6.2 二叉搜尋樹查找性能 235
6.3 AVL樹 236
6.3.1 BST的旋轉操作 237
6.3.2 AVL樹的插入和平衡化旋轉 238
*6.3.3 AVL樹的刪除 240
*6.3.4 AVL樹的性能 241
6.4 B-樹 242
6.4.1 多路動態搜尋樹 242
6.4.2 B-樹的查找 243
6.4.3 B-樹的插入 244
*6.4.4 B-樹的刪除 245
6.5 散列方法 246
6.5.1 散列技術 246
6.5.2 散列函式 247
6.5.3 衝突處理 250
6.5.4 散列的刪除 252
6.5.5 散列的性能 252
6.6 靜態索引結構 253
6.6.1 索引查找 253
6.6.2 索引存儲方式 254
*6.6.3 索引檔案結構 255
6.7 模式匹配 258
6.7.1 字元串及其ADT 258
6.7.2 字元串的存儲表示 259
6.7.3 字元串的模式匹配及簡單匹配算法 259
6.7.4 字元串匹配的KMP算法 260
習題 263
上機練習題 264
第7章 排序 265
7.1 排序的概念及算法性能分析 265
7.2 基本排序方法 266
7.2.1 冒泡排序 267
7.2.2 插入排序 268
7.2.3 直接選擇排序 272
7.2.4 基本排序方法的比較 273
7.3 快速排序 274
7.3.1 快速排序的過程 274
7.3.2 快速排序的性能分析 275
7.4 歸併排序 276
7.4.1 二路歸併 276
7.4.2 自底向上的歸併排序 276
7.4.3 自頂向下的歸併排序 278
*7.5 錦標賽排序 279
7.6 堆排序 280
7.6.1 堆排序的思想 280
7.6.2 堆排序的實現 282
7.7 內排序方法分析 283
*7.7.1 排序方法的下界 283
7.7.2 內排序方法的比較 284
7.8 線性時間複雜度的排序算法 285
*7.8.1 計數排序 285
7.8.2 基數排序 287
7.9 外部排序 290
7.9.1 外部排序方法 290
*7.9.2 基於敗者樹的k路歸併方法 291
*7.9.3 排序——歸併的改進 292
習題 296
上機練習題 297
實驗指導 298
實驗一 順序表及其套用 299
實驗二 求解迷宮問題 301
實驗三 簡單算術表達式的處理 302
實驗四 求解簡單背包問題 303
實驗五 鍊表及其套用 304
實驗六 實驗室機時機位的管理 305
實驗七 實現Huffman編碼 307
實驗八 檔案管理的模擬 309
實驗九 求網路站點間的最短連線 312
實驗十 查找最高分與次高分 314
實驗十一 比賽日程安排與成績統計 316
