程序設(shè)計(jì)方法 第2版

目 錄

開(kāi)篇：如何編程
算術(shù)　3
輸入和輸出　6
計(jì)算的多種方式　10
一個(gè)程序，多個(gè)定義　13
另一個(gè)定義　15
現(xiàn)在你是一名程序員了　17
不！　17
第　一部分 固定大小的數(shù)據(jù)
第　1章 算術(shù)　20
1．1　數(shù)值的算術(shù)　21
1．2　字符串的算術(shù)　22
1．3　二者的混合　23
1．4　圖像的算術(shù)　24
1．5　布爾值的算術(shù)　26
1．6　布爾值的混合　27
1．7　謂詞：了解你的數(shù)據(jù)　29
第　2章 函數(shù)和程序　31
2．1　函數(shù)　31
2．2　計(jì)算　33
2．3　函數(shù)的復(fù)合　36
2．4　全局常量　38
2．5　程序　39
第3章　程序設(shè)計(jì)方法　49
3．1　設(shè)計(jì)函數(shù)　50
3．2　熟練習(xí)題：函數(shù)　54
3．3　領(lǐng)域知識(shí)　54
3．4　從函數(shù)到程序　54
3．5　關(guān)于測(cè)試　55
3．6　設(shè)計(jì)世界程序　56
3．7　虛擬寵物世界　63
第4章　區(qū)間、枚舉和條目　65
4．1　條件編程　65
4．2　條件計(jì)算　67
4．3　枚舉　69
4．4　區(qū)間　71
4．5　條目　75
4．6　條目的設(shè)計(jì)　80
4．7　有限狀態(tài)世界　82
第5章　添加結(jié)構(gòu)體　88
5．1　從位置到posn結(jié)構(gòu)體　88
5．2　posn的計(jì)算　88
5．3　posn的編程　89
5．4　定義結(jié)構(gòu)體類(lèi)型　91
5．5　結(jié)構(gòu)體的計(jì)算　94
5．6　結(jié)構(gòu)體的編程　97
5．7　數(shù)據(jù)的空間　102
5．8　結(jié)構(gòu)體的設(shè)計(jì)　105
5．9　世界中的結(jié)構(gòu)體　106
5．10　圖形編輯器　107
5．11　再探虛擬寵物　109
第6章　條目和結(jié)構(gòu)體　111
6．1　再談條目的設(shè)計(jì)　111
6．2　世界的混合　119
6．3　輸入錯(cuò)誤　121
6．4　世界中的檢查　124
6．5　相等謂詞　125
第7章　總結(jié)　127
獨(dú)立章節(jié)1　初級(jí)語(yǔ)言　128
初級(jí)語(yǔ)言的詞匯　128
初級(jí)語(yǔ)言的文法　129
初級(jí)語(yǔ)言的含義　131
含義和計(jì)算　133
初級(jí)語(yǔ)言中的錯(cuò)誤　133
布爾表達(dá)式　135
常量定義　136
結(jié)構(gòu)體類(lèi)型定義　137
初級(jí)語(yǔ)言中的測(cè)試　139
初級(jí)語(yǔ)言的錯(cuò)誤消息　140
第二部分　任意大的數(shù)據(jù)
第8章　鏈表　146
8．1　創(chuàng)建鏈表　146
8．2　'()是什么，cons又是什么　149
8．3　用鏈表編程　151
8．4　使用鏈表進(jìn)行計(jì)算　154
第9章　使用自引用數(shù)據(jù)定義進(jìn)行設(shè)計(jì)　156
9．1　熟練習(xí)題：鏈表　160
9．2　非空鏈表　161
9．3　自然數(shù)　166
9．4　俄羅斯套娃　168
9．5　鏈表和世界程序　171
9．6　關(guān)于鏈表和集合　174
第　10章 再談鏈表　178
10．1　生成鏈表的函數(shù)　178
10．2　鏈表中的結(jié)構(gòu)體　180
10．3　鏈表中鏈表以及文件　183
10．4　再談圖形編輯器　189
第　11章 組合式設(shè)計(jì)　197
11．1　list函數(shù)　197
11．2　函數(shù)的組合　199
11．3　遞歸的輔助函數(shù)　200
11．4　一般化的輔助函數(shù)　204
第　12章 項(xiàng)目：鏈表　212
12．1　現(xiàn)實(shí)世界中的數(shù)據(jù)：字典　212
12．2　現(xiàn)實(shí)世界中的數(shù)據(jù)：iTunes　213
12．3　文字游戲—組合的示例　217
12．4　文字游戲—問(wèn)題的核心　220
12．5　貪吃蛇　221
12．6　簡(jiǎn)單俄羅斯方塊　223
12．7　全面太空戰(zhàn)爭(zhēng)　225
12．8　有限狀態(tài)機(jī)　226
第　13章 總結(jié)　231
獨(dú)立章節(jié)2　Quote和Unquote　232
Quote　232
Quasiquote和Unquote　233
Unquote　Splice　236
第三部分　抽象
第　14章 無(wú)處不在的相似性　242
14．1　函數(shù)的相似性　242
14．2　不同的相似性　243
14．3　數(shù)據(jù)定義的相似性　246
14．4　函數(shù)是值　248
14．5　函數(shù)的計(jì)算　249
第　15章 設(shè)計(jì)抽象　252
15．1　抽象的示例　252
15．2　簽名的相似性　255
15．3　單個(gè)控制點(diǎn)　259
15．4　模板的抽象　259
第　16章 使用抽象　261
16．1　現(xiàn)有的抽象　261
16．2　局部定義　264
16．3　局部定義增強(qiáng)表達(dá)能力　266
16．4　local的計(jì)算　268
16．5　使用抽象的示例　271
16．6　用抽象設(shè)計(jì)　274
16．7　熟悉抽象的習(xí)題　275
16．8　項(xiàng)目中的抽象　276
第　17章 匿名函數(shù)　278
17．1　lambda函數(shù)　278
17．2　lambda的計(jì)算　280
17．3　用lambda抽象　282
17．4　用lambda制定規(guī)范　284
17．5　用lambda表示　289
第　18章 總結(jié)　293
獨(dú)立章節(jié)3　作用域和抽象　294
作用域　294
中級(jí)語(yǔ)言的循環(huán)　298
模式匹配　304
第四部分　交織的數(shù)據(jù)
第　19章 S表達(dá)式之詩(shī)　310
19．1　樹(shù)　310
19．2　森林　316
19．3　S表達(dá)式　317
19．4　對(duì)交織數(shù)據(jù)的設(shè)計(jì)　321
19．5　項(xiàng)目：二叉查找樹(shù)　322
19．6　函數(shù)的簡(jiǎn)化　325
第　20章 迭代改進(jìn)　327
20．1　數(shù)據(jù)分析　327
20．2　數(shù)據(jù)定義的改進(jìn)　328
20．3　函數(shù)的改進(jìn)　330
第　21章 解釋器的改進(jìn)　332
21．1　表達(dá)式的解釋　332
21．2　變量的解釋　335
21．3　函數(shù)的解釋　336
21．4　解釋一切　338
第　22章 項(xiàng)目：XML商業(yè)　340
22．1　XML和S表達(dá)式　340
22．2　XML枚舉的呈現(xiàn)　344
22．3　領(lǐng)域特定語(yǔ)言　348
22．4　讀入XML　352
第　23章 同時(shí)處理　355
23．1　同時(shí)處理兩個(gè)鏈表：情況1　355
23．2　同時(shí)處理兩個(gè)鏈表：情況2　356
23．3　同時(shí)處理兩個(gè)鏈表：情況3　357
23．4　函數(shù)的簡(jiǎn)化　360
23．5　設(shè)計(jì)讀入兩個(gè)復(fù)雜輸入的函數(shù)　361
23．6　熟練習(xí)題：兩個(gè)輸入　362
23．7　項(xiàng)目：數(shù)據(jù)庫(kù)　365
第　24章 總結(jié)　374
獨(dú)立章節(jié)4　數(shù)值的本質(zhì)　375
固定大小的數(shù)值算術(shù)　375
溢出　379
下溢出　379
教學(xué)語(yǔ)言中的數(shù)值　380
第五部分　生成遞歸
第　25章 非標(biāo)準(zhǔn)遞歸　386
25．1　無(wú)結(jié)構(gòu)體的遞歸　386
25．2　忽略結(jié)構(gòu)體的遞歸　389
第　26章 設(shè)計(jì)算法　393
26．1　調(diào)整設(shè)計(jì)訣竅　393
26．2　終止　394
26．3　對(duì)比結(jié)構(gòu)化遞歸和生成遞歸　396
26．4　做出選擇　397
第　27章 主題的變化　401
27．1　初試分形　401
27．2　二分查找　403
27．3　初探解析　407
第　28章 數(shù)學(xué)的例子　411
28．1　牛頓法　411
28．2　數(shù)值積分　414
28．3　項(xiàng)目：高斯消元　418
第　29章 回溯的算法　423
29．1　圖的遍歷　423
29．2　項(xiàng)目：回溯　430
第30章　總結(jié)　434
獨(dú)立章節(jié)5　計(jì)算的成本　435
具體的時(shí)間和抽象的時(shí)間　436
“數(shù)量級(jí)”的定義　440
為何使用謂詞和選擇函數(shù)　442
第六部分　知識(shí)的累積
第31章　知識(shí)的丟失　446
31．1　結(jié)構(gòu)處理的問(wèn)題　446
31．2　生成遞歸的問(wèn)題　449
第32章　累積器風(fēng)格函數(shù)的設(shè)計(jì)　453
32．1　認(rèn)識(shí)到需要累積器　453
32．2　添加累積器　454
32．3　將函數(shù)轉(zhuǎn)換為累積器風(fēng)格　455
32．4　帶鼠標(biāo)的圖形編輯器　464
第33章　累積的更多用途　466
33．1　累積器和樹(shù)　466
33．2　帶累積器的數(shù)據(jù)表示　470
33．3　作為結(jié)果的累積器　474
第34章　總結(jié)　479
尾聲：繼續(xù)前進(jìn)　481