本書是一本講授使用C語言進行程序設(shè)計的實用參考書。它以C語言為工具,講授程序設(shè)計的過程和方法。從C語言和C程序的基本要素以及程序設(shè)計的基本方法開始,循序漸進地引入對程序設(shè)計專業(yè)化的要求和相關(guān)的知識。從增強讀者的感性認(rèn)識入手,通過多角度對例題的分析,示范對關(guān)鍵知識和技術(shù)的運用,通過對關(guān)鍵內(nèi)容在不同層次上的適當(dāng)重復(fù),深化讀者對概念的理解和掌握。
Foreword 作者自序
本書面向具有一定的C語言編程基礎(chǔ),希望在專業(yè)程序設(shè)計能力方面進一步提高的讀者。本書重點講解C語言中需要深入理解和掌握的知識,程序設(shè)計的基本方法和原則,以及這些方法和原則在實際中的應(yīng)用。希望讀者能夠通過對本書的閱讀和學(xué)習(xí),在編程工作中掌握較為專業(yè)的思維方式和工作方法,能夠正確、準(zhǔn)確、有效地把自己解決實際計算問題的思路轉(zhuǎn)換為具有專業(yè)質(zhì)量的程序。
計算機技術(shù)是信息化時代重要的技術(shù)支撐,是信息化的技術(shù)基石。當(dāng)前人類社會中,計算機系統(tǒng)無處不在,如果說硬件是計算機系統(tǒng)的軀體,那么軟件就是計算機系統(tǒng)的靈魂?梢哉f,程序設(shè)計就是為計算機系統(tǒng)鑄造靈魂的工作。因此程序設(shè)計能力是信息化時代的一種重要能力。
程序設(shè)計離不開編程語言。在編程語言百花齊放的今天,C語言具有非常獨特的地位。在面世近50年之后,C語言仍然保持著旺盛的活力,多年來一直在語言應(yīng)用排行榜中穩(wěn)居前兩名。盡管各種新的編程語言不斷涌現(xiàn),也未能撼動C語言的地位。即使近年來在人工智能熱潮的推動下,Python語言后來居上,但在2021年10月份發(fā)布的TIOBE編程語言排行榜上,C語言也僅僅以0.11%之差屈居第二,是編程語言中名副其實的常青樹。
程序設(shè)計如同寫文章。一篇合格的文章需要立意明確、思路清楚、內(nèi)容完整、布局合理、表達準(zhǔn)確、語言生動。一個具有專業(yè)水平的程序則不但要全面滿足任務(wù)需求,而且要結(jié)構(gòu)清晰、組織合理、代碼簡潔,并能完整實現(xiàn)對程序功能、性能、可靠性和可擴展性等各方面的要求。也就是說,一個好的程序也需要在構(gòu)思和表達兩方面都有完美的表現(xiàn)。程序的構(gòu)思涉及軟件工程、常用算法、數(shù)據(jù)結(jié)構(gòu)以及與具體任務(wù)相關(guān)的知識和算法。本書則主要側(cè)重如何使用C語言準(zhǔn)確地表達程序的構(gòu)思,討論如何寫出結(jié)構(gòu)合理、表達準(zhǔn)確、描述簡練、高效可靠、易于理解和維護的代碼,討論程序的分析、設(shè)計和實現(xiàn)過程、指導(dǎo)原則,以及常用的方法,并結(jié)合示例介紹這些方法和原則在實際編程中的具體運用,為希望進一步提高自己實際程序設(shè)計能力的讀者提供適當(dāng)?shù)闹笇?dǎo)。
理論與實踐相結(jié)合是掌握知識的必由之路。為此,讀者應(yīng)該積極地將所學(xué)到的理論知識應(yīng)用到自己的編程實踐中去。在實踐過程中要把注意力著重放在問題的分析、計算過程的分解、數(shù)據(jù)結(jié)構(gòu)的選擇、程序結(jié)構(gòu)的組織等程序設(shè)計的過程和方法上。只要抓住了這些關(guān)鍵,認(rèn)真思考并勤于實踐,就可以有效地提高自己的專業(yè)素養(yǎng)和實際的程序設(shè)計能力。正如所說的:世上無難事,只要肯登攀。
本書的寫作得到了機械工業(yè)出版社華章分社溫莉芳、劉立卿和劉鋒,以及出版社其他同人的熱情鼓勵和多方支持,作者對此表示衷心的感謝。限于水平,書中難免有錯漏之處,還望讀者不吝指正。
尹寶林
2021年初冬于北京航空航天大學(xué)
尹寶林,1973年畢業(yè)于北京航空學(xué)院(現(xiàn)更名為北京航空航天大學(xué))計算機專業(yè),1984年獲英國愛丁堡大學(xué)博士學(xué)位。曾任北京航空航天大學(xué)計算機系教授、博士生導(dǎo)師。從事計算機專業(yè)教學(xué)和科研工作多年,主講過C語言程序設(shè)計高級語言程序設(shè)計UNIX程序設(shè)計環(huán)境計算機圖形學(xué)圖像處理等課程,其中高級語言程序設(shè)計被評為北京市精品課程。主編過《離散數(shù)學(xué)》《C程序設(shè)計導(dǎo)引》等教材。參加全國信息學(xué)奧林匹克(NOI)活動的組織與指導(dǎo)工作,曾任NOI科學(xué)委員會副主席。
作者自序
第0章 引言1
第1章 程序設(shè)計的基本方法7
1.1 程序設(shè)計的基本過程7
1.2 問題分析9
1.2.1 對程序功能的要求9
1.2.2 對程序性能的要求10
1.2.3 程序的使用方式和環(huán)境11
1.2.4 程序的錯誤處理12
1.2.5 程序的測試13
1.2.6 問題分析的結(jié)果13
1.3 方案設(shè)計18
1.3.1 求解思路18
1.3.2 計算模型21
1.3.3 算法分類24
1.3.4 算法和數(shù)據(jù)結(jié)構(gòu)的選擇26
1.3.5 算法的檢驗33
1.4 編碼:從算法到代碼34
1.4.1 代碼的結(jié)構(gòu)34
1.4.2 編碼的質(zhì)量37
1.4.3 代碼的可維護性39
1.4.4 代碼中的注釋39
1.4.5 代碼的檢查40
1.4.6 代碼中常見的錯誤40
1.5 測試和調(diào)試42
1.5.1 調(diào)試的基本方法43
1.5.2 故障的檢查、確認(rèn)和修改44
1.5.3 常見的故障類型和調(diào)試方法46
1.5.4 調(diào)試數(shù)據(jù)的設(shè)計和使用48
1.5.5 調(diào)試數(shù)據(jù)和標(biāo)準(zhǔn)輸入/輸出的重新定向48
1.5.6 調(diào)試工具50
1.5.7 測試和調(diào)試中常見的問題50
1.6 手冊的使用52
第2章 數(shù)值的表示和計算53
2.1 整型數(shù)據(jù)類型53
2.1.1 有符號數(shù)和無符號數(shù)54
2.1.2 無符號數(shù)和標(biāo)志位56
2.1.3 整型的截斷與擴展56
2.1.4 整型計算的溢出和判斷58
2.1.5 整除所引起的誤差60
2.1.6 整型數(shù)據(jù)的字節(jié)序和尾端62
2.2 浮點數(shù)據(jù)類型65
2.2.1 浮點數(shù)據(jù)的表示方法65
2.2.2 有效數(shù)字和位當(dāng)量67
2.2.3 浮點數(shù)的比較70
2.2.4 浮點數(shù)值計算中的上溢和下溢72
2.3 數(shù)值計算中的類型轉(zhuǎn)換75
2.3.1 基本類型轉(zhuǎn)換和數(shù)據(jù)寬度75
2.3.2 強制類型轉(zhuǎn)換77
2.3.3 char的符號類型79
2.3.4 變量符號類型的判斷80
2.4 按位操作80
2.4.1 移位操作81
2.4.2 標(biāo)志位的設(shè)置、檢測和清除82
2.4.3 常用的位操作模式84
2.4.4 位操作應(yīng)用舉例85
2.5 數(shù)值計算的速度88
第3章 指針、數(shù)組、結(jié)構(gòu)和類型90
3.1 指針變量91
3.1.1 指針變量的定義91
3.1.2 指針的類型93
3.1.3 指針運算94
3.1.4 指針的強制類型轉(zhuǎn)換95
3.1.5 不合法的指針運算97
3.1.6 指針與整數(shù)98
3.1.7 指針的增量運算和減量運算99
3.1.8 作為函數(shù)參數(shù)的指針100
3.2 指針和一維數(shù)組100
3.2.1 指針和數(shù)組的互換100
3.2.2 動態(tài)一維數(shù)組103
3.2.3 數(shù)組復(fù)制與指針賦值106
3.2.4 變量限制符const108
3.2.5 數(shù)組的負數(shù)下標(biāo)109
3.3 二維數(shù)組和一維指針數(shù)組110
3.3.1 作為參數(shù)的二維數(shù)組110
3.3.2 二維數(shù)組和指針111
3.3.3 二維數(shù)組和一維指針數(shù)組的對比113
3.3.4 指針數(shù)組和命令行參數(shù)116
3.3.5 二維數(shù)組的動態(tài)分配118
3.4 函數(shù)指針121
3.4.1 函數(shù)指針變量的定義122
3.4.2 函數(shù)指針變量的使用123
3.4.3 函數(shù)指針數(shù)組的使用128
3.5 結(jié)構(gòu)129
3.5.1 結(jié)構(gòu)類型的定義129
3.5.2 結(jié)構(gòu)成員的訪問131
3.5.3 結(jié)構(gòu)類型的嵌套定義133
3.5.4 結(jié)構(gòu)的自引用134
3.5.5 結(jié)構(gòu)類型與函數(shù)的參數(shù)和返回值134
3.6 復(fù)雜類型的解讀135
3.6.1 變量定義中的復(fù)雜類型說明136
3.6.2 強制類型轉(zhuǎn)換中的復(fù)雜類型139
3.6.3 類型定義語句和復(fù)雜類型的定義139
第4章 程序中的遞歸142
4.1 遞歸的定義142
4.2 遞歸函數(shù)的執(zhí)行149
4.3 遞歸函數(shù)的設(shè)計150
4.4 遞歸的優(yōu)點和缺點155
4.5 遞歸函數(shù)的效率158
4.6 遞歸函數(shù)的使用161
4.6.1 適宜使用遞歸的情況161
4.6.2 不適宜使用遞歸的情況169
4.7 遞歸函數(shù)效率的改進170
4.7.1 尾遞歸函數(shù)的非遞歸化170
4.7.2 帶存儲機制的遞歸171
4.7.3 一般遞歸函數(shù)的非遞歸化172
第5章 搜索176
5.1 搜索的目標(biāo)和基本過程176
5.2 深度優(yōu)先搜索178
5.2.1 深度優(yōu)先搜索的基本算法179
5.2.2 回溯搜索182
5.3 廣度優(yōu)先搜索185
5.4 重復(fù)節(jié)點的判斷188
5.5 帶深度控制的廣度優(yōu)先搜索195
5.6 節(jié)點的編碼和搜索效率199
第6章 常用函數(shù)和函數(shù)庫209
6.1 靜態(tài)鏈接和動態(tài)鏈接209
6.1.1 靜態(tài)鏈接209
6.1.2 動態(tài)鏈接210
6.2 庫函數(shù)的使用211
6.2.1 標(biāo)準(zhǔn)庫函數(shù)的頭文件212
6.2.2 標(biāo)準(zhǔn)函數(shù)庫文件的使用212
6.2.3 錯誤信息函數(shù)和變量213
6.3 數(shù)據(jù)輸入輸出函數(shù)214
6.3.1 文件描述字和字符流215
6.3.2 文件的打開、創(chuàng)建和關(guān)閉217
6.3.3 文件數(shù)據(jù)的二進制格式讀寫220
6.3.4 讀寫操作中的定位223
6.3.5 基礎(chǔ)讀寫與字符流讀寫的效率比較225
6.3.6 字符流的沖刷227
6.3.7 文件的屬性227
6.4 字符類型函數(shù)和字符串操作函數(shù)230
6.4.1 字符類型函數(shù)230
6.4.2 字符串操作函數(shù)231
6.5 時間函數(shù)233
6.5.1 日歷時間233
6.5.2 程序運行時間235
6.6 隨機數(shù)函數(shù)235
6.6.1 基本隨機數(shù)函數(shù)235
6.6.2 均勻分布隨機數(shù)的生成236
6.6.3 非均勻連續(xù)分布隨機數(shù)的生成237
6.6.4 離散分布隨機數(shù)的生成238
第7章 程序的優(yōu)化241
7.1 優(yōu)化的作用和意義241
7.2 優(yōu)化的基本過程242
7.2.1 運算時間和存儲空間242
7.2.2 優(yōu)化可能性的判斷243
7.2.3 程序運行的整體計時244
7.2.4 程序運行的分析計時和程序運行剖面246
7.3 運行效率的改進策略和方法249
7.3.1 調(diào)整代碼249
7.3.2 改進算法254
7.3.3 空間換時間258
7.3.4