第4章程序與算法

第4章

程序與算法3/17/202413/17/20242§2C語言程序的基本結(jié)構(gòu)§2

C語言程序的基本結(jié)構(gòu)一.C語言程序結(jié)構(gòu)main()

程序首部{

說明語句

數(shù)據(jù)結(jié)構(gòu)

語句

輸入語句

執(zhí)行語句運算處理

算法設(shè)計}

輸出語句3/17/202423/17/20243生成執(zhí)行程序的四個過程

編輯、編譯、連接、運行3/17/202433/17/20244§4C語言編程環(huán)境編譯方式用戶目標程序源程序執(zhí)行程序庫文件連接程序編譯程序編輯程序錯誤信息結(jié)果編譯連接編輯.c.obj.exe運行3/17/202443/17/20245END課堂練習題[1.1]運行的程序的后綴是______。[1.2]C語言源程序文件的后綴是______，經(jīng)過編譯后,生成文件的后綴是______，經(jīng)過連接后，生成文件的后綴是______。[1.3]結(jié)構(gòu)化程序由____、____、____三種基本結(jié)構(gòu)組成。.EXE.C.OBJ.EXE順序分支循環(huán)完3/17/20245幾個知識要點程序=數(shù)據(jù)結(jié)構(gòu)+算法“數(shù)據(jù)結(jié)構(gòu)”就是要告訴程序要用到哪些數(shù)據(jù)、哪種類型的數(shù)據(jù)、數(shù)據(jù)間的關(guān)系以及數(shù)據(jù)存儲方法。“算法”就是計算機解題所進行操作的步驟，是程序的邏輯抽象，是解決問題的數(shù)學過程，是對解題過程準確而完整的描述。編程是一種“把一件事情交給計算機去做”的行為，這個行為通過程序語言加以描述。算法設(shè)計是編程前必須要做的事，解決“做什么”和“如何做”的問題，然后程序再根據(jù)算法實現(xiàn)出來，因此算法是程序設(shè)計的靈魂?！?程序設(shè)計與算法概述3/17/20246幾個知識要點C語言本身的語法規(guī)則C語言從基本字符集到關(guān)鍵字、標識符、常量、變量、函數(shù)和表達式等基本“單詞”，再到基本語句，結(jié)合具體的語言規(guī)則和要求就構(gòu)成C語言的程序。C程序的組成要素和設(shè)計、調(diào)試步驟函數(shù)是構(gòu)成程序的基本單位，語句是構(gòu)成函數(shù)的基本單位。函數(shù)用于實現(xiàn)某一項功能，語句用于體現(xiàn)完成這個功能所進行操作的詳細步驟。程序設(shè)計就是分析解決問題的方法步驟，并將其記錄下來的過程。程序設(shè)計過程包括分析、設(shè)計、編碼、測試、排錯、文檔編寫等階段?！?程序設(shè)計與算法概述3/17/202471.程序設(shè)計的步驟一個初級程序員對于一個簡單的問題，若要用計算機解決，具體步驟大致為：①確定待解決問題的計算或處理方法；②將實際問題轉(zhuǎn)變?yōu)橐粋€數(shù)學問題，用數(shù)學模型(表達式)描述；③編制程序框圖，確定程序結(jié)構(gòu)；④選擇計算機語言和它的工作模式；⑤編制程序；⑥上機編輯、調(diào)試（包括編譯和連接），消除語法錯誤；⑦如果結(jié)果正確則生成最終的用戶程序，否則返回①從頭重來，找出邏輯或設(shè)計錯誤所在?！?程序設(shè)計與算法概述3/17/20248如何表示算法？

處理思路：公式？輸入要求？

錯誤處理方法？解決問題方法？2.算法舉例【例4-1】輸入三角形三個邊的值，計算這個三角形的面積。如何輸入？如何計算和輸出？輸入的是什么類型的值，輸出類型、精度如何？輸入值錯誤（不能構(gòu)成三角形）如何解決？§1程序設(shè)計與算法概述3/17/20249算法描述圖示#include<stdio.h>#include<math.h>intmain(){inta,b,c;floats,area;scanf(“%d,%d,%d”,&a,&b,&c);if(“不能構(gòu)成三角形”){printf(“inputerror!”);return0;}else{s=(a+b+c)/2.0;area=sqrt(s*(s-a)*(s-b)*(s-c));printf(“area=%.2f”,area);}return0;}3/17/202410目錄§1程序設(shè)計與算法概述§2程序設(shè)計思想

§3算法描述方法§4算法特性與評價方法§5本章小節(jié)

第4章算法3/17/202411§2程序設(shè)計思想4.2.1

結(jié)構(gòu)化程序設(shè)計思想

1.基本概念1966年C.Bobm提出任何程序都可以用順序、選擇、循環(huán)三種基本結(jié)構(gòu)來組合，這樣編寫出來的程序易懂易讀也易于修改，提高了程序可靠性。這樣的程序稱為結(jié)構(gòu)化程序，編寫這樣的程序稱為結(jié)構(gòu)化程序設(shè)計。“分而治之”是一種解決復雜問題的常用方法，是結(jié)構(gòu)化程序設(shè)計思想的具體體現(xiàn)。大問題可以分解為若干關(guān)聯(lián)的小問題，小問題又可以分解為若干更小、更具體的問題。把小問題逐一求解，大問題就得到解決。2.結(jié)構(gòu)化程序設(shè)計的方法（1）自頂向下、逐步細化。（2）模塊化。（3）結(jié)構(gòu)化編碼。3/17/202412“自頂向下、逐步細化”方法“自頂向下、逐步細化”就是從一個大問題出發(fā)，往下逐步分解，由宏觀到微觀，由一般問題到具體細節(jié)實現(xiàn)等進行有序、有層次、有步驟的分析，最終在編寫程序前，給出所有方法步驟的細節(jié)。例如：計算學院教師的平均工資。這個任務(wù)比較復雜，可分解為如下幾點：（1）找出每個教師的收入；（2）計算共有多少教師；（3）計算工資總額；（4）計算平均工資。對于第（3）步又可再細分為：①找出一位教師檔案；②讀出工資數(shù)額；③累計求和；重復上述三步驟。對于①可再次進一步細分為：打開檔案；找出正確記錄；從磁盤讀取數(shù)據(jù)。§2程序設(shè)計思想3/17/202413模塊化設(shè)計

結(jié)構(gòu)化程序設(shè)計的另一個概念是模塊化設(shè)計，把一個大的復雜的問題逐層分解為一系列小的簡單的模塊來進行處理，每個小模塊只完成單一的具體任務(wù)。模塊內(nèi)部聯(lián)系緊密，而與其他模塊之間聯(lián)系較弱，這樣的模塊稱為獨立性高的模塊，實現(xiàn)“高內(nèi)聚、低耦合”。模塊化“功能分解”即按照問題的功能進行模塊劃分，把相近功能的任務(wù)放到一個模塊中。

§2程序設(shè)計思想3/17/2024141)模塊之間接口關(guān)系簡單，每個模塊完成獨立的工作，易于被人理解，所編寫出來的程序可讀性和可理解性好；

2)各個模塊功能單一，要修改某一個模塊時只涉及到要修改的模塊而不涉及到其他模塊，不會出現(xiàn)修改程序時牽一發(fā)動全身的現(xiàn)象；3)人們可以單獨驗證、測試一個個模塊，保證其正確性；4)可以利用現(xiàn)有模塊，像搭積木一樣進行開發(fā)新的程序。獨立性高的模塊有以下優(yōu)點：§2程序設(shè)計思想3/17/202415模塊之間是一種層次結(jié)構(gòu)，上層模塊對下層模塊進行調(diào)用，下圖所示是報表生成程序的層次結(jié)構(gòu)，以柜形框表示模塊，框中的模塊名稱表明模塊的功能，提出頂層的模塊“做什么”而不涉及“怎樣做”，最下層模塊功能十分具體，涉及“怎樣做”的精確描述，易于編程。

報表生成程序數(shù)據(jù)輸入數(shù)據(jù)計算求和求平均求方差打印報表§2程序設(shè)計思想3/17/202416結(jié)構(gòu)化編碼通過順序、分支、循環(huán)三種基本結(jié)構(gòu)通過函數(shù)方式實現(xiàn)功能通過多程序（.c文件）實現(xiàn)項目1.三種基本控制結(jié)構(gòu)：

順序控制、選擇控制、循環(huán)控制。2.模塊化組織結(jié)構(gòu)：按功能劃分模塊，每個模塊易于理解且不可再分，用函數(shù)實現(xiàn)模塊化組織結(jié)構(gòu)。3.程序設(shè)計過程：自頂而下、逐步細化。結(jié)構(gòu)化程序設(shè)計要點§2程序設(shè)計思想3/17/202417結(jié)構(gòu)化程序有三種基本結(jié)構(gòu)順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)語句執(zhí)行的順序與程序書寫的順序一致條件成立，執(zhí)行A；否則，執(zhí)行B重復執(zhí)行某組動作結(jié)構(gòu)條件成立時，反復執(zhí)行A；條件不成立，停止重復執(zhí)行動作A，當某一條件成立時，停止C程序的基本結(jié)構(gòu)3/17/202418main(){inta,b,c;a=5;b=6;c=a+b;printf(“%d”,c);}程序執(zhí)行的順序和語句書寫的順序一致有一個數(shù)據(jù)入口一個數(shù)據(jù)出口AB基本結(jié)構(gòu)順序結(jié)構(gòu)3/17/202419條件ABYN當條件滿足時,執(zhí)行語句A；否則,執(zhí)行語句B有一個數(shù)據(jù)入口一個數(shù)據(jù)出口鍵盤輸入一個整數(shù),判斷其正負例inta;aa>0if(a>0)printf(“a為正數(shù)”);elseprintf(“a為負數(shù)”);語句A語句B打印a的值選擇結(jié)構(gòu)3/17/202420YN求1~100的自然數(shù)之和

X<=100x=1S=0語句若條件滿足,重復執(zhí)行語句內(nèi)容；否則,退出循環(huán)條件一個數(shù)據(jù)入口一個數(shù)據(jù)出口s=s+x;x=x+1;語句S條件不滿足,不執(zhí)行任何語句循環(huán)結(jié)構(gòu)

1.當型循環(huán)3/17/202421語句NY求1+2+3+~n<=1000的最大的n例:n=1,s=0;s=s+nn=n+1……S>1000n=1s=0語句不論條件是否滿足,語句至少執(zhí)行一次

2.直到型循環(huán)s=1+2+3+……n=?(s<1000)

3/17/2024223.結(jié)構(gòu)化程序設(shè)計的特點

1）以三種基本結(jié)構(gòu)的組合進行程序的編寫；2）程序的編寫采用模塊化結(jié)構(gòu)；3）自頂向下，逐步求精；4）限制使用goto語句，不用或少用goto語句，通常只允許用它從一個循環(huán)中跳出而不允許從外部跳入一個循環(huán)；5）每一個結(jié)構(gòu)只允許有一個入口和一個出口。各部分之間接口簡單，邏輯清晰；6）采用結(jié)構(gòu)化語言編寫程序，程序結(jié)構(gòu)清晰易于閱讀和修改；7）采用良好的編程風格?！?程序設(shè)計思想3/17/2024234.程序設(shè)計步驟1.分析問題，建立數(shù)學模型。2.確定數(shù)據(jù)結(jié)構(gòu)。3.確定算法，描述算法。4.編制程序，調(diào)試程序。5.運行程序，得到結(jié)果。程序設(shè)計要求：書寫正確，結(jié)果正確§2程序設(shè)計思想3/17/2024244.2.2面向?qū)ο蟮某绦蛟O(shè)計基本概念1.基本概念面向?qū)ο蟪绦蛟O(shè)計的本質(zhì)是把數(shù)據(jù)與處理數(shù)據(jù)的過程當成一個整體——對象。類（CLASS）：定義了一類事物的抽象特點，包括事物的屬性和它具有的行為（稱為方法）。父類、子類

實例(Instance)對象(Object)：是類的實例，是某個類別的具體化的事物。方法（method）是一個類能做的事情，代表具體操作功能。

消息（Message）繼承（Inheritance）多態(tài)性（Polymorphism）§2程序設(shè)計思想3/17/2024252.面向?qū)ο蟪绦蛟O(shè)計的優(yōu)點穩(wěn)定性好可重用性好與人類習慣的思維方法一致易于開發(fā)大型軟件產(chǎn)品可維護性好§2程序設(shè)計思想3/17/202426目錄§1程序設(shè)計與算法概述§2程序設(shè)計思想§3算法描述方法§4算法特性與評價方法§5本章小節(jié)

第4章算法3/17/202427算法分類利用計算機解題，一般有兩類算法：數(shù)值計算算法和非數(shù)值計算算法。數(shù)值計算是指求數(shù)值解的問題（如計算方程根，求最大公約數(shù)等），往往有現(xiàn)成的模型、計算方法和公式對應(yīng)。非數(shù)值計算主要解決需要用分析推理、邏輯推導才能解決的問題。由于種類繁多、要求各異，只有一些典型的非數(shù)值計算方法（如排序、查找算法等），許多問題需要設(shè)計解決問題的專門算法?！?算法描述方法3/17/2024282.算法的描述自然語言傳統(tǒng)流程圖NS結(jié)構(gòu)化流程圖偽代碼程序代碼（最準確的描述）?！?算法描述方法3/17/202429§3算法描述方法2.算法的表示②傳統(tǒng)流程圖描述

下圖表示程序流程圖的基本符號，建議初學者養(yǎng)成編寫程序前先畫圖的習慣，通過流程圖使你的算法思想和實現(xiàn)步驟得以體現(xiàn)，便于檢查、修改和交流。

程序流程圖基本符號3/17/202430三種基本結(jié)構(gòu)的流程圖描述模塊A模塊BYesNo條件判斷模塊A模塊B§3算法描述方法3/17/202431三種基本結(jié)構(gòu)的流程圖描述模塊A模塊BYesNo條件判斷模塊A模塊B模塊A條件？No條件？模塊ANo§3算法描述方法3/17/202432②流程圖

人們普遍采用程序流程圖是因為它簡單、直觀。把執(zhí)行的流程表達得一清二楚，易于理解。然而，它也有不少缺陷，程序流程圖中的箭頭十分靈活，使用不當會影響到程序結(jié)構(gòu)的清晰。X1=(-b+)/2aX2=(-b-)/2a開始輸入a,b,cS=b*b-4*a*cS>=0y打印X1，X2打印“無實根解”n結(jié)束方程ax２+bx+c＝0的求解算法§3算法描述方法3/17/202433開始s=0,a=0輸入na=a+1s=s+aa<nYN輸出s結(jié)束

用規(guī)定的一系列圖形、流程線和文字說明算法中的基本操作和控制流程。scanf(“%d”,&n);printf(“%d”,s);While(a<n)流程圖應(yīng)用舉例：例如計算:s=Σa;a=1~n§3算法描述方法3/17/2024343.NS結(jié)構(gòu)化流程圖 N-S圖的基本形式模塊1模塊2模塊3條件TF

模塊A模塊B

While

條件模塊

模塊

Until條件順序分支循環(huán)1循環(huán)2§3算法描述方法3/17/202435

N-S圖舉例

輸入系數(shù)a,b,cS=b*b-4*a*cS>=0

打印“無實根解”X1=(-b+)/2aX2=(-b–)/2a打印X1,X2FT方程ax２+bx+c＝0的求解§3算法描述方法3/17/202436【例4-2】用傳統(tǒng)流程圖和NS結(jié)構(gòu)化流程圖分別描述“求3個整數(shù)中的最大值”的算法。問題分析：求3個整數(shù)最大值方法很多，但都需要通過判斷解決。具體步驟為：（1）輸入3個整數(shù)；（2）通過判斷比較，找出最大值；（3）輸出最大值，然后結(jié)束。算法設(shè)計：本例的關(guān)鍵是如何比較找到最大值。方法很多，這里給出一種做法如下：（1）先設(shè)定一個變量max用于保存最大值；（2）把先輸入的第一個數(shù)作為最大值放入max變量中；（3）把第二個輸入的數(shù)與最大值量max進行比較，若比max中值大，則放入max中；（4）同樣進行第三個數(shù)與max的比較，并保存最大值；（5）最后輸出最大值?！?算法描述方法3/17/202437NoNo開始輸入a,b,c3個數(shù)a

maxb

maxc

maxb>maxc>max輸出max結(jié)束輸入a,b,ca

maxb>max?YesNob

max

c>max?YesNoc

max輸出max值§3算法描述方法3/17/2024384．偽代碼描述偽代碼（Pseudocode）是用介于自然語言和計算機語言之間的文字和符號表示算法，即程序設(shè)計語言具有的關(guān)鍵字用英文表示，其它的可用漢字、英文、數(shù)字和公式等表示，便于書寫和閱讀即可。用此方法描述算法并無格式要求，只要簡單、清晰、易懂?！纠?-3】用偽代碼描述例4-2問題的算法。開始申請4個變量a,b,c,max，其中max用于存放最大值；先后從鍵盤輸入3個整數(shù)給變量a,b,c；a

max當b≤max時，繼續(xù)進行比較，否則執(zhí)行bmax繼續(xù)判斷：當c>max時，執(zhí)行cmax輸出max的值結(jié)束§3算法描述方法3/17/2024395．用計算機語言描述用計算機語言描述算法，應(yīng)該是上述步驟完成后的最后一步，也是最精確的一步。這一步的描述要求必須按照程序設(shè)計語言的語法規(guī)則編寫規(guī)范的程序代碼，只有這樣才能上機調(diào)試和運行。例4-2問題的C語言程序代碼描述如下：/*求3個整數(shù)中的最大值*/#include<stdio.h>intmain(){inta,b,c,max;scanf(“%d,%d,%d”,&a,&b,&c);max=a;if(b>max)max=b;if(c>max)max=c;printf(“max=%d\n”,max);return0;}NoNo開始輸入a,b,c3個數(shù)a

maxb

maxc

maxb>maxc>max輸出max結(jié)束§3算法描述方法3/17/202440算法舉例

程序設(shè)計的關(guān)鍵是算法設(shè)計，有了算法，再用計算機語言去實現(xiàn)算法，就容易了。例1：計算1+2+3+…+100之和。算法步驟分析：S1:累加器變量sum賦初值0，即sum=0S2:計數(shù)器變量i賦初值1，即i=1S3:使累加器變量值sum加計數(shù)器變量值i,結(jié)果仍放在sum中,即sum=sum+i,此時sum值為

sum=sum+i=0+1=1S4:使計數(shù)器變量i加1,結(jié)果仍放在i中,即i=i+1,此時i值為

i=i+1=1+1=2依此類推……§3算法描述方法3/17/202441程序流程圖和N-S圖如下圖所示

圖1累加運算程序流程圖開始

sum=0i=0sum=sum+ii=i+1i<=100打印NY圖2累加運算N-S圖

§3算法描述方法3/17/202442C語言程序算法如下

main(){inti=1,sum=0;/*定義變量及其數(shù)據(jù)類型*/

while(i<=100)

/*循環(huán)控制結(jié)構(gòu)*/{sum+=i; i=i+1;}/*循環(huán)體結(jié)束*/printf(“sum=%d\n”,sum);/*輸出累加結(jié)果*/}

程序算法不是唯一的，這個問題還有其它的算法?！?算法描述方法3/17/202443以此類推可以很容易表示出其它問題的算法例2：計算下式之和的算法，當分母大于100時程序結(jié)束，輸出計算結(jié)果。程序算法如下?！?算法描述方法3/17/202444例2算法的N-S圖如下所示§3算法描述方法3/17/202445附加知識：PAD圖 PAD圖的基本符號S1S2S3While條件SUntil條件S順序分支循環(huán)S1S2條件T§3算法描述方法3/17/202446PAD圖 方程ax２+bx+c＝0的求解輸入系數(shù)a,b,cS=b*b-4*a*cS>=0打印X1,X2打印“無實根解”

X2=(-b–)/2aX1=(-b+)/2a§3算法描述方法3/17/202447目錄§1程序設(shè)計與算法概述§2程序設(shè)計思想§3算法描述方法§4算法特性與評價方法§5本章小節(jié)

第4章算法3/17/2024484.4.1算法的特性

1.有窮性：算法包含的操作步驟是有限的，每一步都應(yīng)在合理的時間內(nèi)完成。2.確定性：算法中的每一步應(yīng)該是確定的，而不應(yīng)當是含糊的、模棱兩可的和歧義的。3.有效性（可行性）：算法中的每一步應(yīng)該能有效執(zhí)行，且能得到確定的結(jié)果。4.有零個或多個輸入：輸入是計算機在執(zhí)行算法時，需要從外界得到必要的信息。5.有一到多個輸出：算法的目的是求得問題的解（計算結(jié)果），而解只有輸出才有意義?！?算法特性與評價方法3/17/2024494.4.2算法分析與評價

1．正確性：算法應(yīng)當滿足具體問題的需求，設(shè)計和選擇算法應(yīng)該正確反映這種需求。對“正確”一詞的理解，可分以下四個層次：（1）程序不含語法錯誤；（2）程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得到滿足規(guī)格說明要求的結(jié)果；（3）程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得到滿足規(guī)格說明要求的結(jié)果；（4）程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能夠得到滿足規(guī)格說明要求的結(jié)果。第一層次是調(diào)試程序確保能夠執(zhí)行的需要，結(jié)果對與否不能保證；第二層次說明程序基本沒有邏輯錯誤，但對于邊緣數(shù)據(jù)、特殊數(shù)據(jù)等還沒有檢驗，不能說明程序不會出現(xiàn)大問題；第三個層次是軟件開發(fā)中“軟件測試”環(huán)節(jié)所采用的方法，是判斷能否達到商品化軟件標準的要求；最后一個層次是理想化的要求，一般無法達到?！?算法特性與評價方法3/17/2024504.4.2算法分析與評價

2．可讀性：算法主要是為了人的閱讀與交流，其次才是機器執(zhí)行。只有可讀性好的軟件才能有助于他人對算法的理解，有助于程序代碼的實現(xiàn)。提高可讀性的方法一般有兩點：一是嚴格遵循程序代碼編寫規(guī)范要求編寫程序；二是添加必要的注釋。3．健壯性：當輸入非法數(shù)據(jù)時，算法程序能做出適當?shù)姆从常ㄈ顼@示輸入錯誤提示等）或針對性的處理，而不會產(chǎn)生莫名其妙的輸出結(jié)果或不可控的執(zhí)行?！?算法特性與評價方法3/17/2024514.4.2算法分析與評價

4．高效率：算法效率指的是算法執(zhí)行所使用的時間（一般為ns納秒級）。對于一個問題，如果有多個算法可以解決，執(zhí)行時間最短的效率最高。5．低存儲量：算法存儲量需求一般指算法執(zhí)行過程中所需要的最大存儲空間?！?算法特性與評價方法3/17/202452附件知識：程序設(shè)計風格1.良好的程序設(shè)計風格語句形式化（準確）。程序一致性（各部分風格一致，文檔格式一致）。適當使用注釋（增加可讀性）。標識符貼近實際，要求見名知意?！扒逦谝唬实诙薄?算法特性與評價方法3/17/202453

2．如何形成良好的設(shè)計風格１）源程序文檔化符號名的命名程序注釋視覺組織２）數(shù)據(jù)說明的方法數(shù)據(jù)說明的次序規(guī)范化說明語句中變量安排有序化使用注釋語句來說明復雜的數(shù)據(jù)結(jié)構(gòu)§4算法特性與評價方法3/17/2024543）語句的結(jié)構(gòu)在一行內(nèi)只寫一條語句；程序編寫應(yīng)優(yōu)先考慮清晰性；除非對效率有特殊要求，要清晰第一，效率第二；首先保證程序正確，然后才提高速度；避免使用臨時變量；避免不必要的轉(zhuǎn)移；盡可能使用庫函數(shù)；避免復雜的條件語句；盡量減少使用“否定”條件的條件語句；數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡化；要模塊