本書適合學過一門程式語言的各類讀者，包括在讀的大中專計算機專業學生、想轉行做開發的非專業人員、欲考計算機研究生的應屆或在職人員，以及工作後需要補學或溫習數據結構及算法的程式設計師等。
基本介紹
- 中文名：數據結構與算法套用實踐教程
- 策劃編輯：鄭 雙
- 責任編輯：鄭 雙
- 標準書號：ISBN 978-7-301-20052-0/TP·1211
內容簡介,圖書簡介,目錄,
內容簡介
本書和傳統同類書籍的區別是除了介紹基本的數據結構知識，如線性表、棧、佇列、鍊表、樹、二叉樹、AVL樹、紅黑樹、排序和查找之外，還引進了一些C語言中的記憶體分配、結構數組和結構指針的有關概念及常見問題分析；另外，還介紹了相應知識點的套用實踐。總的來說，本書選取的內容均側重於在實際中有廣泛套用的數據結構及算法，有很好的實用價值。本書介紹的所有數據結構及算法都以不同複雜程度給出其編碼實現。為了便於讀者自學，每章末附有小結及習題與思考。
本書系統介紹數據結構基礎理論知識及算法設計方法，它在內容選取上符合計算機學科和信息類學科人才培養目標的要求及教學規律和認知規律，在組織編排上體現“先理論、後套用、理論與套用相結合”的原則，併兼顧學科的廣度和深度，力求適用面廣。該書的編寫參考了國內外數據結構的最新教材和研究成果，全書共分為9章。第1章介紹數據結構的討論範疇、基本概念、數據的邏輯結構、物理結構及算法的描述與分析；第2章介紹一些重要的C語言概念，同時我們還對C語言常見問題進行分析。由於本書代碼都使用C語言來實現，因此具有C語言基礎知識對本書的學習是必不可少的；第3章介紹線性表各種存儲結構及相關套用；第4章介紹棧與佇列的基本概念、各種存儲結構及相關套用；第5章介紹字元串、多維數組和特殊矩陣的存儲結構及相關套用；第6章介紹樹、二叉樹和森林的基本概念、各種存儲結構及遍歷、線索化二叉樹、二叉排序樹及相關套用；第7章介紹圖的概念、各種存儲結構及遍歷、最小生成樹、關鍵路徑、拓撲排序、最短路徑及相關套用；第8章介紹了5種基本的排序算法，插入排序、交換排序、選擇排序、歸併排序和基數排序及相關套用；第9章介紹查找的基本概念、靜態查找表及動態查找表的實現算法及相關套用。
圖書簡介
數據結構與算法套用實踐教程/李文書主編. —北京：北京大學出版社，2012.2
(21世紀全國套用型本科計算機案例型規劃教材)
ISBN 978-7-301-20052-0
Ⅰ. ①數… Ⅱ. ①李… Ⅲ. ①數據結構—高等學校—教材②算法分析—高等學校—教材 Ⅳ. ①TP311.12
中國版本圖書館CIP數據核字(2012)第005200號
書 名：數據結構與算法套用實踐教程
著作責任者：李文書 主編
策劃編輯：鄭 雙
責任編輯：鄭 雙
標準書號：ISBN 978-7-301-20052-0/TP·1211
出 版 者：北京大學出版社
地 址：北京市海淀區成府路205號 100871
發 行 者：北京大學出版社
經 銷 者：新華書店
787毫米×1092毫米 16開本 19印張 435千字
2012年2月第1版 2012年2月第1次印刷
定 價：36.00元
目錄
第1章 初識數據結構.... 1
1.1 數據結構討論範疇... 2
1.2 基本概念... 3
1.3 數據的邏輯結構... 4
1.4 數據的物理結構... 6
1.5 算法描述與分析... 7
1.5.1 算法的描述... 7
1.5.2 算法的分析... 7
本章小結... 10
習題與思考... 11
第2章 重要的C語言概念.... 12
2.1 記憶體分配... 13
2.1.1 靜態記憶體分配... 13
2.1.2 動態記憶體分配... 13
2.1.3 C語言程式編譯的
記憶體分配... 14
2.2 結構數組和結構指針... 16
2.2.1 結構數組... 16
2.2.2 結構指針... 17
2.2.3 位結構... 18
2.3 C語言常見問題分析... 19
2.3.1 指針和數組... 20
2.3.2 分支語句... 20
2.3.3 函式編寫... 21
2.3.4 void及void指針... 21
2.3.5 關於C語言的高效編程... 22
2.3.6 其他若干問題... 24
本章小結... 24
習題與思考... 25
第3章 線性表.... 26
3.1 線性表的概念... 27
3.1.1 線性表的定義... 27
3.1.2 線性表的抽象數據類型描述... 27
3.2 線性表的順序存儲... 28
3.2.1 順序表的定義... 28
3.2.2 順序表的基本運算... 29
3.3 單向鍊表... 31
3.3.1 單向鍊表的基本概念... 31
3.3.2 單向鍊表的存儲表示... 31
3.3.3 單向鍊表的基本操作... 32
3.4 循環鍊表... 37
3.5 雙向鍊表... 38
3.5.1 雙向鍊表的基本概念... 38
3.5.2 雙向鍊表的基本操作... 38
3.6 套用實踐... 40
3.6.1 單向鍊表排序問題... 40
3.6.2 自動預訂飛機票問題... 41
3.6.3 約瑟夫(Joseph)環問題... 43
本章小結... 45
習題與思考... 46
第4章 棧與佇列.... 47
4.1 棧... 48
4.1.1 棧的定義... 48
4.1.2 棧的順序存儲... 49
4.1.3 棧的鏈式存儲... 52
4.2 佇列... 54
4.2.1 佇列的定義... 54
4.2.2 佇列的順序存儲... 55
4.2.3 佇列的鏈式存儲... 61
4.3 套用實踐... 64
4.3.1 火車車廂重排問題... 64
4.3.2 四則運算表達式求值... 67
4.3.3 渡口管理問題... 72
4.3.4 農夫過河問題... 74
本章小結... 77
習題與思考... 78
第5章 串、多維數組與特殊矩陣.... 79
5.1 串... 80
5.1.1 串的類型定義... 80
5.1.2 串的順序存儲... 81
5.1.3 串的鏈式存儲... 88
5.2 串的模式匹配... 93
5.2.1 模式匹配的簡單算法... 93
5.2.2 KMP算法... 95
5.2.3 KMP模式匹配改進算法... 99
5.3 多維數組... 100
5.3.1 多維數組的類型定義... 100
5.3.2 多維數組的順序存儲表示... 101
5.4 特殊矩陣的壓縮存儲... 102
5.4.1 對稱矩陣... 102
5.4.2 三角矩陣... 103
5.4.3 對角矩陣... 104
5.5 稀疏矩陣... 105
5.5.1 稀疏矩陣的三元組表示法... 106
5.5.2 稀疏矩陣的十字鍊表法... 109
5.6 套用實踐... 112
5.6.1 漢諾塔問題... 112
5.6.2 最長重複字串... 113
5.6.3 稀疏矩陣的相加... 114
5.6.4 中文分詞... 116
本章小結... 117
習題與思考... 117
第6章 樹.... 119
6.1 樹的基本概念... 120
6.2 二叉樹... 122
6.2.1 二叉樹的基本概念... 122
6.2.2 二叉樹的性質... 123
6.2.3 二叉樹的存儲結構... 125
6.2.4 二叉樹的遍歷... 129
6.2.5 二叉樹的構造... 130
6.3 樹和森林... 133
6.3.1 樹、森林與二叉樹的轉換... 133
6.3.2 樹和森林的存儲表示... 134
6.3.3 樹和森林的遍歷... 138
6.4 線索二叉樹... 139
6.4.1 線索二叉樹的基本概念... 139
6.4.2 線索二叉樹的基本操作... 142
6.5 二叉排序樹... 146
6.5.1 二叉排序樹的基本概念... 146
6.5.2 二叉排序樹的生成... 147
6.5.3 二叉排序樹的插入... 147
6.5.4 二叉排序樹的刪除... 148
6.6 套用實踐... 149
6.6.1 等價類問題... 149
6.6.2 最優二叉樹(哈夫曼樹) 154
6.6.3 判定樹問題... 162
本章小結... 163
習題與思考... 164
第7章 圖.... 166
7.1 圖的基本概念... 167
7.2 圖的存儲方式... 170
7.2.1 鄰接矩陣... 171
7.2.2 鄰接表... 172
7.2.3 關聯矩陣... 175
7.3 圖的遍歷... 176
7.3.1 深度優先搜尋遍歷... 176
7.3.2 廣度優先搜尋遍歷... 179
7.4 最小生成樹... 181
7.4.1 生成樹的概念... 182
7.4.2 最小生成樹的概念... 183
7.4.3 普里姆(Prim)算法... 184
7.4.4 克魯斯卡爾(Kruskal)算法... 186
7.5 最短路徑... 189
7.5.1 單源最短路徑問題... 189
7.5.2 每一對頂點之間的
最短距離... 192
7.6 拓撲排序... 197
7.6.1 什麼是拓撲排序？... 197
7.6.2 拓撲排序的算法... 198
7.7 關鍵路徑... 201
7.8 套用實踐... 203
7.8.1 單源點最短路徑問題... 203
7.8.2 自由樹的直徑問題... 204
7.8.3 醫院選址問題... 205
本章小結... 206
習題與思考... 206
第8章 排序.... 209
8.1 基本概念... 210
8.2 插入排序... 211
8.2.1 直接插入排序... 211
8.2.2 折半插入排序... 213
8.2.3 希爾排序... 214
8.3 交換排序... 216
8.3.1 冒泡排序... 216
8.3.2 快速排序... 220
8.4 選擇排序... 223
8.4.1 直接選擇排序... 223
8.4.2 堆排序... 224
8.5 歸併排序... 227
8.5.1 2-路歸併的疊代算法... 228
8.5.2 2-路歸併的遞歸算法... 229
8.6 基數排序... 229
8.6.1 多關鍵字排序... 229
8.6.2 鏈式基數排序... 230
8.7 排序方法比較... 234
8.8 套用實踐... 235
8.8.1 荷蘭國旗問題... 235
8.8.2 雙向冒泡問題... 236
本章小結... 237
習題與思考... 237
第9章 查找.... 239
9.1 基本概念... 240
9.2 靜態查找... 241
9.2.1 順序查找... 241
9.2.2 折半查找... 242
9.2.3 分塊查找... 244
9.3 動態查找... 245
9.3.1 二叉排序樹查找... 245
9.3.2 AVL搜尋樹... 246
9.3.3 紅黑樹... 257
9.3.4 B-樹... 270
9.3.5 B+樹... 273
9.4 哈希查找... 273
9.4.1 哈希表的概念... 273
9.4.2 哈希函式的構造... 274
9.4.3 解決衝突的方法... 276
9.4.4 查找及分析... 280
9.5 套用實踐... 281
9.5.1 直方圖問題... 281
9.5.2 箱子裝載問題... 282
本章小結... 284
習題與思考... 284
附錄 關鍵字索引.... 286
參考文獻.... 289
