內容簡介
本書闡明了常用的數據結構的內在邏輯關係，討論了各種結構的物理存儲表示方法，通過實例說明各種結構在運算操作時的動態特性，並結合典型套用問題給出算法設計與分析的示例。這樣不僅為後續相關課程提供必要的知識準備，更重要的是可以進一步提高讀者從事軟體分析、設計、編程和數據組織的能力。 全書共8章，在內容的組織上遵循由淺入深、循序漸進的原則，按簡單的線性結構、樹形結構、圖結構、查找和排序的次序安排主要教學內容；在內容的敘述上力求做到通俗易懂，算法描述結構清晰、易讀易理解，並對每個算法都做了大量注釋；全書選取的內容都較好地體現了突出套用的原則，以實例介紹各種數據結構的套用，並在各章都附有相應的習題。
圖書目錄
第1章緒論1
1.1什麼是數據結構1
1.1.1學習數據結構的目的1
1.1.2有關概念和術語4
1.2數據類型和抽象數據類型6
1.2.1數據類型6
1.2.2抽象數據類型6
1.3算法與算法分析8
1.3.1算法的特性8
1.3.2算法描述10
1.3.3算法效率的度量10
本章小結13
習題113
第2章線性表16
2.1線性表的邏輯結構16
2.1.1線性表的定義16
2.1.2線性表的抽象數據類型17
2.2線性表的順序存儲與實現18
2.2.1順序表18
2.2.2順序表基本操作的實現19
2.2.3順序表套用舉例23
2.3線性表的鏈式存儲與實現25
2.3.1單鍊表25
2.3.2單鍊表上基本運算的實現27
2.3.3單鍊表的套用30
2.3.4循環鍊表31
2.3.5雙向鍊表32
2.3.6靜態鍊表33[1]〖2〗深入淺出數據結構與算法[1]目錄〖2〗2.4一元多項式的表示及加法實現36
2.5套用實例——約瑟夫環問題38
本章小結42
習題242
第3章限定性線性表——棧和佇列46
3.1棧46
3.1.1棧的定義46
3.1.2棧的表示和實現47
3.2棧的套用舉例52
3.3佇列56
3.3.1佇列的定義56
3.3.2佇列的表示和實現57
3.4佇列的套用舉例62
3.5套用實例——銀行排隊服務模擬63
本章小結68
習題368
第4章串、數組和廣義表72
4.1串的定義72
4.2串的表示和實現73
4.2.1定長順序存儲表示74
4.2.2堆分配存儲表示75
4.2.3串的塊鏈存儲表示77
4.3模式匹配77
4.3.1簡單模式匹配78
4.3.2一種改進的模式匹配79
4.4數組81
4.4.1數組的定義81
4.4.2數組的順序存儲與實現82
4.4.3矩陣的壓縮存儲83
4.5廣義表91
4.5.1廣義表的定義91
4.5.2廣義表的存儲結構92
4.6套用實例——投票選舉93
本章小結96
習題497
第5章樹和二叉樹100
5.1樹的基本概念100
5.1.1樹的定義100
5.1.2樹的基本術語102
5.2二叉樹104
5.2.1二叉樹的定義104
5.2.2二叉樹的性質105
5.2.3二叉樹的存儲結構107
5.3二叉樹的遍歷110
5.3.1二叉樹的遍歷算法110
5.3.2二叉樹遍歷算法的套用112
5.4線索二叉樹114
5.4.1線索二叉樹的定義114
5.4.2二叉樹的線索化115
5.4.3線索二叉樹的遍歷117
5.5樹和森林118
5.5.1樹的存儲結構118
5.5.2森林與二叉樹的轉換121
5.5.3樹和森林的遍歷122
5.6哈夫曼樹及其套用123
5.6.1基本術語123
5.6.2構造哈夫曼樹124
5.6.3哈夫曼樹的套用127
5.7套用實例——並查集129
本章小結132
習題5133
第6章圖136
6.1圖的基本概念136
6.1.1圖的定義136
6.1.2圖的基本術語137
6.2圖的存儲結構141
6.2.1鄰接矩陣141
6.2.2鄰接表143
6.2.3有向圖的十字鍊表146
6.2.4無向圖的鄰接多重表147
6.3圖的遍歷149
6.3.1深度優先搜尋149
6.3.2廣度優先搜尋151
6.4無向圖的連通分量和生成樹152
6.5圖的套用153
6.5.1最小生成樹153
6.5.2有向無環圖與拓撲排序157
6.5.3關鍵路徑161
6.5.4最短路徑166
6.6套用實例——暢通工程171
本章小結175
習題6175
第7章查找179
7.1查找的基本概念179
7.2靜態查找180
7.2.1順序查找181
7.2.2折半查找183
7.2.3分塊查找185
7.3動態查找187
7.3.1二叉排序樹187
7.3.2平衡二叉樹194
7.3.3B樹203
7.4哈希表204
7.4.1哈希表的概念205
7.4.2哈希函式的構造205
7.4.3處理衝突的方法207
7.4.4哈希表查找及其分析209
7.5套用實例——通訊錄查詢系統210
本章小結217
習題7218
第8章排序221
8.1排序的基本概念221
8.2插入排序222
8.2.1直接插入排序223
8.2.2折半插入排序224
8.2.3希爾排序225
8.3交換排序227
8.3.1冒泡排序227
8.3.2快速排序229
8.4選擇排序232
8.4.1簡單選擇排序232
8.4.2堆排序233
8.5歸併排序237
8.6基數排序239
8.6.1多關鍵字排序239
8.6.2鏈式基數排序240
8.7內部排序方法比較244
8.8套用實例——內部排序算法比較246
本章小結255
習題8256
參考文獻260
