自1996年中國首次舉辦ACM國際大學生程序設計競賽(ACM International Collegiate Programming Contest,ACMICPC或ICPC,網(wǎng)址https://icpc.baylor.edu)亞洲區(qū)預選賽以來,國內高校越來越重視大學生程序設計競賽。中國大學生程序設計競賽(China Collegiate Programming Contest,CCPC,網(wǎng)址https://ccpc.io)旨在“激勵當代大學生運用計算機編程技術和技能來解決實際問題,激發(fā)其學習算法和程序設計的興趣,培養(yǎng)其團隊合作意識、創(chuàng)新能力和挑戰(zhàn)精神”。目前,ICPC、CCPC及團體程序設計天梯賽(Group Programming Ladder Tournament,GPLT,網(wǎng)址https://gplt.patest.cn/)等是國內大學生主要參加的大規(guī)模賽事。
對于零基礎學習程序設計課程且希望在程序設計競賽方面具有較好基礎的學生而言,程序設計競賽與課程教學相結合的教材比較難尋。而本書主要以C++語言描述過程化程序設計,同時兼顧C語言,著重引入大學生程序設計競賽的基礎知識,能滿足這類學生的需求。本書重點討論過程化程序設計的基礎知識、程序控制結構、數(shù)組、函數(shù)、結構體、指針、鏈表等方面的內容,希望能為零基礎學習C/C++程序設計的同學打下較好的基礎。另外,本書還引入大學生程序設計競賽的基礎知識,主要包括在線做題結構、空間換時間思想與方法、C++標準模板庫(Standard Template Library,STL)常用容器、遞推與動態(tài)規(guī)劃、深度優(yōu)先搜索與廣度優(yōu)先搜索、查找與排序、貪心法與回溯法、大整數(shù)運算及簡單數(shù)學問題等,希望對擬參加大學生程序設計競賽的同學有所幫助。
本書立足于在線測評系統(tǒng)(Online Judge,OJ),以OJ上的問題為載體和核心,把對問題的分析和求解作為主線,簡化了語法和理論知識的講解,注重運用知識求解具體問題。本書以問題為導向,適合學生針對OJ問題進行探究式學習,注重培養(yǎng)學生的計算思維及編程求解具體問題的能力。
書中帶“*”的章節(jié),主要是程序設計競賽相關的內容,可根據(jù)實際需要,作為學生自主學習的內容,或由教師酌情選講。因本書編程方面的例題與習題較多,故教師可以酌情選講,學生也可以酌情選學。
本書中的編程例題、習題主要來自OJ。書中大部分例題和編程習題來自紹興文理學院OJ(簡稱HLOJ,網(wǎng)址http://acm.usx.edu.cn),這離不開紹興文理學院程序設計類課程組教師歷年來的辛勤工作,在此對他們表示由衷的感謝!書中部分編程例題和習題參考改編自浙江大學OJ(ZOJ,網(wǎng)址https://zoj.pintia.cn/)、杭州電子科技大學OJ(HDOJ,網(wǎng)址http://acm.hdu.edu.cn)、浙江工業(yè)大學OJ(ZJUTOJ,網(wǎng)址http://cpp.zjut.edu.cn)等OJ上的題目,在此對出題者及相關的老師、同學表示由衷的感謝!為便于讀者在OJ上練習,每章的OJ題解及OJ編程題都標注了一個出處(標題、描述等方面可能有所改編)。
在編寫本書的過程中,作者參閱了國內外一些C/C++程序設計語言、數(shù)據(jù)結構與算法方面的著作,從中吸收了新的思想、新的內容,書中部分內容和習題參考了這些著作及其網(wǎng)絡資源,在這里對所參考著作的作者及相關人員表示衷心感謝!
本書受浙江省首批高等學校省級精品在線開放課程“高級語言”、浙江省一流課程“高級語言”、教育部產(chǎn)學合作協(xié)同育人項目(項目編號: 201902047018)支持,在此表示衷心感謝!
在編寫本書的過程中,編者力圖在問題驅動、競賽引導、能力導向及強化實踐等方面有所突破、有所創(chuàng)新,然而受限于能力和水平,書中難免存在疏漏和不足之處,懇請閱讀本書的讀者批評指正。
編者
2020年8月
第1章緒論
1.1大學生程序設計競賽簡介
1.2程序設計及其語言簡介
1.2.1程序與程序設計
1.2.2程序設計語言
1.3簡單的C/C++程序
1.4DevC++ 開發(fā)環(huán)境簡介
1.5在線做題基本程序結構
1.5.1處理T次
1.5.2處理到文件尾
1.5.3處理到特值結束
1.6OJ題目求解
習題
第2章程序設計基礎知識
2.1C/C++標識符
2.2C/C++數(shù)據(jù)類型
2.2.1基本數(shù)據(jù)類型
2.2.2其他數(shù)據(jù)類型
2.3進制基礎
2.3.1二進制
2.3.2八進制與十六進制
2.3.3進制轉換
2.4常量與變量
2.4.1常量
2.4.2變量
2.5運算符
2.5.1算術運算符
2.5.2賦值運算符
2.5.3自增、自減運算符
2.5.4關系運算符與邏輯運算符
2.5.5條件運算符
2.5.6逗號運算符
2.5.7位運算
2.5.8類型轉換
2.5.9運算符的優(yōu)先級與結合性
2.6C語言輸入/輸出
2.6.1字符/字符串數(shù)據(jù)輸入/輸出
2.6.2格式輸入與輸出
2.7C++語言輸入/輸出
2.8STL之string
2.8.1string基礎
2.8.2使用string
2.9OJ題目求解
習題
第3章程序控制結構
3.1流程圖及程序控制結構簡介
3.1.1流程圖
3.1.2程序控制結構簡介
3.2選擇結構
3.2.1if語句及其使用
3.2.2switch語句及其使用
3.3循環(huán)結構
3.3.1引例與三種循環(huán)語句
3.3.2for語句及其使用
3.3.3while語句及其使用
3.3.4do…while語句及其使用
3.3.5continue、break語句及其使用
3.4OJ題目求解
習題
第4章數(shù)組
4.1引例
4.2一維數(shù)組
4.2.1一維數(shù)組基礎
4.2.2一維數(shù)組的運用
4.3二維數(shù)組
4.3.1二維數(shù)組基礎
4.3.2二維數(shù)組的運用
4.4*STL之vector
4.4.1STL之一維vector
4.4.2STL之二維vector
4.5字符串與字符數(shù)組
4.5.1字符串常量
4.5.2字符數(shù)組
4.6OJ題目求解
習題
第5章函數(shù)
5.1引例與概述
5.1.1引例
5.1.2概述
5.2函數(shù)基本用法
5.2.1函數(shù)的定義
5.2.2函數(shù)的聲明
5.2.3函數(shù)的調用
5.3函數(shù)舉例
5.4數(shù)組作函數(shù)參數(shù)
5.4.1數(shù)組元素作實參
5.4.2數(shù)組名作函數(shù)參數(shù)
5.5引用
5.6遞歸函數(shù)
5.6.1遞歸基礎
5.6.2典型遞歸問題
5.7變量的作用域與生命期
5.7.1變量的作用域
5.7.2變量的生命期
5.8編譯預處理
5.8.1宏定義
5.8.2文件包含
5.8.3條件編譯
5.9程序調試
5.9.1調試簡介
5.9.2DevC++調試過程
5.10OJ題目求解
習題
第6章結構體
6.1引例
6.2結構體基礎
6.2.1結構體類型聲明
6.2.2結構體變量的定義及初始化
6.2.3結構體變量的使用
6.3結構體數(shù)組
6.3.1結構體數(shù)組的定義與初始化
6.3.2結構體數(shù)組應用舉例
6.4OJ題目求解
習題
第7章指針
7.1指針的基本概念
7.1.1變量的地址
7.1.2指針變量
7.1.3指針運算
7.2指針與數(shù)組
7.2.1指針與一維數(shù)組
7.2.2指針與二維數(shù)組
7.2.3指針數(shù)組
7.2.4堆內存分配
7.3指針與函數(shù)
7.3.1指針參數(shù)
7.3.2指針函數(shù)
7.3.3函數(shù)指針
7.4結構體指針
7.5OJ題目求解
習題
第8章鏈表
8.1鏈表概述
8.2創(chuàng)建單鏈表
8.2.1順序鏈表
8.2.2逆序鏈表
8.3單鏈表基本操作
8.3.1基本操作的實現(xiàn)
8.3.2基本操作的應用
8.4*STL之list
8.4.1list基礎
8.4.2list的應用
8.5OJ題目求解
習題
第9章*程序設計競賽基礎
9.1遞推與動態(tài)規(guī)劃
9.2簡單數(shù)學問題
9.3大整數(shù)運算
9.4搜索入門
9.5常用算法
習題
參考文獻