C語(yǔ)言的科學(xué)和藝術(shù)

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