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

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

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

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

4、Nikiklaus Wirth）提出的一）提出的一個(gè)公式：個(gè)公式：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) + + 算法算法 = = 程序程序什么是計(jì)什么是計(jì)算機(jī)程序算機(jī)程序？71.1 1.1 程序設(shè)計(jì)概念程序設(shè)計(jì)概念 程序設(shè)計(jì)語(yǔ)言的發(fā)展n機(jī)器語(yǔ)言編寫(xiě)的1+1程序n匯編語(yǔ)言（Assemble Language）編寫(xiě)的1+1程序101110000000000100000000000001010000000100000000MOV AX, 1ADD AX, 181.1 1.1 程序設(shè)計(jì)概念程序設(shè)計(jì)概念 程序設(shè)計(jì)語(yǔ)言的發(fā)展nBASIC語(yǔ)言編寫(xiě)的1+1程序nC語(yǔ)言編寫(xiě)的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ì)方法具體來(lái)說(shuō)，采用以下方法確保得到結(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ì)是面向過(guò)程設(shè)計(jì)方法的繼承和發(fā)展，是基于一種自然、樸素的思想來(lái)模擬人類(lèi)思維習(xí)慣的程序設(shè)計(jì)方法。它具有抽象、封裝、繼承和多

6、態(tài)性等特征?？陀^世界是由各種各樣的對(duì)象組成的，每個(gè)對(duì)象都有自己的內(nèi)部狀態(tài)和運(yùn)動(dòng)規(guī)律，不同對(duì)象間的相互聯(lián)系和相互作用構(gòu)成了各種不同的系統(tǒng)，進(jìn)而構(gòu)成整個(gè)客觀世界。C+語(yǔ)言是以C語(yǔ)言為基礎(chǔ)的一種面向?qū)ο蟮恼Z(yǔ)言，有著極為廣泛的應(yīng)用。111.2 1.2 算法的概念及表示算法的概念及表示 什么是算法1廣義上來(lái)說(shuō)，任何解決問(wèn)題的過(guò)程都是由一定的步驟組成的，這些解決問(wèn)題確定的方法和有限的步驟都可以稱(chēng)作算法。2. 常用計(jì)算機(jī)算法分為兩大類(lèi)：數(shù)值運(yùn)算算法和非數(shù)值運(yùn)算算法。 數(shù)值運(yùn)算數(shù)值運(yùn)算是指求數(shù)值解，例如對(duì)微分方程求解、對(duì)函數(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ù)雜性時(shí)間復(fù)雜性時(shí)間復(fù)雜性 算法的時(shí)間復(fù)雜性越高，則算法的執(zhí)行時(shí)間越長(zhǎng)；時(shí)間復(fù)雜性越低，則執(zhí)行時(shí)間越短?？臻g復(fù)雜性空間復(fù)雜性 算法的空間復(fù)雜性越高，算法所需的存儲(chǔ)空間越多；空間復(fù)雜性越低，則所需的存儲(chǔ)空間越少。算法的復(fù)雜性分析中，對(duì)時(shí)間復(fù)雜性的分析考慮得更多。141.2 1.2 算法的概念及表示算法的概念及表示 常用算法簡(jiǎn)介枚舉法枚舉法枚舉法又稱(chēng)為窮舉法，將問(wèn)題的所有可能的答案一一

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

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

10、zy 輸出輸出xelse 輸出輸出y結(jié)束結(jié)束181.2 1.2 算法的概念及表示算法的概念及表示用流程圖表示算法用流程圖表示算法; ;規(guī)則：從上到下，從左到右。規(guī)則：從上到下，從左到右。符號(hào)及其意義：符號(hào)及其意義：起止框起止框流程線流程線連接點(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 程序的開(kāi)發(fā)過(guò)程程序的開(kāi)發(fā)過(guò)程程序的編寫(xiě)過(guò)程程序的編寫(xiě)過(guò)程開(kāi)始開(kāi)始編輯編輯編譯編譯語(yǔ)法錯(cuò)？語(yǔ)法錯(cuò)？yesno連接、運(yùn)行連接、運(yùn)行 邏輯錯(cuò)？邏輯錯(cuò)？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語(yǔ)言程序結(jié)構(gòu)及實(shí)例語(yǔ)言程序結(jié)構(gòu)及實(shí)例 C C語(yǔ)言是當(dāng)今世界上最為流行的計(jì)算機(jī)高級(jí)語(yǔ)言之一，語(yǔ)言是當(dāng)今世界上最為流行的計(jì)算機(jī)高級(jí)語(yǔ)言之一，它是它是19721972年由美國(guó)的年由美國(guó)的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語(yǔ)言的設(shè)計(jì)者Dennis M. Ritchie和和Unix的設(shè)計(jì)者的設(shè)計(jì)者Ken Thompson接受美國(guó)國(guó)家技術(shù)勛章接受美國(guó)國(guó)家技術(shù)勛章1.4 C1.4 C語(yǔ)言程序結(jié)構(gòu)及實(shí)例語(yǔ)言程序結(jié)構(gòu)及實(shí)例 目前最流行的目前最流行的C語(yǔ)言版本有以下幾種：語(yǔ)言版本有以下幾種：Microsoft C或稱(chēng)或稱(chēng)MSC Borland Turbo C或稱(chēng)Turbo C AT&T C 這些這些C語(yǔ)言版本不僅實(shí)現(xiàn)了語(yǔ)言版本不僅實(shí)現(xiàn)了ANSI C標(biāo)準(zhǔn)，而且在標(biāo)準(zhǔn)，而且在此基礎(chǔ)上各自作了一些擴(kuò)充，使之更加方便、此基礎(chǔ)上各自作了一些擴(kuò)充，使之更加方便、完美。完美。25 C 語(yǔ)言的特點(diǎn)（1）語(yǔ)言

14、簡(jiǎn)潔、結(jié)構(gòu)緊湊，程序書(shū)寫(xiě)方便，實(shí)用靈活。 （2）C語(yǔ)言是結(jié)構(gòu)化的程序設(shè)計(jì)語(yǔ)言。（3）C語(yǔ)言提供了豐富的運(yùn)算符。（4）C語(yǔ)言具有豐富的數(shù)據(jù)類(lèi)型。（5）C語(yǔ)言可以直接對(duì)硬件進(jìn)行操作。（6）與匯編語(yǔ)言相比，用C語(yǔ)言寫(xiě)的程序可移植性好。（7）C語(yǔ)言對(duì)語(yǔ)法的限制不太嚴(yán)格、程序設(shè)計(jì)自由度大，并且C語(yǔ)言程序生成代碼質(zhì)量高，程序執(zhí)行效率高。1.4 C1.4 C語(yǔ)言程序結(jié)構(gòu)及實(shí)例語(yǔ)言程序結(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)說(shuō)明：1每個(gè)C語(yǔ)言程序都是由若干個(gè)函數(shù)組成的，其中至少應(yīng)該包括一個(gè)主函數(shù)main()： main() 主函數(shù)的名稱(chēng)是main，在C語(yǔ)言中是固定的，不能被改變。它后面的被稱(chēng)為函數(shù)體，由一條一條的語(yǔ)句組成。函數(shù)中所有的語(yǔ)句都寫(xiě)在之內(nèi)。2函數(shù)是由語(yǔ)句組成的，例1.6程序的主函數(shù)中只包含一個(gè)語(yǔ)句：printf(This is a C program.);printf是一個(gè)函數(shù)名稱(chēng)，它的功能是將括號(hào)中的參數(shù)(用雙引號(hào)括起來(lái)的一串字符)原樣輸出到計(jì)算機(jī)的DOS屏幕上，參

16、數(shù)要放在括號(hào)中。在C語(yǔ)言中printf被稱(chēng)為格式化輸出函數(shù)。3每個(gè)語(yǔ)句后面要加上分號(hào)。4函數(shù)中也可以不包含語(yǔ)句，這就是空函數(shù)。1.4 C1.4 C語(yǔ)言程序結(jié)構(gòu)及實(shí)例語(yǔ)言程序結(jié)構(gòu)及實(shí)例30 例例2 2 輸入兩個(gè)數(shù)及其運(yùn)算關(guān)系，輸出運(yùn)算結(jié)果。輸入兩個(gè)數(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ù)是由語(yǔ)句組成的。其中主函數(shù)有且唯一，主函數(shù)名位main。子函數(shù)可有可無(wú)也可以有多個(gè)。語(yǔ)言的系統(tǒng)構(gòu)詞必須用小寫(xiě)，用戶構(gòu)詞可以大小寫(xiě)混用。 C語(yǔ)言的語(yǔ)句用；作為結(jié)束，因此一句可以用一行或幾行書(shū)寫(xiě)，但不能割裂構(gòu)詞。各詞之間用一個(gè)或幾個(gè)space分隔。1.4 C1.4 C語(yǔ)言程序結(jié)構(gòu)及實(shí)例語(yǔ)言程序結(jié)構(gòu)及實(shí)例31 標(biāo)識(shí)符和關(guān)鍵字 C語(yǔ)言的字符集字母：

18、A、a、B、b、Z、z 52個(gè)數(shù)字符號(hào)：0、1、9 10個(gè)特殊符號(hào)：+ - * / 20個(gè) 關(guān)鍵字（又稱(chēng)保留字 ）系統(tǒng)占用詞（共32個(gè)）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語(yǔ)言程序結(jié)構(gòu)及實(shí)例語(yǔ)言程序結(jié)構(gòu)及實(shí)例32 標(biāo)識(shí)符和關(guān)鍵字 標(biāo)識(shí)符組成規(guī)則： 字母和數(shù)字以及 下劃線_ 組