第1章-程序設(shè)計(jì)基礎(chǔ)-2015

1、程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)基礎(chǔ)（C C語言）語言）計(jì)算機(jī)學(xué)院高偉21-434 133516835472第第1 1章章 程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)基礎(chǔ) 1.1 程序設(shè)計(jì)概念 1.2 算法的概念及其表示 1.3 程序開發(fā)過程 1.4 C語言程序結(jié)構(gòu)及實(shí)例31.1 1.1 程序設(shè)計(jì)概念程序設(shè)計(jì)概念 計(jì)算機(jī)是用來延伸人的能力的工具，需要人來駕計(jì)算機(jī)是用來延伸人的能力的工具，需要人來駕馭馭 我們的職責(zé)是讓非計(jì)算機(jī)專業(yè)的人更容易駕馭它我們的職責(zé)是讓非計(jì)算機(jī)專業(yè)的人更容易駕馭它 完成這一目標(biāo)的主要手段之一就是完成這一目標(biāo)的主要手段之一就是“編程（ProgrammingProgramming）”什么是計(jì)算機(jī)？什么是計(jì)算機(jī)

2、？41.1 1.1 程序設(shè)計(jì)概念程序設(shè)計(jì)概念什么是什么是程序設(shè)計(jì)程序設(shè)計(jì)？n解決特定問題是程序設(shè)計(jì)的目的，程序設(shè)計(jì)的最終目的就是用程序來控制計(jì)算機(jī)來為人們解決特定的問題。程序設(shè)計(jì)一般包括以下幾個步驟：程序設(shè)計(jì)一般包括以下幾個步驟： （1）分析待解決的問題并建立相應(yīng)的數(shù)學(xué)模型； （2）確定數(shù)據(jù)結(jié)構(gòu)和算法。根據(jù)建立的數(shù)學(xué)模型，確定存放數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，針對所確定的數(shù)據(jù)結(jié)構(gòu)選擇合適的算法； （3）編程； （4）調(diào)試程序； （5）整理并寫出文檔資料。51.1 1.1 程序設(shè)計(jì)概念程序設(shè)計(jì)概念 人們要人們要利用利用計(jì)算機(jī)完成各種預(yù)定的工作，就必須把完成計(jì)算機(jī)完成各種預(yù)定的工作，就必須把完成該項(xiàng)工作所需要的

3、步驟編寫成計(jì)算機(jī)可以執(zhí)行的指令，該項(xiàng)工作所需要的步驟編寫成計(jì)算機(jī)可以執(zhí)行的指令，程序即是為實(shí)現(xiàn)特定目標(biāo)或解決特定問題而用計(jì)算機(jī)語即是為實(shí)現(xiàn)特定目標(biāo)或解決特定問題而用計(jì)算機(jī)語言編寫的指令序列的集合。言編寫的指令序列的集合。什么是什么是計(jì)計(jì)算機(jī)程序算機(jī)程序？61.1 1.1 程序設(shè)計(jì)概念程序設(shè)計(jì)概念 一個程序應(yīng)該包括兩方面的內(nèi)容：一個程序應(yīng)該包括兩方面的內(nèi)容： 對數(shù)據(jù)的描述，指定數(shù)據(jù)類型和組織形式指定數(shù)據(jù)類型和組織形式，即是數(shù)據(jù)即是數(shù)據(jù)結(jié)構(gòu)；結(jié)構(gòu)； 對操作步驟的描述，對操作步驟的描述即是算法對操作步驟的描述即是算法。正如著名計(jì)算機(jī)科學(xué)家沃思（正如著名計(jì)算機(jī)科學(xué)家沃思（Nikiklaus Wirth

4、Nikiklaus Wirth）提出的一）提出的一個公式：個公式：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) + + 算法算法 = = 程序程序什么是計(jì)什么是計(jì)算機(jī)程序算機(jī)程序？71.1 1.1 程序設(shè)計(jì)概念程序設(shè)計(jì)概念 程序設(shè)計(jì)語言的發(fā)展n機(jī)器語言編寫的1+1程序n匯編語言（Assemble Language）編寫的1+1程序101110000000000100000000000001010000000100000000MOV AX, 1ADD AX, 181.1 1.1 程序設(shè)計(jì)概念程序設(shè)計(jì)概念 程序設(shè)計(jì)語言的發(fā)展nBASIC語言編寫的1+1程序nC語言編寫的1+1程序PRINT 1+1#include main(

5、)main()printf(%dn, 1+1);91.1 1.1 程序設(shè)計(jì)概念程序設(shè)計(jì)概念 程序設(shè)計(jì)思想1結(jié)構(gòu)化程序設(shè)計(jì)思想模塊化結(jié)構(gòu)化程序設(shè)計(jì)的概念是E.W.Dijkstra在20世紀(jì)60年代末提出的，其實(shí)質(zhì)是控制編程中的復(fù)雜性。它的主要觀點(diǎn)是采用自頂向下、逐步求精的程序設(shè)計(jì)方法具體來說，采用以下方法確保得到結(jié)構(gòu)化的程序：（1）自頂向下（2）逐步求精（3）模塊化設(shè)計(jì)（4）結(jié)構(gòu)化編碼101.1 1.1 程序設(shè)計(jì)概念程序設(shè)計(jì)概念 程序設(shè)計(jì)思想1面向?qū)ο蟪绦蛟O(shè)計(jì)思想面向?qū)ο蟪绦蛟O(shè)計(jì)是面向過程設(shè)計(jì)方法的繼承和發(fā)展，是基于一種自然、樸素的思想來模擬人類思維習(xí)慣的程序設(shè)計(jì)方法。它具有抽象、封裝、繼承和多

6、態(tài)性等特征?？陀^世界是由各種各樣的對象組成的，每個對象都有自己的內(nèi)部狀態(tài)和運(yùn)動規(guī)律，不同對象間的相互聯(lián)系和相互作用構(gòu)成了各種不同的系統(tǒng)，進(jìn)而構(gòu)成整個客觀世界。C+語言是以C語言為基礎(chǔ)的一種面向?qū)ο蟮恼Z言，有著極為廣泛的應(yīng)用。111.2 1.2 算法的概念及表示算法的概念及表示 什么是算法1廣義上來說，任何解決問題的過程都是由一定的步驟組成的，這些解決問題確定的方法和有限的步驟都可以稱作算法。2. 常用計(jì)算機(jī)算法分為兩大類：數(shù)值運(yùn)算算法和非數(shù)值運(yùn)算算法。 數(shù)值運(yùn)算數(shù)值運(yùn)算是指求數(shù)值解，例如對微分方程求解、對函數(shù)的定積分求解等，都屬于數(shù)值運(yùn)算的范圍。 非數(shù)值運(yùn)算非數(shù)值運(yùn)算包括的范圍非常廣，如人事管

7、理、數(shù)據(jù)處理、資料檢索等。121.2 1.2 算法的概念及表示算法的概念及表示 算法的特征算法的特征（1）確定性（2）有窮性（3）有效性（4）輸入（5）輸出131.2 1.2 算法的概念及表示算法的概念及表示 算法的復(fù)雜性時間復(fù)雜性時間復(fù)雜性 算法的時間復(fù)雜性越高，則算法的執(zhí)行時間越長；時間復(fù)雜性越低，則執(zhí)行時間越短。空間復(fù)雜性空間復(fù)雜性 算法的空間復(fù)雜性越高，算法所需的存儲空間越多；空間復(fù)雜性越低，則所需的存儲空間越少。算法的復(fù)雜性分析中，對時間復(fù)雜性的分析考慮得更多。141.2 1.2 算法的概念及表示算法的概念及表示 常用算法簡介枚舉法枚舉法枚舉法又稱為窮舉法，將問題的所有可能的答案一一

8、列舉，然后根據(jù)條件判斷此答案是否合適，合適就為本題的一個答案，不合適就丟棄。若全部可能答案均不符合條件，則說明該題無答案。迭代法迭代法迭代法是一種不斷用變量的舊值遞推新值的過程，是一種數(shù)值近似求解的方法，迭代算法是用計(jì)算機(jī)解決問題的一種常見的方法。151.2 1.2 算法的概念及表示算法的概念及表示 常用算法簡介遞歸法和遞推法遞歸法和遞推法枚舉法遞推法是一種比較簡單的算法，通過已知條件，利用遞推公式，由簡到繁逐次迭代，直至得到結(jié)果的算法。遞推法的關(guān)鍵是找到進(jìn)行遞推的通項(xiàng)公式。遞歸法也是利用遞推公式，但不同的是，它是由繁化簡，用簡單的問題和已知的操作運(yùn)算來解決復(fù)雜的問題。分治法分治法分治法就是把

9、一個復(fù)雜的問題分解成兩個或更多的相同或相似的子問題，再把子問題分成更加小的子問題，直到最后子問題可以簡單直接的求解，最后再把子問題的解合并，就組合成原問題的解。161.2 1.2 算法的概念及表示算法的概念及表示 算法的表示用自然語言表示算法用自然語言表示算法例例1.3輸入輸入3個數(shù)，輸出最小的數(shù)。個數(shù)，輸出最小的數(shù)。首先定義首先定義3個變量個變量x、y、z，將，將3個數(shù)依次輸入到個數(shù)依次輸入到x、y、z中，再定義一個變中，再定義一個變量量MIN，存放最小數(shù)。算法步驟如下：，存放最小數(shù)。算法步驟如下：（1）輸入）輸入x，y，z。（2）若）若xy，則，則xMIN，否則，否則yMIN。（3）若）若

10、zy 輸出輸出xelse 輸出輸出y結(jié)束結(jié)束181.2 1.2 算法的概念及表示算法的概念及表示用流程圖表示算法用流程圖表示算法; ;規(guī)則：從上到下，從左到右。規(guī)則：從上到下，從左到右。符號及其意義：符號及其意義：起止框起止框流程線流程線連接點(diǎn)連接點(diǎn)處理框處理框判斷框判斷框I/OI/O框框191.2 1.2 算法的概念及表示算法的概念及表示 算法的表示流程圖表示舉例流程圖表示舉例 用框圖描述函數(shù)用框圖描述函數(shù) 1 x 1 x 0 0 y = y = -1 x 0 -1 x 0startstart輸入輸入x xA Ax x 0?0?y=1y=1y=-1y=-1yesyesnonoA A輸出輸出y

11、 yendend201.2 1.2 算法的概念及表示算法的概念及表示211.2 1.2 算法的概念及表示算法的概念及表示 算法的表示N-SN-S流程圖表示算法流程圖表示算法ABC順序結(jié)構(gòu)順序結(jié)構(gòu)分支結(jié)構(gòu)分支結(jié)構(gòu)條件條件成立成立不成立不成立A AB B循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)（條件在前（條件在前/ /條件在后）條件在后）當(dāng)條件成立A 直到條件成立A當(dāng)型循環(huán)當(dāng)型循環(huán) 直到型循環(huán)直到型循環(huán)231.3 1.3 程序的開發(fā)過程程序的開發(fā)過程程序的編寫過程程序的編寫過程開始開始編輯編輯編譯編譯語法錯？語法錯？yesno連接、運(yùn)行連接、運(yùn)行 邏輯錯？邏輯錯？yesnoAA完成完成n編輯（編輯（EditEdit）擴(kuò)展

12、名為.c.c的文件 n編譯（編譯（CompileCompile）擴(kuò)展名為. .objobj的文件 n鏈接（鏈接（LinkLink）形成最后的可執(zhí)行文件擴(kuò)展名為.exe.exe的文件 n運(yùn)行運(yùn)行 （RunRun）241.4 C1.4 C語言程序結(jié)構(gòu)及實(shí)例語言程序結(jié)構(gòu)及實(shí)例 C C語言是當(dāng)今世界上最為流行的計(jì)算機(jī)高級語言之一，語言是當(dāng)今世界上最為流行的計(jì)算機(jī)高級語言之一，它是它是19721972年由美國的年由美國的Dennis RitchieDennis Ritchie設(shè)計(jì)發(fā)明的設(shè)計(jì)發(fā)明的, ,并首并首次在次在UNIXUNIX操作系統(tǒng)的操作系統(tǒng)的 DEC PDP-11 DEC PDP-11 計(jì)算機(jī)

13、上使用。計(jì)算機(jī)上使用。C語言的設(shè)計(jì)者Dennis M. Ritchie和和Unix的設(shè)計(jì)者的設(shè)計(jì)者Ken Thompson接受美國國家技術(shù)勛章接受美國國家技術(shù)勛章1.4 C1.4 C語言程序結(jié)構(gòu)及實(shí)例語言程序結(jié)構(gòu)及實(shí)例 目前最流行的目前最流行的C語言版本有以下幾種：語言版本有以下幾種：Microsoft C或稱或稱MSC Borland Turbo C或稱Turbo C AT&T C 這些這些C語言版本不僅實(shí)現(xiàn)了語言版本不僅實(shí)現(xiàn)了ANSI C標(biāo)準(zhǔn)，而且在標(biāo)準(zhǔn)，而且在此基礎(chǔ)上各自作了一些擴(kuò)充，使之更加方便、此基礎(chǔ)上各自作了一些擴(kuò)充，使之更加方便、完美。完美。25 C 語言的特點(diǎn)（1）語言

14、簡潔、結(jié)構(gòu)緊湊，程序書寫方便，實(shí)用靈活。 （2）C語言是結(jié)構(gòu)化的程序設(shè)計(jì)語言。（3）C語言提供了豐富的運(yùn)算符。（4）C語言具有豐富的數(shù)據(jù)類型。（5）C語言可以直接對硬件進(jìn)行操作。（6）與匯編語言相比，用C語言寫的程序可移植性好。（7）C語言對語法的限制不太嚴(yán)格、程序設(shè)計(jì)自由度大，并且C語言程序生成代碼質(zhì)量高，程序執(zhí)行效率高。1.4 C1.4 C語言程序結(jié)構(gòu)及實(shí)例語言程序結(jié)構(gòu)及實(shí)例例例1在在DOS屏幕上輸出屏幕上輸出This is a C program.程序如下程序如下:void main() printf(“This is a C program.”); /函數(shù)體函數(shù)體該程序的功能是：該程序

15、的功能是：執(zhí)行該程序，將在屏幕上輸出一行信息執(zhí)行該程序，將在屏幕上輸出一行信息: This is a C program .27 程序結(jié)構(gòu)說明：1每個C語言程序都是由若干個函數(shù)組成的，其中至少應(yīng)該包括一個主函數(shù)main()： main() 主函數(shù)的名稱是main，在C語言中是固定的，不能被改變。它后面的被稱為函數(shù)體，由一條一條的語句組成。函數(shù)中所有的語句都寫在之內(nèi)。2函數(shù)是由語句組成的，例1.6程序的主函數(shù)中只包含一個語句：printf(This is a C program.);printf是一個函數(shù)名稱，它的功能是將括號中的參數(shù)(用雙引號括起來的一串字符)原樣輸出到計(jì)算機(jī)的DOS屏幕上，參

16、數(shù)要放在括號中。在C語言中printf被稱為格式化輸出函數(shù)。3每個語句后面要加上分號。4函數(shù)中也可以不包含語句，這就是空函數(shù)。1.4 C1.4 C語言程序結(jié)構(gòu)及實(shí)例語言程序結(jié)構(gòu)及實(shí)例30 例例2 2 輸入兩個數(shù)及其運(yùn)算關(guān)系，輸出運(yùn)算結(jié)果。輸入兩個數(shù)及其運(yùn)算關(guān)系，輸出運(yùn)算結(jié)果。 #include void main(void) char ch; int a, b; int c; scanf(“%d%c%d”,&a,&ch,&b); c=fun(a,ch,b); printf(“a%cb=%d”,ch,c);int fun(int x,char op,int y) int

17、z; switch(op) case +: z=x+y; break; case - : z=x-y; break; case *: z=x*y; break; case / : z=x/y; break; return z;子函數(shù) 程序是由函數(shù)組成的，函數(shù)是由語句組成的。其中主函數(shù)有且唯一，主函數(shù)名位main。子函數(shù)可有可無也可以有多個。語言的系統(tǒng)構(gòu)詞必須用小寫，用戶構(gòu)詞可以大小寫混用。 C語言的語句用；作為結(jié)束，因此一句可以用一行或幾行書寫，但不能割裂構(gòu)詞。各詞之間用一個或幾個space分隔。1.4 C1.4 C語言程序結(jié)構(gòu)及實(shí)例語言程序結(jié)構(gòu)及實(shí)例31 標(biāo)識符和關(guān)鍵字 C語言的字符集字母：

18、A、a、B、b、Z、z 52個數(shù)字符號：0、1、9 10個特殊符號：+ - * / 20個 關(guān)鍵字（又稱保留字 ）系統(tǒng)占用詞（共32個）auto、break、case、char、const、continue、default、do、double、else、enum、extern、float、for、goto、if、int、long、register、return、short、signed、sizeof、static、struct、switch、typedef、union、unsigned、void、volatile、while建議不要使用：define、undef、include、ifdef、ifndef、endif、line、error、elif、pragma1.4 C1.4 C語言程序結(jié)構(gòu)及實(shí)例語言程序結(jié)構(gòu)及實(shí)例32 標(biāo)識符和關(guān)鍵字 標(biāo)識符組成規(guī)則： 字母和數(shù)字以及 下劃線_ 組