●章數據結構基礎1
1.1數據結構的基本概念2
1.1.1數據結構的研究內容.2
1.1.2基本概念和術語.5
1.1.3數據結構課程的內容.8
1.2數據類型和抽像數據類型9
1.2.1數據類型.9
1.2.2抽像數據類型.9
1.3算法和算法分析10
1.3.1算法特性.11
1.3.2算法描述.12
1.3.3算法性能分析.12
1.4本章小結15
習題.16
編程實例.18
第2章線性表.19
2.1線性表的定義20
2.1.1線性表的邏輯結構.20
2.1.2線性表的抽像數據類型.20
2.2線性表的順序存儲及實現22
2.2.1順序表.22
2.2.2順序表的基本運算.23
2.3線性表的鏈式存儲及實現28
2.3.1單鏈表.29
2.3.2單鏈表的基本運算.30
2.3.3循環鏈表.36
2.3.4雙向鏈表.37
2.3.5靜態鏈表.39
2.3.6單鏈表應用舉例.40
2.4順序表與鏈表的比較43
2.5本章小結44
習題.44
編程實例.46
第3章棧和隊列.48
3.1棧49
3.1.1棧的定義.49
3.1.2棧的表示和實現.50
3.2棧的應用55
3.2.1數制轉換問題.56
3.2.2括號匹配檢驗.57
3.2.3表達式求值.58
3.2.4棧與遞歸.61
3.3隊列64
3.3.1隊列的定義.64
3.3.2隊列的表示和實現.65
3.4隊列的應用71
3.5本章小結73
習題.74
編程實例.75
第4章串79
4.1串的定義和基本運算80
4.1.1串的定義.80
4.1.2串的基本操作.81
4.2串的存儲結構82
4.2.1定長順序存儲.82
4.2.2堆存儲.83
4.2.3鏈式存儲.85
4.3串的運算實現86
4.4串的模式匹配90
4.4.1BF算法.90
4.4.2KMP算法.92
4.5本章小結95
習題.96
編程實例.99
第5章數組和廣義表103
5.1數組的定義及存儲104
5.1.1數組的定義.104
5.1.2數組的基本操作.105
5.1.3數組的順序存儲.105
5.2特殊矩陣的壓縮存儲107
5.2.1對稱矩陣.108
5.2.2三角矩陣.109
5.2.3對角矩陣.110
5.3稀疏矩陣.111
5.3.1稀疏矩組表存儲111
5.3.2稀疏矩陣的十字鏈表存儲.115
5.4廣義表117
5.4.1廣義表的定義.117
5.4.2廣義表的存儲結構.119
5.4.3廣義表的基本操作實現.121
5.5本章小結122
習題.123
編程實例.124
第6章樹和二叉樹127
6.1樹的定義與基本術語128
6.1.1樹的定義.128
6.1.2樹的基本術語.131
6.2二叉樹131
6.2.1二叉樹的定義.131
6.2.2二叉樹的性質.134
6.2.3二叉樹的存儲實現.136
6.3遍歷二叉樹139
6.3.1遍歷二叉樹的遞歸實現.139
6.3.2遍歷二叉樹的非遞歸實現.141
6.3.3遍歷算法的應用.145
6.4線索二叉樹148
6.4.1線索二叉樹的基本概念.148
6.4.2線索二叉樹的運算實現.150
6.5樹和森林153
6.5.1樹的存儲結構.153
6.5.2樹、森林與二叉樹的轉換.156
6.5.3樹和森林的遍歷.158
6.6哈夫曼樹及其應用159
6.6.1哈夫曼樹的基本概念.159
6.6.2構造哈夫曼樹.161
6.6.3哈夫曼編碼.163
6.7本章小結165
習題.166
編程實例.168
第7章圖172
7.1圖的定義與基本術語173
7.1.1圖的定義.173
7.1.2基本術語.175
7.2圖的存儲結構177
7.2.1鄰接矩陣.177
7.2.2鄰接鏈表.179
7.2.3十字鏈表.182
7.2.4鄰接多重表.183
7.3圖的遍歷184
7.3.1深度優先搜索.185
7.3.2廣度優先搜索.187
7.4圖的應用189
7.4.1最小生成樹.189
7.4.2最短路徑問題.195
7.4.3AOV網與拓撲排序.200
7.4.4AOE網與關鍵路徑203
7.5本章小結208
習題.209
編程實例.211
第8章查找.216
8.1查找的基本概念217
8.2線性表的查找218
8.2.1順序查找.218
8.2.2折半查找.219
8.2.3分塊查找.222
8.3樹表的查找223
8.3.1二叉排序樹.223
8.3.2平衡二叉樹.229
8.3.3B樹234
8.4散列表的查找241
8.4.1散列表的基本概念.241
8.4.2散列函數的構造方法.242
8.4.3處理衝突的方法.244
8.4.4散列表的查找.247
8.5本章小結248
習題.249
編程實例.251
第9章排序.254
9.1排序的基本概念255
9.1.1什麼是排序.255
9.1.2排序的實現.256
9.2插入排序257
9.2.1直接插入排序.257
9.2.2折半插入排序.259
9.2.3希爾排序.260
9.3交換排序261
9.3.1冒泡排序.261
9.3.2快速排序.263
9.4選擇排序266
9.4.1簡單選擇排序.266
9.4.2堆排序.268
9.5歸並排序273
9.6基數排序275
9.6.1多關鍵字排序.275
9.6.2鏈式基數排序.275
9.7本章小結279
習題.280
編程實例.282
內容簡介
數據結構是計算機和信息技術等相關專業的一門重要的專業基礎課程,數據結構及其處理算法是設計與實現繫統軟件和大型應用軟件的重要基礎,結合數據結構課程的現狀和發展趨勢,本書具有難度適中、結構合理、應用性強的特點。
全書共9章,內容包括章數據結構基礎,綜述數據結構的基本概念;第2章至第5章主要討論幾種基本的線性結構,即線性表、棧和隊列、串、數組和廣義表;第6章和第7章主要介紹非線性結構,即樹和二叉樹、圖;第8章和第9章分別討論兩種基本的操作,即查找和排序。
全書采用C語言作為數據結構和算法的描述語言,對數據結構的定義和算法描述詳細,代碼注釋完整,便於初學者模仿訓練,循序漸進,穩步提高。本書既可作為高等院校計算機科學與技術、軟件工程、通信工程等信息類專業的教材,也可供從事軟件開發與工程應用設計的工作人員參考使用。