本書用輕松的圖解方式來(lái)講解數(shù)據(jù)結(jié)構(gòu)，全書采用豐富的圖例闡述數(shù)據(jù)結(jié)構(gòu)的基本概念及應(yīng)用，并將重要理論、演算方法做詳細(xì)的詮釋與舉例，是一本兼具內(nèi)容及專業(yè)的數(shù)據(jù)結(jié)構(gòu)的教學(xué)用書。
由于作者長(zhǎng)期從事信息教育及寫作，在文字的表達(dá)上簡(jiǎn)潔明了、邏輯清晰，并安排了大量的習(xí)題，供讀者檢驗(yàn)學(xué)習(xí)成果。
數(shù)據(jù)結(jié)構(gòu)毫無(wú)疑問(wèn)是計(jì)算機(jī)科學(xué)既經(jīng)典又核心的課程之一，不管是從事計(jì)算機(jī)軟件還是硬件的開(kāi)發(fā)工作，如果沒(méi)有系統(tǒng)地學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)或者是沒(méi)有專心自學(xué)過(guò)，很容易被人打上“非專業(yè)”的標(biāo)簽。對(duì)于任何在信息技術(shù)行業(yè)工作的專業(yè)人員或者想進(jìn)入此行業(yè)的人來(lái)說(shuō)，什么時(shí)候開(kāi)始學(xué)數(shù)據(jù)結(jié)構(gòu)都不會(huì)晚，更不會(huì)過(guò)時(shí)。
從“數(shù)據(jù)結(jié)構(gòu)”的名字看，它不僅僅只是講授數(shù)據(jù)的結(jié)構(gòu)以及在計(jì)算機(jī)內(nèi)如何存儲(chǔ)和組織數(shù)據(jù)的方式，這些只是它的表面現(xiàn)象。數(shù)據(jù)結(jié)構(gòu)背后真正蘊(yùn)含的是與之息息相關(guān)的算法，精心選擇的數(shù)據(jù)結(jié)構(gòu)配合恰如其分的算法就意味著數(shù)據(jù)或者信息在計(jì)算機(jī)內(nèi)被高效率地存儲(chǔ)和高效率地處理。算法其實(shí)就是數(shù)據(jù)結(jié)構(gòu)的靈魂，它既神秘又神奇“好玩”，當(dāng)然對(duì)初學(xué)者也比較難，算法可以說(shuō)是“聰明人在計(jì)算機(jī)上的游戲”。
本書是一本綜合而且全面講述數(shù)據(jù)結(jié)構(gòu)及其算法分析的教科書，為了便于高校的教學(xué)或者讀者自學(xué)，作者在描述數(shù)據(jù)結(jié)構(gòu)原理和算法時(shí)文字清晰并且嚴(yán)謹(jǐn)，為每個(gè)算法及其數(shù)據(jù)結(jié)構(gòu)提供了演算的詳細(xì)圖解。另外，為了適合在教學(xué)中讓學(xué)生上機(jī)實(shí)踐或者自學(xué)者上機(jī)“操練”，本書為每個(gè)經(jīng)典的算法都提供了C語(yǔ)言編寫的完整范例程序的源代碼，每個(gè)范例程序都不需要經(jīng)過(guò)修改，直接通過(guò)編譯就可以運(yùn)行，目的就是讓本書的學(xué)習(xí)者以這些范例程序作為參照迅速掌握數(shù)據(jù)結(jié)構(gòu)和算法的要點(diǎn)。
全書的所有范例程序都可以在標(biāo)準(zhǔn)的C語(yǔ)言編程環(huán)境中編譯通過(guò)并且成功運(yùn)行，我們?cè)诟木幈緯倪^(guò)程中選用了免費(fèi)的Dev C++ 5.11集成開(kāi)發(fā)環(huán)境，對(duì)原書的所有范例程序進(jìn)行編譯、修改、調(diào)試和測(cè)試，并確保它們都可以準(zhǔn)確無(wú)誤地運(yùn)行。附錄A包含了“C/C++編譯程序的介紹與安裝”，其中重點(diǎn)就介紹了Dev C++。附錄B則包含了“C語(yǔ)言快速入門”。
序
數(shù)據(jù)結(jié)構(gòu)一直是計(jì)算機(jī)信息相關(guān)學(xué)科的必修科目，對(duì)于第一次接觸數(shù)據(jù)結(jié)構(gòu)課程的學(xué)生來(lái)說(shuō)，內(nèi)容過(guò)多及表達(dá)不清楚常常是造成學(xué)習(xí)障礙最主要的因素，為了讓讀者能用最輕松的方式快速理解數(shù)據(jù)結(jié)構(gòu)，本書特別征詢多位教師意見(jiàn)，采用豐富的圖例來(lái)闡述基本概念及應(yīng)用，并且將重要理論和演算方法做了非常詳實(shí)的詮釋，是一本兼具內(nèi)容及專業(yè)的數(shù)據(jù)結(jié)構(gòu)教學(xué)用書。
由于筆者長(zhǎng)期從事咨詢教育及寫作工作，在文句的表達(dá)上盡量以簡(jiǎn)潔有力、邏輯清楚闡述為主。為了驗(yàn)收各章的學(xué)習(xí)成果，特別搜集了大量的習(xí)題，并參閱重要考試，提供給讀者更多的實(shí)戰(zhàn)演練經(jīng)驗(yàn)。
另外，為了減輕讀者的學(xué)習(xí)壓力及經(jīng)濟(jì)負(fù)擔(dān)，在整本書所涉及的主題分量不減的情況下，書中僅收錄精華的演算方法及程式范例的執(zhí)行畫面，本書所有的程序代碼在提供的下載地址中可以下載，讀者可直接下載并運(yùn)行驗(yàn)證。最后希望本書能帶給各位對(duì)數(shù)據(jù)結(jié)構(gòu)更完整的認(rèn)識(shí)。
胡昭民 敬筆
胡昭民，現(xiàn)任榮欽科技股份有限公司董事長(zhǎng)，美國(guó)Rochester Institute of Technology計(jì)算機(jī)科學(xué)研究所畢業(yè)，長(zhǎng)期從事信息教育及計(jì)算機(jī)圖書寫作的工作，并監(jiān)制過(guò)多套游戲及教學(xué)軟件的研發(fā)。
第1章 數(shù)據(jù)結(jié)構(gòu)導(dǎo)論 1
1-1 數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介 2
1-1-1 數(shù)據(jù)與信息 2
1-1-2 算法 3
1-1-3 算法的條件 3
1-1-4 數(shù)據(jù)結(jié)構(gòu)的應(yīng)用 6
1-2 數(shù)據(jù)抽象化 7
1-2-1 基本數(shù)據(jù)類型 7
1-2-2 抽象數(shù)據(jù)類型 7
1-3 算法與程序設(shè)計(jì) 8
1-3-1 認(rèn)識(shí)程序設(shè)計(jì) 8
1-3-2 程序開(kāi)發(fā)流程 9
1-3-3 程序設(shè)計(jì)的風(fēng)格 9
1-4 面向?qū)ο蟪绦蛟O(shè)計(jì) 11
1-4-1 封裝（Encapsulation） 12
1-4-2 繼承（Inheritance） 13
1-4-3 多態(tài)（Polymorphism） 13
1-5 模塊化設(shè)計(jì)與C語(yǔ)言 13
1-5-1 函數(shù)的基本概念 13
1-5-2 參數(shù)類型的介紹 14
1-5-3 參數(shù)的傳遞方式 15
1-6 遞歸算法 15
1-6-1 遞歸的定義 15
1-6-2 斐波拉契數(shù)列 17
1-6-3 漢諾塔問(wèn)題 18
1-7 程序效率的分析 23
1-7-1 Big-oh 25
1-7-2 Ω(omega) 26
1-7-3 θ(theta) 27
本章習(xí)題 27
第2章 線性表 32
2-1 線性表的定義 33
2-1-1 線性表的用途 33
2-2 數(shù)組 34
2-2-1 一維數(shù)組 34
2-2-2 二維數(shù)組 36
2-2-3 多維數(shù)組 40
2-2-4 結(jié)構(gòu)數(shù)組 44
2-2-5 字符數(shù)組 46
2-2-6 字符串?dāng)?shù)組 48
2-2-7 指針數(shù)組 49
2-3 矩陣 50
2-3-1 矩陣的運(yùn)算 51
2-3-2 稀疏矩陣 53
2-3-3 上三角形矩陣 55
2-3-4 下三角形矩陣 59
2-3-5 帶狀矩陣 64
本章習(xí)題 65
第3章 鏈表 69
3-1 動(dòng)態(tài)分配內(nèi)存 70
3-1-1 C的動(dòng)態(tài)分配變量 70
3-1-2 C++的動(dòng)態(tài)分配變量 72
3-2 單向鏈表 73
3-2-1 建立單向鏈表 74
3-2-2 遍歷單向鏈表 75
3-2-3 釋放單向鏈表節(jié)點(diǎn)的空間 76
3-2-4 單向鏈表插入新節(jié)點(diǎn) 77
3-2-5 單向鏈表刪除節(jié)點(diǎn) 79
3-2-6 單向鏈表的反轉(zhuǎn) 81
3-3 環(huán)形鏈表 83
3-3-1 環(huán)形鏈表的建立與遍歷 83
3-3-2 環(huán)形鏈表中插入新節(jié)點(diǎn) 85
3-3-3 環(huán)形鏈表節(jié)點(diǎn)的刪除 86
3-3-4 環(huán)形鏈表的連接功能 88
3-4 雙向鏈表 89
3-4-1 雙向鏈表的建立與遍歷 90
3-4-2 雙向鏈表中加入新節(jié)點(diǎn) 92
3-4-3 雙向鏈表節(jié)點(diǎn)的刪除 94
3-5 鏈表相關(guān)應(yīng)用簡(jiǎn)介 96
3-5-1 多項(xiàng)式表式法 96
3-5-2 稀疏矩陣表示法 100
本章習(xí)題 102
第4章 堆棧與隊(duì)列 109
4-1 堆棧簡(jiǎn)介 110
4-1-1 堆棧的基本操作 111
4-1-2 用數(shù)組實(shí)現(xiàn)堆棧 111
4-1-3 用鏈表實(shí)現(xiàn)堆棧 112
4-1-4 堆棧類樣板的實(shí)現(xiàn) 114
4-1-5 老鼠走迷宮 116
4-1-6 八皇后問(wèn)題 119
4-2 算術(shù)表達(dá)式的表示法 120
4-2-1 中序轉(zhuǎn)為前序與后序 121
4-2-2 前序與后序轉(zhuǎn)為中序 126
4-2-3 中序表示法求值 129
4-2-4 前序法的求值運(yùn)算 130
4-2-5 后序法的求值運(yùn)算 131
4-3 隊(duì)列 132
4-3-1 隊(duì)列的基本操作 133
4-3-2 用數(shù)組實(shí)現(xiàn)隊(duì)列 133
4-3-3 環(huán)形隊(duì)列 135
4-3-4 雙向隊(duì)列 139
4-3-5 雙向隊(duì)列 141
4-3-6 優(yōu)先隊(duì)列 143
本章習(xí)題 144
第5章 樹(shù)狀結(jié)構(gòu) 156
5-1 樹(shù)的基本概念 157
5-1-1 專有名詞介紹 158
5-2 二叉樹(shù) 159
5-2-1 二叉樹(shù)的特性 159
5-2-2 特殊二叉樹(shù)簡(jiǎn)介 160
5-3 二叉樹(shù)的存儲(chǔ)方式 161
5-3-1 一維數(shù)組表示法 161
5-3-2 鏈表表示法 164
5-4 二叉樹(shù)的遍歷 166
5-4-1 中序遍歷 166
5-4-2 后序遍歷 167
5-4-3 前序遍歷 167
5-4-4 二叉樹(shù)節(jié)點(diǎn)的插入與刪除 170
5-4-5 二叉運(yùn)算樹(shù) 174
5-5 線索二叉樹(shù) 176
5-5-1 二叉樹(shù)轉(zhuǎn)為線索二叉樹(shù) 176
5-6 樹(shù)的二叉樹(shù)表示法 180
5-6-1 樹(shù)轉(zhuǎn)化為二叉樹(shù) 180
5-6-2 二叉樹(shù)轉(zhuǎn)換成樹(shù) 182
5-6-3 森林化為二叉樹(shù) 183
5-6-4 二叉樹(shù)轉(zhuǎn)換成森林 184
5-6-5 樹(shù)與森林的遍歷 185
5-6-6 確定唯一二叉樹(shù) 189
5-7 優(yōu)化二叉查找樹(shù) 191
5-7-1 擴(kuò)充二叉樹(shù) 191
5-7-2 霍夫曼樹(shù) 192
5-8 平衡樹(shù) 194
5-8-1 平衡樹(shù)的定義 194
5-9 高級(jí)樹(shù)狀結(jié)構(gòu)的研究 196
5-9-1 決策樹(shù) 196
5-9-2 B樹(shù) 198
5-9-3 二叉空間分割樹(shù) 198
5-9-4 四叉樹(shù)與八叉樹(shù) 199
本章習(xí)題 200
第6章 圖形結(jié)構(gòu) 210
6-1 圖形簡(jiǎn)介 211
6-1-1 圖的定義 212
6-1-2 無(wú)向圖 212
6-1-3 有向圖 214
6-2 圖的數(shù)據(jù)表示法 215
6-2-1 鄰接矩陣法 215
6-2-2 鄰接表法 218
6-2-3 鄰接復(fù)合鏈表法 220
6-2-4 索引表格法 222
6-3 圖的遍歷 225
6-3-1 深度優(yōu)先遍歷法 225
6-3-2 廣度優(yōu)先遍歷法 227
6-4 生成樹(shù) 229
6-4-1 DFS生成樹(shù)和BFS生成樹(shù) 229
6-4-2 最小生成樹(shù) 231
6-4-3 Kruskal算法 231
6-4-4 Prim算法 235
6-5 圖的最短路徑 236
6-5-1 單點(diǎn)對(duì)全部頂點(diǎn) 237
6-5-2 兩兩頂點(diǎn)間的最短路徑 240
6-6 AOV網(wǎng)絡(luò)與拓?fù)渑判?244
6-6-1 拓?fù)渑帕泻?jiǎn)介 244
6-7 AOE網(wǎng)絡(luò) 246
6-7-1 關(guān)鍵路徑 246
本章習(xí)題 248
第7章 排序 257
7-1 排序簡(jiǎn)介 258
7-1-1 排序的分類 259
7-2 內(nèi)部排序法 260
7-2-1 冒泡排序法 260
7-2-2 選擇排序法 262
7-2-3 插入排序法 264
7-2-4 希爾排序法 266
7-2-5 合并排序法 268
7-2-6 快速排序法 269
7-2-7 堆積排序法 271
7-2-8 基數(shù)排序法 278
7-3 外部排序法 280
7-3-1 直接合并排序法 280
7-3-2 k路合并法 284
7-3-3 多相合并法 284
本章習(xí)題 285
第8章 查找 295
8-1 常見(jiàn)的查找方法 296
8-1-1 順序查找法 296
8-1-2 二分查找法 297
8-1-3 插值查找法 299
8-1-4 斐波那契查找法 301
8-2 哈希查找法 305
8-2-1 哈希法簡(jiǎn)介 305
8-3 常見(jiàn)的哈希函數(shù) 306
8-3-1 除留余數(shù)法 306
8-3-2 平方取中法 307
8-3-3 折疊法 308
8-3-4 數(shù)字分析法 308
8-4 碰撞與溢出問(wèn)題的處理 309
8-4-1 線性探測(cè)法 309
8-4-2 平方探測(cè) 310
8-4-3 再哈希 310
8-4-4 鏈表 311
本章習(xí)題 312
附錄A C/C++編譯程序的介紹與安裝 318
A-1 C/C++編譯程序簡(jiǎn)介 319
A-1-1 Visual C++ 2010 Express 319
A-1-2 C++ Builder 320
A-1-3 Visual C++ 320
A-1-4 Dev C++ 321
A-1-5 GCC 322
A-2 Dev C++的安裝與介紹 322
A-2-1 下載Dev-C++ 323
A-2-2 安裝Dev C++ 323
附錄B C語(yǔ)言快速入門介紹與安裝 329
B-1 輕松學(xué)C程序 330
B-1-1 編譯與執(zhí)行 331
B-1-2 編譯程序 332
B-1-3 開(kāi)始執(zhí)行程序 333
B-2 C的基本數(shù)據(jù)處理 333
B-2-1 變量 333
B-2-2 常數(shù) 334
B-2-3 數(shù)據(jù)類型簡(jiǎn)介 334
B-3 C語(yǔ)言的輸出與輸入 335
B-3-1 printf()函數(shù) 336
B-3-2 scanf()函數(shù) 337
B-4 流程控制 338
B-4-1 順序結(jié)構(gòu) 338
B-4-2 選擇結(jié)構(gòu) 339
B-4-3 重復(fù)結(jié)構(gòu) 343
B-5 數(shù)組簡(jiǎn)介 346
B-5-1 字符串簡(jiǎn)介 347
B-5-2 字符串?dāng)?shù)組 347
B-6 函數(shù)介紹 349
B-6-1 傳遞參數(shù)的方式 350
B-6-2 標(biāo)準(zhǔn)函數(shù)庫(kù) 352
第8章 查找
在數(shù)據(jù)處理過(guò)程中，是否能在最短時(shí)間內(nèi)查找到所需要的數(shù)據(jù)，是一個(gè)相當(dāng)值得信息從業(yè)人員關(guān)心的問(wèn)題。所謂查找（search，或搜索）指的是從數(shù)據(jù)文件中找出滿足某些條件的記錄。用以查找的條件稱為“鍵值”（key），就如同排序所用的鍵值一樣。
例如聯(lián)系人中找某人的電話號(hào)碼，那么這個(gè)人的姓名就成為在聯(lián)系人中查找電話號(hào)碼的鍵值。通常影響查找時(shí)間長(zhǎng)短的主要因素包括算法的選擇、數(shù)據(jù)存儲(chǔ)的方式和結(jié)構(gòu)。
8-1 常見(jiàn)的查找方法
如果根據(jù)數(shù)據(jù)量的大小，可將查找分為：
1. 內(nèi)部查找：數(shù)據(jù)量較小的文件，可以一次性全部加載到內(nèi)存中進(jìn)行查找。
2. 外部查找：數(shù)據(jù)量大的文件，無(wú)法一次加載到內(nèi)存中處理，而需使用輔助存儲(chǔ)器來(lái)分次處理。
如果從另一個(gè)角度來(lái)看，查找的技巧又可分為“靜態(tài)查找”和“動(dòng)態(tài)查找”兩種。定義如下所示。
1. 靜態(tài)查找：指的是在查找過(guò)程中，查找的表格或文件的內(nèi)容不會(huì)被改動(dòng)。例如符號(hào)表的查找就是一種靜態(tài)查找。
2. 動(dòng)態(tài)查找：指的是在查找過(guò)程中，查找的表格或文件的內(nèi)容可能會(huì)被改動(dòng)，例如在樹(shù)狀結(jié)構(gòu)中所談的B-tree查找就屬于一種動(dòng)態(tài)查找。
至于查找技巧中比較常見(jiàn)的方法有順序法、二分查找法、斐波那契法、插值法、哈希法、m路查找樹(shù)、B-tree等。為了讓大家能確實(shí)掌握各種查找的技巧和基本原理，以便應(yīng)用于日后的各種領(lǐng)域，現(xiàn)將幾個(gè)主要的查找方法分述于后。
8-1-1 順序查找法
順序查找通常用于未經(jīng)組織化的文件，又稱為線性查找。查找的過(guò)程從文件第一項(xiàng)數(shù)據(jù)開(kāi)始，按序比較每個(gè)鍵值。由于順序查找法是逐項(xiàng)對(duì)比，因此只要一找到數(shù)據(jù)就可以結(jié)束數(shù)據(jù)的查找。以n項(xiàng)數(shù)據(jù)為例，使用順序查找法來(lái)查找數(shù)據(jù)時(shí)，有可能在第1項(xiàng)就找到了，在這種情形下僅需執(zhí)行一次比較操作。如果數(shù)據(jù)在第2項(xiàng)、第3項(xiàng)…第n項(xiàng)，則其需要的比較次數(shù)分別為2、3、4、…、n次。因此，在平均情況下，順序查找法，查找一項(xiàng)數(shù)據(jù)需要的平均比較次數(shù)為 (n+1)/2。
現(xiàn)在以一個(gè)例子來(lái)說(shuō)明，假設(shè)已有數(shù)列74、53、61、28、99、46、88，若要查找28，則需要比較4次；要查找74僅需比較1次；要查找88則需查找7次，這表示當(dāng)查找的數(shù)列長(zhǎng)度n很大時(shí)，利用順序查找是不太適合的，它是一種適用于小數(shù)據(jù)文件的查找方法。
另外，在最差的情況下，逐一對(duì)比后沒(méi)有找到數(shù)據(jù)，則必須花費(fèi)n次，其最壞情況下（Worst Case）的時(shí)間復(fù)雜度為O(n)。也就是說(shuō)，除非可以預(yù)知要查找的數(shù)據(jù)大概位于文件的前端，否則當(dāng)文件的數(shù)據(jù)項(xiàng)數(shù)過(guò)大時(shí)，順序查找法在查找的效率上顯然不如其他的查找法。
線性查找法的優(yōu)點(diǎn)是文件或數(shù)據(jù)事前不需要經(jīng)過(guò)任何的處理與排序，也由于它未考慮到數(shù)據(jù)的特征對(duì)于查找的影響，所以在應(yīng)用上適合于各種情況，其缺點(diǎn)則是查找的速度較慢。
順序查找法的C語(yǔ)言算法如下所示。
while (val!=-1)
{
find=0;
printf("請(qǐng)輸入查找鍵值(1-150)，輸入-1離開(kāi)：");
scanf("%d",&val);
for (i=0;i<80;i++)
{
if(data[i]==val)
{
printf("在第 %3d個(gè)位置找到鍵值 [%3d]\n",i+1,data[i]);
find++;
}
}
if(find==0 && val !=-1)
printf("######沒(méi)有找到 [%3d]######\n",val);
}
8.1.1
請(qǐng)?jiān)O(shè)計(jì)一個(gè)C程序，以隨機(jī)數(shù)生成1~150之間的80個(gè)整數(shù)，然后實(shí)現(xiàn)順序查找法的過(guò)程。
請(qǐng)參考程序CH08_01.c，本范例程序的運(yùn)行結(jié)果如圖8-1所示。
圖8-1 實(shí)現(xiàn)順序查找法的范例程序的運(yùn)行結(jié)果
8-1-2 二分查找法
如果要查找的數(shù)據(jù)已經(jīng)事先排好序了，則可使用二分查找法來(lái)進(jìn)行查找。二分查找法是將數(shù)據(jù)平均分割成兩份，再比較鍵值與中間值的大小，如果鍵值小于中間值，可確定要查找的數(shù)據(jù)在前半段，否則在后半部。如此分割數(shù)次直到找到或確定不存在為止。例如，以下已排序的數(shù)列 2、3、5、8、9、11、12、16、18 ，而所要查找值為11時(shí)：
首先跟第5個(gè)數(shù)值 9 比較，如圖8-2所示。
圖8-2 先和中值比較
因?yàn)?1＞9，所以和后半部的中間值 12 比較，如圖8-3所示：
圖8-3 再和后半部的中值比較
因?yàn)?11＜12，所以和前半部的中間值 11比較，如圖8-4所示：
圖8-4 再和后半部的前半部中值比較
因?yàn)?11=11，表示查找到了即查找完成，如果不相等則表示沒(méi)有找到。
二分查找法的C語(yǔ)言算法如下所示。
int bin_search(int data[50],int val)
{
int low,mid,high;
low=0;
high=49;
printf("查找過(guò)程中......\n");
while(low <= high && val !=-1)
{
mid=(low+high)/2;
if(val
{
printf("%d 介于位置 %d[%3d]和中間值 %d[%3d]，找左半邊\n",val,low+1, data[low],mid+1,data[mid]);
high=mid-1;
}
else if(val>data[mid])
{
printf("%d 介于中間值位置 %d[%3d] 和 %d[%3d]，找右半邊\n",val,mid+1, data[mid],high+1,data[high]);
low=mid+1;
}
else
return mid;
}
return -1;
……
新書資訊