內容簡介
本書全面介紹了數據結構的基礎內容，幫助學生深入了解軟體工程的思想和技術。學生還可以通過對一些高級編程概念（如接口、抽象和封裝）的了解，為進一步深入學習高級編程知識打下堅實的基礎。本書觀點清晰明了、語言風格鮮明獨特，深入淺出地介紹了一些高級主題。 本書特色： ◆介紹了多個庫包，可用於簡化編程流程，使學生可以專注於高層次理論問題的研究，避免了C語言編程的繁瑣細節； ◆詳細討論了遞歸編程的用法，包括大量難度各異的編程示例和練習，如簡單的遞歸函式，分析雙人遊戲的最小最大(minimax)策略，等等； ◆幫助讀者培養編寫健壯、可重用代碼的良好編程習慣。
圖書目錄
第Ⅰ部分 預備知識 1
第1章 ANSI C概述 1
1.1 什麼是C 1
1.2 C程式的結構 3
1.2.1 注釋 4
1.2.2 庫包含 5
1.2.3 程式級定義 5
1.2.4 函式原型 5
1.2.5 main程式 6
1.2.6 函式定義 7
1.3 變數、值和類型 7
1.3.1 變數 7
1.3.2 命名規則 8
1.3.3 局部變數和全局變數 9
1.3.4 數據類型的概念 9
1.3.5 整數類型 9
1.3.6 浮點類型 10
1.3.7 文本類型 11
1.3.8 布爾類型 12
1.3.9 簡單的輸入與輸出 12
1.4 表達式 14
1.4.1 優先權與結合性 14
1.4.2 表達式中的類型混合 15
1.4.3 整數除法和求余運算符 16
1.4.4 類型轉換 17
1.4.5 賦值運算符 17
1.4.6 遞增與遞減運算符 19
1.4.7 布爾運算符 20
1.5 語句 22
1.5.1 簡單語句 22
1.5.2 塊 22
1.5.3 if語句 23
1.5.4 switch語句 23
1.5.5 while語句 25
1.5.6 for語句 28
1.6 函式 29
1.6.1 返回函式結果 29
1.6.2 函式定義和原型 30
1.6.3 函式調用過程的機制 30
1.6.4 逐步求精 31
1.7 小結 31
1.8 複習題 32
1.9 編程練習 33
第2章 C的數據類型 38
2.1 枚舉類型 38
2.1.1 枚舉類型的內部表示 39
2.1.2 標量類型 40
2.1.3 理解typedef 41
2.2 數據和記憶體 41
2.2.1 位、位元組、字 42
2.2.2 記憶體地址 42
2.3 指針 44
2.3.1 把地址當作數值 44
2.3.2 聲明指針變數 45
2.3.3 基本的指針運算 45
2.3.4 特殊指針NULL 47
2.3.5 通過引用傳遞參數 48
2.4 數組 51
2.4.1 聲明數組 51
2.4.2 數組選擇 52
2.4.3 有效空間和已分配空間 53
2.4.4 作為參數傳遞數組 54
2.4.5 初始化數組 56
2.4.6 多維數組 57
2.5 指針和數組 59
2.5.1 指針運算 60
2.5.2 指針的自加和自減 62
2.5.3 指針和數組的關係 62
2.6 記錄 64
2.6.1 定義一種新的結構類型 65
2.6.2 聲明結構變數 66
2.6.3 記錄選擇 66
2.6.4 初始化紀錄 66
2.6.5 記錄的指針 67
2.7 動態分配 68
2.7.1 類型void* 68
2.7.2 應對記憶體限制 70
2.7.3 動態數組 71
2.7.4 動態記錄 72
2.8 小結 73
2.9 複習題 74
2.10 編程練習 76
第3章 庫和接口 83
3.1 接口的概念 83
3.1.1 接口和實現 84
3.1.2 包和抽象 84
3.1.3 良好的接口設計規則 85
3.2 隨機數字 85
3.2.1 random.h接口的結構 86
3.2.2 構建客戶程式 89
3.2.3 有關隨機數字的ANSI函式 91
3.2.4 實現random.c 93
3.3 字元串 96
3.3.1 字元串的底層表示 96
3.3.2 數據類型string 97
3.3.3 ANSI字元串庫 98
3.3.4 接口strlib.h 102
3.4 標準的I/O庫 108
3.4.1 數據檔案 108
3.4.2 在C中使用檔案 109
3.4.3 標準檔案 110
3.4.4 字元I/O 110
3.4.5 從輸入檔案中重讀字元 111
3.4.6 更新檔案 112
3.4.7 面向行的I/O 113
3.4.8 格式化的I/O 114
3.4.9 scanf函式 115
3.5 其他ANSI庫 116
3.6 小結 118
3.7 複習題 118
3.8 編程練習 120
第Ⅱ部分 遞歸和算法分析 127
第4章 遞歸入門 127
4.1 一個簡單的遞歸示例 128
4.2 階乘函式 129
4.2.1 Fact的遞歸公式 130
4.2.2 追蹤遞歸過程 130
4.2.3 遞歸跳躍的信任 134
4.3 費波那契函式 134
4.3.1 計算費波那契序列 135
4.3.2 增進實現遞歸的信心 136
4.3.3 遞歸實現的效率 137
4.3.4 不應該責備遞歸 138
4.4 其他遞歸示例 139
4.4.1 探測回文 139
4.4.2 二分查找 142
4.4.3 互動遞歸 143
4.5 以遞歸的方式思考 144
4.5.1 保持整體觀 145
4.5.2 避免常見的錯誤 145
4.6 小結 146
4.7 複習題 147
4.8 編程練習 149
第5章 遞歸過程 152
5.1 漢諾塔 152
5.1.1 分解問題 153
5.1.2 尋找遞歸策略 153
5.1.3 驗證遞歸策略 155
5.1.4 解決方案的編碼 156
5.1.5 追蹤遞歸過程 156
5.2 產生排列 160
5.3 遞歸在繪圖中的套用 162
5.3.1 圖形庫 162
5.3.2 電腦藝術示例 165
5.3.3 不規則碎片形 169
5.4 小結 173
5.5 複習題 174
5.6 編程練習 175
第6章 回溯算法 183
6.1 用遞歸回溯解決迷宮問題 183
6.1.1 右手規則 183
6.1.2 尋找遞歸方法 184
6.1.3 識別簡單情景 185
6.1.4 編寫迷宮解決方案算法 186
6.1.5 確信解決方案可以正確運行 190
6.2 回溯與遊戲 192
6.2.1 拿子遊戲 193
6.2.2 常規化的雙人遊戲程式 199
6.2.3 最小最大策略 200
6.2.4 實現最小最大化算法 202
6.2.5 在具體的遊戲中採用常規策略 204
6.3 小結 216
6.4 複習題 217
6.5 編程練習 218
第7章 算法分析 225
7.1 排序問題 225
7.1.1 選擇排序算法 226
7.1.2 性能的經驗度量 227
7.1.3 分析選擇排序的性能 228
7.2 計算複雜度 230
7.2.1 大O符號 230
7.2.2 大O的標準簡化 230
7.2.3 排序算法的計算複雜度 231
7.2.4 根據代碼結構預測計算複雜度 232
7.2.5 最差情況複雜度與平均情況複雜度 233
7.2.6 大O的正式定義 233
7.3 遞歸幫助 235
7.3.1 分治策略的威力 235
7.3.2 合併兩個數組 236
7.3.3 合併排序算法 237
7.3.4 合併排序的計算複雜度 239
7.3.5 比較N2和NlogN的性能 240
7.4 標準複雜度類型 241
7.5 快速排序算法 242
7.5.1 分割數組 244
7.5.2 分析快速排序的性能 246
7.6 數學歸納法 247
7.7 小結 250
7.8 複習題 250
7.9 編程練習 252
第Ⅲ部分 數 據 抽 象 257
第8章 抽象數據類型 257
8.1 堆疊 258
8.1.1 基本的堆疊比喻 258
8.1.2 堆疊和函式調用 258
8.1.3 堆疊和袖珍計算器 259
8.2 定義堆疊的ADT 259
8.2.1 定義堆疊抽象的類型 260
8.2.2 不透明類型 261
8.2.3 定義stack.h接口 262
8.3 在應用程式中使用堆疊 265
8.4 實現堆疊抽象 269
8.4.1 定義具體類型 269
8.4.2 實現堆疊操作 269
8.4.3 不透明類型的優點 271
8.4.4 改進stack.c的實現 272
8.5 定義掃描器ADT 273
8.5.1 封裝狀態的危險 274
8.5.2 抽象數據類型作為封裝狀態的替代 274
8.5.3 實現掃描器抽象 279
8.6 小結 283
8.7 複習題 284
8.8 編程練習 285
第9章 效率與ADT 297
9.1 編輯器緩衝區的概念 297
9.2 定義緩衝區抽象 298
9.2.1 接口buffer.h中的函式 299
9.2.2 為編輯器應用程式編寫代碼 301
9.3 用數組實現編輯器 303
9.3.1 定義具體類型 303
9.3.2 實現緩衝區的操作 304
9.3.3 數組實現的計算複雜度 308
9.4 用堆疊實現編輯器 309
9.4.1 定義基於堆疊的緩衝區的具體結構 310
9.4.2 實現緩衝區的操作 310
9.4.3 比較計算複雜度 313
9.5 用鍊表實現編輯器 313
9.5.1 鍊表的概念 314
9.5.2 設計鍊表數據結構 314
9.5.3 使用鍊表表示緩衝區 316
9.5.4 鍊表緩衝區中的插入 317
9.5.5 鍊表緩衝區中的刪除 320
9.5.6 鍊表表示中的游標移動 321
9.5.7 鍊表的習慣用法 323
9.5.8 完成緩衝區實現 324
9.5.9 鍊表緩衝區的計算複雜度 328
9.5.10 雙向鍊表 328
9.5.11 時間-空間的權衡 329
9.6 小結 329
9.7 複習題 330
9.8 編程練習 331
第10章 線性結構 337
10.1 堆疊回顧 337
10.2 佇列 344
10.2.1 接口queue.h的結構 344
10.2.2 基於數組的佇列實現 347
10.2.3 佇列的鍊表實現 351
10.3 使用佇列的仿真 355
10.3.1 仿真與模型 356
10.3.2 排隊模型 356
10.3.3 離散時間 356
10.3.4 仿真時間中的事件 357
10.3.5 實現仿真 357
10.4 小結 364
10.5 複習題 365
10.6 編程練習 366
第11章 符號表 371
11.1 定義符號表抽象 371
11.1.1 選擇值和鍵的類型 372
11.1.2 表示未定義項 373
11.1.3 符號表接口的初始版本 373
11.2 散列 375
11.2.1 實現散列表策略 375
11.2.2 選擇散列函式 380
11.2.3 確定桶的數量 381
11.3 初級接口的限制 382
11.4 使用函式作為數據 384
11.4.1 通用繪圖函式 384
11.4.2 聲明函式指針與函式類 385
11.4.3 實現PlotFunction 386
11.4.4 qsort函式 387
11.5 映射函式 391
11.5.1 映射符號表中的所有項 391
11.5.2 實現MapSymbolTable 394
11.5.3 向回調函式傳遞客戶數據 395
11.6 疊代器 396
11.6.1 使用疊代器 396
11.6.2 定義疊代器接口 397
11.6.3 實現針對符號表的疊代器抽象 398
11.7 命令分派表 401
11.8 小結 404
11.9 複習題 405
11.10 編程練習 406
第Ⅳ部分 遞 歸 數 據 411
第12章 遞歸鍊表 411
12.1 鍊表的遞歸表述 412
12.2 定義抽象鍊表類型 413
12.2.1 不變類型 416
12.2.2 操縱鍊表結構的函式 417
12.2.3 連線多個鍊表 419
12.2.4 不變類型間的內部共享 421
12.3 使用鍊表表示大整數 422
12.3.1 bigint.h接口 423
12.3.2 表示類型bigIntADT 425
12.3.3 實現bigint包 426
12.3.4 使用bigint.h包 430
12.4 小結 432
12.5 複習題 433
12.6 編程練習 434
第13章 樹 438
13.1 家譜樹 438
13.1.1 描述樹的術語 439
13.1.2 樹的遞歸特性 439
13.1.3 用C語言表示家譜樹 440
13.2 二叉搜尋樹 441
13.2.1 使用二叉搜尋樹的底層動機 442
13.2.2 在二叉搜尋樹中查找節點 443
13.2.3 在二叉搜尋樹中插入新節點 444
13.2.4 樹的遍歷 447
13.3 平衡樹 449
13.3.1 樹的平衡策略 450
13.3.2 舉例說明AVL的思想 451
13.3.3 單旋轉 452
13.3.4 雙旋轉 454
13.3.5 實現AVL算法 455
13.4 為二叉搜尋樹定義通用接口 458
13.4.1 允許客戶定義節點結構 462
13.4.2 泛化鍵的類型 465
13.4.3 刪除節點 465
13.4.4 實現二叉搜尋樹包 467
13.4.5 使用二叉樹實現symtab.h接口 472
13.5 小結 474
13.6 複習題 474
13.7 編程練習 477
第14章 表達式樹 484
14.1 解釋器概述 484
14.2 表達式的抽象結構 487
14.2.1 表達式的遞歸定義 487
14.2.2 歧義性 488
14.2.3 表達式樹 489
14.2.4 定義表達式的抽象接口 490
14.3 定義具體表達式類型 494
14.3.1 聯合類型 494
14.3.2 用帶標記聯合表示表達式 496
14.3.3 可視化具體表示 498
14.3.4 實現構造器和選擇器函式 500
14.4 分析表達式 502
14.4.1 語法分析和語法 502
14.4.2 不考慮優先權的語法分析 503
14.4.3 在語法分析器中加入優先權 507
14.5 計算表達式 509
14.6 小結 511
14.7 複習題 512
14.8 編程練習 513
第15章 集合 525
15.1 作為數學抽象的集合 525
15.1.1 成員資格 526
15.1.2 集合運算 526
15.1.3 集合恆等式 527
15.2 設計集合接口 529
15.2.1 定義元素類型 529
15.2.2 編寫set.h 接口 531
15.2.3 字元集合 534
15.2.4 使用指針集合來避免重複 535
15.3 實現集合包 537
15.4 設計多態疊代器 544
15.4.1 泛化疊代器函式的原型 544
15.4.2 在疊代器中實現多態性 545
15.4.3 導出聚集類型 546
15.4.4 編碼疊代器包 550
15.4.5 foreach的習慣用法 554
15.5 提高整數集合的效率 554
15.5.1 特徵向量 555
15.5.2 壓縮的位數組 555
15.5.3 位運算符 556
15.5.4 使用位運算符實現特徵向量 559
15.5.5 實現高級集合操作 561
15.5.6 使用混合實現 561
15.6 小結 561
15.7 複習題 563
15.8 編程練習 565
第16章 圖 570
16.1 圖的結構 570
16.1.1 有向圖和無向圖 572
16.1.2 路徑和環 573
16.1.3 連通性 573
16.2 圖的實現策略 574
16.2.1 使用鄰接列表表示連線 575
16.2.2 使用鄰接矩陣表示連線 578
16.3 擴展圖抽象 581
16.3.1 將數據與節點和圖關聯 581
16.3.2 顯式弧 581
16.3.3 疊代和圖 582
16.3.4 分層抽象 583
16.3.5 基於集合的圖接口 584
16.4 圖的遍歷 592
16.4.1 深度優先遍歷 593
16.4.2 廣度優先搜尋 595
16.5 尋找最短路徑 597
16.6 小結 604
16.7 複習題 605
16.8 編程練習 607
第17章 展望Java 614
17.1 面向對象範式 614
17.1.1 面向對象編程的歷史 615
17.1.2 對象、類和方法 616
17.1.3 類層次結構與繼承 616
17.2 Java簡介 618
17.2.1 Web結構 618
17.2.2 applet 619
17.2.3 執行Java applet 623
17.3 Java結構 624
17.3.1 Java的語法 625
17.3.2 Java中的原子類型 626
17.3.3 定義一個新類 626
17.3.4 構造器方法 628
17.3.5 this關鍵字 628
17.3.6 定義方法 629
17.3.7 定義子類 631
17.4 Java中的預定義類 637
17.4.1 String類 637
17.4.2 Hashtable類 638
17.4.3 原子類型的對象包裝器 641
17.4.4 Vector類 641
17.4.5 Stack類 643
17.5 創建互動式applet的工具 644
17.5.1 組件與容器 644
17.5.2 action方法 645
17.5.3 用於繪製簡單圖形的applet 646
17.5.4 更進一步 654
17.6 小結 654
17.8 複習題 654
17.9 編程練習 656
作者簡介
Eric S.Roberts於1980年在哈佛大學獲取了套用數學的博士學位，畢業後在Wellesley大學創建了計算機科學系並擔任主任，隨後在加利福尼亞的Digital Equipemnt Corporation的系統研發中心擔任了5年的調研員，現就職於史丹福大學計算機科學系，並擔任史丹福大學教務部主任。作為一位知名教授，Roberts還編寫過The Art and Science of C等經典教材。
閃四清，大學教師，長期從事資料庫、數據挖掘、數據結構等方面的數學、學術研究。已經發表學術論文30多篇，翻譯、編寫了《資料庫系統原理和套用》等多部著作。
