主任： 李曉明副主任： 蔣宗禮盧先和委員： （按姓氏筆畫為序）馬華東馬殿富王志英王曉東寧洪劉辰孫茂松李仁發(fā)李文新楊波吳朝暉何炎祥宋方敏張莉金海周興社孟祥旭袁曉潔錢樂秋黃國(guó)興曾明廖明宏秘書： 張瑞慶

本書主審： 李曉明
本 書 序PREFACE
本書是一本與眾不同的程序設(shè)計(jì)入門教材，實(shí)踐性極強(qiáng)，不論對(duì)于高等學(xué)校計(jì)算機(jī)專業(yè)的學(xué)生，還是非計(jì)算機(jī)專業(yè)的學(xué)生，都非常適用。目前絕大部分程序設(shè)計(jì)入門教材的主要內(nèi)容就是詳細(xì)介紹一門程序設(shè)計(jì)語言，這對(duì)于高等學(xué)校計(jì)算機(jī)專業(yè)的學(xué)生是遠(yuǎn)遠(yuǎn)不夠的；對(duì)于非計(jì)算機(jī)專業(yè)的學(xué)生也略顯膚淺。許多大學(xué)本科計(jì)算機(jī)專業(yè)的課程設(shè)置，在程序設(shè)計(jì)語言和數(shù)據(jù)結(jié)構(gòu)這兩門課之間，并無空間進(jìn)行基礎(chǔ)算法的教學(xué)，這就容易導(dǎo)致學(xué)生由于基本技能缺失而在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程時(shí)產(chǎn)生困難，或難以學(xué)精。對(duì)于非計(jì)算機(jī)專業(yè)的學(xué)生來說，如果僅掌握一門程序設(shè)計(jì)語言的語法規(guī)則，寫幾個(gè)打印由星號(hào)組成的三角形之類的玩具程序，而對(duì)計(jì)算機(jī)科學(xué)的基礎(chǔ)與靈魂算法一無所知，不明白計(jì)算機(jī)到底是怎么解決問題的，那么在日后的工作中，不但不可能自己編寫實(shí)用程序，甚至不能敏感地及時(shí)意識(shí)到哪些問題適合用計(jì)算機(jī)處理，可以交給計(jì)算機(jī)專業(yè)人士來做。本書將程序設(shè)計(jì)語言和最基本的算法思想相結(jié)合，能夠有效避免上述現(xiàn)象。本書的最大特點(diǎn)是和北京大學(xué)程序在線評(píng)測(cè)系統(tǒng)緊密結(jié)合，具有極強(qiáng)的實(shí)踐性。北京大學(xué)程序在線評(píng)測(cè)系統(tǒng)(Peking University Online Judge System,POJ)是一個(gè)免費(fèi)的公益性網(wǎng)上程序設(shè)計(jì)題庫(kù)，網(wǎng)址為http://acm.pku.edu.cn/JudgeOnline(注意這里的網(wǎng)址區(qū)分大小寫)。它包含2000多道饒有趣味的程序設(shè)計(jì)題目，題目大部分來自ACM/ICPC國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽，很多題目就反映工作和生活中的實(shí)際問題。這些題目有易有難，比如最簡(jiǎn)單的題A B Problem就是給出兩個(gè)數(shù)，輸出它們的和。用戶可以針對(duì)某個(gè)題目編寫程序并提交，POJ 會(huì)自動(dòng)判定程序的對(duì)錯(cuò)。本書的所有例題和課后習(xí)題大都精選自POJ題庫(kù)，難度較低，學(xué)生做習(xí)題時(shí)可以將自己的程序提交給POJ，幾秒鐘之內(nèi)即可知道是對(duì)還是錯(cuò)。作為教學(xué)支持，每位學(xué)生在POJ上可以建立自己的賬號(hào)，教師在POJ上一眼就能看到學(xué)生是否已經(jīng)完成布置的習(xí)題，這幾乎將教師評(píng)判學(xué)生作業(yè)的工作量減少到零。POJ對(duì)于程序的正確性評(píng)判是極為嚴(yán)格的，學(xué)生的程序根據(jù)POJ給出的輸入數(shù)據(jù)進(jìn)行計(jì)算并輸出結(jié)果，POJ在服務(wù)器端編譯、運(yùn)行學(xué)生提交的程序，取得輸出結(jié)果和標(biāo)準(zhǔn)答案對(duì)比，必須一個(gè)字節(jié)都不差，程序才能夠通過。這對(duì)于培養(yǎng)嚴(yán)謹(jǐn)、周密的程序設(shè)計(jì)作風(fēng)極為有效，學(xué)生必須考慮到每一個(gè)細(xì)節(jié)和特殊邊界條件，而不是大體上正確就能夠通過。傳統(tǒng)的人工評(píng)判是難以做到這一點(diǎn)的。本書的另一特點(diǎn)是在敘述中穿插了許多精心編制的思考題，特別適合教師進(jìn)行啟發(fā)式教學(xué)。思考題沒有答案，以便教師引導(dǎo)學(xué)生進(jìn)行討論。程序設(shè)計(jì)導(dǎo)引及在線實(shí)踐(第2版)本書還有一個(gè)亮點(diǎn)，就是在許多例題后都會(huì)總結(jié)學(xué)生在完成該題時(shí)容易犯的典型錯(cuò)誤，讓學(xué)生少走彎路。這些錯(cuò)誤都總結(jié)自學(xué)生在POJ上提交的程序，因而具有典型性。本書中代碼的風(fēng)格也很值得一提。許多程序設(shè)計(jì)教程，其編寫者雖有豐富的教學(xué)經(jīng)驗(yàn)，但卻不一定具有實(shí)際的軟件開發(fā)經(jīng)歷，因而書中的例子程序往往在變量命名、代碼效率等程序設(shè)計(jì)風(fēng)格方面不是很在意，只求正確即可，教學(xué)代碼的痕跡明顯。而本書的作者除了具有多年的教學(xué)經(jīng)驗(yàn)以外，還從事過多年的軟件開發(fā)。李文新教授是國(guó)內(nèi)第一個(gè)自主研制的地理信息系統(tǒng)開發(fā)環(huán)境Geo�睻nion的主要設(shè)計(jì)者和核心代碼編寫者之一，曾經(jīng)擔(dān)任過圖原空間信息技術(shù)有限公司和長(zhǎng)天科技有限公司的總工程師。她目前是中國(guó)計(jì)算機(jī)學(xué)會(huì)信息學(xué)奧林匹克競(jìng)賽科學(xué)委員會(huì)的科學(xué)委員，是ACM/ICPC競(jìng)賽北京大學(xué)代表隊(duì)的原任教練和現(xiàn)任領(lǐng)隊(duì)。余華山副教授多年來一直從事支持高性能計(jì)算的程序開發(fā)與運(yùn)行環(huán)境的研究工作，是集群并行程序開發(fā)與運(yùn)行平臺(tái)P_HPF系統(tǒng)的主要研制者之一，主持開發(fā)了計(jì)算網(wǎng)格協(xié)同平臺(tái) Harmonia系統(tǒng)。在中國(guó)教育科研網(wǎng)格China Grid公共軟件支撐平臺(tái)CGSP的研制過程中，他是總體設(shè)計(jì)的主要負(fù)責(zé)人之一，并負(fù)責(zé)CGSP信息服務(wù)系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)。郭煒老師的專業(yè)研究方向是計(jì)算機(jī)輔助教學(xué)，他獨(dú)立開發(fā)了《我愛背單詞》等系列著名英語學(xué)習(xí)軟件，同時(shí)還擔(dān)任教練，和李文新教授一起率領(lǐng)北京大學(xué)ACM/ICPC國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽隊(duì)在國(guó)際競(jìng)賽中取得了較好名次。本書中的例子程序的代碼風(fēng)格優(yōu)美、注釋完備、可讀性強(qiáng)，以此作為范例，對(duì)培養(yǎng)良好的程序設(shè)計(jì)風(fēng)格，日后在團(tuán)隊(duì)開發(fā)中贏得同事的信任和喜愛十分有益。在這個(gè)提倡創(chuàng)新的年代，本書是特別富有創(chuàng)意的，希望并相信讀者能夠喜歡。
2007年8月北京大學(xué)教授原教育部高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會(huì)副主任21世紀(jì)大學(xué)本科計(jì)算機(jī)專業(yè)系列教材編委會(huì)主任
前言FOREWORD計(jì)算機(jī)程序是通過在計(jì)算機(jī)內(nèi)存中開辟一塊存儲(chǔ)空間，并用一個(gè)語句序列不斷修改這塊存儲(chǔ)空間上的內(nèi)容，最終得到問題的答案的方法來解決實(shí)際問題的。計(jì)算機(jī)程序一般需要用一種具體的程序設(shè)計(jì)語言表達(dá)出來。一種計(jì)算機(jī)語言通過定義變量的形式給出了申請(qǐng)內(nèi)存的方式，并通過表達(dá)式和賦值語句給出了對(duì)內(nèi)存中的數(shù)據(jù)進(jìn)行運(yùn)算和修改的方法，通過分支和循環(huán)語句提供了用不同方式安排語句序列的能力。大部分計(jì)算機(jī)語言還提供了基礎(chǔ)函數(shù)庫(kù)來完成一些常用的計(jì)算和數(shù)據(jù)處理的功能。使用計(jì)算機(jī)程序解決實(shí)際問題，首先要能夠?qū)⒁粋�(gè)具體問題抽象成一個(gè)可計(jì)算的問題，并找出可行的計(jì)算過程；其次是掌握一門程序設(shè)計(jì)語言，將設(shè)計(jì)的計(jì)算過程寫成具體的代碼在機(jī)器上運(yùn)行。作者總結(jié)了多年計(jì)算機(jī)程序設(shè)計(jì)類課程的教學(xué)經(jīng)驗(yàn)，認(rèn)為在程序設(shè)計(jì)課程的教學(xué)中應(yīng)該把握5個(gè)基本的教學(xué)環(huán)節(jié)： 第一，讓學(xué)生充分理解計(jì)算機(jī)程序在內(nèi)存中的運(yùn)行原理和過程。在程序運(yùn)行過程中任意時(shí)刻都清楚語句運(yùn)行到了哪里，以及當(dāng)前存儲(chǔ)數(shù)據(jù)的內(nèi)存區(qū)的內(nèi)容是什么。只有清楚這些，才能在程序調(diào)試過程中及時(shí)地找到出錯(cuò)位置，并修改錯(cuò)誤，最終讓程序按照設(shè)計(jì)者的意圖執(zhí)行。第二，以一門高級(jí)程序設(shè)計(jì)語言為例，讓學(xué)生了解該設(shè)計(jì)語言使用哪些語句定義變量，哪些語句修改變量，變量有哪些基本類型，每種類型的變量占多大的存儲(chǔ)空間，不同類型的變量可以進(jìn)行哪些運(yùn)算，哪些語句用來控制語句序列的分支和循環(huán)，如何用簡(jiǎn)單變量組合出復(fù)雜變量（如數(shù)組或結(jié)構(gòu)體），如何控制復(fù)雜的計(jì)算過程（如通過函數(shù)實(shí)現(xiàn)分而治之），有哪些庫(kù)函數(shù)是可用的，等等。第三，講授一些常用的、基本的計(jì)算過程，使得學(xué)生在解決復(fù)雜問題之前，手上有一些可用的基本方法。例如，如何通過分支和循環(huán)語句模擬一個(gè)手工計(jì)算的過程，進(jìn)行不同數(shù)制轉(zhuǎn)換時(shí)可以選定一個(gè)共同的基數(shù)進(jìn)行轉(zhuǎn)換，字符串處理的問題應(yīng)該多使用庫(kù)函數(shù)，處理日期問題時(shí)可以用一個(gè)數(shù)組來存儲(chǔ)每個(gè)月的天數(shù)，這樣可以很方便地處理不規(guī)則的數(shù)據(jù)，等等。第四，圍繞一些具體的問題實(shí)例，讓學(xué)生學(xué)會(huì)通過分析問題抽象出數(shù)學(xué)模型，從而設(shè)計(jì)出計(jì)算過程和中間數(shù)據(jù)的存儲(chǔ)方式，最終實(shí)現(xiàn)代碼并調(diào)試成功。學(xué)生只有通過這樣一個(gè)完整的程序設(shè)計(jì)過程的訓(xùn)練，才能充分理解寫程序是要干什么，并且學(xué)會(huì)判斷什么樣的問題適合用計(jì)算機(jī)來解決。第五，學(xué)生學(xué)習(xí)效果的檢驗(yàn)方式直接決定了最終的教學(xué)效果。如果想讓學(xué)生真正學(xué)會(huì)獨(dú)立動(dòng)手寫出正確的程序，就必須采取上機(jī)考查的方式，要求學(xué)生針對(duì)實(shí)際問題寫出最終可以正確運(yùn)行并能解決問題的程序。本書的內(nèi)容安排充分體現(xiàn)了上述的教學(xué)理念。為了方便理解例題中的代碼，本書先用1/3的篇幅簡(jiǎn)明扼要地介紹C/C 語言的基本語法，包括變量的定義，變量的值的修改，基本的變量類型，用基本類型的變量構(gòu)造數(shù)組、結(jié)構(gòu)體等復(fù)雜的數(shù)據(jù)類型，定義表達(dá)式，控制語句序列，以及常用的C語言標(biāo)準(zhǔn)庫(kù)函數(shù)。程序設(shè)計(jì)導(dǎo)引及在線實(shí)踐(第2版)之后所有的內(nèi)容都采用以問題為中心的講述方式。首先用近1/3的篇幅講述面對(duì)不同類型的常見問題，應(yīng)該如何抽象計(jì)算過程，并將計(jì)算過程寫成具體代碼。這些問題包括簡(jiǎn)單計(jì)算問題、數(shù)制轉(zhuǎn)換問題、字符串處理問題、日期和時(shí)間處理問題、計(jì)算過程模擬問題等。接著用近1/4的篇幅講述了計(jì)算機(jī)程序設(shè)計(jì)中常用的但不同于數(shù)學(xué)計(jì)算方法的三種算法思想： 枚舉、遞歸和動(dòng)態(tài)規(guī)劃。本書的最后兩章講述了如何用基本的數(shù)據(jù)類型構(gòu)造一些稍微復(fù)雜的數(shù)據(jù)結(jié)構(gòu)： 鏈表和二叉樹，作為本書向數(shù)據(jù)結(jié)構(gòu)遞進(jìn)的序曲。配合本書的教學(xué)，我們使用了北京大學(xué)在線評(píng)測(cè)系統(tǒng)，書中所有的例題和練習(xí)題都在該系統(tǒng)上，學(xué)生可以隨時(shí)針對(duì)某一題目編寫程序并提交給系統(tǒng)，幾秒鐘內(nèi)就可以獲得正確與否的回答。我們也利用該系統(tǒng)進(jìn)行學(xué)生的期中、期末考試，學(xué)生必須現(xiàn)場(chǎng)在給定的時(shí)間內(nèi)完成從問題分析到代碼實(shí)現(xiàn)的全部過程才能通過考試。為了測(cè)試程序在不同數(shù)據(jù)輸入下的正確性，該系統(tǒng)中的題目大部分采用輸入多組測(cè)試數(shù)據(jù)的形式，所以在書中會(huì)看到每個(gè)程序都要讀入多組數(shù)據(jù)進(jìn)行處理。這些測(cè)試數(shù)據(jù)是彼此獨(dú)立的，可以讀入一組，處理一組并輸出結(jié)果，然后再讀入下一組。本書作者分工如下： 李文新編寫第1章中的1.1、1.2、1.4、1.7、1.8、1.9節(jié)，第2章，第5章，第9章中的9.3、9.4、9.6、9.10節(jié)，以及附錄A和附錄B。郭煒編寫第1章中的1.3、1.5、1.6、1.10～1.19節(jié)，第6章，第7章，第9章中的9.1、9.2、9.5、9.7、9.8和9.9節(jié)，以及第10章。余華山編寫第3章、第4章、第8章、第11章和第12章。由于水平和精力所限，書中難免存在不當(dāng)之處，懇請(qǐng)專家和讀者批評(píng)指正。
作者2016年9月于燕園