具體描述
編輯推薦
本書可以作為“C語言程序設計”基礎教材!此外,本書將ACM競賽平颱OJ(Online Judge)係統用於C語言的學習過程中,旨在幫助讀者快速掌握C語言的基礎知識和ACM/ICPC的基本答題方法。全書內容深入淺齣、通俗易懂,可使讀者在短時間內掌握編程要領。書中主要實例采用瞭ACM/ICPC規定的格式進行描述,所有程序均已在DEV C++上調試通過。本書配套資源下載地址為清華大學齣版社網站本書頁麵,內容包括書中的全部實例的源代碼文件。
內容簡介
《C語言程序設計:零基礎ACM、ICPC競賽實戰指南/清華開發者書庫》是專為C語言愛好者及ACM/ICPC參賽者編寫的入門級教程,針對C語言學習過程中普遍存在的重理論輕實踐、重語法輕編程的現象,通過貫穿全書的大量實例來介紹C語言編程的方法和技巧。全書分為三個部分: 第一部分介紹C語言的基礎性語法,包括標準程序框架、數據類型和控製結構; 第二部分介紹瞭常見的OJ(Online Judge)平颱、使用方法及OJ係統的基本輸入與輸齣的常見類型; 第三部分通過實例介紹瞭數組、函數和結構體編程過程中常用的知識點。
本書可以作為“C語言程序設計”課程的基礎教材,也可作為參加ACM/ICPC競賽的指導用書,並可作為各高校和相關培訓機構的教學參考書。
內頁插圖
目錄
第1章死記硬背
1.1引子
1.2死記硬背
1.2.1編程基本步驟
1.2.2記死
1.3初學者方法
第2章數據類型
2.1從A+B說起
2.2A+B繼續
2.3基本數據類型
2.3.1數據類型與“模子”
2.3.2常量
2.3.3變量
2.3.4強製類型轉換
2.4變量的命名規則
2.5拓展訓練
第3章數據的控製颱輸入與輸齣
3.1printf()函數和scanf()函數
3.1.1printf()函數
3.1.2scanf()函數
3.2getchar()函數與putchar()函數
3.2.1字符輸入函數getchar()
3.2.2字符輸齣函數: putchar()
3.3標準程序解讀
3.3.1頭文件
3.3.2函數
第4章控製結構
4.1從+1開始
4.2灌湯包
4.3順序結構
4.4分支結構
4.4.1if語句
4.4.2switch語句
4.5循環結構
4.5.1while語句
4.5.2do�瞱hile語句
4.5.3for語句
4.6continue語句和break語句
4.6.1continue語句
4.6.2break語句
4.7實例分析
第5章運算符和錶達式
5.1算術運算符
5.2邏輯運算符
5.2.1邏輯代數基礎
5.2.2邏輯運算符
5.3關係運算符
5.4位運算
5.4.1按位與運算
5.4.2按位或運算
5.4.3按位異或運算
5.4.4求反運算
5.4.5左移運算
5.4.6右移運算
5.5錶達式
5.5.1(算術)運算符的優先級與結閤性
5.5.2賦值運算符
5.5.3逗號運算符和逗號錶達式
5.5.4運算符優先級總結
5.6實例分析
第6章基本輸入與輸齣
6.1OJ係統簡介
6.2OJ係統使用說明
6.2.1OJ係統注冊
6.2.2常見評判結果
6.2.3簡單題
6.3基本輸入與輸齣
6.3.1基本輸入類型
6.3.2基本輸齣
6.4解題報告
第7章數組
7.1一維數組
7.1.1一維數組的定義
7.1.2一維數組元素的引用
7.1.3一維數組的初始化賦值
7.1.4實例分析
7.2二維數組
7.2.1二維數組的定義
7.2.2二維數組元素的引用
7.2.3二維數組的初始化賦值
7.2.4實例分析
7.3字符數組
7.3.1字符數組的定義
7.3.2字符數組的初始化
7.3.3字符數組的引用
7.3.4字符串和字符串結束標誌
7.3.5字符數組的輸入與輸齣
7.4動態數組
7.4.1為什麼引進動態數組
7.4.2動態數組的創建
7.5測試程序運行時間
7.6拓展訓練
第8章自定義函數
8.1為什麼要引入函數
8.1.1模塊化程序設計思想
8.1.2函數分類
8.1.3實例分析
8.2函數定義
8.2.1函數定義形式
8.2.2函數參數
8.2.3函數的返迴值
8.3函數調用
8.3.1函數調用形式
8.3.2函數聲明
8.3.3函數聲明和函數定義的區彆
第9章結構體
9.1引子
9.2結構體基本概念
9.2.1結構體類型的定義
9.2.2結構體變量的定義
9.2.3結構體變量占據的內存空間
9.2.4結構體變量對結構體成員的引用
9.2.5結構體變量的賦值
9.3結構體類型的數組
9.3.1結構體數組變量的定義
9.3.2結構體數組的引用
9.3.3結構體數組的初始化
附錄ADev C++安裝說明
附錄BDEV C++使用說明
附錄C常見錯誤信息中英語句索引
附錄D常用頭文件及包含的函數
附錄EC語言32個關鍵字和9種控製語句
參考文獻
前言/序言
C語言功能豐富、錶達能力強、使用靈活方便,20世紀90年代以來,C語言迅速在全世界普及推廣。C語言具有高級語言的優點又有低級語言的特性,既適閤編寫操作係統軟件,又能方便地開發領域應用軟件。目前,C語言程序設計已經成為最為廣泛的一門程序設計課程。依據基於世界範圍內的資深軟件工程師和第三方供應商提供作為指數的TIOBE開發語言排行榜(每月發布一次),C語言排名一直名列前茅。C語言是實踐性很強的一門課程,必須不斷地練習編程。在信息技術飛速發展的今天,如何將理論與實踐有機結閤,有效地推進素質教育和高水平人纔培養,是新時期IT人纔麵臨的新課題。
ACM國際大學生程序設計競賽(ACM International Collegiate Programming Contest,ACM/ICPC)是由美國計算機協會(Association for Computing Machinery,ACM)主辦,其目的是使大學生充分展示分析問題和運用計算機解決問題的能力。ACM/ICPC作為一項世界性的競賽活動,自1970年開始至今,是世界範圍內曆史最悠久、規模最大的程序設計競賽。正好迎閤瞭當今社會對創新性IT人纔的需求,競賽較全麵地考驗學生對知識的綜閤運用能力、創造性地分析解決問題能力,所以在IT界具有超凡的影響力。該項賽事極大地提高瞭參賽同學的學習熱情、實踐動手能力、團隊閤作能力和創造創新能力。ACM/ICPC在綫評判(Online Judge,OJ)係統是該項比賽的評判事務處理平颱,提供瞭一個基於B/S結構的多用戶在綫係統,允許用戶在綫提交自己的解題代碼,係統自動編譯運行給齣評判結果,並根據用戶解題數和用時綜閤排齣名次。
針對C語言學習過程中普遍存在的重理論輕實踐、重語法講解輕編程思想的現象,本書將“A+B”的示例程序貫穿全書,將ACM競賽平颱OJ係統用於C語言的教學講解和自學過程中。全書分為三個部分: 第一部分為C語言的基礎性語法,包括標準程序框架,數據類型和控製結構; 第二部分針對常見的OJ平颱、使用方法及OJ係統的基本輸入與輸齣等常見類型進行講解; 第三部分為數組、函數和結構體。
本書主要特點: ①所講解的程序框架是ACM/ICPC通用的標準框架; ②采用實例講解方法引齣理論; ③每個例程均已通過測試,確保能夠正確編譯並運行; ④詳細講解如何使用OJ係統進行編程實踐。
本書適用人群: ①大學本科一年級沒有學過C語言的學生; ②已學過或正在學C語言,但對已學內容不得要領的學生; ③有強烈參加ACM/ICPC競賽願望的學生; ④大學本科四年級考取研究生,復試階段需要上機復試C語言的學生; ⑤有強烈提高自己編程能力欲望,但苦於找不到閤適訓練方法和習題的讀者。
本書程序運行的操作係統為Windows 7,計算機硬件配置為Intel(R) Core(TM) i5 CPU M480 @2.67GHz,係統類型為64位操作係統。
本書作者是長期從事ACM/ICPC競賽指導和C語言教學的一綫教師,同時也一直緻力於C語言教學改革,近三年來所帶學生在計算機軟件類學科競賽中獲得省級以上奬勵三百餘人次。
在本書的編寫過程中,部分題目參考或改編自杭州電子科技大學和北京大學的在綫評判(OJ)係統,在此錶示感謝!
由於作者能力和水平所限,加之時間倉促,書中不足之處懇請廣大專傢、讀者批評指正!在C語言程序設計競賽相關書籍中,希望本書拋齣的“磚”能夠引齣更多的“玉”!
編著者2015年2月
C語言程序設計:零基礎ACM/ICPC競賽實戰指南 目錄 第一部分:C語言基礎篇 第一章:程序設計入門 1.1 什麼是程序設計? 程序設計的概念與發展 算法與程序的關係 計算機語言的種類與選擇 1.2 你的第一個C程序 搭建開發環境:安裝GCC編譯器 編寫、編譯與運行:Hello, World! 程序的基本構成:`include`, `main` 函數, `printf` 1.3 C語言的開發流程 源代碼、目標文件、可執行文件的概念 編譯、鏈接的過程解析 1.4 編程風格與規範 代碼可讀性的重要性 注釋的藝術:單行注釋與多行注釋 命名規範:變量、函數、常量 代碼縮進與排版 第二章:變量、數據類型與運算符 2.1 數據類型探秘 整型傢族:`int`, `short`, `long`, `long long`,以及 `unsigned` 浮點型傢族:`float`, `double`, `long double` 字符型:`char` 理解數據類型的存儲空間與取值範圍 類型轉換:隱式轉換與顯式轉換 2.2 變量的聲明與初始化 變量的本質:內存中的命名空間 聲明與初始化:讓變量“活”起來 局部變量與全局變量的作用域 2.3 運算符的魔力 算術運算符:`+`, `-`, ``, `/`, `%` 關係運算符:`>`, `<`, `>=`, `<=`, `==`, `!=` 邏輯運算符:`&&`, `||`, `!` 賦值運算符:`=`, `+=`, `-=`, `=`, `/=`, `%=` 自增與自減運算符:`++`, `--` 位運算符:`&`, `|`, `^`, `~`, `<<`, `>>` 條件運算符(三目運算符):`?:` 運算符的優先級與結閤性 第三章:流程控製結構 3.1 條件判斷:程序的“選擇” `if` 語句:單一條件判斷 `if-else` 語句:兩種情況的選擇 `if-else if-else` 語句:多重條件判斷 嵌套 `if` 語句:復雜的邏輯組閤 `switch-case` 語句:多分支選擇的優雅實現 3.2 循環迭代:程序的“重復” `while` 循環:先判斷後執行 `do-while` 循環:先執行後判斷 `for` 循環:計數循環的經典 循環的嵌套:構建復雜的重復模式 `break` 與 `continue`:跳齣與跳過循環 3.3 流程控製的藝術 如何根據問題選擇閤適的控製結構 避免死循環與不必要的計算 第四章:函數:模塊化編程的核心 4.1 函數的定義與聲明 函數的意義:代碼復用與模塊化 函數定義:實現功能 函數聲明(原型):告知編譯器函數的存在 返迴值類型與參數列錶 4.2 函數的調用與傳參 如何調用一個函數 值傳遞:函數內部對參數的修改不影響實參 理解函數調用棧 4.3 作用域與生命周期 局部變量與全局變量的生命周期 靜態變量 (`static`):變量的“記憶” 4.4 遞歸函數:自我調用的魅力 遞歸的定義:解決大規模問題,分解為小規模問題 遞歸的基石:終止條件 經典的遞歸問題:階乘、斐波那契數列 遞歸的優缺點與棧溢齣風險 第五章:數組:數據的有序集閤 5.1 一維數組 數組的定義與初始化 數組元素的訪問與修改 數組的遍曆 數組作為函數參數 5.2 多維數組 二維數組的定義與初始化 二維數組元素的訪問 二維數組的遍曆 多維數組作為函數參數 5.3 字符串:字符數組的特殊處理 C語言中字符串的錶示:以 ` ` 結尾的字符數組 字符串的輸入與輸齣:`scanf("%s", ...)` 與 `printf("%s", ...)` 常用的字符串處理函數:`strlen`, `strcpy`, `strcat`, `strcmp` (在``庫中) 第六章:指針:內存地址的操縱者 6.1 指針的概念與定義 指針變量:存儲內存地址的變量 地址運算符:`&` 解引用運算符:`` 6.2 指針與數組 數組名即首地址 指針算術:移動指針訪問數組元素 使用指針遍曆數組 6.3 指針與函數 指針作為函數參數:實現“引用傳遞” 函數返迴指針:需要注意內存管理 6.4 指針的進階 指嚮指針的指針 指嚮數組的指針 指嚮函數的指針 6.5 指針的注意事項 野指針:未初始化的指針 空指針:指嚮NULL的指針 懸掛指針:指嚮已被釋放內存的指針 第七章:結構體與共用體:自定義數據類型 7.1 結構體:組閤不同類型數據的容器 結構體的定義與聲明 結構體變量的定義與初始化 訪問結構體成員:`.` 運算符 結構體作為函數參數與返迴值 指嚮結構體的指針:`->` 運算符 `typedef`:為結構體定義彆名 7.2 共用體:節省內存的“共享”空間 共用體的定義與聲明 共用體變量的內存布局 共用體的應用場景 7.3 枚舉類型:命名一組整型常量 枚舉的定義與使用 第八章:文件操作:數據的持久化存儲 8.1 文件流的概念 文件與程序之間的數據傳輸 8.2 文件打開與關閉 `fopen()` 函數:以不同模式打開文件 文件模式:`"r"`, `"w"`, `"a"`, `"rb"`, `"wb"`, `"ab"` 等 `fclose()` 函數:關閉文件,釋放資源 8.3 文件讀寫操作 字符讀寫:`fgetc()`, `fputc()` 字符串讀寫:`fgets()`, `fputs()` 格式化讀寫:`fscanf()`, `fprintf()` 二進製讀寫:`fread()`, `fwrite()` 8.4 文件定位 `fseek()` 函數:移動文件指針 `ftell()` 函數:獲取當前文件指針位置 `rewind()` 函數:將文件指針移至文件開頭 第二部分:ACM/ICPC競賽進階篇 第九章:數據結構初步 9.1 綫性數據結構 順序錶(靜態數組實現): 優缺點分析,基本操作實現。 鏈錶: 單嚮鏈錶:節點定義,插入,刪除,查找,遍曆。 雙嚮鏈錶:節點定義,插入,刪除,查找,遍曆。 循環鏈錶:概念與應用。 棧: 棧的抽象數據類型(ADT)定義: LIFO(後進先齣)。 基於數組和鏈錶的實現。 基本操作:`push`, `pop`, `top`, `isEmpty`。 應用:錶達式求值,括號匹配。 隊列: 隊列的抽象數據類型(ADT)定義: FIFO(先進先齣)。 基於數組和鏈錶的實現。 基本操作:`enqueue`, `dequeue`, `front`, `isEmpty`。 應用:廣度優先搜索(BFS)。 9.2 非綫性數據結構 樹: 樹的基本概念:根節點,子節點,父節點,葉子節點,深度,高度。 二叉樹: 二叉樹的定義與性質。 遍曆方式:前序,中序,後序。 基於數組和鏈錶的實現。 應用:錶達式樹,搜索二叉樹。 圖: 圖的基本概念:頂點,邊,度,連通分量。 圖的錶示:鄰接矩陣,鄰接錶。 基本的圖遍曆算法: 深度優先搜索(DFS):遞歸與非遞歸實現,應用。 廣度優先搜索(BFS):隊列實現,應用。 第十章:算法設計基礎 10.1 算法復雜度分析 時間復雜度:大O錶示法,O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n) 等。 空間復雜度:大O錶示法。 如何分析算法的復雜度。 10.2 貪心算法 貪心算法的思想:局部最優推導全局最優。 典型問題:活動選擇問題,背包問題(部分),霍夫曼編碼。 判斷一個問題是否適閤使用貪心算法。 10.3 分治算法 分治算法的思想:分解,解決,閤並。 典型問題:歸並排序,快速排序,二分查找。 遞歸在分治算法中的應用。 10.4 動態規劃 動態規劃的思想:將大問題分解為子問題,記憶化搜索,避免重復計算。 狀態定義與狀態轉移方程。 典型問題:斐波那契數列(優化),背包問題(0/1背包),最長公共子序列,最長遞增子序列。 自底嚮上與自頂嚮下(記憶化搜索)兩種實現方式。 10.5 迴溯算法 迴溯算法的思想:深度優先搜索,剪枝。 當搜索到某個狀態時,如果發現當前路徑不可能得到最優解,則迴溯到上一步,嘗試其他路徑。 典型問題:N皇後問題,排列組閤問題,迷宮求解。 10.6 查找算法 順序查找 二分查找(前提:有序) 哈希查找(基本概念) 第十一章:數學在ACM/ICPC中的應用 11.1 數論基礎 整除與模運算: 概念,性質,擴展歐幾裏得算法(求解綫性同餘方程)。 素數: 判定素數(試除法),篩法(埃拉托色尼篩法)。 最大公約數 (GCD): 歐幾裏得算法。 最小公倍數 (LCM): GCD與LCM的關係。 同餘方程: 綫性同餘方程的求解。 模冪運算: 快速冪算法。 11.2 組閤數學 排列與組閤: 基本公式。 容斥原理: 解決包含“或”的關係的計數問題。 鴿巢原理: 證明存在性。 11.3 概率與期望 基本概率概念。 期望的綫性性質。 利用期望解決問題。 第十二章:ACM/ICPC競賽技巧與策略 12.1 理解題目 如何快速準確地讀懂題目要求。 注意題目中的陷阱和特殊情況。 分析題目的輸入輸齣格式。 12.2 編程實現 模塊化編程:將代碼拆分成函數。 代碼的可讀性與魯棒性。 調試技巧:利用 `printf` 調試,學會使用調試器。 12.3 優化與效率 選擇閤適的數據結構和算法。 減少不必要的計算。 注意常數因子和邊界條件。 12.4 常見的錯誤與陷阱 數組越界。 整數溢齣。 浮點數精度問題。 死循環。 內存泄露(雖然C語言需要手動管理,但競賽中通常題目不考察嚴格的內存管理)。 12.5 模擬題與實戰演練 分析往屆真題,瞭解題目難度和齣題風格。 進行模擬比賽,提高在壓力下的解題能力。 總結比賽經驗,分析失誤原因。 12.6 團隊協作(針對團隊賽) 溝通與協作的重要性。 分工與閤作。 附錄 C語言常用庫函數速查 ACM/ICPC常見算法列錶 參考資料推薦 --- 本指南旨在為C語言初學者提供堅實的編程基礎,並在此基礎上引導讀者逐步深入ACM/ICPC競賽所需的算法和數據結構知識。通過理論講解、代碼示例和習題練習,讀者將能夠掌握C語言的精髓,並逐步建立起解決算法競賽題目的思維模式和實踐能力。我們將從最基本的“Hello, World!”開始,一路探索變量、控製流、函數、指針、數組等核心概念,構建起紮實的C語言功底。 進階部分將專注於ACM/ICPC競賽的核心內容,深入講解各種重要的數據結構,如鏈錶、棧、隊列、樹和圖,以及掌握核心算法設計思想,包括貪心、分治、動態規劃和迴溯。同時,我們將梳理數論、組閤數學等與競賽密切相關的數學知識,並分享實用的競賽技巧和策略,幫助讀者在實戰中提升解題速度和準確率。 本書的目標是讓每一位對編程競賽充滿熱情的零基礎學習者,都能在掌握C語言的基礎上,一步步蛻變為能夠獨立思考、解決復雜算法問題的競賽選手。我們相信,通過係統的學習和大量的練習,你一定能在ACM/ICPC的賽場上大放異彩。