數(shù)據(jù)結(jié)構(gòu)算法與應(yīng)用 C++語言描述
本資源來自于互聯(lián)網(wǎng)，僅供學(xué)習(xí)研究之用，不可涉及任何商業(yè)用途，請在下載后24小時內(nèi)刪除。
著作權(quán)歸原作者或出版社所有。未經(jīng)發(fā)貼人conanwj許可，嚴(yán)禁任何人以任何形式轉(zhuǎn)貼本文，違者必究！

Authors
        
Publisher:
Pub Date:
Pages: 535

     本書是關(guān)于計算機(jī)科學(xué)與工程領(lǐng)域的基礎(chǔ)性研究科目之一——數(shù)據(jù)結(jié)構(gòu)與算法的專著。 本書在簡要回顧了基本的C++ 程序設(shè)計概念的基礎(chǔ)上，全面系統(tǒng)地介紹了隊列、堆棧、樹、圖等基本數(shù)據(jù)結(jié)構(gòu)，以及貪婪算法、分而治之算法、分枝定界算法等多種算法設(shè)計方法，為數(shù)據(jù)結(jié)構(gòu)與算法的繼續(xù)學(xué)習(xí)和研究奠定了一個堅實(shí)的基礎(chǔ)。更為可貴的是，本書不僅僅介紹了理論知識，還提供了50多個應(yīng)用實(shí)例及600多道練習(xí)題。 本書內(nèi)容廣博權(quán)威，結(jié)構(gòu)清晰合理，是一本全新的有關(guān)數(shù)據(jù)結(jié)構(gòu)與算法的教材，對于計算機(jī)科學(xué)與工程領(lǐng)域的從業(yè)人員也是一本很好的參考書。

目錄
目      錄
譯者序
前言
第一部分   預(yù)備知識
第1章   C++程序設(shè)計        1
1.1   引言        1
1.2   函數(shù)與參數(shù)        2
1.2.1   傳值參數(shù)        2
1.2.2   模板函數(shù)        3
1.2.3   引用參數(shù)        3
1.2.4   常量引用參數(shù)        4
1.2.5   返回值        4
1.2.6   遞歸函數(shù)        5
1.3   動態(tài)存儲分配        9
1.3.1   操作符new        9
1.3.2   一維數(shù)組        9
1.3.3   異常處理        10
1.3.4   操作符delete        10
1.3.5   二維數(shù)組        10
1.4   類        13
1.4.1   類Currency        13
1.4.2   使用不同的描述方法        18
1.4.3   操作符重載        20
1.4.4   引發(fā)異常        22
1.4.5   友元和保護(hù)類成員        23
1.4.6   增加#ifndef,   #define和#endif語句        24
1.5   測試與調(diào)試        24
1.5.1   什么是測試        24
1.5.2   設(shè)計測試數(shù)據(jù)        26
1.5.3   調(diào)試        28
1.6   參考及推薦讀物        29
第2章   程序性能        30
2.1   引言        30
2.2   空間復(fù)雜性        31
2.2.1   空間復(fù)雜性的組成        31
2.2.2   舉例        35
2.3   時間復(fù)雜性        37
2.3.1   時間復(fù)雜性的組成        37
2.3.2   操作計數(shù)        37
2.3.3   執(zhí)行步數(shù)        44
2.4   漸進(jìn)符號（O、 健?、 o）        55
2.4.1   大寫O符號        56
2.4.2   椒��?58
2.4.3   符號        59
2.4.4   小寫o符號        60
2.4.5   特性        60
2.4.6   復(fù)雜性分析舉例        61
2.5   實(shí)際復(fù)雜性        66
2.6   性能測量        68
2.6.1   選擇實(shí)例的大小        69
2.6.2   設(shè)計測試數(shù)據(jù)        69
2.6.3   進(jìn)行實(shí)驗(yàn)        69
2.7   參考及推薦讀物        74
第二部分   數(shù)據(jù)結(jié)構(gòu)
第3章   數(shù)據(jù)描述        75
3.1   引言        75
3.2   線性表        76
3.3   公式化描述        77
3.3.1   基本概念        77
3.3.2   異常類NoMem        79
3.3.3   操作        79
3.3.4   評價        83
3.4   鏈表描述        86
3.4.1   類ChainNode 和Chain        86
3.4.2   操作        88
3.4.3   擴(kuò)充類Chain        91
3.4.4   鏈表遍歷器類        92
3.4.5   循環(huán)鏈表        93
3.4.6   與公式化描述方法的比較        94
3.4.7   雙向鏈表        95
3.4.8   小結(jié)        96
3.5   間接尋址        99
3.5.1   基本概念        99
3.5.2   操作        100
3.6   模擬指針        102
3.6.1   SimSpace的操作        103
3.6.2   采用模擬指針的鏈表        106
3.7   描述方法的比較        110
3.8   應(yīng)用        111
3.8.1   箱子排序        111
3.8.2   基數(shù)排序        116
3.8.3   等價類        117
3.8.4   凸包        122
3.9   參考及推薦讀物        127
第4章   數(shù)組和矩陣        128
4.1   數(shù)組        128
4.1.1   抽象數(shù)據(jù)類型        128
4.1.2   C++數(shù)組        129
4.1.3   行主映射和列主映射        129
4.1.4   類Array1D        131
4.1.5   類Array2D        133
4.2   矩陣        137
4.2.1   定義和操作        137
4.2.2   類Matrix        138
4.3   特殊矩陣        141
4.3.1   定義和應(yīng)用        141
4.3.2   對角矩陣        143
4.3.3   三對角矩陣        144
4.3.4   三角矩陣        145
4.3.5   對稱矩陣        146
4.4   稀疏矩陣        149
4.4.1   基本概念        149
4.4.2   數(shù)組描述        149
4.4.3   鏈表描述        154
第5章   堆棧        161
5.1   抽象數(shù)據(jù)類型        161
5.2   派生類和繼承        162
5.3   公式化描述        163
5.3.1   Stack的效率        164
5.3.2   自定義Stack        164
5.4   鏈表描述        166
5.5   應(yīng)用        169
5.5.1   括號匹配        169
5.5.2   漢諾塔        170
5.5.3   火車車廂重排        172
5.5.4   開關(guān)盒布線        176
5.5.5   離線等價類問題        178
5.5.6   迷宮老鼠        180
5.6   參考及推薦讀物        188
第6章   隊列        189
6.1   抽象數(shù)據(jù)類型        189
6.2   公式化描述        190
6.3   鏈表描述        194
6.4   應(yīng)用        197
6.4.1   火車車廂重排        197
6.4.2   電路布線        201
6.4.3   識別圖元        204
6.4.4   工廠仿真        206
6.5   參考及推薦讀物        217
第7章   跳表和散列        218
7.1   字典        218
7.2   線性表描述        219
7.3   跳表描述        222
7.3.1   理想情況        222
7.3.2   插入和刪除        223
7.3.3   級的分配        224
7.3.4   類SkipNode        224
7.3.5   類SkipList        225
7.3.6   復(fù)雜性        229
7.4   散列表描述        229
7.4.1   理想散列        229
7.4.2   線性開型尋址散列        230
7.4.3   鏈表散列        234
7.5   應(yīng)用——文本壓縮        238
7.5.1   LZW壓縮        239
7.5.2   LZW壓縮的實(shí)現(xiàn)        239
7.5.3   LZW解壓縮        243
7.5.4   LZW解壓縮的實(shí)現(xiàn)        243
7.6   參考及推薦讀物        247
第8章   二叉樹和其他樹        248
8.1   樹        248
8.2   二叉樹        251
8.3   二叉樹的特性        252
8.4   二叉樹描述        253
8.4.1   公式化描述        253
8.4.2   鏈表描述        254
8.5   二叉樹常用操作        256
8.6   二叉樹遍歷        256
8.7   抽象數(shù)據(jù)類型BinaryTree        259
8.8   類BinaryTree        260
8.9   抽象數(shù)據(jù)類型及類的擴(kuò)充        263
8.9.1   輸出        263
8.9.2   刪除        264
8.9.3   計算高度        264
8.9.4   統(tǒng)計節(jié)點(diǎn)數(shù)        265
8.10   應(yīng)用        265
8.10.1   設(shè)置信號放大器        265
8.10.2   在線等價類        268
8.11   參考及推薦讀物        275
第9章   優(yōu)先隊列        276
9.1   引言        276
9.2   線性表        277
9.3   堆        278
9.3.1   定義        278
9.3.2   最大堆的插入        279
9.3.3   最大堆的刪除        279
9.3.4   最大堆的初始化        280
9.3.5   類MaxHeap        281
9.4   左高樹        285
9.4.1   高度與寬度優(yōu)先的最大及最小
左高樹        285
9.4.2   最大HBLT的插入        287
9.4.3   最大HBLT的刪除        287
9.4.4   合并兩棵最大HBLT        287
9.4.5   初始化最大HBLT        289
9.4.6   類MaxHBLT        289
9.5   應(yīng)用        293
9.5.1   堆排序        293
9.5.2   機(jī)器調(diào)度        294
9.5.3   霍夫曼編碼        297
9.6   參考及推薦讀物        302
第10章   競��?303
10.1   引言        303
10.2   抽象數(shù)據(jù)類型WinnerTree        306
10.3   類WinnerTree        307
10.3.1   定義        307
10.3.2   類定義        307
10.3.3   構(gòu)造函數(shù)、析構(gòu)函數(shù)及Winner
函數(shù)        308
10.3.4   初始化贏者樹        308
10.3.5   重新組織比賽        310
10.4   輸者樹        311
10.5   應(yīng)用        312
10.5.1   用最先匹配法求解箱子裝載
問題        312
10.5.2   用相鄰匹配法求解箱子裝載
問題        316
第11章   搜索樹        319
11.1   二叉搜索樹        320
11.1.1   基本概念        320
11.1.2   抽象數(shù)據(jù)類型BSTree和
IndexedBSTree        321
11.1.3   類BSTree        322
11.1.4   搜索        322
11.1.5   插入        323
11.1.6   刪除        324
11.1.7   類DBSTree        326
11.1.8   二叉搜索樹的高度        327
11.2   AVL樹        328
11.2.1   基本概念        328
11.2.2   AVL樹的高度        328
11.2.3   AVL樹的描述        329
11.2.4   AVL搜索樹的搜索        329
11.2.5   AVL搜索樹的插入        329
11.2.6   AVL搜索樹的刪除        332
11.3   紅－黑樹        334
11.3.1   基本概念        334
11.3.2   紅－黑樹的描述        336
11.3.3   紅－黑樹的搜索        336
11.3.4   紅－黑樹的插入        336
11.3.5   紅－黑樹的刪除        339
11.3.6   實(shí)現(xiàn)細(xì)節(jié)的考慮及復(fù)雜性分析        343
11.4   B－樹        344
11.4.1   索引順序訪問方法        344
11.4.2   m 叉搜索樹        345
11.4.3   m 序B－樹        346
11.4.4   B－樹的高度        347
11.4.5   B－樹的搜索        348
11.4.6   B－樹的插入        348
11.4.7   B－樹的刪除        350
11.4.8   節(jié)點(diǎn)結(jié)構(gòu)        353
11.5   應(yīng)用        354
11.5.1   直方圖        354
11.5.2   用最優(yōu)匹配法求解箱子裝載
問題        357
11.5.3   交叉分布        359
11.6   參考及推薦讀物        363
第12章   圖        365
12.1   基本概念        365
12.2   應(yīng)用        366
12.3   特性        368
12.4   抽象數(shù)據(jù)類型Graph和Digraph        370
12.5   無向圖和有向圖的描述        371
12.5.1   鄰接矩陣        371
12.5.2   鄰接壓縮表        373
12.5.3   鄰接鏈表        374
12.6   網(wǎng)絡(luò)描述        375
12.7   類定義        376
12.7.1   不同的類        376
12.7.2   鄰接矩陣類        377
12.7.3   擴(kuò)充Chain類        380
12.7.4   類LinkedBase        381
12.7.5   鏈接類        382
12.8   圖的遍歷        386
12.8.1   基本概念        386
12.8.2   鄰接矩陣的遍歷函數(shù)        387
12.8.3   鄰接鏈表的遍歷函數(shù)        388
12.9   語言特性        389
12.9.1   虛函數(shù)和多態(tài)性        389
12.9.2   純虛函數(shù)和抽象類        391
12.9.3   虛基類        391
12.9.4   抽象類和抽象數(shù)據(jù)類型        393
12.10   圖的搜索算法        394
12.10.1   寬度優(yōu)先搜索        394
12.10.2   類Network        395
12.10.3   BFS的實(shí)現(xiàn)        395
12.10.4   BFS的復(fù)雜性分析        396
12.10.5   深度優(yōu)先搜索        397
12.11   應(yīng)用        399
12.11.1   尋找路徑        399
12.11.2   連通圖及其構(gòu)件        400
12.11.3   生成樹        402
第三部分   算法設(shè)計方法
第13章   貪婪算法        405
13.1   最優(yōu)化問題        405
13.2   算法思想        406
13.3   應(yīng)用        409
13.3.1   貨箱裝船        409
13.3.2   0/1背包問題           410
13.3.3   拓?fù)渑判?nbsp;       412
13.3.4   二分覆蓋        415
13.3.5   單源最短路徑        421
13.3.6   最小耗費(fèi)生成樹        424
13.4   參考及推薦讀物        433
第14章   分而治之算法        434
14.1   算法思想        434
14.2   應(yīng)用        440
14.2.1   殘缺棋盤        440
14.2.2   歸并排序        443
14.2.3   快速排序        447
14.2.4   選擇        452
14.2.5   距離最近的點(diǎn)對        454
14.3   解遞歸方程        462
14.4   復(fù)雜性的下限        463
14.4.1   最小最大問題的下限        464
14.4.2   排序算法的下限        465
第15章   動態(tài)規(guī)劃        467
15.1   算法思想        467
15.2   應(yīng)用        469
15.2.1   0/1背包問題        469
15.2.2   圖像壓縮        471
15.2.3   矩陣乘法鏈        476
15.2.4   最短路徑        480
15.2.5   網(wǎng)絡(luò)的無交叉子集        483
15.2.6   元件折疊        486
15.3   參考及推薦讀物        491
第16章   回溯        492
16.1   算法思想        492
16.2   應(yīng)用        496
16.2.1   貨箱裝船        496
16.2.2   0/1背包問題        503
16.2.3   最大完備子圖        506
16.2.4   旅行商問題        508
16.2.5   電路板排列        510
第17章   分枝定界        516
17.1   算法思想        516
17.2   應(yīng)用        519
17.2.1   貨箱裝船        519
17.2.2   0/1背包問題        526
17.2.3   最大完備子圖        528
17.2.4   旅行商問題        529
17.2.5   電路板排列        532



本資源免費(fèi)奉送，15.5 MB。
----------------------------------------------------------------------------

數(shù)據(jù)結(jié)構(gòu)算法與應(yīng)用-C++語言描述-Sahni.rar
---------------------------------------------------------------------------- 返回小木蟲查看更多