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

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