"編輯的話2008年，一本特立獨行的IT技術圖書《大話設計模式》橫空出世，開創了一種新派技術圖書風格，橫掃各大排行。作者程傑並沒有滿足這個成績，耗時3年潛心創作了另外一本同樣是程序員基礎的著作——《大話數據結構》，不出意外地好評如潮。直到今天，這兩本書仍然常駐各大排行。作為本土原創圖書，這個成績簡直不可思議——印像裡隻有國外經典技術圖書具備如此強的生命力。雖然在這十幾年裡程傑兄未再動筆，但依然與我保持著密切聯繫。非常榮幸的是，在這本新作中，我依然是他的編輯。十幾年來，IT技術等

●第1章數據結構緒論1
1.1開場白2
1.2你數據結構怎麼學的3
1.3數據結構起源4
1.4基本概念和術語5
1.4.1數據5
1.4.素6
1.4.3數據項7
1.4.4數據對像7
1.4.5數據結構7
1.5邏輯結構與物理結構8
1.5.1邏輯結構8
1.5.2物理結構9
1.6數據類型11
1.6.1數據類型定義11
1.6.2抽像數據類型12
1.7總結回顧13
1.8結尾語14
第2章算法15
2.1開場白16
2.2數據結構與算法的關繫16
2.3兩種算法的比較17
2.4算法定義18
2.5算法的特性19
2.5.1輸入輸出19
2.5.2有窮性19
2.5.3確定性20
2.5.4可行性20
2.6算法設計的要求20
2.6.1正確性21
2.6.2可讀性21
2.6.3健壯性21
2.6.4時間效率高和存儲量低22
2.7算法效率的度量方法22
2.7.1事後統計方法22
2.7.2事前分析估算方法23
2.8函數的漸近增長25
2.9算法時間復雜度27
2.9.1算法時間復雜度定義27
2.9.2推導大O階方法28
2.9.3常數階28
2.9.4線性階29
2.9.5對數階29
2.9.6平方階29
2.10常見的時間復雜度31
2.11最壞情況與平均情況32
2.12算法空間復雜度33
2.13總結回顧34
2.14結尾語35
第3章線性表37
3.1開場白38
3.2線性表的定義39
3.3線性表的抽像數據類型41
3.4線性表的順序存儲結構43
3.4.1順序存儲定義43
3.4.2順序存儲方式43
3.4.3數據長度與線性表長度的區別44
3.4.4地址計算方法45
3.5順序存儲結構的插入與刪除46
3.5.素操作46
3.5.2插入操作46
3.5.3刪除操作47
3.5.4線性表順序存儲結構的優缺點49
3.6線性表的鏈式存儲結構49
3.6.1順序存儲結構不足的解決辦法49
3.6.2線性表鏈式存儲結構定義50
3.6.3頭指針與頭結點的異同52
3.6.4線性表鏈式存儲結構代碼描述52
3.7單鏈表的讀取53
3.8單鏈表的插入與刪除54
3.8.1單鏈表的插入54
3.8.2單鏈表的刪除56
3.9單鏈表的整表創建58
3.10單鏈表的整表刪除60
3.11單鏈表結構與順序存儲結構的優缺點61
3.12靜態鏈表62
3.12.1靜態鏈表的插入操作64
3.12.2靜態鏈表的刪除操作65
3.12.3靜態鏈表的優缺點67
3.13循環鏈表67
3.14雙向鏈表70
3.15總結回顧72
3.16結尾語73
第4章棧與隊列75
4.1開場白76
4.2棧的定義76
4.2.1棧的定義76
4.2.2進棧出棧變化形式78
4.3棧的抽像數據類型78
4.4棧的順序存儲結構及實現79
4.4.1棧的順序存儲結構79
4.4.2棧的順序存儲結構——進棧操作80
4.4.3棧的順序存儲結構——出棧操作81
4.5兩棧共享空間81
4.6棧的鏈式存儲結構及實現83
4.6.1棧的鏈式存儲結構83
4.6.2棧的鏈式存儲結構——進棧操作84
4.6.3棧的鏈式存儲結構——出棧操作85
4.7棧的作用85
4.8棧的應用——遞歸86
4.8.1斐波那契數列的實現86
4.8.2遞歸的定義88
4.9棧的應用——四則運算表達式求值89
4.9.1後綴（逆波蘭）表示法的定義89
4.9.2後綴表達式的計算結果90
4.9.3中綴表達式轉後綴表達式92
4.10隊列的定義93
4.11隊列的抽像數據類型94
4.12循環隊列95
4.12.1隊列順序存儲的不足95
4.12.2循環隊列的定義96
4.13隊列的鏈式存儲結構及實現99
4.13.1隊列的鏈式存儲結構——入隊操作100
4.13.2隊列的鏈式存儲結構——出隊操作100
4.14總結回顧101
4.15結尾語102
第5章串103
5.1開場白104
5.2串的定義104
5.3串的比較105
5.4串的抽像數據類型107
5.5串的存儲結構108
5.5.1串的順序存儲結構108
5.5.2串的鏈式存儲結構109
5.6樸素的模式匹配算法110
5.7KMP模式匹配算法113
5.7.1KMP模式匹配算法的原理113
5.7.2next數組值的推導116
5.7.3KMP模式匹配算法的實現117
5.7.4KMP模式匹配算法的改進119
5.7.5nextval數組值的推導120
5.8總結回顧122
5.9結尾語122
第6章樹125
6.1開場白126
6.2樹的定義126
6.2.1結點的分類127
6.2.2結點間的關繫128
6.2.3樹的其他相關概念129
6.3樹的抽像數據類型129
6.4樹的存儲結構130
6.4.1雙親表示法130
6.4.2孩子表示法133
6.4.3孩子兄弟表示法136
6.5二叉樹的定義137
6.5.1二叉樹的特點139
6.5.2特殊二叉樹140
6.6二叉樹的性質142
6.6.1二叉樹的性質1142
6.6.2二叉樹的性質2143
6.6.3二叉樹的性質3143
6.6.4二叉樹的性質4144
6.6.5二叉樹的性質5144
6.7二叉樹的存儲結構145
6.7.1二叉樹的順序存儲結構145
6.7.2二叉鏈表146
6.8遍歷二叉樹147
6.8.1二叉樹的遍歷原理147
6.8.2二叉樹的遍歷方法148
6.8.3前序遍歷算法150
6.8.4中序遍歷算法153
6.8.5後序遍歷算法156
6.8.6推導遍歷結果156
6.9二叉樹的建立158
6.10線索二叉樹159
6.10.1線索二叉樹的原理159
6.10.2線索二叉樹結構的實現162
6.11樹、森林與二叉樹的轉換165
6.11.1樹轉換為二叉樹166
6.11.2森林轉換為二叉樹167
6.11.3二叉樹轉換為樹168
6.11.4二叉樹轉換為森林169
6.11.5樹與森林的遍歷170
6.12哈夫曼樹及其應用171
6.12.1哈夫曼樹171
6.12.2哈夫曼樹的定義與原理173
6.12.3哈夫曼編碼176
6.13總結回顧177
6.14結尾語178
第7章圖181
7.1開場白182
7.2圖的定義182
7.2.1各種圖的定義183
7.2.2圖的頂點與邊間的關繫185
7.2.3連通圖的相關術語187
7.2.4圖的定義與術語總結189
7.3圖的抽像數據類型190
7.4圖的存儲結構191
7.4.1鄰接矩陣192
7.4.2鄰接表195
7.4.3十字鏈表198
7.4.4鄰接多重表199
7.4.5邊集數組201
7.5圖的遍歷202
7.5.1深度優先遍歷203
7.5.2廣度優先遍歷205
7.6最小生成樹208
7.6.1普裡姆（Prim）算法209
7.6.2克魯斯卡爾（Kruskal）算法213
7.7最短路徑218
7.7.1迪傑斯特拉（Dijkstra）算法220
7.7.2弗洛伊德（Floyd）算法225
7.8拓撲排序229
7.8.1拓撲排序介紹229
7.8.2拓撲排序算法230
7.9關鍵路徑234
7.9.1關鍵路徑算法的原理236
7.9.2關鍵路徑算法237
7.10總結回顧242
7.11結尾語243
第8章查找245
8.1開場白246
8.2查找概論247
8.3順序表查找249
8.3.1順序表查找算法249
8.3.2順序表查找優化250
8.4有序表查找251
8.4.1折半查找251
8.4.2插值查找253
8.4.3斐波那契查找255
8.5線性索引查找257
8.5.1稠密索引258
8.5.2分塊索引258
8.5.3倒排索引260
8.6二叉排序樹262
8.6.1二叉排序樹的查找操作264
8.6.2二叉排序樹的插入操作266
8.6.3二叉排序樹的刪除操作267
8.6.4二叉排序樹總結272
8.7平衡二叉樹（AVL樹）273
8.7.1平衡二叉樹的實現原理275
8.7.2平衡二叉樹的實現算法278
8.8多路查找樹（B樹）284
8.8.12-3樹285
8.8.22-3-4樹289
8.8.3B樹290
8.8.4B樹292
8.9散列表查找（哈希表）概述294
8.9.1散列表查找定義294
8.9.2散列表查找步驟295
8.10散列函數的構造方法296
8.10.1直接定址法297
8.10.2數字分析法297
8.10.3平方取中法298
8.10.4折疊法298
8.10.5除留餘數法298
8.10.6隨機數法299
8.11處理散列衝突的方法300
8.11.1開放定址法300
8.11.2再散列函數法302
8.11.3鏈地址法302
8.11.4公共溢出區法302
8.12散列表查找的實現303
8.12.1散列表查找的算法實現303
8.12.2散列表查找的性能分析305
8.13總結回顧305
8.14結尾語306
第9章排序309
9.1開場白310
9.2排序的基本概念與分類310
9.2.1排序的穩定性311
9.2.2內排序與外排序312
9.2.3排序用到的結構與函數313
9.3冒泡排序314
9.3.1最簡單排序的實現314
9.3.2冒泡排序算法315
9.3.3冒泡排序優化316
9.3.4冒泡排序復雜度分析317
9.4簡單選擇排序318
9.4.1簡單選擇排序算法318
9.4.2簡單選擇排序復雜度分析319
9.5直接插入排序320
9.5.1直接插入排序算法320
9.5.2直接插入排序復雜度分析322
9.6希爾排序323
9.6.1希爾排序原理324
9.6.2希爾排序算法325
9.6.3希爾排序復雜度分析328
9.7堆排序329
9.7.1堆排序算法331
9.7.2堆排序復雜度分析337
9.8歸並排序337
9.8.1歸並排序算法338
9.8.2歸並排序復雜度分析343
9.8.3非遞歸實現歸並排序343
9.9快速排序346
9.9.1快速排序算法346
9.9.2快速排序復雜度分析349
9.9.3快速排序優化350
9.10總結回顧354
9.11結尾語357

本書以一個計算機教師的教學過程為場景，講解數據結構和相關算法的知識。全書以趣味方式來敘述，大量引用各種各樣的生活知識來類比，並充分運用全彩色圖形語言來解讀抽像內容，對數據結構所涉及的一些經典算法做出逐行分析、多算法比較。與同類圖書相比，本書內容有趣易讀，算法講解細致深入，是一本非常適合自學的讀物。對於學習數據結構來說，難點之一是對相關算法的理解。本書創新性地采用全彩印刷，圖表、流程、代碼等內容結合色彩來重新進行約定和歸納，使得對一些難以理解的知識點的解析更加清晰順暢，極大提升了閱讀體驗。本書主要內容包含：數據結構介紹、算法推導大O階的方法；順序結構與鏈式結構差異、棧與隊列的應用；串的樸素模式匹配、KMP模式匹配算法；二叉樹前中後序遍歷、哈夫曼樹及應用；圖的深度、廣度遍歷；最小生成樹兩種算法、最短路徑兩種算法；拓撲排序與關鍵路徑算法；折半查找、插值查找、斐波那契查找等靜態查找；稠密索引、分塊等

程傑 著