本書以程序設計的分析問題和解決問題為重點,講授在C/C 語言環(huán)境下程序設計的解題思路、算法設計和程序實現,可幫助讀者提高編程能力和上機解題能力。全書語言簡潔,示例豐富,深入淺出地引導讀者理性思維和理性實踐,章節(jié)結構安排合理,教學方法引人入勝,便于讀者自學。
本書可作為高等院校計算機相關專業(yè)程序設計課程的教材,亦可供從事計算機、自動化及其他相關領域的科研技術人員參考。
1. 強調轉變觀念,以學生為中心,安排教學首先考慮培養(yǎng)目標、學生的認知規(guī)律和學習特點。2. 強化實踐,讓學生在理論指導下動手動腦,更多地上機編程,鼓勵和引導探索式的學習;以任務驅動方式,通過示例講授程序設計的基本概念和方法。3. 重點放在思路、算法、編程構思和程序實現上,訓練學生分析問題和解決問題的能力;注重培養(yǎng)學生良好的編程習慣。
第4版前言本書第3版是2010年11月完成的。六年來,我們在使用本教材的過程中,認真聽取學生反饋意見,不斷改進教學方法、完善教學環(huán)節(jié)、調整教學次序,使得課程學習效果有了進一步提升。為及時反映課內教學成果,我們又在第3版基礎上對文字教材進行了修訂,包括調整了若干章節(jié)的次序、補充了部分章節(jié)的課后習題、修改了一些地方的文字錯誤和代碼錯誤等等。我們還系統(tǒng)梳理了第3版教材中的所有示例源程序,調整了所有代碼中的注釋,清除了在部分代碼中發(fā)現的問題,并用最新的編譯環(huán)境進行了編譯測試。希望本次修訂能為計算機語言程序設計學習者提供一本內容與時俱進、更加易學易用的教材。由于時間倉促,作者水平有限,書中難免還有紕漏,歡迎廣大讀者朋友多提寶貴意見!
吳文虎,徐明星,鄔曉鈞2017年1月
第3版前言本書的第1版是2003年9月完成的,經過一年的試用,于2004年9月發(fā)行了第2版。 學生普遍反映,這本教材思路清晰,重點突出,易學易用,特別是強化實踐教學思想,使學生既動手又動腦,學會了編程的基本思路和方法,受到了學生的好評。從第2版的使用到現在又經過了6年時間,這期間我們在實踐中認真聽取學生的反饋意見,不斷改進教學方法,與時俱進地充實教學內容,特別是注重將講課內容與作業(yè)提交系統(tǒng)形成一個有機的整體;使學生的學習更容易做到理性思維和理性實踐,以期達到進一步提高教學質量的目標。為此,我們又在第2版的基礎上調整了部分章節(jié),增加了一些常用的重要算法及程序實現,形成了現在的第3版。從教材改版的目標而言,我們認為沒有最好,只有更好。
吳文虎 徐明星2010年9月
第2版前言本書第1版是2003年9月出版的,經過一年的使用后,學生普遍反映本書重點突出,易學易用。但作為教師,我感到還要不斷地研究教學規(guī)律,化解教學中的難點。為此,我又重新審閱了全書,在文字上做了調整,內容上做了修正,力求講得明白透徹。在教學中發(fā)現,初學者往往要花費很多的時間在程序調試上,效率很低。實際上程序調試已成為學生編程實踐中的攔路虎。所以,配合本書,又專門編著了《程序設計基礎(第2版)習題解答與上機指導》,還準備上小班輔導課讓學生學會調試程序的基本方法。我認為這可能是進一步提高該課教學質量的一個關鍵。
吳文虎2004年8月
第1版前言計算機語言與程序設計是一門十分重要的基礎課程。該課長期沿襲著這樣的教學模式:過于注重語句、語法和一些細節(jié),基本上是以高級語言自身的體系為脈絡展開的,沒有把邏輯與編程解題思路放在主體地位上;對如何分析問題和解決問題講得不夠,對學生編程的能力、上機解題的能力訓練不夠。這樣就給后續(xù)課程及研究生階段的課題研究留下了缺憾。很多學生在學習這門課時感到枯燥難學,學過之后,不能用來解決實際問題。我個人的經歷有些不同,除了學校給我安排的教學和科研任務之外,20年來我一直指導初中學生、高中學生和大學生參加有關計算機的各種比賽,包括國際信息學奧林匹克和ACM世界大學生程序設計競賽,通過對這些學生成長道路的反復思考和研究,使我感到很有必要改變我們的課程教學模式,用新的教學理念和方法培養(yǎng)一流人才。對這一問題,我和有關領導談了自己的想法,他們非常支持。從2001年9月起,我接受了程序設計基礎課程的教學任務,并開始對該課程教學模式進行改革:以強調動手實踐上機編程為切入點;以任務驅動方式,通過實例講授程序設計的基本概念和基本方法;重點放在思路上,即在C/C 語言的環(huán)境下,針對問題進行分析,構建數學模型,理出算法并編程實現。同時,要求學生養(yǎng)成良好的編程習慣;在教學過程中培養(yǎng)學生的思維能力和動手能力,鼓勵學生探索、研究和創(chuàng)新。在指導思想上,強調轉變觀念,以學生為中心,將學生視為教學的主體,安排教學首先考慮培養(yǎng)目標、學生的認知規(guī)律和學習特點。在教學的每一個環(huán)節(jié),顧及學生的實際情況,多想怎樣才能有利于調動學生學習的積極性,引導學生主動學習。具體的改革措施主要針對兩個方面:教學模式和對學生學習的評價方式。對教學模式的改革提出強化實踐。明確告訴學生:程序設計課是高強度的腦力勞動,不是聽會的,也不是看會的,而是自己練會的。只有讓學生動手,他才會有成就感,進而對課程產生興趣,學起來才比較從容。因此,我們的基本思想是在理論指導下,讓學生動手、動腦,更多地上機實踐。學生只有在編寫大量程序之后,才能獲得真知灼見,感到運用自如。注重學生動手能力的培養(yǎng)是這門課和以往課程最大的不同之處。提出理性思維和理性實踐。按照建構主義的學習理論,學生作為學習的主體在與客觀環(huán)境(指所學內容)的交互過程中構建自己的知識結構。教師應引導學生在解題編程的實踐中探索其中帶規(guī)律性的認識,將感性認識升華到理性高度,只有這樣,學生才能舉一 反三。提出授課的原則是要學生抱西瓜而不是撿芝麻,重點放在思路、算法、編程構思和程序實現上。語句只是表達工具,講一些最主要的,對細枝末節(jié)的東西根本不講。要求學生在課堂上積極思考,盡量當堂學懂。突出上機訓練,在編寫程序的過程中,使學生提高利用計算機這個智力工具來分析問題和解決問題的能力。提出要讓學生養(yǎng)成良好的編程習慣。我們在與國內一些軟件公司的技術人員座談時了解到,中國軟件之所以上不去的原因之一就有習慣問題。印度十個人編程,會編出一樣的東西,而我們十個人編程可能會有十種風格。因為我們忽略了一個重要問題,即顧客的感受,程序的編寫是給別人看的,而不是只給我們自己看的。再者,盡管我們學生模型構思做得很快,但編程的基本功不扎實,往往到了關鍵的時候,就出問題。鑒于此,在課上我們強調程序的可讀性、規(guī)范性;要求變量必須加注釋;程序構思要有說明;學會如何調試程序;盡量使程序優(yōu)化;還要求對程序的運行結果做正確與否的判斷和分析。提出自學、動手、應用、上網的學習習慣。我認為在本科階段就應該注意培養(yǎng)學生的自學能力。很多東西完全是可以自學的,尤其是計算機。計算機是實踐性極強的學科,所學的內容和要實踐的東西是一個整體,因此可以自己動手來學,書上看不懂的在機器上動手試試,往往就弄懂了。上網是指充分利用網絡平臺,提高獲取信息、處理信息和交流信息的能力。對學生學習評價方式的改革考試是檢驗學生學習效果、評價學生學習業(yè)績的重要環(huán)節(jié)。考試作為指揮棒對教學目標、教學過程有著相當大的影響。我一直在思考如何進行考試改革,如何借助考試環(huán)節(jié)調動和激發(fā)學生自主學習的積極性、創(chuàng)造性等問題。開學之初,我就向學生宣布考試方式上機解題,判分也是由計算機來完成,對就是對,錯就是錯,不紙上談兵,不考筆試,不考死記硬背的東西。我們平時比較注意對學生學習方式的引導,讓學生明白:理論很重要,要在理論指導下,動手動腦、有條理地進行實踐。實踐才能出真知,動手才能學到真本事。我們還將一些有較好程序設計基礎的學生組織起來,因材施教,引導他們進行探索式的研究性學習,讓他們繼續(xù)提高。同時讓他們在班上擔任小教員,幫助同學學習。這樣做行不行呢?經過兩年的教學實踐,這門課取得了很好的教學效果,學生給以很高的評價。學生點評為:授課方式獨特新穎,深入淺出,啟發(fā)式教學,激發(fā)學生興趣,調動學生的積極性,有助于學生獨立思考能力的提高。(引自清華大學2001年下半年教學評估結果查詢)參加小教員工作的學生,提高了責任感,培養(yǎng)了敬業(yè)精神。他們的水平和能力也有相應的提高,其中三名同學代表清華大學參加了2002年ACM世界大學生程序設計競賽的分區(qū)賽和總決賽,取得了世界總排名第四的好成績(2300支隊伍參加區(qū)域賽,60支隊伍參加總決賽)。2002年5月,在北京市高校計算機基礎教育研討會上,我曾應約就此課程的教學改革作了專題報告,受到了與會專家和老師們的好評,他們認為這是非常好的新的教學范例。改革是沒有止境的。經過兩年的實踐,我感到在一些方面還要進一步努力,還有許多工作要做:要進一步加大學生訓練環(huán)節(jié)的力度;要加強對基礎較差學生的輔導;要建立一個因材施教的機制,創(chuàng)造條件,讓學生能有更廣闊的發(fā)展空間;要建立平時的督促機制,讓每一個學生真正落實動手實踐;要考慮與后續(xù)課程的銜接。現在大家看到的這本教材就是在上述的背景下,整理了課上的教案,補充了一些內容寫出來的。在教材成文的過程中,我的同事和學生(博士生)起了很大作用。他們提出了很好的建議,對一些算法進行了研究和整理,特別是對全書整體上的結構進行了縝密的 推敲。從一種體系轉變?yōu)楝F在的體系是有相當大的難度的,也有風險,學生愛不愛這樣學,能不能學到真本事,是不是能夠達到預期的教學目標,都會存在問題。但我以為,要改革就要知難而進,不付諸努力就收到良好的教學效果是不可能的。目前這本教材可能存在很多不足,但是我們有這種思想準備,在教學實踐中,多聽取學生的反饋意見,不斷修改,使之日臻完善。我們相信,恒心與虛心能夠成就一本好的 教材。參加本書研究、撰寫工作的還有徐明星(參加本書總體策劃與章節(jié)編排)、鄔曉鈞(撰寫第9、10、13章及附錄)和李凈(進行教案整理、圖文設計),此外,趙強工程師和楊非同學也做了大量的書稿整理和成文工作,吳根清、孫輝、劉建、劉林泉、鄧菁、陳德鋒、侯啟明等同學看了本書的第一稿,提出了寶貴的修改意見。在此一并感謝他們所付出的 勞動。由于時間倉促,作者水平有限,書中難免有紕漏,歡迎讀者多提寶貴意見。
吳文虎2003年9月
目錄
第1章 緒論 1
第2章 編程準備 4
2.1 程序編寫 4
2.1.1
用Visual C 6.0編寫程序 4
2.1.2
使用Dev-C 開發(fā)程序 8
2.2 程序代碼及說明 14
2.3 輸出流對象cout 15
2.4 程序注釋 16
2.5 算術運算符 16
2.6 數學函數 17
2.7 小結 17
習題 17
第3章 代數思維與計算機解題 19
3.1 程序的基本結構 19
3.2 變量與數據類型 21
3.2.1
變量的基本概念 21
3.2.2
數據類型與變量的地址空間 22
3.3 定義變量和賦初值 22
3.4 變量賦值 23
3.4.1
賦值符號與賦值表達式 23
3.4.2
變量賦值的5要素 24
3.5 指針變量 25
3.5.1
指針定義與初始化 25
3.5.2
指針賦值 26
3.5.3
在賦值語句中使用間接訪問運算符 26
3.6 小結 27
習題 28
第4章 邏輯思維與計算機解題 29
4.1 關系運算和關系表達式 30
4.1.1
關系運算符 30
4.1.2
關系表達式的一般格式 30
4.1.3
將是否寫成關系表達式 30
4.2 枚舉法的思路 31
4.3 循環(huán)結構 33
4.3.1
使用循環(huán)結構的部分程序 33
4.3.2
for語句的格式和執(zhí)行過程 33
4.3.3
使用for循環(huán)解題實例 34
4.3.4
for循環(huán)的程序框圖 36
4.4 分支結構 36
4.4.1
if語句的格式 37
4.4.2
分支結構的實例 38
4.5 任務4.1的程序框圖 39
4.6 任務4.1的參考程序 40
4.7 邏輯問題及其解法 41
4.7.1
邏輯運算符與邏輯表達式 42
4.7.2
邏輯問題的解題思路 43
4.7.3
任務4.2的參考程序 47
4.8 小結 48
課后閱讀材料 48
習題 53
第5章 函數思維與模塊化設計 55
5.1 函數 55
5.1.1
函數的說明 56
5.1.2
函數的定義 56
5.1.3
函數的返回值 56
5.1.4
函數的調用 57
5.1.5
形式參數和實在參數 57
5.1.6
調用和返回 58
5.1.7
帶自定義函數的程序設計 58
5.2 編程實例1 60
5.3 編程實例2 61
5.4 幾種參數傳遞方式的比較 63
5.5 小結 66
習題 66
第6章 數據的組織與處理(1) 數組 69
6.1 數組 69
6.1.1
一維數組的定義 71
6.1.2
數組初始化 71
6.1.3
字符數組的定義、初始化和賦值 72
6.1.4
數組與指針 75
6.2 篩法 77
6.3 線性查找與折半查找 78
6.4 冒泡排序法 80
6.5 遞推 82
6.5.1
遞推數列的定義 82
6.5.2
遞推算法的程序實現 83
6.6 字符數組應用 86
6.7 函數跳轉表 91
6.8 二維數組 93
6.8.1
二維數組的定義 94
6.8.2
二維數組的初始化 95
6.8.3
二維數組中的元素存放順序 95
6.9 小結 97
課后閱讀材料 98
習題 102
第7章 數據的組織與處理(2) 結構 105
7.1 結構與結構數組 105
7.1.1
結構體類型的定義 105
7.1.2
結構體變量的定義和引用 106
7.1.3
結構體變量的初始化 107
7.1.4
結構數組 108
7.2 指針和結構 110
7.3 鏈表 111
7.3.1
建立鏈表的過程 112
7.3.2
鏈表結點的插入與刪除 116
7.3.3
循環(huán)鏈表 124
7.4 小結 128
習題 128
第8章 數據的組織與處理(3) 文件 130
8.1 將數據保存到文件 130
8.2 從文件中讀取數據 132
8.3 利用輸入輸出文件解交互類型的題 135
8.4 小結 145
習題 145
第9章 遞歸思想與相應算法 146
9.1 遞歸及其實現 146
9.2 遞歸算法舉例 153
9.2.1
計算組合數 153
9.2.2
快速排序 154
9.2.3
數字旋轉方陣 158
9.2.4
下樓問題 162
9.2.5
跳馬問題 164
9.2.6
分書問題 166
9.2.7
八皇后問題 169
9.2.8
青蛙過河 172
9.3 小結 177
課外閱讀材料 177
習題 181
第10章 多步決策問題 182
10.1
多步決策問題的解題思路 182
10.1.1
人鬼渡河的任務與規(guī)則要點 182
10.1.2
人鬼渡河的安全性考慮 183
10.1.3
安全狀態(tài)的描述 183
10.2
安全條件形式化 184
10.3
從狀態(tài)圖上研究怎樣一步一步過河 186
10.4
多步決策問題的編程思路 186
10.5
小結 189
習題 189
第11章 寬度優(yōu)先搜索 191
11.1
騎士聚會問題 191
11.2
解題思路 196
11.3
小結 202
習題 203
第12章 深度優(yōu)先搜索 204
12.1
問題描述 204
12.2
解題思路 205
12.3
深度優(yōu)先搜索與剪枝 211
12.4
小結 216
習題 216
第13章 貪心法 217
13.1
貪心法解題的一般步驟 217
13.1.1
裝船問題 217
13.1.2
事件序列問題 220
13.1.3
貪心法解題的一般步驟 222
13.2
貪心法相關理論 223
13.2.1
多階段決策問題、無后向性與最優(yōu)化原理 223
13.2.2
有向圖最短路徑的Dijkstra算法 223
13.2.3
貪心法解題的注意事項 227
13.3
小結 228
習題 228
第14章 動態(tài)規(guī)劃 230
14.1
最短路徑問題 230
14.1.1
問題描述 230
14.1.2
分析與題解 231
14.2
動態(tài)規(guī)劃的基本概念 234
14.3
動態(tài)規(guī)劃思想 235
14.4
舉例說明動態(tài)規(guī)劃思路 237
14.5
小結 244
習題 244
第15章 蒙特卡羅法 246
15.1
偽隨機數的產生 246
15.1.1
產生隨機整數 246
15.1.2
產生隨機小數 247
15.2
偽隨機數的應用 248
15.2.1
求的近似值 248
15.2.2
計算圖形面積 249
15.3
小結 250
習題 250
附錄A 程序調試 251
A.1 計分程序的調試 251
A.1.1
編譯時的調試 252
A.1.2
運行時的調試 254
A.1.3
其他調試相關知識 259
A.2 跳馬程序的調試 260
附錄B 庫函數 267
B.1 數學函數 267
B.2 字符判斷函數 268
B.3 字符串相關函數 271
附錄C ASCII碼表 277
附錄D 輸入輸出的格式控制 278
D.1 流的概念與輸入輸出格式 278
D.2 改變整數的進制 278
D.3 設置浮點數的精度 279
D.4 設置輸入輸出寬度 280
D.5 設置對齊方式和填充字符 281
D.6 其他設置 282
參考文獻 284