圖書簡介：
本書依據(jù)高職高專計算機基礎(chǔ)教育的特點，結(jié)合作者多年從事計算機教育的經(jīng)驗編寫而成。全書共10章，主要內(nèi)容包括緒論、線性表、棧和隊列、串、數(shù)組及廣義表、樹、圖、查找、排序以及綜合實訓(xùn)。
本書以“工作場景導(dǎo)入”→“知識講解”→“回到工作場景”→“工作實訓(xùn)營”為主線編寫，以例題配合深入學(xué)習(xí)，知識講解細致。同時，每章都有配套的實訓(xùn)練習(xí)，突出了實用性和操作性，另外還提供了實踐中常見問題解析，能夠進一步拓展學(xué)生的知識，靈活應(yīng)對實際操作時會遇到的困難，使學(xué)生提高操作能力。本書結(jié)構(gòu)清晰、易教易學(xué)、實例豐富、可操作性強、學(xué)以致用、注重能力的培養(yǎng)。
本書注重實際應(yīng)用，既可作為高職高專院校計算機及相關(guān)專業(yè)的教材，也可作為各類培訓(xùn)班的培訓(xùn)教程。此外，本書也適合于有關(guān)工程技術(shù)人員、技師參考閱讀。
前 言
數(shù)據(jù)結(jié)構(gòu)課程是我國計算機教學(xué)中較早形成和完善的一門專業(yè)基礎(chǔ)課程，也是計算機課程體系的核心課程，是從事計算機軟件開發(fā)、應(yīng)用人員必備的專業(yè)基礎(chǔ)知識。如今數(shù)據(jù)結(jié)構(gòu)的教材也有很多，但經(jīng)常被采用的只有幾種，這些被采用的教材比較注重理論，適合計算機本科專業(yè)或者是更深層次的院校使用，卻忽略了可操作性。我們苦于尋找不到一本適合高職高專院校使用的數(shù)據(jù)結(jié)構(gòu)教材。于是，我們決定自己編寫一本主要適合高職高專學(xué)生使用的數(shù)據(jù)結(jié)構(gòu)教材，把數(shù)據(jù)結(jié)構(gòu)的經(jīng)典算法與實際的工作場景相結(jié)合，讓同學(xué)們輕松、快速地掌握這些算法，為將來走上工作崗位打下堅實的基礎(chǔ)。
本書每章通過導(dǎo)入工作場景引出問題，然后詳細講解用來解決問題的知識點，同學(xué)們開始就帶著問題來學(xué)習(xí)本章內(nèi)容，學(xué)完本章內(nèi)容就會發(fā)現(xiàn)工作場景的問題變得相當(dāng)簡單，從而掌握本章的重點內(nèi)容。本書主要講述了線性表、串、樹、圖等幾種數(shù)據(jù)結(jié)構(gòu)，以及查找、排序中的經(jīng)典算法。最后一章則是對前面各章的知識點的應(yīng)用，在學(xué)習(xí)完前面9章內(nèi)容后，讀者可以嘗試自己編寫程序。
本書具有以下特點。
(1) 結(jié)構(gòu)清晰、模式合理。以“工作場景導(dǎo)入”→“知識講解”→“回到工作場景”→“工作實訓(xùn)營”為主線編寫，以這種新穎的模式合理安排全文。
(2) 針對性強、實用性強。學(xué)生們最需要的是提高實際操作能力，本書正是以解決工作場景為中心展開內(nèi)容，每一章中都涵蓋了完成工作所需的知識和具體操作過程，因而具有很強的針對性與實用性。
(3) 上手快、易教學(xué)。通過具體案例引出問題，在掌握知識后立刻回到工作場景解決問題，使學(xué)生很快上手；以教與學(xué)的實際需要取材謀篇，方便教師教學(xué)。
(4) 安排實訓(xùn)，提高能力。除緒論和綜合實訓(xùn)外，每一章都安排了“工作實訓(xùn)營”板塊，針對問題給出明確的解決步驟，并對工作實踐中常見問題進行分析，使學(xué)生進一步提高操作能力。
本書組織精練，例題簡單，易于理解，并配合了各種類型的練習(xí)和實踐操作題，便于學(xué)生進一步掌握知識和提高操作能力。對于數(shù)據(jù)結(jié)構(gòu)中重要和較難理解、容易出錯的內(nèi)容，書中均加以特別強調(diào)和說明。本書后附有習(xí)題的參考答案，可供讀者學(xué)習(xí)時參考。
本書由張居曉、葛武滇、喬正洪、朱勝強編著。參與本書的編寫和資料整理的還有姜傳金、汪大鋒、何光明、王珊珊、吳濤濤、陳海燕、周海霞、毛幸甜、盧振俠、江梅、劉宇松等，在此表示感謝。
本書可作為高職高專、成人高校及應(yīng)用型本科計算機類專業(yè)的教材，也可作為各類工程技術(shù)人員的參考書，亦可供計算機愛好者自學(xué)使用。
由于編者水平有限，書中難免有不足和疏漏之處，懇請讀者批評指正。
編 者目 錄
第1章 緒論 1
1.1 什么是數(shù)據(jù)結(jié)構(gòu) 2
1.1.1 數(shù)據(jù)結(jié)構(gòu)的產(chǎn)生與發(fā)展 2
1.1.2 數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu) 3
1.1.3 數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu) 3
1.1.4 數(shù)據(jù)類型 5
1.2 算法與算法分析 7
1.2.1 算法 7
1.2.2 算法設(shè)計的目標(biāo) 7
1.2.3 算法設(shè)計的時間復(fù)雜度 8
1.2.4 算法設(shè)計的空間復(fù)雜度 9
本章小結(jié) 9
習(xí)題 10
第2章 線性表 13
2.1 工作場景導(dǎo)入 14
2.2 線性表的定義和基本操作 14
2.2.1 線性表的定義 14
2.2.2 線性表的基本操作 15
2.3 線性表的順序存儲結(jié)構(gòu) 16
2.3.1 順序表的特點 16
2.3.2 順序表的基本操作 16
2.4 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 19
2.4.1 單鏈表 19
2.4.2 雙向鏈表 25
2.4.3 循環(huán)鏈表 27
2.5 回到工作場景 28
2.6 工作實訓(xùn)營 32
2.6.1 訓(xùn)練實例 32
2.6.2 常見問題解析 36
本章小結(jié) 38
習(xí)題 39
第3章 棧和隊列 43
3.1 工作場景導(dǎo)入 44
3.2 棧 44
3.2.1 棧的概念及操作 45
3.2.2 棧的實現(xiàn)與基本操作 46
3.2.3 棧的應(yīng)用 51
3.3 隊列 55
3.3.1 隊列的概念及操作 55
3.3.2 循環(huán)隊列 56
3.3.3 隊列的基本操作實現(xiàn) 58
3.3.4 隊列的應(yīng)用 62
3.4 回到工作場景 66
3.5 工作實訓(xùn)營 71
3.5.1 訓(xùn)練實例一：模擬排隊看病 71
3.5.2 訓(xùn)練實例二：模擬計算器 74
3.5.3 常見問題解析 79
本章小結(jié) 80
習(xí)題 80
第4章 串 83
4.1 工作場景導(dǎo)入 84
4.2 串的基本概念 84
4.3 串的順序存儲結(jié)構(gòu)與基本操作 85
4.4 串的鏈?zhǔn)酱鎯Y(jié)構(gòu) 88
4.5 串的模式匹配 90
4.5.1 Brute.Force算法 91
4.5.2 KMP算法 92
4.6 回到工作場景 95
4.7 工作實訓(xùn)營 97
4.7.1 訓(xùn)練實例 97
4.7.2 常見問題解析 99
本章小結(jié) 99
習(xí)題 100
第5章 數(shù)組及廣義表 103
5.1 工作場景導(dǎo)入 104
5.2 數(shù)組的定義 104
5.3 數(shù)組的順序存儲結(jié)構(gòu)與實現(xiàn) 105
5.3.1 數(shù)組的順序存儲結(jié)構(gòu) 105
5.3.2 基本操作的實現(xiàn) 106
5.3.3 數(shù)組的應(yīng)用舉例 108
5.4 矩陣的壓縮存儲 112
5.4.1 特殊矩陣 112
5.4.2 稀疏矩陣 116
5.5 廣義表 119
5.5.1 廣義表的定義 119
5.5.2 廣義表的存儲結(jié)構(gòu) 119
5.5.3 廣義表的應(yīng)用 124
5.6 回到工作場景 125
5.7 工作實訓(xùn)營 127
5.7.1 訓(xùn)練實例 127
5.7.2 常見問題解析 128
本章小結(jié) 129
習(xí)題 130
第6章 樹 133
6.1 工作場景導(dǎo)入 134
6.2 樹的基本概念 134
6.2.1 樹的定義 134
6.2.2 樹的基本術(shù)語 135
6.3 二叉樹 136
6.3.1 二叉樹的基本概念 136
6.3.2 二叉樹的存儲結(jié)構(gòu) 138
6.4 二叉樹的遍歷 143
6.4.1 二叉樹的前序遍歷 143
6.4.2 二叉樹的中序遍歷 144
6.4.3 二叉樹的后序遍歷 145
6.5 線索二叉樹 148
6.5.1 線索二叉樹的定義 148
6.5.2 中序線索二叉樹 149
6.6 樹和森林 151
6.6.1 樹的存儲結(jié)構(gòu) 151
6.6.2 森林、樹、二叉樹的相互轉(zhuǎn)化 153
6.6.3 樹和森林的遍歷 155
6.7 哈夫曼樹及其應(yīng)用 155
6.7.1 哈夫曼樹的概念 156
6.7.2 哈夫曼編碼 158
6.8 回到工作場景 161
6.9 工作實訓(xùn)營 164
6.9.1 訓(xùn)練實例 164
6.9.2 常見問題解析 167
本章小結(jié) 168
習(xí)題 168
第7章 圖 171
7.1 工作場景導(dǎo)入 172
7.2 圖的基本概念與存儲方式 172
7.2.1 鄰接矩陣表示法 175
7.2.2 鄰接表表示法 178
7.3 圖的遍歷 179
7.3.1 深度優(yōu)先搜索遍歷 179
7.3.2 廣度優(yōu)先搜索遍歷 180
7.3.3 遍歷算法的實現(xiàn) 182
7.4 生成樹和最小生成樹 185
7.4.1 生成樹 185
7.4.2 最小生成樹 185
7.4.3 普里姆算法 186
7.4.4 克魯斯卡爾算法 190
7.5 最短路徑 196
7.5.1 單源點最短路徑 197
7.5.2 所有頂點對最短路徑問題 199
7.6 回到工作場景 199
7.7 工作實訓(xùn)營 202
7.7.1 訓(xùn)練實例 202
7.7.2 常見問題解析 205
本章小結(jié) 207
習(xí)題 208
第8章 查找 211
8.1 工作場景導(dǎo)入 212
8.2 查找的基本概念 212
8.3 順序查找 213
8.4 二分查找 214
8.5 分塊查找 217
8.6 二叉查找樹 220
8.6.1 二叉查找樹的定義 220
8.6.2 二叉查找樹的插入 221
8.6.3 二叉查找樹的查找 222
8.6.4 二叉查找樹的刪除 224
8.7 哈希表 227
8.7.1 構(gòu)造哈希函數(shù)的方法 228
8.7.2 哈希沖突解決方法 229
8.7.3 哈希表的查找與分析 235
8.8 回到工作場景 237
8.9 工作實訓(xùn)營 238
8.9.1 訓(xùn)練實例 238
8.9.2 常見問題解析 240
本章小結(jié) 241
習(xí)題 242
第9章 排序 245
9.1 工作場景導(dǎo)入 246
9.2 排序的基本概念 246
9.3 插入排序 247
9.3.1 直接插入排序 247
9.3.2 希爾排序 248
9.4 交換排序 250
9.4.1 冒泡排序 250
9.4.2 快速排序 251
9.5 選擇排序 252
9.5.1 直接選擇排序 252
9.5.2 堆排序 254
9.6 歸并排序 256
9.6.1 二路歸并排序 256
9.6.2 二路歸并排序的實現(xiàn) 257
9.7 回到工作場景 259
9.8 工作實訓(xùn)營 260
9.8.1 訓(xùn)練實例 260
9.8.2 常見問題解析 262
本章小結(jié) 264
習(xí)題 264
第10章 綜合實訓(xùn) 267
10.1 綜合實訓(xùn)一 268
10.1.1 案例導(dǎo)入 268
10.1.2 問題解析 268
10.1.3 設(shè)計目標(biāo) 269
10.1.4 代碼編寫 269
10.1.5 調(diào)試運行 279
10.2 綜合實訓(xùn)二 279
10.2.1 案例導(dǎo)入 279
10.2.2 問題解析 280
10.2.3 設(shè)計目標(biāo) 280
10.2.4 代碼編寫 281
10.2.5 調(diào)試運行 285
10.3 綜合實訓(xùn)三 287
10.3.1 案例導(dǎo)入 287
10.3.2 問題解析 287
10.3.3 設(shè)計目標(biāo) 287
10.3.4 代碼編寫 287
10.3.5 調(diào)試運行 295
附錄 習(xí)題參考答案 297
參考文獻 341
