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

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