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

程序設(shè)計(jì)基礎(chǔ)

（C語言）劉杰教授計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2第1章

程序設(shè)計(jì)基礎(chǔ)1.1程序設(shè)計(jì)概念1.2算法的概念及其表示1.3程序編寫過程1.4C語言程序結(jié)構(gòu)及實(shí)例31.1程序設(shè)計(jì)概念什么是程序設(shè)計(jì)？解決特定問題是程序設(shè)計(jì)的目的，程序設(shè)計(jì)的最終目的就是用程序來控制計(jì)算機(jī)來為人們解決特定的問題。程序設(shè)計(jì)一般包括以下幾個(gè)步驟：

（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）整理并寫出文檔資料。41.1程序設(shè)計(jì)概念人們要利用計(jì)算機(jī)完成各種預(yù)定的工作，就必須把完成該項(xiàng)工作所需要的步驟編寫成計(jì)算機(jī)可以執(zhí)行的指令，程序即是為實(shí)現(xiàn)特定目標(biāo)或解決特定問題而用計(jì)算機(jī)語言編寫的指令序列的集合。什么是計(jì)算機(jī)程序？51.1程序設(shè)計(jì)概念一個(gè)程序應(yīng)該包括兩方面的內(nèi)容：

對數(shù)據(jù)的描述，指定數(shù)據(jù)類型和組織形式，即是數(shù)據(jù)結(jié)構(gòu)；對操作步驟的描述即是算法。正如著名計(jì)算機(jī)科學(xué)家沃思（NikiklausWirth）提出的一個(gè)公式：

數(shù)據(jù)結(jié)構(gòu)+算法=程序什么是計(jì)算機(jī)程序？61.1程序設(shè)計(jì)概念計(jì)算機(jī)基本工作過程輸入/輸出設(shè)備存儲(chǔ)器運(yùn)算器控制器源程序和輸入數(shù)據(jù)輸出結(jié)果取出數(shù)據(jù)存入數(shù)據(jù)操作命令存取命令取出程序指令輸入輸出命令計(jì)算結(jié)果CPU“馮·諾依曼機(jī)”結(jié)構(gòu)大腦記憶裝置眼睛和耳朵軟件的形成與運(yùn)行過程的簡單描述軟件的形成程序員（Programmer）編寫程序源代碼（SourceCode）編譯器（Compiler）把源代碼轉(zhuǎn)換為可被計(jì)算機(jī)理解的機(jī)器代碼（MachineCode）并把機(jī)器代碼以可執(zhí)行文件（ExecutableFile）的形式保存在磁盤上軟件的運(yùn)行計(jì)算機(jī)把機(jī)器代碼讀入到內(nèi)存(Memory)由CPU運(yùn)行這些代碼讀取輸入（Input）產(chǎn)生輸出（Output）完成程序員預(yù)定的功能程序和數(shù)據(jù)硬盤CPU內(nèi)存執(zhí)行結(jié)果程序設(shè)計(jì)語言的工作原理編譯運(yùn)行編輯、編譯、鏈接和運(yùn)行解釋運(yùn)行程序員編寫程序源代碼解釋器讀入源代碼，并執(zhí)行源代碼解釋運(yùn)行的語言特點(diǎn)執(zhí)行速度慢好學(xué)易用先編譯、后解釋把源代碼編譯成更容易解釋的中間代碼，然后再解釋運(yùn)行程序設(shè)計(jì)語言的故事程序設(shè)計(jì)語言（ProgrammingLanguage）是人與計(jì)算機(jī)進(jìn)行交流的語言。計(jì)算機(jī)直接能讀懂的語言。機(jī)器語言（MachineCode），也叫機(jī)器代碼一種純粹的二進(jìn)制語言一種程序設(shè)計(jì)語言對應(yīng)一種編譯器。程序員按照該語言的語法編寫程序源代碼，把自己的意圖融入到代碼中。編譯器讀入源代碼，把程序員的意圖轉(zhuǎn)換成可執(zhí)行程序，供他人使用。用各種語言編寫的1+1程序機(jī)器語言編寫的1+1程序101110000000000100000000000001010000000100000000匯編語言編寫的1+1程序MOVAX,1ADDAX,1BASIC語言編寫的1+1程序PRINT1+1C語言編寫的1+1程序#include<stdio.h>main(){

printf("%d\n",1+1);}程序設(shè)計(jì)語言的發(fā)展機(jī)器語言匯編語言高級(jí)語言面向過程面向?qū)ο驝PU指令系統(tǒng)，由0、1序列構(gòu)成的指令碼組成如：10000000加

10010000減用助記符號(hào)描述的指令系統(tǒng)如ADDA,B面向機(jī)器的語言程序設(shè)計(jì)是數(shù)據(jù)被加工的過程客觀世界可以分類，對象是類的實(shí)例對象是數(shù)據(jù)和方法的封裝對象間通過發(fā)送和接受消息發(fā)生聯(lián)系程序設(shè)計(jì)關(guān)鍵是定義類，并由類派生對象程序設(shè)計(jì)語言的發(fā)展5254565860626466687072747678808284868890929496AdaALGOL60ALGOL68PascalModula-2CPLBCPLBCC++JavaLISPPROLOGCOBOLFORTRAN77FORTRANPL/1Simula67Smalltalk80BASICANSI-BASICQBASICVBFORTRAN90131.1程序設(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)化編碼141.1程序設(shè)計(jì)概念程序設(shè)計(jì)思想2．面向?qū)ο蟪绦蛟O(shè)計(jì)思想面向?qū)ο蟪绦蛟O(shè)計(jì)是面向過程設(shè)計(jì)方法的繼承和發(fā)展，是基于一種自然、樸素的思想來模擬人類思維習(xí)慣的程序設(shè)計(jì)方法。它具有抽象、封裝、繼承和多態(tài)性等特征。客觀世界是由各種各樣的對象組成的，每個(gè)對象都有自己的內(nèi)部狀態(tài)和運(yùn)動(dòng)規(guī)律，不同對象間的相互聯(lián)系和相互作用構(gòu)成了各種不同的系統(tǒng)，進(jìn)而構(gòu)成整個(gè)客觀世界。C++語言是以C語言為基礎(chǔ)的一種面向?qū)ο蟮恼Z言，有著極為廣泛的應(yīng)用。151.2算法的概念及表示什么是算法1．廣義上來說，任何解決問題的過程都是由一定的步驟組成的，這些解決問題確定的方法和有限的步驟都可以稱作算法。2.常計(jì)算機(jī)算法分為兩大類：數(shù)值運(yùn)算算法和非數(shù)值運(yùn)算算法。

數(shù)值運(yùn)算是指求數(shù)值解，例如對微分方程求解、對函數(shù)的定積分求解等，都屬于數(shù)值運(yùn)算的范圍。

非數(shù)值運(yùn)算包括的范圍非常廣，如人事管理、數(shù)據(jù)處理、資料檢索等。161.2算法的概念及表示算法的特征（1）確定性（2）有窮性（3）有效性（4）輸入（5）輸出171.2算法的概念及表示算法的復(fù)雜性時(shí)間復(fù)雜性

算法的時(shí)間復(fù)雜性越高，則算法的執(zhí)行時(shí)間越長；時(shí)間復(fù)雜性越低，則執(zhí)行時(shí)間越短?？臻g復(fù)雜性

算法的空間復(fù)雜性越高，算法所需的存儲(chǔ)空間越多；空間復(fù)雜性越低，則所需的存儲(chǔ)空間越少。算法的復(fù)雜性分析中，對時(shí)間復(fù)雜性的分析考慮得更多。181.2算法的概念及表示常用算法簡介枚舉法枚舉法又稱為窮舉法，將問題的所有可能的答案一一列舉，然后根據(jù)條件判斷此答案是否合適，合適就為本題的一個(gè)答案，不合適就丟棄。若全部可能答案均不符合條件，則說明該題無答案。迭代法迭代法是一種不斷用變量的舊值遞推新值的過程，是一種數(shù)值近似求解的方法，迭代算法是用計(jì)算機(jī)解決問題的一種常見的方法。191.2算法的概念及表示枚舉法舉例例1.1

百雞問題，我國古代數(shù)學(xué)家張丘建在他所撰寫的《算經(jīng)》中，提出了這樣的一個(gè)問題：“雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一。百錢買百雞，問雞翁、母、雛各幾只？”令x、y、z分別為公雞數(shù)、母雞數(shù)、小雞數(shù)，根據(jù)題意可得以下約束方程：x+y+z=1005x+3y+z/3=100由題意得x、y、z均為0到100之間的正整數(shù)，所以按照枚舉法解題的基本思路，將x、y、z的所有可能取值一一代入，逐一驗(yàn)證，若滿足約束條件，即為一組解，直至得到全部的解。201.2算法的概念及表示常用算法簡介遞歸法和遞推法枚舉法遞推法是一種比較簡單的算法，通過已知條件，利用遞推公式，由簡到繁逐次迭代，直至得到結(jié)果的算法。遞推法的關(guān)鍵是找到進(jìn)行遞推的通項(xiàng)公式。遞歸法也是利用遞推公式，但不同的是，它是由繁化簡，用簡單的問題和已知的操作運(yùn)算來解決復(fù)雜的問題。分治法分治法就是把一個(gè)復(fù)雜的問題分解成兩個(gè)或更多的相同或相似的子問題，再把子問題分成更加小的子問題，直到最后子問題可以簡單直接的求解，最后再把子問題的解合并，就組合成原問題的解。211.2算法的概念及表示算法的表示用自然語言表示算法例1.3輸入3個(gè)數(shù)，輸出最小的數(shù)。首先定義3個(gè)變量x、y、z，將3個(gè)數(shù)依次輸入到x、y、z中，再定義一個(gè)變量MIN，存放最小數(shù)。算法步驟如下：（1）輸入x，y，z。（2）若x<y，則x→MIN，否則y→MIN。（3）若z<MIN，則z→MIN。221.2算法的概念及表示用偽代碼表示算法例1.4輸入兩個(gè)數(shù)x、y，輸出最大的數(shù)。開始輸入x、yifx>y輸出xelse輸出y結(jié)束231.2算法的概念及表示用偽代碼表示算法例1.5求1×2×3×4×5×6=？用偽代碼表示如下：開始置t的初值為1置i的初值為2當(dāng)i<=6，重復(fù)執(zhí)行下面的操作：使t=t×i使i=i+1(循環(huán)體到此結(jié)束)打印t的值結(jié)束241.2算法的概念及表示用流程圖表示算法;規(guī)則：從上到下，從左到右。符號(hào)及其意義：起止框流程線連接點(diǎn)處理框判斷框I/O框251.2算法的概念及表示算法的表示流程圖表示舉例

用框圖描述函數(shù)

1x0y=-1x<0start輸入xAx0?y=1y=-1yesnoA輸出yend261.2算法的概念及表示271.2算法的概念及表示算法的表示N-S流程圖表示算法ABC順序結(jié)構(gòu)分支結(jié)構(gòu)條件成立不成立AB循環(huán)結(jié)構(gòu)（條件在前/條件在后）當(dāng)條件成立A

直到條件成立A當(dāng)型循環(huán)直到型循環(huán)291.3程序的開發(fā)過程⑴系統(tǒng)描述⑵需求分析描述系統(tǒng)功能⑶結(jié)構(gòu)分析分析設(shè)計(jì)，算法描述⑷詳細(xì)設(shè)計(jì)編碼⑸代碼調(diào)試⑹單元測試調(diào)試⑺系統(tǒng)測試⑻運(yùn)行維護(hù)301.3程序的開發(fā)過程上機(jī)過程開始編輯編譯語法錯(cuò)？yesno連接、運(yùn)行邏輯錯(cuò)？yesnoAA完成編輯（Edit）擴(kuò)展名為.c的文件編譯（Compile）擴(kuò)展名為.obj的文件鏈接（Link）形成最后的可執(zhí)行文件擴(kuò)展名為.exe的文件運(yùn)行（Run）311.3程序的開發(fā)過程圖1.16

C程序開發(fā)步驟執(zhí)行連接編譯編輯用戶C源程序目標(biāo)文件可執(zhí)行程序結(jié)果其他目標(biāo)文件C庫函數(shù)321.4C語言程序結(jié)構(gòu)及實(shí)例C語言是當(dāng)今世界上最為流行的計(jì)算機(jī)高級(jí)語言之一，它是1972年由美國的DennisRitchie設(shè)計(jì)發(fā)明的,并首次在UNIX操作系統(tǒng)的DECPDP-11計(jì)算機(jī)上使用。C語言的設(shè)計(jì)者

DennisM.Ritchie和Unix的設(shè)計(jì)者KenThompson

接受美國國家技術(shù)勛章C語言的發(fā)展過程產(chǎn)生背景產(chǎn)生過程BCPL語言進(jìn)化成B語言，B語言又進(jìn)化為C語言。時(shí)間：1972~1973地點(diǎn)：美國貝爾實(shí)驗(yàn)室目的：UNIX操作系統(tǒng)設(shè)計(jì)人:：Ken.Thompson和Dennis.M.RitchieC標(biāo)準(zhǔn)標(biāo)準(zhǔn)C：K&R合著《TheCProgrammingLanguage》ANSIC：1983年

87ANSIC：1987年

1990年國際標(biāo)準(zhǔn)的ANSICC語言的地盤硬件（Hardware）操作系統(tǒng)（OS）應(yīng)用程序

（Application）應(yīng)用

平臺(tái)基于

平臺(tái)的

應(yīng)用

程序低級(jí)語言的地盤高級(jí)語言的地盤C語言的地盤1.4C語言程序結(jié)構(gòu)及實(shí)例目前最流行的C語言版本有以下幾種：

?MicrosoftC或稱MSC

?BorlandTurboC或稱TurboC

?AT&TC這些C語言版本不僅實(shí)現(xiàn)了ANSIC標(biāo)準(zhǔn)，而且在此基礎(chǔ)上各自作了一些擴(kuò)充，使之更加方便、完美。351.4C語言程序結(jié)構(gòu)及實(shí)例例1.6在DOS屏幕上輸出ThisisaCprogram.

程序如下: voidmain() { printf(“ThisisaCprogram.”);//函數(shù)體 }

該程序的功能是：

執(zhí)行該程序，將在屏幕上輸出一行信息:ThisisaCprogram

.361.4C語言程序結(jié)構(gòu)及實(shí)例例1.7編程從鍵盤輸入兩個(gè)整數(shù)，輸出它們的和.

程序如下: voidmain(){inta,b,c;scanf("%d%d",&a,&b);c=a+b;

printf("\na+b=%d",c);

}37執(zhí)行程序，輸入：36輸出： a+b=9再次執(zhí)行程序，輸入：23-5輸出： a+b=181.4C語言程序結(jié)構(gòu)及實(shí)例38標(biāo)識(shí)符和關(guān)鍵字⒈C語言的字符集⑴字母：A、a、B、b…、Z、z52個(gè)⑵數(shù)字符號(hào)：0、1…、910個(gè)⑶特殊符號(hào)：+-*/…20個(gè)⒉關(guān)鍵字（又稱保留字）系統(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、unsig