基本介紹
- 書名：數據結構C和C++語言描述（第2版）
- ISBN：9787302080688
- 定價：68元
- 出版時間：2004-3-11
- 裝幀：平裝
圖書簡介,目錄,
圖書簡介
本書是一本非常暢銷的數據結構基礎教材的第2版，它使用標準ANSIC和C++程式設計語言來實現數據結構。我們通過大量實際的問題演示了如何套用C和C++程式來實現抽象概念，並逐步地指導讀者標識問題，實現解決方案，以及將方案套用到實際情況中。對於專業程式設計師來說，本書也是極有價值的參考書。
目錄
第1章數據結構入門 1
1.1信息和涵義 1
1.1.1二進制整數和十進制整數 2
1.1.2實數 3
1.1.3字元串 4
1.1.4硬體和軟體 5
1.1.5實現的概念 6
1.1.6示例 6
1.1.7抽象數據類型 10
1.1.8序列的值定義 13
1.1.9變長字元串的ADT表示 14
1.1.10C的數據類型 16
1.1.11C中的指針 16
1.1.12C中的數據結構 18
1.1.13練習1 19
1.2C中的數組 19
1.2.1數組的抽象數據類型定義 20
1.2.2使用一維數組 21
1.2.3一維數組的實現 23
1.2.4將數組作為參數 25
1.2.5C中的字元串 25
1.2.6字元串操作 26
1.2.7二維數組 27
1.2.8多維數組 29
1.2.9練習2 31
1.3C中的結構 33
1.3.1結構的實現 37
1.3.2聯合(Union) 38
1.3.3聯合的實現 41
1.3.4結構參數 42
1.3.5表示其他數據結構 44
1.3.6有理數 44
1.3.7記憶體的分配和變數的作用域 47
1.3.8練習3 51
1.4C++中的類 53
1.4.1Rational類 53
1.4.2Rational類的使用 54
1.4.3方法的實現 56
1.4.4重載 61
1.4.5繼承 61
1.4.6構造函式 63
1.4.7練習4 64
第2章堆疊 65
2.1定義和示例 65
2.1.1基本操作 66
2.1.2示例 67
2.1.3堆疊的抽象數據類型定義 70
2.1.4練習1 71
2.2用C描述堆疊 71
2.2.1pop操作的實現 75
2.2.2測試異常情況 76
2.2.3實現push操作 77
2.2.4練習2 79
2.3示例：中綴、後綴和前綴 80
2.1.4練習1 71
2.2用C描述堆疊 71
2.2.1pop操作的實現 75
2.2.2測試異常情況 76
2.2.3實現push操作 77
2.2.4練習2 79
2.3示例：中綴、後綴和前綴 80
2.3.1基本定義和示例 80
2.3.2後綴表達式的計算 82
2.3.3計算後綴表達式的程式 83
2.3.4程式的局限性 85
2.3.5中綴表達式轉換為後綴表達式 86
2.3.6將中綴表達式轉換為後綴表達式的程式 90
2.3.7用C++模板實現的堆疊 92
2.3.8練習3 97
第3章遞歸 100
3.1遞歸定義和遞歸過程 100
3.1.1階乘函式 100
3.1.2自然數的乘法 102
3.1.3斐波納契數列 103
3.1.4對分查找 104
3.1.5遞歸定義或算法的特點 107
3.1.6練習1 107
3.2C中的遞歸 108
3.2.1用C實現階乘 108
3.2.2用C實現斐波納契數列 111
3.2.3用C實現對分查找 113
3.2.4遞歸鏈 114
3.2.5代數表達式的遞歸定義 115
3.2.6練習2 118
3.3編寫遞歸程式 120
3.3.1漢諾塔問題 121
3.3.2使用遞歸將前綴表達式轉換為後綴表達式 125
3.3.3練習3 129
3.4遞歸的模擬 131
3.4.1從函式中返回 133
3.4.2遞歸函式的實現 134
3.4.3階乘的模擬 134
3.4.4最佳化模擬例程 138
3.4.5消除goto語句 140
3.4.6模擬漢諾塔問題 142
3.4.7練習4 147
3.5遞歸的效率 149
第4章佇列和鍊表 151
4.1佇列及其順序表示 151
4.1.1佇列的抽象數據類型定義 152
4.1.2佇列的C語言實現 152
4.1.3insert操作 156
4.1.4優先佇列 157
4.1.5用數組實現的優先佇列 157
4.1.6練習1 159
4.2鍊表 160
4.2.1從鍊表中插入和刪除結點 161
4.2.2堆疊的鍊表實現 164
4.2.3getnode和freenode操作 165
4.2.4佇列的鍊表實現 166
4.2.5鍊表數據結構 167
4.2.6鍊表操作的例子 169
4.2.7優先佇列的鍊表實現 171
4.2.8頭結點 171
4.2.9練習2 172
4.3C中的鍊表 173
4.3.1鍊表的數組實現 173
4.3.2數組實現的局限性 176
4.3.3動態變數的分配和釋放 176
4.3.4使用動態變數實現的鍊表 180
4.3.5用鍊表實現的佇列 181
4.3.6C中鍊表操作的例子 183
4.3.7非整數鍊表和非齊次鍊表 184
4.3.8數組實現和動態實現鍊表的比較 186
4.3.9頭結點的實現 186
4.3.10練習3 186
4.4示例：用鍊表進行模擬 188
4.4.1模擬進程 188
4.4.2數據結構 189
4.4.3模擬程式 190
4.4.4練習4 193
4.5其他鍊表結構 195
4.5.1循環鍊表 195
4.5.2用循環鍊表表示堆疊 196
4.5.3用循環鍊表表示佇列 197
4.5.4循環鍊表的基本操作 197
4.5.5約瑟夫問題 199
4.5.6頭結點 200
4.5.7使用循環鍊表實現長正整數的加法 201
4.5.8雙向鍊表 203
4.5.9使用雙向鍊表實現長整數的加法 205
4.5.10練習5 209
4.6C++中的鍊表 210
第5章樹 214
5.1二叉樹 214
5.1.1二叉樹中的操作 218
5.1.2二叉樹的套用 219
5.1.3練習1 223
5.2二叉樹的表示 224
5.2.1二叉樹的結點表示 224
5.2.2內部結點和外部結點 227
5.2.3二叉樹的隱式數組表示 227
5.2.4選擇一個二叉樹表示 231
5.2.5二叉樹遍歷的C語言表示 232
5.2.6線索化二叉樹 234
5.2.7使用father欄位的遍歷 238
5.2.8異構二叉樹 240
5.2.9練習2 241
5.3示例：哈夫曼算法 243
5.3.1哈夫曼算法 245
5.3.2C程式 247
5.3.3練習3 250
5.4將表表示為二叉樹 251
5.4.1尋找第k個元素 252
5.4.2刪除元素 254
5.4.3用C語言實現用樹表示的表 257
5.4.4構建一個用樹表示的表 259
5.4.5回顧約瑟夫問題 261
5.4.6練習4 262
5.5樹及其套用 262
5.5.1樹的C語言表示 264
5.5.2樹的遍歷 267
5.5.3用樹來表示廣義表達式 268
5.5.4對表達式樹求值 270
5.5.5構建樹 272
5.5.6練習5 274
5.6示例：遊戲樹 275
第6章排序 282
6.1背景 282
6.1.1效率方面的考慮 284
6.1.2符號O 285
6.1.3排序的效率 287
6.1.4練習1 289
6.2交換排序 290
6.2.1冒泡排序 290
6.2.2快速排序 292
6.2.3快速排序的效率 298
6.2.4練習2 300
6.3選擇排序以及樹排序 301
6.3.1直接選擇排序 302
6.3.2二叉樹排序 303
6.3.3堆排序 305
6.3.4作為優先權佇列的堆 306
6.3.5使用堆進行排序 308
6.3.6堆排序的過程 310
6.3.7練習3 311
6.4插入排序 312
6.4.1簡單插入 312
6.4.2希爾排序 313
6.4.3地址計算排序 316
6.4.4練習4 318
6.5歸併排序以及基數排序 320
6.5.1歸併排序 320
6.5.2Cook-Kim算法 323
6.5.3基數排序 323
6.5.4練習5 327
第7章搜尋 329
7.1基本搜尋技術 329
7.1.1作為抽象數據類型的目錄 330
7.1.2算法符號 331
7.1.3順序搜尋 331
7.1.4順序搜尋的效率 333
7.1.5重新排序鍊表以最大化搜尋效率 334
7.1.6在有序表中進行搜尋 335
7.1.7使用索引的順序搜尋 335
7.1.8二叉樹搜尋 338
7.1.9插值搜尋 339
7.1.10練習1 340
7.2樹搜尋 342
7.2.1在二叉搜尋樹中插入元素 343
7.2.2在二叉搜尋樹中刪除元素 346
7.2.3二叉搜尋樹操作的效率 348
7.2.4不均勻的二叉搜尋樹的效率 350
7.2.5最佳搜尋樹 351
7.2.6平衡二叉樹 353
7.2.7練習2 360
7.3廣義搜尋樹 362
7.3.1多路搜尋樹 362
7.3.2在多路樹中進行搜尋 364
7.3.3實現多路樹 365
7.3.4遍歷多路樹 366
7.3.5在多路搜尋樹中進行插入 368
7.3.6B樹 372
7.3.7B樹插入算法 377
7.3.8計算father和index 380
7.3.9在多路搜尋樹中進行刪除 383
7.3.10多路搜尋樹的效率 387
7.3.11改進B樹 390
7.3.12B+樹 392
7.3.13數字搜尋樹 393
7.3.14Trie 396
7.3.15練習3 396
7.4散列 397
7.4.1使用開放定址來解決散列衝突 399
7.4.2從散列表刪除項 401
7.4.3再散列方法的效率 402
7.4.4散列表重新排序 404
7.4.5Brent方法 405
7.4.6二叉樹散列 407
7.4.7通過額外的存儲空間來獲得改進 409
7.4.8聯合散列 412
7.4.9單獨鏈地址法 414
7.4.10在外部存儲器中進行散列 416
7.4.11分離方法 418
7.4.12動態散列以及可擴展散列 419
7.4.13線性散列 423
7.4.14選擇散列函式 429
7.4.15理想的散列函式 430
7.4.16散列函式的通用類 434
7.4.17練習4 435
第8章圖及其套用 437
8.1圖 437
8.1.1圖的套用 439
8.1.2圖的C語言表示 440
8.1.3傳遞閉包 442
8.1.4Warshall算法 445
8.1.5最短路徑算法 446
8.1.6練習1 448
8.2流問題 449
8.2.1改進流函式 450
8.2.2示例 453
8.2.3算法和程式 454
8.2.4練習2 458
8.3圖的連結表示 458
8.3.1再訪Dijkstra算法 463
8.3.2組織圖結點集合 465
8.3.3調度的套用 465
8.3.4C程式 469
8.3.5練習3 472
8.4圖的遍歷以及生成森林 474
8.4.1圖的遍歷方法 474
8.4.2生成森林 477
8.4.3無向圖以及它們的遍歷 479
8.4.4深度優先遍歷 480
8.4.5深度優先遍歷的套用 483
8.4.6深度優先遍歷的效率 484
8.4.7廣度優先遍歷 484
8.4.8最小生成樹 486
8.4.9Kruskal算法 487
8.4.10Round-Robin算法 488
8.4.11練習4 488
第9章存儲管理 490
9.1廣義表 490
9.1.1修改表的操作 492
9.1.2示例 493
9.1.3表的鍊表表示 494
9.1.4表的表示 495
9.1.5crlist操作 497
9.1.6表頭的用法 499
9.1.7釋放表結點 499
9.1.8C中的廣義表 500
9.1.9程式語言和表 503
9.1.10練習1 504
9.2自動表管理 504
9.2.1引用計數方法 505
9.2.2無用信息收集 509
9.2.3無用信息收集的算法 510
9.2.4收集和壓縮 515
9.2.5無用信息收集的變種 521
9.2.6練習2 521
9.3動態存儲管理 522
9.3.1存儲塊的壓縮 523
9.3.2首次匹配、最佳匹配和最差匹配 525
9.3.3首次匹配方法的改進 528
9.3.4釋放存儲塊 529
9.3.5邊界標籤方法 531
9.3.6BuddySystem 533
9.3.7其他的BuddySystem 538
9.3.8練習3 540
8.3.2組織圖結點集合 465
8.3.3調度的套用 465
8.3.4C程式 469
8.3.5練習3 472
8.4圖的遍歷以及生成森林 474
8.4.1圖的遍歷方法 474
8.4.2生成森林 477
8.4.3無向圖以及它們的遍歷 479
8.4.4深度優先遍歷 480
8.4.5深度優先遍歷的套用 483
8.4.6深度優先遍歷的效率 484
8.4.7廣度優先遍歷 484
8.4.8最小生成樹 486
8.4.9Kruskal算法 487
8.4.10Round-Robin算法 488
8.4.11練習4 488
第9章存儲管理 490
9.1廣義表 490
9.1.1修改表的操作 492
9.1.2示例 493
9.1.3表的鍊表表示 494
9.1.4表的表示 495
9.1.5crlist操作 497
9.1.6表頭的用法 499
9.1.7釋放表結點 499
9.1.8C中的廣義表 500
9.1.9程式語言和表 503
9.1.10練習1 504
9.2自動表管理 504
9.2.1引用計數方法 505
9.2.2無用信息收集 509
9.2.3無用信息收集的算法 510
9.2.4收集和壓縮 515
9.2.5無用信息收集的變種 521
9.2.6練習2 521
9.3動態存儲管理 522
9.3.1存儲塊的壓縮 523
9.3.2首次匹配、最佳匹配和最差匹配 525
9.3.3首次匹配方法的改進 528
9.3.4釋放存儲塊 529
9.3.5邊界標籤方法 531
9.3.6BuddySystem 533
9.3.7其他的BuddySystem 538
9.3.8練習3 540
