本書系統(tǒng)地介紹了線性表、棧、隊列、串、數(shù)組、廣義表、樹、二叉樹、圖等常用數(shù)據(jù)結構以及查找、排序、索引等算法設計技術，給出了較多的數(shù)據(jù)結構應用實例及其算法在計算機中的存儲和實現(xiàn)，分析了復雜度。書中各種算法采用C++語言描述，既適合在MSVC下使用，也適合在MSVC++.NET中使用。全書注重程序設計風格，可讀性和實用性強。本書內(nèi)容豐富，層次清晰，講解深入淺出，可作為計算機及相關專業(yè)本、�？茢�(shù)據(jù)結構課程的教材，也可供從事計算機軟件開發(fā)和應用的工程技術人員閱讀或參考。
更多科學出版社服務，請掃碼獲取。
目錄
前言
第1章 緒論1
1.1引言1
1.2數(shù)據(jù)結構中的基本概念和術語4
1.3算法和算法描述12
1.3.1算法的概念12
1.3.2算法的描述方法13
1.4算法的評價方法16
1.4.1評價算法的一般原則16
1.4.2算法的復雜度17
1.5C++中的typedef、模板與異常處理*24
本章小結和學習要點33
習題134
思考題136
上機題136
第2章 線性表37
2.1線性表及其基本操作37
2.1.1線性表的邏輯結構定義37
2.1.2線性表的抽象數(shù)據(jù)類型定義38
2.2線性表的順序存儲結構——順序表40
2.2.1順序表的基本表示40
2.2.2順序表模板類表示下的基本操作44
2.2.3順序表表示線性表下的其他操作49
2.2.4間接尋址方式及其他方式實現(xiàn)的順序表56
2.3線性表的鏈式存儲結構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線性表的應用73
2.4.1一元多項式的表示及相加73
2.4.2算法舉例77
2.5順序表和單鏈表的比較82
2.5.1時間性能比較82
2.5.2空間性能比較82
本章內(nèi)容小結和學習要點83
習題284
思考題288
上機題288
第3章 棧和隊列89
3.1棧89
3.1.1棧的邏輯結構89
3.1.2棧的順序存儲結構——順序棧91
3.1.3棧的鏈式存儲結構96
3.2隊列99
3.2.1隊列的邏輯結構99
3.2.2隊列的鏈式存儲結構102
3.2.3隊列的順序存儲結構106
3.3棧和隊列的綜合應用115
3.3.1算術表達式求值115
3.3.2用順序棧作輔助存儲結構求迷宮的一條路徑解124
本章內(nèi)容小結和學習要點126
習題3126
思考題3128
上機題3129
第4章 字符串130
4.1串及其運算130
4.2串的順序存儲結構134
4.3串的鏈式存儲結構137
4.4串的模式匹配算法138
4.5串的應用149
4.5.1大整數(shù)加法149
4.5.2名字特征數(shù)152
本章小結和學習要點153
習題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廣義表的存儲結構172
5.3.3廣義表的操作174
本章小結和學習要點178
習題5178
思考題5180
上機題5180
第6章 樹和二叉樹182
6.1樹的基本定義182
6.2二叉樹186
6.2.1二叉樹的定義和基本運算187
6.2.2二叉樹的性質(zhì)189
6.2.3二叉樹的存儲結構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哈夫曼樹及其應用228
本章小結和學習要點237
習題6237
思考題6242
上機題6242
第7章 圖的數(shù)據(jù)結構243
7.1圖的定義、基本術語和操作243
7.2圖的存儲結構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求帶權圖中每一對頂點之間的最短路徑288
7.6拓撲排序291
7.7求關鍵路徑298
7.8圖的遍歷算法的應用305
7.8.1求過給定點v長度大于或等于k的簡單有向回路305
7.8.2地圖四色問題306
本章小結和學習要點308
習題7308
思考題7313
上機題7313
第8章 排序315
8.1排序的基本概念和術語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
本章小結和學習要點349
習題8350
思考題8355
上機題8355
第9章 查找356
9.1查找的基本概念和術語356
9.2以順序表為基礎的查找358
9.2.1順序表的順序查找358
9.2.2有序表的二分法查找361
9.2.3靜態(tài)樹表的查找366
9.2.4分塊查找370
9.3樹形結構的查找373
9.3.1二叉排序樹373
9.3.2平衡二叉樹383
9.4散列表的查找391
9.4.1散列技術中的主要概念391
9.4.2散列函數(shù)的構造方法392
9.4.3沖突的處理方法396
9.4.4散列表上的查找算法400
9.4.5散列表查找的時間復雜度分析400
本章小結和學習要點405
習題9405
思考題9408
上機題9408
第10章 索引技術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)容小結和學習要點432
習題10432
思考題10434
上機題10434
主要參考文獻435
附錄上機實驗報告格式437
索引439
書單推薦
