本書系統(tǒng)地介紹了線性表、棧、隊(duì)列、串、數(shù)組、廣義表、樹、二叉樹、圖等常用數(shù)據(jù)結(jié)構(gòu)以及查找、排序、索引等算法設(shè)計(jì)技術(shù)，給出了較多的數(shù)據(jù)結(jié)構(gòu)應(yīng)用實(shí)例及其算法在計(jì)算機(jī)中的存儲(chǔ)和實(shí)現(xiàn)，分析了復(fù)雜度。書中各種算法采用C++語言描述，既適合在MSVC下使用，也適合在MSVC++.NET中使用。全書注重程序設(shè)計(jì)風(fēng)格，可讀性和實(shí)用性強(qiáng)。本書內(nèi)容豐富，層次清晰，講解深入淺出，可作為計(jì)算機(jī)及相關(guān)專業(yè)本、�？茢�(shù)據(jù)結(jié)構(gòu)課程的教材，也可供從事計(jì)算機(jī)軟件開發(fā)和應(yīng)用的工程技術(shù)人員閱讀或參考。
更多科學(xué)出版社服務(wù)，請(qǐng)掃碼獲取。
目錄
前言
第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算法的評(píng)價(jià)方法16
1.4.1評(píng)價(jià)算法的一般原則16
1.4.2算法的復(fù)雜度17
1.5C++中的typedef、模板與異常處理*24
本章小結(jié)和學(xué)習(xí)要點(diǎn)33
習(xí)題134
思考題136
上機(jī)題136
第2章 線性表37
2.1線性表及其基本操作37
2.1.1線性表的邏輯結(jié)構(gòu)定義37
2.1.2線性表的抽象數(shù)據(jù)類型定義38
2.2線性表的順序存儲(chǔ)結(jié)構(gòu)——順序表40
2.2.1順序表的基本表示40
2.2.2順序表模板類表示下的基本操作44
2.2.3順序表表示線性表下的其他操作49
2.2.4間接尋址方式及其他方式實(shí)現(xiàn)的順序表56
2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(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間接尋址方式實(shí)現(xiàn)的單鏈表*73
2.4線性表的應(yīng)用73
2.4.1一元多項(xiàng)式的表示及相加73
2.4.2算法舉例77
2.5順序表和單鏈表的比較82
2.5.1時(shí)間性能比較82
2.5.2空間性能比較82
本章內(nèi)容小結(jié)和學(xué)習(xí)要點(diǎn)83
習(xí)題284
思考題288
上機(jī)題288
第3章 棧和隊(duì)列89
3.1棧89
3.1.1棧的邏輯結(jié)構(gòu)89
3.1.2棧的順序存儲(chǔ)結(jié)構(gòu)——順序棧91
3.1.3棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)96
3.2隊(duì)列99
3.2.1隊(duì)列的邏輯結(jié)構(gòu)99
3.2.2隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)102
3.2.3隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)106
3.3棧和隊(duì)列的綜合應(yīng)用115
3.3.1算術(shù)表達(dá)式求值115
3.3.2用順序棧作輔助存儲(chǔ)結(jié)構(gòu)求迷宮的一條路徑解124
本章內(nèi)容小結(jié)和學(xué)習(xí)要點(diǎn)126
習(xí)題3126
思考題3128
上機(jī)題3129
第4章 字符串130
4.1串及其運(yùn)算130
4.2串的順序存儲(chǔ)結(jié)構(gòu)134
4.3串的鏈?zhǔn)酱鎯?chǔ)結(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í)要點(diǎn)153
習(xí)題4153
思考題4154
上機(jī)題4154
第5章 數(shù)組和廣義表155
5.1數(shù)組的尋址和運(yùn)算155
5.2矩陣的壓縮存儲(chǔ)159
5.2.1特殊矩陣160
5.2.2稀疏矩陣163
5.3廣義表*170
5.3.1廣義表的概念170
5.3.2廣義表的存儲(chǔ)結(jié)構(gòu)172
5.3.3廣義表的操作174
本章小結(jié)和學(xué)習(xí)要點(diǎn)178
習(xí)題5178
思考題5180
上機(jī)題5180
第6章 樹和二叉樹182
6.1樹的基本定義182
6.2二叉樹186
6.2.1二叉樹的定義和基本運(yùn)算187
6.2.2二叉樹的性質(zhì)189
6.2.3二叉樹的存儲(chǔ)結(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í)要點(diǎn)237
習(xí)題6237
思考題6242
上機(jī)題6242
第7章 圖的數(shù)據(jù)結(jié)構(gòu)243
7.1圖的定義、基本術(shù)語和操作243
7.2圖的存儲(chǔ)結(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求某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑283
7.5.2求帶權(quán)圖中每一對(duì)頂點(diǎn)之間的最短路徑288
7.6拓?fù)渑判?91
7.7求關(guān)鍵路徑298
7.8圖的遍歷算法的應(yīng)用305
7.8.1求過給定點(diǎn)v長度大于或等于k的簡(jiǎn)單有向回路305
7.8.2地圖四色問題306
本章小結(jié)和學(xué)習(xí)要點(diǎn)308
習(xí)題7308
思考題7313
上機(jī)題7313
第8章 排序315
8.1排序的基本概念和術(shù)語315
8.2插入排序318
8.2.1直接插入排序318
8.2.2謝爾排序322
8.3選擇排序324
8.3.1簡(jiǎn)單選擇排序325
8.3.2改進(jìn)的簡(jiǎn)單選擇排序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í)要點(diǎn)349
習(xí)題8350
思考題8355
上機(jī)題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散列表查找的時(shí)間復(fù)雜度分析400
本章小結(jié)和學(xué)習(xí)要點(diǎn)405
習(xí)題9405
思考題9408
上機(jī)題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í)要點(diǎn)432
習(xí)題10432
思考題10434
上機(jī)題10434
主要參考文獻(xiàn)435
附錄上機(jī)實(shí)驗(yàn)報(bào)告格式437
索引439
書單推薦
