C語言的科學和藝術

第1章  概述        1
1.1  計算簡史        1
1.2  什么是計算機科學        4
1.3  計算機硬件簡介        4
1.3.1  CPU        4
1.3.2  內存        5
1.3.3  輔助存儲器        5
1.3.4  I/O設備        5
1.4  算法        6
1.5  程序設計語言和編譯        7
1.6  編程錯誤和調試        8
1.7  軟件維護        9
1.8  軟件工程的重要性        10
1.9  關于C程序設計語言的一些思考        10
小結        10
復習題        11
第一部分  C語言程序設計基礎
第2章  通過例子學習        14
2.1  “Hello world”程序        14
2.1.1  注釋        15
2.1.2  庫包含        15
2.1.3  主程序        16
2.2  兩個數(shù)的加法程序        17
2.2.1  輸入階段        19
2.2.2  計算階段        20
2.2.3  輸出階段        20
2.3  有關程序設計過程的觀點        21
2.4  數(shù)據(jù)類型        22
2.4.1  浮點型數(shù)據(jù)        22
2.4.2  字符串類型的數(shù)據(jù)        23
2.5  表達式        25
2.5.1  常量        25
2.5.2  變量        26
2.5.3  賦值語句        27
2.5.4  運算符和操作數(shù)        29
2.5.5  整型數(shù)和浮點型數(shù)的結合        30
2.5.6  整數(shù)除法和求余運算符        30
2.5.7  優(yōu)先級        31
2.5.8  優(yōu)先級法則的應用        33
2.5.9  類型轉換        33
小結        35
復習題        36
程序設計練習        37
第3章  問題求解        40
3.1  程序設計習語和范例        40
3.1.1  復合賦值習語        41
3.1.2  自增和自減運算符        42
3.2  解決規(guī)模稍大的問題        43
3.3  控制語句        44
3.3.1  重復N次習語        44
3.3.2  迭代和循環(huán)        45
3.3.3  下標變量        45
3.3.4  初始化的重要性        47
3.3.5  讀入-直到-標志習語        47
3.3.6  創(chuàng)造一個更實用的應用程序        49
3.3.7  條件執(zhí)行和if語句        51
3.4  一個調試練習        53
3.5  格式化輸出        56
3.5.1  printf的格式碼        57
3.5.2  控制空格、對齊方式和精度        57
3.6  構思一個程序        60
3.6.1  程序設計風格        60
3.6.2  設計時考慮將來的修改        61
3.6.3  #define機制        61
小結        63
復習題        63
程序設計練習        64
第4章  語句形式        68
4.1  簡單語句        68
4.1.1  賦值的嵌套        69
4.1.2  多重賦值        70
4.1.3  程序塊        70
4.2  控制語句        71
4.3  布爾型數(shù)據(jù)        72
4.3.1  關系運算符        72
4.3.2  邏輯運算符        73
4.3.3  簡化求值        75
4.3.4  標志        75
4.3.5  避免布爾表達式中的冗余        76
4.3.6  布爾計算示例        76
4.4  if語句        77
4.4.1  單行if語句        78
4.4.2  多行if語句        79
4.4.3  if/else語句        79
4.4.4  級聯(lián)if語句        79
4.4.5  ?: 運算符（可選的）        80
4.5  switch語句        81
4.6  while語句        83
4.6.1  while循環(huán)的應用        84
4.6.2  無限循環(huán)        85
4.6.3  解決半途退出問題        86
4.7  for語句        87
4.7.1  嵌套的for循環(huán)        89
4.7.2  for和while的關系        90
4.7.3  for語句中浮點型數(shù)據(jù)的使用問題        91
小結        92
復習題        93
程序設計練習        93
第5章  函數(shù)        96
5.1  使用庫函數(shù)        96
5.2  函數(shù)聲明        98
5.3  自己編寫函數(shù)        99
5.3.1  return語句        99
5.3.2  將函數(shù)與主程序放在一起        100
5.3.3  包含內部控制結構的函數(shù)        101
5.3.4  返回非數(shù)字值的函數(shù)        103
5.3.5  謂詞函數(shù)        104
5.3.6  測試字符串是否相等的謂詞函數(shù)        105
5.4  函數(shù)調用過程機制        106
5.4.1  參數(shù)傳遞        107
5.4.2  在其他函數(shù)中調用函數(shù)        109
5.5  過程        115
5.6  逐步精化        116
5.6.1  從頂開始        116
5.6.2  實現(xiàn)PrintCalendar        117
5.6.3  實現(xiàn)PrintCalendarMonth        118
5.6.4  完成最后的片段        121
小結        125
復習題        126
程序設計練習        126
第6章  算法        131
6.1  測試素數(shù)        131
6.1.1  一個IsPrime的簡單版本        132
6.1.2  驗證一個策略是否表示一個算法        132
6.1.3  說明IsPrime算法的正確性        133
6.1.4  改進算法的效率        133
6.1.5  在各個可選方案中選擇        136
6.2  計算最大公約數(shù)        136
6.2.1  brute-force算法        136
6.2.2  歐幾里德算法        137
6.2.3  歐幾里德算法的正確性說明（可選）        138
6.2.4  比較GCD算法的效率        138
6.3  數(shù)值算法        139
6.3.1  連續(xù)逼近        139
6.3.2  報告錯誤        141
6.4  級數(shù)展開        141
6.4.1  Zeno悖論        141
6.4.2  用級數(shù)展開法設計平方根函數(shù)        143
6.4.3  估計平方根的泰勒級數(shù)展開（可選）        143
6.4.4  泰勒級數(shù)近似的實現(xiàn)        144
6.4.5  停留在收斂半徑之內        146
6.5  指定數(shù)值類型的大小        147
6.5.1  整數(shù)類型        148
6.5.2  無符號類型        149
6.5.3  浮點類型        149
小結        149
復習題        150
程序設計練習        150
第二部分  庫和模塊化開發(fā)
第7章  庫和接口：一個簡單的圖形庫        156
7.1  接口的概念        156
7.2  圖形庫介紹        158
7.2.1  graphics.h的基本模型        158
7.2.2  graphics.h接口的函數(shù)        159
7.2.3  軟件包初始化        163
7.2.4  畫直線        163
7.2.5  畫圓和弧        164
7.2.6  獲取有關圖形窗口的信息        166
7.3  建立自己的工具        166
7.3.1  定義DrawBox        167
7.3.2  定義DrawCenteredCircle        169
7.3.3  絕對坐標和相對坐標間的切換        169
7.3.4  定義過程的好處        170
7.4  解決一個較大的問題        170
7.4.1  使用逐步精化        171
7.4.2  實現(xiàn)DrawHouse過程        172
7.4.3  尋找共同的模式        172
7.4.4  結束分解        173
小結        177
復習題        178
程序設計練習        179
第8章  設計接口：一個隨機數(shù)庫        183
8.1  接口設計        183
8.1.1  同一主題的重要性        184
8.1.2  簡單性和信息隱藏的原則        184
8.1.3  滿足客戶的需要        185
8.1.4  通用工具的優(yōu)勢        185
8.1.5  穩(wěn)定性的價值        186
8.2  用計算機生成隨機數(shù)        186
8.2.1  確定行為與非確定行為        186
8.2.2  隨機數(shù)和偽隨機數(shù)        187
8.2.3  ANSI C中生成偽隨機數(shù)        187
8.2.4  改變隨機數(shù)的范圍        188
8.2.5  將此問題通用化        192
8.3  在庫中保存工具        193
8.3.1  接口的內容        193
8.3.2  寫random.h接口        195
8.3.3  random.c的實現(xiàn)        196
8.3.4  構造客戶程序        197
8.3.5  初始化隨機數(shù)發(fā)生器        198
8.4  評價random.h接口的設計        200
8.4.1  產(chǎn)生隨機實數(shù)        201
8.4.2  模擬一個概率事件        201
8.4.3  在接口中包含頭文件        202
8.4.4  完成隨機數(shù)軟件包的實現(xiàn)        202
8.5  使用隨機數(shù)軟件包        202
小結        205
復習題        206
程序設計練習        207
第9章  字符串和字符        213
9.1  枚舉的原理        213
9.1.1  在機器內部表示枚舉類型        214
9.1.2  將枚舉類型表示為整數(shù)        214
9.1.3  定義新的枚舉類型        215
9.1.4  枚舉類型的操作        217
9.1.5  標量類型        217
9.2  字符        218
9.2.1  數(shù)據(jù)類型char        218
9.2.2  ASCII代碼        218
9.2.3  字符常量        219
9.2.4  ASCII代碼方案的重要特性        219
9.2.5  特殊字符        220
9.2.6  字符運算        221
9.2.7  ctype.h接口        222
9.2.8  涉及字符的控制語句        223
9.2.9  字符的輸入輸出        223
9.3  字符串作為抽象數(shù)據(jù)類型        224
9.3.1  分層抽象        224
9.3.2  抽象類型的概念        225
9.4  strlib.h接口        226
9.4.1  確定字符串的長度        226
9.4.2  從一個字符串中選擇字符        227
9.4.3  連接        227
9.4.4  將字符轉換為字符串        228
9.4.5  抽取字符串的一部分        229
9.4.6  比較兩個字符串        229
9.4.7  在一個字符串內搜索        230
9.4.8  大小寫轉換        232
9.4.9  數(shù)值轉換        232
9.4.10  效率和strlib.h庫        235
小結        235
復習題        236
程序設計練習        237
第10章  模塊化開發(fā)        241
10.1  Pig Latin—一個模塊化開發(fā)的案例研究        242
10.1.1  應用自頂向下的設計        243
10.1.2  使用偽代碼        243
10.1.3  實現(xiàn)TranslateLine        244
10.1.4  考慮空格和標點符號的問題        245
10.1.5  精化單詞的定義        246
10.1.6  設計記號掃描器        247
10.1.7  完成TranslateLine的實現(xiàn)        248
10.1.8  定義掃描器模塊接口        250
10.2  在模塊中維護內部狀態(tài)        252
10.2.1  全局變量        252
10.2.2  使用全局變量的危險性        253
10.2.3  保持變量的模塊私有化        253
10.2.4  初始化全局變量        253
10.2.5  私有函數(shù)        255
10.3  實現(xiàn)掃描器抽象        255
小結        261
復習題        261
程序設計練習        261
第三部分  復合數(shù)據(jù)類型
第11章  數(shù)組        268
11.1  數(shù)組        268
11.1.1  數(shù)組聲明        269
11.1.2  數(shù)組選擇        270
11.1.3  一個簡單的數(shù)組實例        271
11.1.4  改變下標值的范圍        271
11.2  數(shù)據(jù)的內部表示法        272
11.2.1  比特、字節(jié)和字        273
11.2.2  內存地址        273
11.2.3  運算符sizeof        274
11.2.4  變量的內存分配        274
11.2.5  引用超出數(shù)組范圍的元素        275
11.3  數(shù)組作為參數(shù)進行傳遞        276
11.3.1  元素個數(shù)的通用化        277
11.3.2  數(shù)組參數(shù)傳遞機制        279
11.3.3  實現(xiàn)函數(shù)PrintIntegerArray和GetIntegerArray        281
11.3.4  實現(xiàn)函數(shù)ReverseIntegerArray        282
11.3.5  實現(xiàn)函數(shù)SwapIntegerElements        283
11.4  使用數(shù)組制作表格        286
11.5  數(shù)組的靜態(tài)初始化        291
11.5.1  自動確定數(shù)組大小        292
11.5.2  確定初始化數(shù)組的大小        292
11.5.3  初始化數(shù)組和標量類型        293
11.6  多維數(shù)組        293
11.6.1  向函數(shù)傳送多維數(shù)組        294
11.6.2  初始化多維數(shù)組        295
小結        295
復習題        296
程序設計練習        297
第12章  查找和排序        303
12.1  查找        303
12.1.1  在整數(shù)數(shù)組中查找        303
12.1.2  關于查找的另一個更復雜的例子        305
12.1.3  線性查找        307
12.1.4  二分查找        308
12.1.5  查找算法的相對效率        310
12.2  排序        311
12.2.1  對一個整數(shù)數(shù)組排序        312
12.2.2  選擇排序算法        313
12.2.3  選擇排序效率的評估        315
12.2.4  測試程序的運行時間        316
12.2.5  選擇排序的算法分析        317
小結        318
復習題        318
程序設計練習        318
第13章  指針        323
13.1  將地址作為數(shù)據(jù)值        324
13.2  C語言的指針操作        325
13.2.1  在C語言中聲明指針變量        325
13.2.2  基本的指針操作        325
13.2.3  特殊指針NULL        327
13.3  通過引用傳遞參數(shù)        327
13.3.1  設計函數(shù)SwapInteger        329
13.3.2  用引用調用返回多個結果        330
13.3.3  過度使用引用調用的危險        332
13.4  指針和數(shù)組        332
13.4.1  指針運算        333
13.4.2  運算符＋＋和－－的新作用        335
13.4.3  指針的自增和自減        336
13.4.4  指針和數(shù)組的關系        337
13.5  動態(tài)分配        338
13.5.1  Void *類型        339
13.5.2  動態(tài)數(shù)組        340
13.5.3  查找malloc中的錯誤        340
13.5.4  釋放內存        341
小結        341
復習題        342
程序設計練習        344
第14章  再論字符串        347
14.1  string類型的概念表示        347
14.1.1  字符串作為數(shù)組        347
14.1.2  字符串作為指針        349
14.1.3  字符串作為抽象類型        350
14.1.4  字符串參數(shù)        350
14.1.5  字符串變量        351
14.1.6  指針和數(shù)組變量間的區(qū)別        352
14.1.7  決定字符串的表示方法        354
14.2  ANSI字符串庫        354
14.2.1  strcpy函數(shù)        355
14.2.2  strncpy函數(shù)        357
14.2.3  strcat和strncat函數(shù)        358
14.2.4  strlen、strcmp和strncmp函數(shù)        359
14.2.5  strchr、strrchr和strstr函數(shù)        359
14.2.6  ANSI字符串函數(shù)的應用        360
14.3  strlib庫的實現(xiàn)        360
14.3.1  實現(xiàn)轉換函數(shù)        360
14.3.2  strlib分配函數(shù)的實現(xiàn)        363
小結        364
復習題        365
程序設計練習        365
第15章  文件        368
15.1  文本文件        368
15.2  C語言中文件的使用        369
15.2.1  聲明FILE*類型的變量        370
15.2.2  打開文件        370
15.2.3  執(zhí)行I/O操作        371
15.2.4  關閉文件        371
15.2.5  標準文件        371
15.3  字符I/O        371
15.3.1  文件更新        374
15.3.2  在輸入文件中重新讀取字符        376
15.4  面向行的I/O        377
15.5  格式化I/O        379
15.5.1  printf的三種形式        380
15.5.2  scanf函數(shù)        380
15.5.3  用scanf讀入字符串        381
15.5.4  格式化I/O的一個實例        383
15.5.5  使用scanf的局限        385
小結        385
復習題        386
程序設計練習        387
第16章  記錄        393
16.1  數(shù)據(jù)記錄的概念        393
16.2  記錄在C語言中的使用        394
16.2.1  定義一個結構類型        394
16.2.2  聲明結構變量        395
16.2.3  記錄選擇        395
16.2.4  記錄初始化        395
16.2.5  簡單記錄        396
16.3  數(shù)組與記錄的結合        397
16.4  記錄的指針        399
16.4.1  定義一個指向記錄類型的指針        399
16.4.2  為記錄數(shù)據(jù)分配空間        400
16.4.3  對記錄指針進行操作        401
16.5  創(chuàng)建記錄的數(shù)據(jù)庫        402
16.5.1  創(chuàng)建員工信息數(shù)據(jù)庫        402
16.5.2  數(shù)據(jù)庫的使用        404
16.6  基于記錄的應用程序設計        405
16.6.1  使用數(shù)據(jù)庫的重要性        405
16.6.2  問題的框架        405
16.6.3  設計內部表示        406
16.6.4  設計外部結構        408
16.6.5  程序代碼        409
16.6.6  數(shù)據(jù)驅動設計方法的重要性        415
小結        415
復習題        417
程序設計練習        418
第17章  深入學習        424
17.1  遞歸        424
17.1.1  遞歸的簡單說明        425
17.1.2  Factorial函數(shù)        425
17.1.3  遞歸信任        429
17.1.4  遞歸范例        430
17.1.5  排列的生成        431
17.1.6  用遞歸的思想思考        433
17.2  抽象數(shù)據(jù)類型        433
17.2.1  隊列抽象        434
17.2.2  以隊列抽象表示類型        434
17.2.3  queue.h 接口        436
17.2.4  實現(xiàn)隊列抽象        437
17.2.5  隊列抽象的另一種實現(xiàn)方法        441
17.3  算法分析        444
17.3.1  評估算法效率        444
17.3.2  O標記        444
17.3.3  再看選擇排序        445
17.3.4  分而治之策略        446
17.3.5  合并兩個數(shù)組        447
17.3.6  合并排序算法        447
17.3.7  合并排序的計算復雜性        448
17.3.8  比較平方復雜性與NlogN復雜性的性能        450
小結        450
復習題        451
程序設計練習        451
附      錄
附錄A  C語言的語法和結構總結        457
附錄B  庫源代碼        471
索引        491