程序設計抽象思想：C語言描述

第Ⅰ部分 預備知識
第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 函數(shù)原型 5
1.2.5 main程序 6
1.2.6 函數(shù)定義 7
1.3 變量、值和類型 7
1.3.1 變量 7
1.3.2 命名規(guī)則 8
1.3.3 局部變量和全局變量 9
1.3.4 數(shù)據(jù)類型的概念 9
1.3.5 整數(shù)類型 9
1.3.6 浮點類型 10
1.3.7 文本類型 11
1.3.8 布爾類型 12
1.3.9 簡單的輸入與輸出 12
1.4 表達式 14
1.4.1 優(yōu)先級與結合性 14
1.4.2 表達式中的類型混合 15
1.4.3 整數(shù)除法和求余運算符 16
1.4.4 類型轉(zhuǎn)換 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 函數(shù) 29
1.6.1 返回函數(shù)結果 29
1.6.2 函數(shù)定義和原型 30
1.6.3 函數(shù)調(diào)用過程的機制 30
1.6.4 逐步求精 31
1.7 小結 31
1.8 復習題 32
1.9 編程練習 33
第2章 C的數(shù)據(jù)類型 38
2.1 枚舉類型 38
2.1.1 枚舉類型的內(nèi)部表示 39
2.1.2 標量類型 40
2.1.3 理解typedef 41
2.2 數(shù)據(jù)和內(nèi)存 41
2.2.1 位、字節(jié)、字 42
2.2.2 內(nèi)存地址 42
2.3 指針 44
2.3.1 把地址當作數(shù)值 44
2.3.2 聲明指針變量 45
2.3.3 基本的指針運算 45
2.3.4 特殊指針NULL 47
2.3.5 通過引用傳遞參數(shù) 48
2.4 數(shù)組 51
2.4.1 聲明數(shù)組 51
2.4.2 數(shù)組選擇 52
2.4.3 有效空間和已分配空間 53
2.4.4 作為參數(shù)傳遞數(shù)組 54
2.4.5 初始化數(shù)組 56
2.4.6 多維數(shù)組 57
2.5 指針和數(shù)組 59
2.5.1 指針運算 60
2.5.2 指針的自加和自減 62
2.5.3 指針和數(shù)組的關系 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 動態(tài)分配 68
2.7.1 類型void* 68
2.7.2 應對內(nèi)存限制 70
2.7.3 動態(tài)數(shù)組 71
2.7.4 動態(tài)記錄 72
2.8 小結 73
2.9 復習題 74
2.10 編程練習 76
第3章 庫和接口 83
3.1 接口的概念 83
3.1.1 接口和實現(xiàn) 84
3.1.2 包和抽象 84
3.1.3 良好的接口設計規(guī)則 85
3.2 隨機數(shù)字 85
3.2.1 random.h接口的結構 86
3.2.2 構建客戶程序 89
3.2.3 有關隨機數(shù)字的ANSI函數(shù) 91
3.2.4 實現(xiàn)random.c 93
3.3 字符串 96
3.3.1 字符串的底層表示 96
3.3.2 數(shù)據(jù)類型string 97
3.3.3 ANSI字符串庫 98
3.3.4 接口strlib.h 102
3.4 標準的I/O庫 108
3.4.1 數(shù)據(jù)文件 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函數(shù) 115
3.5 其他ANSI庫 116
3.6 小結 118
3.7 復習題 118
3.8 編程練習 120
第Ⅱ部分 遞歸和算法分析
第4章 遞歸入門 127
4.1 一個簡單的遞歸示例 128
4.2 階乘函數(shù) 129
4.2.1 Fact的遞歸公式 130
4.2.2 追蹤遞歸過程 130
4.2.3 遞歸跳躍的信任 134
4.3 費波那契函數(shù) 134
4.3.1 計算費波那契序列 135
4.3.2 增進實現(xiàn)遞歸的信心 136
4.3.3 遞歸實現(xiàn)的效率 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 產(chǎn)生排列 160
5.3 遞歸在繪圖中的應用 162
5.3.1 圖形庫 162
5.3.2 電腦藝術示例 165
5.3.3 不規(guī)則碎片形 169
5.4 小結 173
5.5 復習題 174
5.6 編程練習 175
第6章 回溯算法 183
6.1 用遞歸回溯解決迷宮問題 183
6.1.1 右手規(guī)則 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 常規(guī)化的雙人游戲程序 199
6.2.3 最小最大策略 200
6.2.4 實現(xiàn)最小最大化算法 202
6.2.5 在具體的游戲中采用常規(guī)策略 204
6.3 小結 216
6.4 復習題 217
6.5 編程練習 218
第7章 算法分析 225
7.1 排序問題 225
7.1.1 選擇排序算法 226
7.1.2 性能的經(jīng)驗度量 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 根據(jù)代碼結構預測計算復雜度 232
7.2.5 最差情況復雜度與平均情況復雜度 233
7.2.6 大O的正式定義 233
7.3 遞歸幫助 235
7.3.1 分治策略的威力 235
7.3.2 合并兩個數(shù)組 236
7.3.3 合并排序算法 237
7.3.4 合并排序的計算復雜度 239
7.3.5 比較N2和NlogN的性能 240
7.4 標準復雜度類型 241
7.5 快速排序算法 242
7.5.1 分割數(shù)組 244
7.5.2 分析快速排序的性能 246
7.6 數(shù)學歸納法 247
7.7 小結 250
7.8 復習題 250
7.9 編程練習 252
第Ⅲ部分 數(shù)據(jù)抽象
第8章 抽象數(shù)據(jù)類型 257
8.1 堆棧 258
8.1.1 基本的堆棧比喻 258
8.1.2 堆棧和函數(shù)調(diào)用 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 實現(xiàn)堆棧抽象 269
8.4.1 定義具體類型 269
8.4.2 實現(xiàn)堆棧操作 269
8.4.3 不透明類型的優(yōu)點 271
8.4.4 改進stack.c的實現(xiàn) 272
8.5 定義掃描器ADT 273
8.5.1 封裝狀態(tài)的危險 274
8.5.2 抽象數(shù)據(jù)類型作為封裝狀態(tài)的替代 274
8.5.3 實現(xiàn)掃描器抽象 279
8.6 小結 283
8.7 復習題 284
8.8 編程練習 285
第9章 效率與ADT 297
9.1 編輯器緩沖區(qū)的概念 297
9.2 定義緩沖區(qū)抽象 298
9.2.1 接口buffer.h中的函數(shù) 299
9.2.2 為編輯器應用程序編寫代碼 301
9.3 用數(shù)組實現(xiàn)編輯器 303
9.3.1 定義具體類型 303
9.3.2 實現(xiàn)緩沖區(qū)的操作 304
9.3.3 數(shù)組實現(xiàn)的計算復雜度 308
9.4 用堆棧實現(xiàn)編輯器 309
9.4.1 定義基于堆棧的緩沖區(qū)的具體結構 310
9.4.2 實現(xiàn)緩沖區(qū)的操作 310
9.4.3 比較計算復雜度 313
9.5 用鏈表實現(xiàn)編輯器 313
9.5.1 鏈表的概念 314
9.5.2 設計鏈表數(shù)據(jù)結構 314
9.5.3 使用鏈表表示緩沖區(qū) 316
9.5.4 鏈表緩沖區(qū)中的插入 317
9.5.5 鏈表緩沖區(qū)中的刪除 320
9.5.6 鏈表表示中的光標移動 321
9.5.7 鏈表的習慣用法 323
9.5.8 完成緩沖區(qū)實現(xiàn) 324
9.5.9 鏈表緩沖區(qū)的計算復雜度 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 基于數(shù)組的隊列實現(xiàn) 347
10.2.3 隊列的鏈表實現(xiàn) 351
10.3 使用隊列的仿真 355
10.3.1 仿真與模型 356
10.3.2 排隊模型 356
10.3.3 離散時間 356
10.3.4 仿真時間中的事件 357
10.3.5 實現(xiàn)仿真 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 實現(xiàn)散列表策略 375
11.2.2 選擇散列函數(shù) 380
11.2.3 確定桶的數(shù)量 381
11.3 初級接口的限制 382
11.4 使用函數(shù)作為數(shù)據(jù) 384
11.4.1 通用繪圖函數(shù) 384
11.4.2 聲明函數(shù)指針與函數(shù)類 385
11.4.3 實現(xiàn)PlotFunction 386
11.4.4 qsort函數(shù) 387
11.5 映射函數(shù) 391
11.5.1 映射符號表中的所有項 391
11.5.2 實現(xiàn)MapSymbolTable 394
11.5.3 向回調(diào)函數(shù)傳遞客戶數(shù)據(jù) 395
11.6 迭代器 396
11.6.1 使用迭代器 396
11.6.2 定義迭代器接口 397
11.6.3 實現(xiàn)針對符號表的迭代器抽象 398
11.7 命令分派表 401
11.8 小結 404
11.9 復習題 405
11.10 編程練習 406
第Ⅳ部分 遞 歸 數(shù) 據(jù)
第12章 遞歸鏈表 411
12.1 鏈表的遞歸表述 412
12.2 定義抽象鏈表類型 413
12.2.1 不變類型 416
12.2.2 操縱鏈表結構的函數(shù) 417
12.2.3 連接多個鏈表 419
12.2.4 不變類型間的內(nèi)部共享 421
12.3 使用鏈表表示大整數(shù) 422
12.3.1 bigint.h接口 423
12.3.2 表示類型bigIntADT 425
12.3.3 實現(xiàn)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 在二叉搜索樹中查找節(jié)點 443
13.2.3 在二叉搜索樹中插入新節(jié)點 444
13.2.4 樹的遍歷 447
13.3 平衡樹 449
13.3.1 樹的平衡策略 450
13.3.2 舉例說明AVL的思想 451
13.3.3 單旋轉(zhuǎn) 452
13.3.4 雙旋轉(zhuǎn) 454
13.3.5 實現(xiàn)AVL算法 455
13.4 為二叉搜索樹定義通用接口 458
13.4.1 允許客戶定義節(jié)點結構 462
13.4.2 泛化鍵的類型 465
13.4.3 刪除節(jié)點 465
13.4.4 實現(xiàn)二叉搜索樹包 467
13.4.5 使用二叉樹實現(xiàn)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 聯(lián)合類型 494
14.3.2 用帶標記聯(lián)合表示表達式 496
14.3.3 可視化具體表示 498
14.3.4 實現(xiàn)構造器和選擇器函數(shù) 500
14.4 分析表達式 502
14.4.1 語法分析和語法 502
14.4.2 不考慮優(yōu)先級的語法分析 503
14.4.3 在語法分析器中加入優(yōu)先級 507
14.5 計算表達式 509
14.6 小結 511
14.7 復習題 512
14.8 編程練習 513
第15章 集合 525
15.1 作為數(shù)學抽象的集合 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 實現(xiàn)集合包 537
15.4 設計多態(tài)迭代器 544
15.4.1 泛化迭代器函數(shù)的原型 544
15.4.2 在迭代器中實現(xiàn)多態(tài)性 545
15.4.3 導出聚集類型 546
15.4.4 編碼迭代器包 550
15.4.5 foreach的習慣用法 554
15.5 提高整數(shù)集合的效率 554
15.5.1 特征向量 555
15.5.2 壓縮的位數(shù)組 555
15.5.3 位運算符 556
15.5.4 使用位運算符實現(xiàn)特征向量 559
15.5.5 實現(xiàn)高級集合操作 561
15.5.6 使用混合實現(xiàn) 561
15.6 小結 561
15.7 復習題 563
15.8 編程練習 565
第16章 圖 570
16.1 圖的結構 570
16.1.1 有向圖和無向圖 572
16.1.2 路徑和環(huán) 573
16.1.3 連通性 573
16.2 圖的實現(xiàn)策略 574
16.2.1 使用鄰接列表表示連接 575
16.2.2 使用鄰接矩陣表示連接 578
16.3 擴展圖抽象 581
16.3.1 將數(shù)據(jù)與節(jié)點和圖關聯(lián) 581
16.3.2 顯式弧 581
16.3.3 迭代和圖 582
16.3.4 分層抽象 583
16.3.5 基于集合的圖接口 584
16.4 圖的遍歷 592
16.4.1 深度優(yōu)先遍歷 593
16.4.2 廣度優(yōu)先搜索 595
16.5 尋找最短路徑 597
16.6 小結 604
16.7 復習題 605
16.8 編程練習 607
第17章 展望Java 614
17.1 面向?qū)ο蠓妒?614
17.1.1 面向?qū)ο缶幊痰臍v史 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 執(zhí)行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 創(chuàng)建交互式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