《數據結構與算法分析——C++語言描述（第2版）》是2014年清華大學出版社出版的圖書，作者是Larry Nyhoff。
基本介紹
- 書名：數據結構與算法分析——C++語言描述（第2版
- 作者：（美）奈霍夫
- 譯者：黃達明
- ISBN：9787302138396
- 頁數：830
- 定價：98.00元
- 出版社：清華大學出版社
- 出版時間：2014年8月28日
- 裝幀：平裝
圖書簡介,內容簡介,目錄,
圖書簡介
本書準備了很多輔助資料：
*本書中例子的原始碼。
其他輔助資料。
*本書中例子的原始碼。
其他輔助資料。
內容簡介
本書的第1版來自於對作者在長達20年的時間裡教授一門數據結構入門課程（通常是CS2）的經驗的總結。接著發展成為由JoelAdams和LarryNyhoff編著的，被廣泛使用的“C++:AnIntroductiontoComputing”，一本起源於他們多年來以C++教授的第一門程式設計課程（CS1）的書籍。但是計算機科學教學目錄隨著教育方法和方法學的改變也改變了。為了跟上這些變化，這本入門性質的C++教材也經過了修訂，最近推出了第3版。
目錄
第1章 軟體開發 1
1.1 問題分析和需求規格說明 3
1.2 設計 5
1.2.1 自頂向下設計 5
1.2.2 面向對象設計 7
1.2.3 小規模設計 9
1.3 編碼 15
1.4 測試、運行和調試 27
1.5 維護 34
1.6 本章小結 36
第2章 抽象數據類型入門 40
2.1 對ADT及其實現的第一瞥 40
2.2 C++的簡單數據類型 41
2.2.1 整型數據 42
2.2.2 實型數據 46
2.2.3 字元數據 49
2.4.4 布爾數據 50
2.3 程式設計師定義的數據類型 53
2.3.1 Typedefs 53
2.3.2 枚舉 53
2.3.3 類 55
2.4 指針 56
2.4.1 聲明和初始化指針 57
2.4.2 基本指針操作 60
2.4.3 動態記憶體分配——new操作 64
2.4.4 關於引用形參的注釋 65
2.5 本章小結 68
第3章 數據結構和抽象數據類型 73
3.1 數據結構，抽象數據類型和實現 73
3.2 靜態數組 77
3.2.1 一維靜態數組 78
3.2.2 下標運算 81
3.2.3 數組作為形參 82
3.2.4 越界錯誤 83
3.2.5 數組的問題 86
3.3 多維數組 88
3.3.1 二維數組 88
3.3.2 高維數組 89
3.3.3 數組的數組聲明 91
3.3.4 多維數組作函式參數 95
3.4 動態數組 97
3.4.1 new操作——動態數組 98
3.4.2 指針的其他用法 110
3.5 C風格結構（可選） 112
指向結構的指針 116
3.6 過程式編程 117
過程式編程的例子 118
3.7 本章小結 123
第4章 OOP和ADT進階——類 129
4.1 過程式編程vs.面向對象編程 129
4.2 類 130
4.2.1 “傳統的”（C）結構和OOP
（C++）結構以及類之間的
區別 131
4.2.2 類聲明 131
4.3 例子：用戶定義的Time類的
第一個版本 135
4.3.1 為什麼不使所有成員都
公有化 137
4.3.2 實現一個類 138
4.3.3 一些現象 141
4.4 類構造函式 142
4.5 其他類操作 150
4.5.1 複製操作——初始化和
賦值 150
4.5.2 訪問函式和更動函式 151
4.5.3 重載運算符 153
4.5.4 重載輸入/輸出運算符 154
4.5.5 其他操作：前進和關係
操作 161
4.5.6 總結以及其他一些細節 163
4.5.7 指向類對象的指針 167
4.5.8 this指針 168
4.6 本章小結 171
第5章 標準C++輸入/輸出和字
符串類 176
5.1 C++標準I/O類 177
5.1.1 istream類 178
5.1.2 ostream類 182
5.1.3 檔案I/O：ifstream和
ofstream類 186
5.1.4 I/O類層次 188
5.2 C++ String類型 192
5.2.1 C風格的字元串 193
5.2.2 一個字元串類 195
5.2.3 C++ String類 196
5.2.4 String流 204
5.3 案例學習：文本編輯 208
5.4 模式匹配介紹（可選） 216
5.5 數據加密介紹（可選） 219
5.5.1 數據加密標準（Data Encryption
Standard） 222
5.5.2 公共密鑰加密（Public-Key
Encryption） 222
5.6 本章小結 224
第6章 列表 228
6.1 作為ADT的列表 229
設計和創建一個列表類 230
6.2 基於數組的列表實現 231
6.2.1 選擇存儲結構 231
6.2.2 實現操作 232
6.2.3 一個使用靜態數組存儲的
列表類 234
6.3 使用動態分配的基於數組實現的
列表 242
6.3.1 類中的動態分配——析構函式、複製構造函式和賦值運算符 246
6.3.2 最後一點 253
6.4 對鍊表的介紹 257
6.4.1 它們是什麼 257
6.4.2 實現基本列表操作 258
6.4.3 小結 262
6.5 在C++中基於指針來實現鍊表 264
6.5.1 節點結構 264
6.5.2 鍊表實現中的數據成員 266
6.5.3 鍊表實現中的函式成員 267
6.6 基於數組的鍊表實現 271
6.6.1 節點結構 272
6.6.2 存儲池管理 274
6.7 本章小結 276
第7章 棧 280
7.1 棧的介紹 281
7.2 設計和創建一個Stack類——
基於數組 285
7.2.1 選擇存儲結構 285
7.2.2 實現操作 288
7.2.3 實現pop操作的算法 290
7.2.4 完整的Stack類 290
7.2.5 使用動態數組存儲棧元素 296
7.2.6 前瞻 309
7.3 鏈式棧 312
7.3.1 選擇存儲結構 313
7.3.2 實現操作 314
7.3.3 完整的Stack類：鍊表
版本 317
7.4 棧在函式調用中的使用 324
7.5 案例學習：後綴（RPN）表示 329
7.5.1 計算後綴表達式 330
7.5.2 將中綴表達式轉換成後綴
表達式 331
7.6 本章小節 341
第8章 佇列 345
8.1 佇列入門 345
8.2 設計和創建一個Queue類——
基於數組 353
8.2.1 使用靜態數組存儲佇列
元素 356
8.2.2 使用動態數組存儲佇列
元素 361
8.3 鏈式佇列 365
8.3.1 一種自然的鍊表實現 365
8.3.2 使用循環鍊表 374
8.4 佇列的套用：緩衝區和調度 376
8.5 案例學習：信息中心仿真 379
8.5.1 問題分析和需求規格說明 380
8.5.2 創建一個Simulation類 380
8.5.3 Time類和Call類 389
8.6 本章小結 390
第9章 ADT實現：模板和標準容器 393
9.1 介紹：可重用性和通用性的發展 394
9.1.1 從算法到算法 394
9.1.2 從數據到容器 396
9.2 函式通用性——重載和模板 396
9.2.1 重載 397
9.2.2 函式模板 399
9.2.3 另一個例子：顯示一個
數組 403
9.3 類通用性——模板 404
9.3.1 Typedef有什麼錯 404
9.3.2 類模板 405
9.3.3 Stack類模板的另一個版本 417
9.3.4 對標準C++容器類模板的
快速一瞥 418
9.4 vector容器 420
9.4.1 定義vector對象 421
9.4.2 一些vector操作 423
9.4.3 內部實現一瞥——增加
容量 427
9.4.4 對疊代器的第一次探討 430
9.4.5 一些牽涉到疊代器的vector
函式成員 433
9.4.6 綜合比較：vector對數組 434
9.5 案例學習：計算機系統登錄統計 438
9.6 多維vector（可選） 443
9.6.1 二維vector對象 443
9.6.2 二維vector操作 444
9.7 其他標準容器——deque、stack以及queue 447
9.7.1 STL的deque類模板 447
9.7.2 我們的stack類模板的一個
新（但是非必須的）版本 450
9.7.3 STL的stack適配器 452
9.7.4 STL的queue適配器 453
9.8 Bitset和Valarray（可選） 454
9.8.1 Bitset 454
9.8.2 Valarray 456
9.8.3 Slics、Mask、以及間接
數組 458
9.9 本章小結 459
第10章 ADT實現--遞歸、算法分析
以及標準算法 464
10.1 遞歸 464
10.1.1 遞歸的例子 465
10.1.2 遞歸函式的編碼 466
10.1.3 糟糕遞歸的例子：Fibonacci
數字 468
10.1.4 例子：折半查找 470
10.1.5 例子：回文檢查程式 473
10.2 遞歸的例子：Hanoi塔；分析 478
10.2.1 Hanoi塔 478
10.2.2 分析 481
10.3 實現遞歸 485
10.4 算法效率 489
10.5 C++中的標準算法 500
10.5.1 例：STL的sort算法 500
10.5.2 STL算法的例子 505
10.5.3 <numeric>庫中的算法 506
10.5.4 例：花樣滑冰評判 507
10.6 算法正確性證明(可選) 508
10.6.1 例：計算平均值 509
10.6.2 例：遞歸求冪函式 510
10.6.3 總結 511
10.7 本章小節 513
第11章 其他鍊表結構 519
11.1 單向鍊表的某些變種 519
11.1.1 帶頭節點的鍊表 519
11.1.2 循環鍊表 522
11.2 稀疏多項式的鏈式實現 526
11.3 雙向鍊表和標準C++list 534
11.3.1 雙向鍊表 534
11.3.2 標準list類模板 536
11.3.3 例：網際網路地址 542
11.3.4 對C++中list的內部一瞥 546
11.4 案例學習：長整數運算 551
11.4.1 問題 551
11.4.2 設計 551
11.4.3 實現 553
11.5 其他鏈列表 560
11.5.1 多序列表 560
11.5.2 稀疏矩陣 561
11.5.3 廣義表 563
11.6 本章小結 566
第12章 二叉樹和散列表 571
12.1 線性查找和折半查找的複習 571
12.1.1 線性查找 572
12.1.2 折半查找 573
12.2 二叉樹的介紹 576
12.2.1 樹的定義 577
12.2.2 二叉樹的一些例子 578
12.2.3 二叉樹的數組表示 579
12.2.4 二叉樹的鍊表表示 581
12.3 作為遞歸數據結構的二叉樹 583
12.4 二叉查找樹 589
12.4.1 BST的實現 590
12.4.2 遍歷BST 592
12.4.3 BST的查找 596
12.4.4 BST中的插入操作 599
12.4.5 從BST中刪除一個節點 602
12.4.6 不平衡（Lopsidedness）
問題 612
12.5 案例學習：計算機登錄驗證 616
12.5.1 問題 616
12.5.2 設計 616
12.5.3 編碼 617
12.6 線索化二叉查找樹（可選） 620
12.7 散列表 624
12.7.1 散列函式 625
12.7.2 衝突處理策略 626
12.7.3 改進 627
12.8 本章小結 631
第13章 排序 636
13.1 某些計算時間為O(n2)的排序
方法 637
13.1.1 選擇排序 637
13.1.2 交換排序 639
13.1.3 插入排序 641
13.1.4 排序算法的性能比較 643
13.1.5 間接排序 644
13.2 堆、堆排序和優先佇列 647
13.2.1 堆 648
13.2.2 堆的基本操作 649
13.2.3 堆排序 652
13.2.4 STL中的堆算法 655
13.2.5 堆和優先佇列 658
13.3 快速排序 662
13.3.1 拆分操作 663
13.3.2 快速排序 665
13.3.3 改進 668
13.4 歸併排序 670
13.4.1 歸併列表 670
13.4.2 折半歸併排序 672
13.4.3 自然歸併排序 674
13.5 基數排序（Radix Sort） 677
13.6 本章小結 680
第14章 OOP和ADT 684
14.1 OOP和ADT的簡要歷史和概覽 684
14.1.1 封裝性 685
14.1.2 繼承性 686
14.1.3 多態性和動態聯編 687
14.2 繼承和面向對象設計 688
14.2.1 第1個例子：許可證 689
14.2.2 公有、私有和保護域 693
14.2.3 派生類的形式 693
14.2.4 類之間的Is-a、Has-a和
Uses-a關係 694
14.3 創建派生類 696
14.3.1 派生類構造函式 697
14.3.2 訪問繼承的數據成員 697
14.3.3 復用操作 698
14.3.4 例子：棧和有限棧 700
14.4 案例學習：工資 703
14.4.1 問題 703
14.4.2 設計 703
14.5 多態性、虛函式和ADT 711
14.5.1 為什麼需要多態性：聯編
問題 711
14.5.2 虛函式和動態聯編 713
14.5.3 例1：使用句柄 716
14.5.4 例2：棧和有限棧 717
14.5.5 純虛函式和抽象類 720
14.6 案例學習：異構數據結構 722
14.6.1 虛函式的必要性 723
14.7 本章小結 726
第15章 樹 729
15.1 案例學習：哈夫曼編碼 729
15.1.1 變長碼 730
15.1.2 立刻可解碼性 730
15.1.3 哈夫曼編碼 731
15.2 平衡樹：AVL樹 735
15.2.1 例子：州簡稱的BST 735
15.2.2 基本的重新平衡旋轉
操作 743
15.3 2-3-4樹、紅-黑樹、B-樹和
其他樹 748
15.3.1 2-3-4樹 750
15.3.2 紅-黑樹 756
15.3.3 B-樹 760
15.3.4 用二叉樹來表示樹和
森林 761
15.4 STL中的關聯容器——
map（可選） 765
15.5 本章小結 771
第16章 圖和有向圖 773
16.1 有向圖 773
16.1.1 鄰接矩陣表示（Adjacency-
Matrix Representation） 775
16.1.2 鄰接表表示（Adjacency-
List Representation） 776
16.2 搜尋和遍歷有向圖 781
16.2.1 深度優先搜尋 782
16.2.2 廣度優先搜尋 783
16.2.3 遍歷和最短路經問題 785
16.2.4 NP完全性問題 794
16.3 圖 796
16.3.1 鄰接矩陣和鄰接表表示 797
16.3.2 邊列表表示 798
16.3.3 連通性 799
16.4 本章小結 810
附錄A ASCII字元集 812
附錄B 小測驗答案 814
