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