寫給學生
寫給教師
緻　　謝
第一部分　預備知識
第1章　ANSI C概述2
1.1　什麼是C2
1.2　C程序的結構4
1.2.1　注釋5
1.2.2　包含的庫文件5
1.2.3　程序級的定義6
1.2.4　函數原型6
1.2.5　主程序6
1.2.6　函數定義7
1.3　變量、值和類型8
1.3.1　變量8
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　錶達式13
1.4.1　優先級與結閤性14
1.4.2　錶達式中的類型混閤15
1.4.3　整數除法和求餘運算15
1.4.4　類型轉換16
1.4.5　賦值運算符16
1.4.6　遞增與遞減運算符17
1.4.7　布爾運算符18
1.5　語句20
1.5.1　簡單語句20
1.5.2　塊20
1.5.3　if語句21
1.5.4　switch語句21
1.5.5　while語句23
1.5.6　for語句25
1.6　函數26
1.6.1　返迴函數結果27
1.6.2　函數定義和原型27
1.6.3　函數調用過程的機製28
1.6.4　逐步求精28
1.7　總結28
1.8　復習題29
1.9　編程練習30
第2章　C的數據類型34
2.1　枚舉類型34
2.1.1　枚舉類型的內部錶示35
2.1.2　標量類型36
2.1.3　理解typedef36
2.2　數據和內存37
2.2.1　位、字節、字37
2.2.2　內存地址38
2.3　指針39
2.3.1　把地址當作數值40
2.3.2　聲明指針變量40
2.3.3　基本的指針運算41
2.3.4　特殊指針NULL43
2.3.5　傳遞引用43
2.4　數組46
2.4.1　聲明數組46
2.4.2　數組選擇47
2.4.3　分配的空間和利用的空間48
2.4.4　把數組作為參數48
2.4.5　初始化數組51
2.4.6　多維數組52
2.5　指針和數組53
2.5.1　指針運算54
2.5.2　指針的自加和自減56
2.5.3　指針和數組的關係56
2.6　記錄58
2.6.1　定義一種新的結構類型58
2.6.2　聲明結構變量59
2.6.3　記錄選擇59
2.6.4　初始化紀錄59
2.6.5　記錄的指針60
2.7　動態分配61
2.7.1　類型void61
2.7.2　對內存限製的處理62
2.7.3　動態數組63
2.7.4　動態記錄64
2.8　總結65
2.9　復習題66
2.10　編程練習68
第3章　庫和接口74
3.1　接口的概念74
3.1.1　接口和實現75
3.1.2　包和抽象75
3.1.3　良好的接口設計規則76
3.2　隨機數字76
3.2.1　random.h接口的結構77
3.2.2　構造一個客戶程序80
3.2.3　ANSI中有關隨機數字的函數82
3.2.4　實現random.c83
3.3　字符串86
3.3.1　字符的底層錶示86
3.3.2　數據類型string88
3.3.3　ANSI字符串庫89
3.3.4　接口strlib.h92
3.4　標準的I/O庫98
3.4.1　數據文件98
3.4.2　在C中使用文件99
3.4.3　標準文件100
3.4.4　字符I/O100
3.4.5　從輸入文件中重讀字符101
3.4.6　更新文件102
3.4.7　麵嚮行的I/O103
3.4.8　格式化的I/O103
3.4.9　scanf函數104
3.5　其他ANSI庫105
3.6　總結107
3.7　復習題107
3.8　編程練習109
第二部分　遞歸和算法分析
第4章　遞歸入門116
4.1　一個簡單的遞歸示例116
4.2　階乘函數118
4.2.1　Fact的遞歸公式118
4.2.2　追蹤遞歸過程119
4.2.3　遞歸跳躍的信任122
4.3　費波那契函數123
4.3.1　計算費波那契序列123
4.3.2　增進實現遞歸的信心125
4.3.3　遞歸實現的效率125
4.3.4　不應該責備遞歸126
4.4　其他遞歸示例127
4.4.1　探測迴文128
4.4.2　二分查找130
4.4.3　交互遞歸131
4.5　遞歸的思考133
4.5.1　保持整體觀133
4.5.2　避免常見的陷阱133
4.6　總結134
4.7　復習題135
4.8　編程練習137
第5章　遞歸過程140
5.1　漢諾塔140
5.1.1　分解問題141
5.1.2　尋找遞歸策略142
5.1.3　證實遞歸策略143
5.1.4　編碼解決方案144
5.1.5　追蹤遞歸過程144
5.2　産生排列148
5.3　遞歸的繪圖應用150
5.3.1　繪圖庫150
5.3.2　電腦藝術示例152
5.3.3　不規則碎片形155
5.4　總結159
5.5　復習題160
5.6　編程練習161
第6章　迴溯算法168
6.1　用遞歸迴溯解決迷宮問題168
6.1.1　右手規則168
6.1.2　尋找遞歸方法169
6.1.3　識彆簡單情景170
6.1.4　迷宮解決方案算法編碼171
6.1.5　確信解決方案可以正確運行175
6.2　迴溯與對策176
6.2.1　拿子遊戲177
6.2.2　一般化的雙人遊戲程序183
6.2.3　最小最大策略184
6.2.4　實現最小最大化算法185
6.2.5　在具體的遊戲中采用一般化策略187
6.3　總結199
6.4　復習題199
6.5　編程練習200
第7章　算法分析206
7.1　排序問題206
7.1.1　選擇排序算法207
7.1.2　性能的經驗度量208
7.1.3　分析選擇排序的性能209
7.2　計算復雜度210
7.2.1　大O符號210
7.2.2　大O的標準簡化211
7.2.3　排序算法的計算復雜度211
7.2.4　根據代碼結構預測計算復雜度212
7.2.5　最差情況復雜度與平均情況復雜度213
7.2.6　大O的正式定義214
7.3　遞歸幫助215
7.3.1　分治策略的威力215
7.3.2　閤並兩個數組216
7.3.3　閤並排序算法216
7.3.4　閤並排序的計算復雜度218
7.3.5　比較N2和NlogN的性能219
7.4　標準復雜度類型220
7.5　快速排序算法221
7.5.1　分割數組223
7.5.2　分析快速排序的性能225
7.6　數學歸納法225
7.7　總結227
7.8　復習題228
7.9　編程練習230
第三部分　數據抽象
第8章　抽象數據類型236
8.1　棧236
8.1.1　棧的基本概念237
8.1.2　棧和函數調用237
8.1.3　棧和袖珍計算器237
8.2　定義棧的ADT238
8.2.1　定義棧抽象的類型238
8.2.2　不透明類型240
8.2.3　定義stack.h接口240
8.3　在應用中使用棧244
8.4　實現棧抽象247
8.4.1　定義具體類型247
8.4.2　實現棧操作247
8.4.3　不透明類型的優點249
8.4.4　改進stack.c的實現250
8.5　定義一個scannerADT251
8.5.1　封裝狀態的危險252
8.5.2　抽象數據類型作為封裝狀態的替代252
8.5.3　實現掃描器抽象256
8.6　總結261
8.7　復習題262
8.8　編程練習263
第9章　效率與ADT273
9.1　編輯器緩衝區的概念273
9.2　定義緩衝區抽象274
9.2.1　接口buffer.h中的函數275
9.2.2　為編輯器應用編寫代碼277
9.3　用數組實現編輯器279
9.3.1　定義具體類型279
9.3.2　實現緩衝區的操作280
9.3.3　數組實現的計算復雜度283
9.4　用棧實現編輯器284
9.4.1　定義基於棧的緩衝區的具體結構284
9.4.2　實現緩衝區的操作284
9.4.3　比較計算復雜度287
9.5　用鏈錶實現編輯器288
9.5.1　鏈錶的概念288
9.5.2　設計鏈錶數據結構289
9.5.3　使用鏈錶錶示緩衝區290
9.5.4　鏈錶緩衝區中的插入291
9.5.5　鏈錶緩衝區中的刪除292
9.5.6　鏈錶錶示中的光標移動293
9.5.7　鏈錶的習慣用法295
9.5.8　完成緩衝區實現296
9.5.9　鏈錶緩衝區的計算復雜度299
9.5.10　雙嚮鏈錶300
9.5.11　時間空間的權衡300
9.6　總結301
9.7　復習題301
9.8　編程練習302
第10章　綫性結構307
10.1　棧迴顧307
10.2　隊列313
10.2.1　接口queue.h的結構313
10.2.2　基於數組的隊列實現316
10.2.3　隊列的鏈錶實現320
10.3　使用隊列的仿真324
10.3.1　仿真與模型324
10.3.2　排隊模型324
10.3.3　離散時間325
10.3.4　仿真時間中的事件325
10.3.5　實現仿真325
10.4　總結331
10.5　復習題332
10.6　編程練習333
第11章　符號錶338
11.1　定義符號錶抽象338
11.1.1　選擇值和鍵的類型339
11.1.2　錶示未定義項340
11.1.3　符號錶接口的初始版本340
11.2　散列342
11.2.1　實現散列錶策略342
11.2.2　選擇散列函數347
11.2.3　確定桶的數量348
11.3　初級接口的限製348
11.4　使用函數作為數據350
11.4.1　一個一般測繪函數351
11.4.2　聲明函數指針與函數類352
11.4.3　實現PlotFunction352
11.4.4　qsort函數352
11.5　映射函數356
11.5.1　映射符號錶中的所有項357
11.5.2　實現MapSymbolTable359
11.5.3　嚮迴調函數傳遞客戶數據360
11.6　迭代器361
11.6.1　使用迭代器361
11.6.2　定義迭代器接口362
11.6.3　實現符號錶的迭代器抽象363
11.7　命令分派錶366
11.8　總結368
11.9　復習題369
11.10　編程練習370
第四部分　遞歸數據
第12章　遞歸列錶376
12.1　鏈錶的遞歸錶述377
12.2　定義抽象鏈錶類型378
12.2.1　不變類型380
12.2.2　操縱鏈錶結構的函數381
12.2.3　連接多個鏈錶383
12.2.4　不變類型間的內部共享385
12.3　使用鏈錶錶示大整數386
12.3.1　bigint.h 接口386
12.3.2　錶示類型bigIntADT388
12.3.3　實現bigint包389
12.3.4　使用bigint.h包394
12.4　總結395
12.5　復習題396
12.6　編程練習397
第13章　樹400
13.1　傢譜樹401
13.1.1　描述樹的術語401
13.1.2　樹的遞歸特性401
13.1.3　用C語言錶示傢譜樹402
13.2　二叉搜索樹403
13.2.1　使用二叉搜索樹的底層動機403
13.2.2　在二叉搜索樹中查找節點405
13.2.3　在二叉搜索樹中插入新節點405
13.2.4　樹的遍曆408
13.3　平衡樹409
13.3.1　樹的平衡策略410
13.3.2　舉例說明AVL的思想411
13.3.3　單鏇轉412
13.3.4　雙鏇轉414
13.3.5　實現AVL算法414
13.4　為二叉搜索樹定義一般化接口418
13.4.1　允許用戶定義節點結構421
13.4.2　一般化用作鍵的類型424
13.4.3　刪除節點424
13.4.4　實現二叉搜索樹包425
13.4.5　使用二叉樹實現symtab.h接口431
13.5　總結432
13.6　復習題433
13.7　編程練習435
第14章　錶達式樹442
14.1　解釋器概述443
14.2　錶達式的抽象結構445
14.2.1　錶達式的遞歸定義445
14.2.2　多義性446
14.2.3　錶達式樹447
14.2.4　定義錶達式的抽象接口448
14.3　定義具體錶達式類型451
14.3.1　聯閤類型451
14.3.2　使用標記的聯閤錶示錶達式453
14.3.3　可視化具體錶示454
14.3.4　實現構建器和選擇器函數456
14.4　語法分析錶達式458
14.4.1　語法分析和語法458
14.4.2　不考慮優先級的語法分析459
14.4.3　在語法分析器中加入優先級462
14.5　計算錶達式464
14.6　總結467
14.7　復習題467
14.8　編程練習468
第15章　集閤479
15.1　為數學抽象的集閤479
15.1.1　成員資格480
15.1.2　集閤運算480
15.1.3　集閤恒等式481
15.2　設計集閤接口482
15.2.1　定義元素類型483
15.2.2　編寫set.h 接口484
15.2.3　字符集閤488
15.2.4　使用指針集閤來避免重復488
15.3　實現集閤包490
15.4　設計多態迭代器497
15.4.1　泛化迭代器函數的原型497
15.4.2　在迭代器實現中加入多態性497
15.4.3　導齣聚集類型498
15.4.4　編碼迭代器包502
15.4.5　foreach的習慣用法506
15.5　提高整型集閤的效率506
15.5.1　特徵嚮量507
15.5.2　壓縮的位數組507
15.5.3　位運算符508
15.5.4　使用位操作符實現特徵嚮量510
15.5.5　實現高級集閤操作512
15.5.6　使用混閤實現513
15.6　總結513
15.7　復習題514
15.8　編程練習517
第16章　圖521
16.1　圖的結構521
16.1.1　有嚮圖和無嚮圖523
16.1.2　路徑和環524
16.1.3　連通性524
16.2　圖的實現策略525
16.2.1　使用鄰接列錶錶示連接526
16.2.2　使用鄰接矩陣錶示連接529
16.3　擴展圖抽象532
16.3.1　將數據與節點和圖關聯532
16.3.2　顯式弧532
16.3.3　迭代和圖533
16.3.4　分層抽象534
16.3.5　基於集閤的圖接口534
16.4　圖的遍曆543
16.4.1　深度優先遍曆543
16.4.2　廣度優先搜索545
16.5　尋找最短路徑548
16.6　總結554
16.7　復習題555
16.8　編程練習556
第17章　Java的未來563
17.1　麵嚮對象範例563
17.1.1　麵嚮對象編程的曆史564
17.1.2　對象、類和方法565
17.1.3　類層次與繼承566
17.2　Java入門567
17.2.1　Web結構567
17.2.2　applet568
17.2.3　執行Java applet572
17.3　Java的結構573
17.3.1　Java的語法574
17.3.2　Java中的原子類型575
17.3.3　定義新類575
17.3.4　構造器方法576
17.3.5　this關鍵字577
17.3.6　定義方法577
17.3.7　定義子類579
17.4　Java中的預定義類586
17.4.1　String類586
17.4.2　Hashtable類587
17.4.3　原子類型的對象包裝器589
17.4.4　Vector類590
17.4.5　Stack類591
17.5　創建交互applet的工具592
17.5.1　組件與容器592
17.5.2　action方法593
17.5.3　用於畫圖形的簡單applet594
17.5.4　更進一步602
17.6　總結602
17.7　復習題602
17.8　編程練習604
· · · · · · (收起)