本書主要講解如何將數(shù)據(jù)結(jié)構(gòu)概念用C++程序語言進(jìn)行實(shí)作。本書將復(fù)雜的理論結(jié)合圖文并茂的解說方式，并搭配豐富的圖表及范例介紹，將數(shù)據(jù)結(jié)構(gòu)中重要的觀念及演算方法加以詮釋，集中學(xué)習(xí)焦點(diǎn)。
本書適合數(shù)據(jù)結(jié)構(gòu)的初學(xué)者使用，也可以作為計(jì)算機(jī)相關(guān)專業(yè)的教科書。
數(shù)據(jù)結(jié)構(gòu)毫無疑問是計(jì)算機(jī)科學(xué)既經(jīng)典又核心的課程之一，不管是從事計(jì)算機(jī)軟件還是硬件的開發(fā)工作，如果沒有系統(tǒng)地學(xué)習(xí)過數(shù)據(jù)結(jié)構(gòu)或者沒有專心自學(xué)過，很容易被人打上“非專業(yè)”的標(biāo)簽。對(duì)于任何在信息技術(shù)行業(yè)工作的專業(yè)人員或者想進(jìn)入此行業(yè)的人來說，什么時(shí)候開始學(xué)數(shù)據(jù)結(jié)構(gòu)都不會(huì)晚，更不會(huì)過時(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é)者也比較難，算法可以說是“聰明人在計(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++語言編寫的完整范例程序?qū)嵗ò暾脑创a），每個(gè)范例程序都不需要經(jīng)過修改，直接通過編譯就可以運(yùn)行，目的就是讓本書的學(xué)習(xí)者以這些范例程序作為參照迅速掌握數(shù)據(jù)結(jié)構(gòu)和算法的要點(diǎn)。
全書的所有范例程序都可以在標(biāo)準(zhǔn)的C++語言編程環(huán)境中編譯通過并順利運(yùn)行，我們?cè)诟木幈緯倪^程中選用了免費(fèi)的DevC++5.11集成開發(fā)環(huán)境，對(duì)原書的所有范例程序進(jìn)行編譯、修改、調(diào)試和測(cè)試，并確保它們都可以準(zhǔn)確無誤地運(yùn)行。附錄A包含了“C/C++編譯程序的介紹與安裝”，其中重點(diǎn)就介紹了DevC++。附錄B則包含了“C++程序設(shè)計(jì)語言簡(jiǎn)介”。
胡昭民，現(xiàn)任榮欽科技股份有限公司董事長(zhǎng)，美國(guó)Rochester Institute of Technology計(jì)算機(jī)科學(xué)研究所畢業(yè)，長(zhǎng)期從事信息教育及計(jì)算機(jī)圖書寫作的工作，并監(jiān)制過多套游戲及教學(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ù)結(jié)構(gòu)的應(yīng)用 2
1.1.2 算法 4
1.1.3 算法的描述工具 5
1.2 認(rèn)識(shí)程序設(shè)計(jì) 7
1.2.1 高級(jí)程序設(shè)計(jì)語言 7
1.2.2 程序設(shè)計(jì)要領(lǐng) 8
1.3 程序設(shè)計(jì)的風(fēng)格 8
1.3.1 自頂向下與模塊化設(shè)計(jì) 8
1.3.2 可讀性設(shè)計(jì) 8
1.3.3 控制結(jié)構(gòu)設(shè)計(jì) 9
1.3.4 面向?qū)ο笤O(shè)計(jì) 10
1.4 面向?qū)ο笤O(shè)計(jì)與C++ 12
1.4.1 C++的面向?qū)ο蠊δ?12
1.4.2 類的基本概念 13
1.4.3 訪問權(quán)限關(guān)鍵詞 14
1.4.4 繼承關(guān)系 15
1.4.5 多態(tài) 16
1.5 遞歸算法 17
1.5.1 遞歸的定義 17
1.5.2 斐波拉契數(shù)列 19
1.5.3 漢諾塔問題 20
1.6 程序效率的分析 25
1.6.1 Big-oh 27
1.6.2 Ω(omega) 28
1.6.3 θ(theta) 28
本章習(xí)題 29
第2章 線性表 33
2.1 線性表的定義 34
2.1.1 線性表的用途 34
2.2 數(shù)組 35
2.2.1 一維數(shù)組 35
2.2.2 二維數(shù)組 37
2.2.3 多維數(shù)組 41
2.2.4 結(jié)構(gòu)數(shù)組 45
2.2.5 C++的字符串 48
2.2.6 字符串?dāng)?shù)組 50
2.2.7 String類 51
2.2.8 指針數(shù)組 52
2.3 矩陣 54
2.3.1 矩陣的運(yùn)算 54
2.3.2 稀疏矩陣 57
2.3.3 上三角形矩陣 60
2.3.4 下三角形矩陣 62
2.3.5 帶狀矩陣 66
本章習(xí)題 66
第3章 鏈表 70
3.1 動(dòng)態(tài)分配內(nèi)存 71
3.1.1 C++的動(dòng)態(tài)分配變量 72
3.1.2 動(dòng)態(tài)配置數(shù)組 73
3.2 單向鏈表 74
3.2.1 單向鏈表的創(chuàng)建與遍歷 74
3.2.2 單向鏈表插入新節(jié)點(diǎn) 76
3.2.3 單向鏈表刪除節(jié)點(diǎn) 78
3.2.4 單向鏈表的反轉(zhuǎn) 80
3.3 環(huán)形鏈表 82
3.3.1 環(huán)形鏈表中插入新節(jié)點(diǎn) 83
3.3.2 環(huán)形鏈表節(jié)點(diǎn)的刪除 84
3.3.3 環(huán)形鏈表的連接功能 86
3.4 雙向鏈表 87
3.4.1 雙向鏈表的建立與遍歷 87
3.4.2 雙向鏈表中加入新節(jié)點(diǎn) 88
3.4.3 雙向鏈表節(jié)點(diǎn)的刪除 90
3.5 鏈表相關(guān)應(yīng)用簡(jiǎn)介 91
3.5.1 多項(xiàng)式表式法 92
3.5.2 稀疏矩陣表示法 95
本章習(xí)題 97
第4章 堆棧與隊(duì)列 103
4.1 堆棧簡(jiǎn)介 104
4.1.1 堆棧的基本操作 105
4.1.2 用數(shù)組實(shí)現(xiàn)堆棧 105
4.1.3 用鏈表實(shí)現(xiàn)堆棧 107
4.1.4 堆棧類樣板的實(shí)現(xiàn) 108
4.1.5 老鼠走迷宮 109
4.1.6 八皇后問題 112
4.2 算術(shù)表達(dá)式的表示法 114
4.2.1 中序轉(zhuǎn)為前序與后序 115
4.2.2 前序與后序轉(zhuǎn)為中序 120
4.2.3 中序表示法求值 122
4.2.4 前序法的求值運(yùn)算 124
4.2.5 后序法的求值運(yùn)算 125
4.3 隊(duì)列 125
4.3.1 隊(duì)列的基本操作 126
4.3.2 用數(shù)組實(shí)現(xiàn)隊(duì)列 126
4.4 隊(duì)列的相關(guān)應(yīng)用 129
4.4.1 環(huán)形隊(duì)列 129
4.4.2 雙向隊(duì)列 133
4.4.3 優(yōu)先隊(duì)列 134
本章習(xí)題 135
第5章 樹狀結(jié)構(gòu) 147
5.1 樹的基本概念 148
5.1.1 專有名詞介紹 149
5.2 二叉樹 150
5.2.1 二叉樹的特性 150
5.2.2 特殊二叉樹簡(jiǎn)介 152
5.3 二叉樹的存儲(chǔ)方式 153
5.3.1 一維數(shù)組表示法 153
5.3.2 鏈表表示法 155
5.4 二叉樹的遍歷 156
5.4.1 中序遍歷 157
5.4.2 后序遍歷 158
5.4.3 前序遍歷 158
5.4.4 二叉樹節(jié)點(diǎn)的插入與刪除 160
5.4.5 二叉運(yùn)算樹 165
5.5 線索二叉樹 167
5.5.1 二叉樹轉(zhuǎn)為線索二叉樹 167
5.6 樹的二叉樹表示法 171
5.6.1 樹轉(zhuǎn)化為二叉樹 171
5.6.2 二叉樹轉(zhuǎn)換成樹 173
5.6.3 森林化為二叉樹 174
5.6.4 二叉樹轉(zhuǎn)換成森林 175
5.6.5 樹與森林的遍歷 176
5.6.6 確定唯一二叉樹 180
5.7 優(yōu)化二叉查找樹 182
5.7.1 擴(kuò)充二叉樹 182
5.7.2 霍夫曼樹 184
5.8 平衡樹 185
5.8.1 平衡樹的定義 185
5.9 高級(jí)樹狀結(jié)構(gòu)的研究 187
5.9.1 決策樹 187
5.9.2 B樹 189
5.9.3 二叉空間分割樹 190
5.9.4 四叉樹與八叉樹 191
本章習(xí)題 192
第6章 圖形結(jié)構(gòu) 202
6.1 圖形簡(jiǎn)介 203
6.1.1 圖的定義 204
6.1.2 無向圖 204
6.1.3 有向圖 206
6.2 圖的數(shù)據(jù)表示法 207
6.2.1 鄰接矩陣法 207
6.2.2 鄰接表法 210
6.2.3 鄰接復(fù)合鏈表法 212
6.2.4 索引表格法 214
6.3 圖的遍歷 217
6.3.1 深度優(yōu)先遍歷法 217
6.3.2 廣度優(yōu)先遍歷法 219
6.4 生成樹 221
6.4.1 DFS生成樹和BFS生成樹 222
6.4.2 最小生成樹 223
6.4.3 Kruskal算法 224
6.4.4 Prim算法 227
6.5 圖的最短路徑 228
6.5.1 單點(diǎn)對(duì)全部頂點(diǎn) 229
6.5.2 兩兩頂點(diǎn)間的最短路徑 232
6.6 AOV網(wǎng)絡(luò)與拓樸排序 235
6.6.1 拓樸排列簡(jiǎn)介 236
6.7 AOE網(wǎng)絡(luò) 237
6.7.1 關(guān)鍵路徑 238
本章習(xí)題 239
第7章 排序 248
7.1 排序簡(jiǎn)介 249
7.1.1 排序的分類 250
7.2 內(nèi)部排序法 251
7.2.1 冒泡排序法 251
7.2.2 選擇排序法 254
7.2.3 插入排序法 256
7.2.4 希爾排序法 258
7.2.5 合并排序法 260
7.2.6 快速排序法 260
7.2.7 堆積排序法 263
7.2.8 基數(shù)排序法 269
7.3 外部排序法 272
7.3.1 直接合并排序法 272
7.3.2 k路合并法 275
7.3.3 多相合并法 276
本章習(xí)題 276
第8章 查找 286
8.1 常見的查找方法 287
8.1.1 順序查找法 287
8.1.2 二分查找法 288
8.1.3 插值查找法 290
8.1.4 斐波那契查找法 292
8.2 哈希查找法 295
8.2.1 哈希法簡(jiǎn)介 296
8.3 常見的哈希函數(shù) 297
8.3.1 除留余數(shù)法 297
8.3.2 平方取中法 297
8.3.3 折疊法 298
8.3.4 數(shù)字分析法 299
8.4 碰撞與溢出問題的處理 300
8.4.1 線性探測(cè)法 300
8.4.2 平方探測(cè) 301
8.4.3 再哈希 301
8.4.4 鏈表 301
本章習(xí)題 303
附錄A C/C++編譯程序的介紹與安裝 309
A.1 C/C++編譯程序簡(jiǎn)介 310
A.2 Dev C++的安裝與介紹 313
附錄B C++程序設(shè)計(jì)語言簡(jiǎn)介 319
B.1 C++語言的基本概念 320
B.2 C++語言的運(yùn)算符與表達(dá)式 323
B.3 C++語言的流程控制 327
B.4 C++語言的高級(jí)語法 332
B.5 C++語言與面向?qū)ο蟾拍?341
附錄C 數(shù)據(jù)結(jié)構(gòu)專有名詞索引 349
新書資訊