本書系統(tǒng)地介紹了線性表、棧、隊列、串、數(shù)組、廣義表、樹、二叉樹、圖等常用數(shù)據(jù)結(jié)構(gòu)以及查找、排序、索引等算法設(shè)計技術(shù)，給出了較多的數(shù)據(jù)結(jié)構(gòu)應(yīng)用實例及其算法在計算機中的存儲和實現(xiàn)，分析了復(fù)雜度。書中各種算法采用C++語言描述，既適合在MSVC下使用，也適合在MSVC++.NET中使用。全書注重程序設(shè)計風(fēng)格，可讀性和實用性強。本書內(nèi)容豐富，層次清晰，講解深入淺出，可作為計算機及相關(guān)專業(yè)本、�？茢�(shù)據(jù)結(jié)構(gòu)課程的教材，也可供從事計算機軟件開發(fā)和應(yīng)用的工程技術(shù)人員閱讀或參考。
更多科學(xué)出版社服務(wù)，請掃碼獲取。
目錄
前言
第1章 緒論1
1.1引言1
1.2數(shù)據(jù)結(jié)構(gòu)中的基本概念和術(shù)語4
1.3算法和算法描述12
1.3.1算法的概念12
1.3.2算法的描述方法13
1.4算法的評價方法16
1.4.1評價算法的一般原則16
1.4.2算法的復(fù)雜度17
1.5C++中的typedef、模板與異常處理*24
本章小結(jié)和學(xué)習(xí)要點33
習(xí)題134
思考題136
上機題136
第2章 線性表37
2.1線性表及其基本操作37
2.1.1線性表的邏輯結(jié)構(gòu)定義37
2.1.2線性表的抽象數(shù)據(jù)類型定義38
2.2線性表的順序存儲結(jié)構(gòu)——順序表40
2.2.1順序表的基本表示40
2.2.2順序表模板類表示下的基本操作44
2.2.3順序表表示線性表下的其他操作49
2.2.4間接尋址方式及其他方式實現(xiàn)的順序表56
2.3線性表的鏈式存儲結(jié)構(gòu)56
2.3.1單鏈表56
2.3.2循環(huán)單鏈表67
2.3.3雙鏈表及循環(huán)雙鏈表68
2.3.4靜態(tài)鏈表71
2.3.5間接尋址方式實現(xiàn)的單鏈表*73
2.4線性表的應(yīng)用73
2.4.1一元多項式的表示及相加73
2.4.2算法舉例77
2.5順序表和單鏈表的比較82
2.5.1時間性能比較82
2.5.2空間性能比較82
本章內(nèi)容小結(jié)和學(xué)習(xí)要點83
習(xí)題284
思考題288
上機題288
第3章 棧和隊列89
3.1棧89
3.1.1棧的邏輯結(jié)構(gòu)89
3.1.2棧的順序存儲結(jié)構(gòu)——順序棧91
3.1.3棧的鏈式存儲結(jié)構(gòu)96
3.2隊列99
3.2.1隊列的邏輯結(jié)構(gòu)99
3.2.2隊列的鏈式存儲結(jié)構(gòu)102
3.2.3隊列的順序存儲結(jié)構(gòu)106
3.3棧和隊列的綜合應(yīng)用115
3.3.1算術(shù)表達式求值115
3.3.2用順序棧作輔助存儲結(jié)構(gòu)求迷宮的一條路徑解124
本章內(nèi)容小結(jié)和學(xué)習(xí)要點126
習(xí)題3126
思考題3128
上機題3129
第4章 字符串130
4.1串及其運算130
4.2串的順序存儲結(jié)構(gòu)134
4.3串的鏈式存儲結(jié)構(gòu)137
4.4串的模式匹配算法138
4.5串的應(yīng)用149
4.5.1大整數(shù)加法149
4.5.2名字特征數(shù)152
本章小結(jié)和學(xué)習(xí)要點153
習(xí)題4153
思考題4154
上機題4154
第5章 數(shù)組和廣義表155
5.1數(shù)組的尋址和運算155
5.2矩陣的壓縮存儲159
5.2.1特殊矩陣160
5.2.2稀疏矩陣163
5.3廣義表*170
5.3.1廣義表的概念170
5.3.2廣義表的存儲結(jié)構(gòu)172
5.3.3廣義表的操作174
本章小結(jié)和學(xué)習(xí)要點178
習(xí)題5178
思考題5180
上機題5180
第6章 樹和二叉樹182
6.1樹的基本定義182
6.2二叉樹186
6.2.1二叉樹的定義和基本運算187
6.2.2二叉樹的性質(zhì)189
6.2.3二叉樹的存儲結(jié)構(gòu)192
6.3二叉樹的建立和遍歷197
6.3.1遍歷二叉樹197
6.3.2建立和釋放一棵二叉樹的二叉鏈表202
6.3.3二叉鏈表其他函數(shù)和主函數(shù)204
6.3.4二叉樹的三種遍歷的非遞歸算法206
6.3.5二叉樹的其他算法例210
6.4線索二叉樹213
6.5樹和森林219
6.6哈夫曼樹及其應(yīng)用228
本章小結(jié)和學(xué)習(xí)要點237
習(xí)題6237
思考題6242
上機題6242
第7章 圖的數(shù)據(jù)結(jié)構(gòu)243
7.1圖的定義、基本術(shù)語和操作243
7.2圖的存儲結(jié)構(gòu)248
7.2.1鄰接矩陣248
7.2.2邊數(shù)組252
7.2.3鄰接表252
7.2.4圖的十字鏈表表示258
7.2.5鄰接多重表260
7.3圖的遍歷262
7.3.1深度優(yōu)先搜索遍歷圖262
7.3.2廣度優(yōu)先搜索遍歷圖266
7.3.3圖的遍歷268
7.4圖的連通性和生成樹270
7.4.1圖的連通性和連通分量270
7.4.2生成樹和生成森林272
7.4.3最小生成樹274
7.5最短路徑問題283
7.5.1求某個源點到其余各頂點的最短路徑283
7.5.2求帶權(quán)圖中每一對頂點之間的最短路徑288
7.6拓撲排序291
7.7求關(guān)鍵路徑298
7.8圖的遍歷算法的應(yīng)用305
7.8.1求過給定點v長度大于或等于k的簡單有向回路305
7.8.2地圖四色問題306
本章小結(jié)和學(xué)習(xí)要點308
習(xí)題7308
思考題7313
上機題7313
第8章 排序315
8.1排序的基本概念和術(shù)語315
8.2插入排序318
8.2.1直接插入排序318
8.2.2謝爾排序322
8.3選擇排序324
8.3.1簡單選擇排序325
8.3.2改進的簡單選擇排序326
8.3.3堆排序327
8.4交換排序333
8.4.1冒泡排序333
8.4.2快速排序335
8.5歸并排序340
8.6基數(shù)排序342
8.7各種內(nèi)部排序算法的比較346
本章小結(jié)和學(xué)習(xí)要點349
習(xí)題8350
思考題8355
上機題8355
第9章 查找356
9.1查找的基本概念和術(shù)語356
9.2以順序表為基礎(chǔ)的查找358
9.2.1順序表的順序查找358
9.2.2有序表的二分法查找361
9.2.3靜態(tài)樹表的查找366
9.2.4分塊查找370
9.3樹形結(jié)構(gòu)的查找373
9.3.1二叉排序樹373
9.3.2平衡二叉樹383
9.4散列表的查找391
9.4.1散列技術(shù)中的主要概念391
9.4.2散列函數(shù)的構(gòu)造方法392
9.4.3沖突的處理方法396
9.4.4散列表上的查找算法400
9.4.5散列表查找的時間復(fù)雜度分析400
本章小結(jié)和學(xué)習(xí)要點405
習(xí)題9405
思考題9408
上機題9408
第10章 索引技術(shù)409
10.1索引的基本概念409
10.2線性索引410
10.2.1稠密索引410
10.2.2稀疏索引411
10.2.3多重表413
10.2.4倒排表413
10.3樹形索引415
10.3.1B-樹415
10.3.2B+樹424
10.3.3鍵樹425
本章內(nèi)容小結(jié)和學(xué)習(xí)要點432
習(xí)題10432
思考題10434
上機題10434
主要參考文獻435
附錄上機實驗報告格式437
索引439
書單推薦
