C語言第三章算法和基本程序設(shè)計

1、第3章 算法和基本程序設(shè)計 3.1 算法的概念算法的概念 3.2 結(jié)構(gòu)化程序設(shè)計方法結(jié)構(gòu)化程序設(shè)計方法 3.3 程序的基本結(jié)構(gòu)程序的基本結(jié)構(gòu) 3.4 順序結(jié)構(gòu)程序設(shè)計順序結(jié)構(gòu)程序設(shè)計 3.5 數(shù)據(jù)的輸入輸出數(shù)據(jù)的輸入輸出 3.6 c程序的上機步驟程序的上機步驟3.1 算法的概念 1.定義: 做任何事情都有一定的步驟。為解決一個問題而采取的方法和步驟，就稱為算法。 2.計算機算法可分為兩大類： 數(shù)值運算算法：求解數(shù)值； 非數(shù)值運算算法：事務(wù)管理領(lǐng)域。一個著名的公式一個著名的公式 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)+ +算法算法= =程序程序 數(shù)據(jù)：計算機所能識別、存儲和處理的數(shù)據(jù)：計算機所能識別、存儲和處理的對象

2、。數(shù)據(jù)的動態(tài)性。對象。數(shù)據(jù)的動態(tài)性。 數(shù)據(jù)結(jié)構(gòu)：確定數(shù)據(jù)對象及其存儲方式，數(shù)據(jù)結(jié)構(gòu)：確定數(shù)據(jù)對象及其存儲方式，并定義在這些數(shù)據(jù)對象上的運算集合。并定義在這些數(shù)據(jù)對象上的運算集合。 算法：為解決一個問題而采取的方法和算法：為解決一個問題而采取的方法和步驟。步驟。 算法的特性 1 1 有窮性有窮性 操作步驟是有限的，不是無限的操作步驟是有限的，不是無限的。 2 2 確定性確定性 每個步驟是確定的，無歧義性。每個步驟是確定的，無歧義性。 3 3 有零個或多個輸入有零個或多個輸入 4 4 有一個或多個輸出有一個或多個輸出 5 5 有效性有效性 每一步驟能有效執(zhí)行，并得到確定結(jié)果每一步驟能有效執(zhí)行，并得

3、到確定結(jié)果。 3.1.2 算法的評價標(biāo)準(zhǔn) 1. 正確性 對任何合法的輸入，算法都會得出正確的結(jié)果。 2. 可讀性 可讀性指算法被理解的難易程度。 3. 健壯性（魯棒性） 健壯性即對非法輸入的抵抗能力。 4. 高效率與低存儲量需求 通常，效率指的是算法執(zhí)行時間；存儲量指的是算法執(zhí)行過程中所需的最大存儲空間，兩者都與問題的規(guī)模有關(guān)。二者往往是一對矛盾，常?？梢杂每臻g換時間，也可以用時間換空間。 怎樣表示一個算法用自然語言表示算法用自然語言表示算法用流程圖表示算法用流程圖表示算法用用n-s流程圖表示算法流程圖表示算法用偽代碼表示算法用偽代碼表示算法用計算機語言表示算法用計算機語言表示算法 歧義性，描

4、述分支、循環(huán)算法不方便歧義性，描述分支、循環(huán)算法不方便起止框起止框輸入輸出框輸入輸出框處理框處理框判斷框判斷框流程線流程線連接點連接點 【例3.1】 求三個整數(shù)的和。 求三個整數(shù)和的算法流程圖如圖所示。開始x+y+z = sum輸出sum 的值結(jié)束輸入x,y,z圖3.2 求三個整數(shù)和的算法【例3.2】 求最大公約數(shù)。m,n為正整數(shù)開始結(jié)束輸入m,n求m/n的余數(shù)rr = 0 ?n =m, r =n輸出n是否最大公因數(shù)的算法求最大公因數(shù)的最普遍的算法是歐幾里得算法，它最初是公元前由歐幾里得提出來的，有時也稱它為輾轉(zhuǎn)相除法表述如下：設(shè)給定m，n(mn)，令r0=m，r1=n，有 則得rk=gcd(

5、rk-1，rk)=gcd(rk-2，rk-1)=gcd(r2，r3)=gcd(r1，r2)=gcd(r0，r1)=gcd(m，n)b|a 表示b整除a或者a整除以b 則 a是b的倍數(shù)，b是a的約數(shù)rk-2 = qk-1 qk rk + rk =(qk-1 qk +1) rk s1: 求求12=2 s2: 求求23=6 s3: 求求64=24 天??！共需天啊！共需999個步驟，太可個步驟，太可怕了。怕了。案例案例 求求12341000 s1: 1 p (p:被乘數(shù)被乘數(shù)) s2: 2 i (i:乘數(shù)乘數(shù)) s3: pi p s4: i+1 i s5: 若若i1000,返回返回s3；否則，結(jié)束。否

6、則，結(jié)束。 只需只需5個步驟，簡單。個步驟，簡單。3.2 結(jié)構(gòu)化程序設(shè)計的方法 結(jié)構(gòu)化程序設(shè)計思想采用了模塊分解與功能抽象和自頂向下、分而治之的方法，從而有效地將一個較復(fù)雜的程序系統(tǒng)設(shè)計任務(wù)分解成許多易于控制和處理的子程序，便于開發(fā)和維護，減少程序的出錯概率和提高軟件的開發(fā)效率。 采用結(jié)構(gòu)化程序設(shè)計方法應(yīng)遵循以下原則。 1. 自頂向下 即在程序設(shè)計時，先考慮總體，做出全局設(shè)計，然后再考慮細(xì)節(jié)進行局部設(shè)計，逐步實現(xiàn)精細(xì)化。這種方法稱為“自頂向下，逐步細(xì)化”的方法。 2. 模塊化 就是將一個大任務(wù)分成若干個較小的部分，每一部分承擔(dān)一定的功能，稱為“功能模塊”。每個模塊可以分別編程和調(diào)試，然后組成一

7、個完整的程序。模塊的劃分應(yīng)遵循一些基本原則，如模塊內(nèi)部聯(lián)系要緊密，關(guān)聯(lián)程度要高；模塊間的接口要盡可能簡單，以減少模塊間的數(shù)據(jù)傳遞。 3. 限制使用goto語句 結(jié)構(gòu)化的程序設(shè)計方法結(jié)構(gòu)化的程序設(shè)計方法 基本思路基本思路: 把一個復(fù)雜問題的求解過把一個復(fù)雜問題的求解過程分階段進行程分階段進行, ,每個階段處理的問題每個階段處理的問題都控制在人們?nèi)菀桌斫夂吞幚淼姆抖伎刂圃谌藗內(nèi)菀桌斫夂吞幚淼姆秶鷥?nèi)圍內(nèi). . 采用的方法采用的方法: 1 1 自頂而下自頂而下 2 2 逐步細(xì)化逐步細(xì)化 3 3 模塊化設(shè)計模塊化設(shè)計 4 4 結(jié)構(gòu)化編碼結(jié)構(gòu)化編碼三種基本結(jié)構(gòu)三種基本結(jié)構(gòu) 1 1 順序結(jié)構(gòu)順序結(jié)構(gòu) 2 2

8、 選擇結(jié)構(gòu)選擇結(jié)構(gòu) 3 3 循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)3.3 程序的基本結(jié)構(gòu)程序的基本結(jié)構(gòu)三種基本結(jié)構(gòu)的特點三種基本結(jié)構(gòu)的特點 1 1 只有一個入口只有一個入口 2 2 只有一個出口只有一個出口pa 3 3 結(jié)構(gòu)內(nèi)的每一部分都有機會被執(zhí)行到結(jié)構(gòu)內(nèi)的每一部分都有機會被執(zhí)行到ab 4 4 結(jié)構(gòu)內(nèi)沒有死循環(huán)結(jié)構(gòu)內(nèi)沒有死循環(huán)順序結(jié)構(gòu)的流程圖符號順序結(jié)構(gòu)的流程圖符號ababab傳統(tǒng)流程圖傳統(tǒng)流程圖n-s流程圖流程圖選擇結(jié)構(gòu)的流程圖符號選擇結(jié)構(gòu)的流程圖符號ap成立不成立bap成立不成立傳統(tǒng)流程圖傳統(tǒng)流程圖選擇結(jié)構(gòu)的流程圖符號（續(xù)）選擇結(jié)構(gòu)的流程圖符號（續(xù)）成立不成立apbn-s流程圖流程圖循環(huán)結(jié)構(gòu)的流程圖符號循環(huán)結(jié)

9、構(gòu)的流程圖符號ap1成立不成立ab不成立ap2成立ab傳統(tǒng)流程圖傳統(tǒng)流程圖while型型until型型循環(huán)結(jié)構(gòu)的流程圖符號（續(xù)）循環(huán)結(jié)構(gòu)的流程圖符號（續(xù)）直到直到p1成立成立a當(dāng)當(dāng)p1成立成立awhile型型until型型n-s流程圖流程圖一個有用的結(jié)論一個有用的結(jié)論 已經(jīng)證明：已經(jīng)證明： 三種基本結(jié)構(gòu)的三種基本結(jié)構(gòu)的順序組順序組成成可以表示任何復(fù)雜的算法可以表示任何復(fù)雜的算法結(jié)構(gòu)。結(jié)構(gòu)。 由基本結(jié)構(gòu)構(gòu)成的算法，屬于由基本結(jié)構(gòu)構(gòu)成的算法，屬于“結(jié)構(gòu)化結(jié)構(gòu)化”算法。算法。有關(guān)結(jié)構(gòu)化算法的總結(jié)有關(guān)結(jié)構(gòu)化算法的總結(jié) 一個結(jié)構(gòu)化的算法是由一些基本結(jié)構(gòu)順一個結(jié)構(gòu)化的算法是由一些基本結(jié)構(gòu)順序組成的；基本結(jié)

10、構(gòu)之間不存在向前或序組成的；基本結(jié)構(gòu)之間不存在向前或向后的跳轉(zhuǎn)，流程的轉(zhuǎn)移只存在于一個向后的跳轉(zhuǎn)，流程的轉(zhuǎn)移只存在于一個基本結(jié)構(gòu)的范圍之內(nèi)（如循環(huán)中的流程基本結(jié)構(gòu)的范圍之內(nèi)（如循環(huán)中的流程跳轉(zhuǎn)）；跳轉(zhuǎn)）； 一個非結(jié)構(gòu)化算法可以用一個等價的結(jié)一個非結(jié)構(gòu)化算法可以用一個等價的結(jié)構(gòu)化算法代替，其功能不變。構(gòu)化算法代替，其功能不變。 如果一個算法不能分解為若干個節(jié)本結(jié)如果一個算法不能分解為若干個節(jié)本結(jié)構(gòu)，則它必然不是一個結(jié)構(gòu)化算法。構(gòu)，則它必然不是一個結(jié)構(gòu)化算法。3.4 順序結(jié)構(gòu)程序設(shè)計 1. 表達式語句 表達式語句是在各種表達式后加一個分號(；)形成一個表達式語句。 2. 空語句 空語句直接由分號(

11、；)組成，常用于控制語句中必須出現(xiàn)語句之處。它不做任何操作，只在邏輯上起到有一個語句的作用。例如： ; 空語句也是一個語句，不產(chǎn)生任何動作?？照Z句常用于構(gòu)成標(biāo)號語句，標(biāo)識程序中相關(guān)位置；循環(huán)語句中空循環(huán)體；模塊化程序中未實現(xiàn)的模塊及暫不鏈入的模塊。 3. 函數(shù)調(diào)用語句 由函數(shù)調(diào)用加上分號組成。 4.復(fù)合語句是由一對花括號 括起的若干個語句，語法上可以看成是一個語句。復(fù)合語句中最后一個語句的分號不能省略。例如下面是一個復(fù)合語句： z = x； x = y； y =z; 凡是單一語句可以存在的位置，均可以使用復(fù)合語句。復(fù)合語句用在語法上是單一語句，而相應(yīng)操作需多條語句描述的情況。 5. 控制語句

12、控制語句有條件判斷語句(if、switch)，循環(huán)語句(for、while、do-while)，轉(zhuǎn)移語句(goto、continue、break、return)?？刂普Z句根據(jù)控制條件決定程序的執(zhí)行流程，控制語句不是順序執(zhí)行的。 順序結(jié)構(gòu)是c語言的基本結(jié)構(gòu)，除非指示轉(zhuǎn)移，否則計算機自動以語句編寫的順序一句一句地執(zhí)行c語句。 5c語言無i/o語句，i/o操作由函數(shù)實現(xiàn)5 #include 字符輸出函數(shù)3.5 數(shù)據(jù)的輸入與輸出 格式格式: putchar( c ): putchar( c )參數(shù)參數(shù): c: c為字符常量、變量或表達式為字符常量、變量或表達式功能：把字符功能：把字符c c輸出到顯示器

13、上輸出到顯示器上返值：正常，為顯示的代碼值；出錯，為返值：正常，為顯示的代碼值；出錯，為eof(-1eof(-1)【例3.3】 字符數(shù)據(jù)的輸出。#include main( ) char a, b; a=r; b=e; putchar(a); putchar(b); putchar(d); putchar(n)；運行后，在屏幕上顯示：red 數(shù)據(jù)輸入數(shù)據(jù)輸入字符輸入函數(shù) 格式格式:getchar( ):getchar( )功能：從鍵盤讀一字符功能：從鍵盤讀一字符返值：正常，返回讀取的代碼值；出錯返值：正常，返回讀取的代碼值；出錯, ,返回返回eof(-1)eof(-1)注意：getchar()

14、函數(shù)的括號中沒有參數(shù)，該函數(shù)的輸入一直到“回車”才結(jié)束。回車前的所有輸入字符都會逐個顯示在屏幕上，但只只有第一個字符作為函數(shù)的返回值有第一個字符作為函數(shù)的返回值。 運行時，輸入xxx ，在屏幕上顯示：x【例3.4】 單個字符的輸入和輸出。#include main() char ch; /*從鍵盤上讀入字符直到從鍵盤上讀入字符直到“回車回車”結(jié)束結(jié)束*/ ch= getchar(); /*顯示輸入的第一個字符顯示輸入的第一個字符*/ putchar(ch); putchar(n); /*換行換行*/【例3.5】 將小寫字母轉(zhuǎn)換成大寫。#include main( ) char ch; ch=g

15、etche( ); putchar(ch-32);若輸入b，在屏幕上顯示： bb 3. 字符串輸入/輸出函數(shù) 字符串輸入函數(shù)gets() 用來從鍵盤讀入一串字符。函數(shù)的調(diào)用形式： gets(字符串變量名字符串變量名)；在輸入字符串后，必須用回車作為輸入結(jié)束用回車作為輸入結(jié)束。該回車符并不屬于這串字符，由一個“空操作字符( 0 )”在串的最后來代替它。此時空格不能結(jié)束字符串的輸入，gets函數(shù)返回一個指針。字符串輸出函數(shù)puts()，將字符串?dāng)?shù)據(jù)(可以是字符串字符串常量、字符指針或字符數(shù)組名常量、字符指針或字符數(shù)組名)顯示在屏幕上并換行。函數(shù)的調(diào)用形式是： puts(字符串?dāng)?shù)據(jù)字符串?dāng)?shù)據(jù))；【例

16、3.6】 字符串的輸入和輸出。#include main( ) char str80; gets(str); puts(str);當(dāng)輸入為“how are you?”，則輸出為：how are you?格式：格式：printf(“printf(“格式控制串格式控制串”，輸出表，輸出表) )功能：按指定格式向顯示器輸出數(shù)據(jù)功能：按指定格式向顯示器輸出數(shù)據(jù)返值：正常，返回輸出字節(jié)數(shù)；出錯，返回返值：正常，返回輸出字節(jié)數(shù)；出錯，返回eof(-1)eof(-1)3.5.3 格式輸入與輸出_格式輸出函數(shù) 輸出表：要輸出的數(shù)據(jù)（可以沒有，多個時以輸出表：要輸出的數(shù)據(jù)（可以沒有，多個時以“,”分隔）分隔）

17、格式控制串：包含兩種信息格式控制串：包含兩種信息格式說明：格式說明： %修飾符修飾符格式字符格式字符 ，用于指定，用于指定輸出格式輸出格式普通字符或轉(zhuǎn)義序列：原樣輸出普通字符或轉(zhuǎn)義序列：原樣輸出 格式字符格式字符d,ix,xoucse,efg%格式字符：十六進制無符號整數(shù)不帶符號十進制整數(shù)十進制整數(shù)指數(shù)形式浮點小數(shù)單一字符字符串八進制無符號整數(shù)小數(shù)形式浮點小數(shù)e和f中較短一種百分號本身int a=567;printf ( “%d”,a);int a=255;printf(“%x”,a);int a=65;printf(“%o”,a);int a=567;printf(“%u”,a);char

18、a=65;printf(“%c”,a);printf(“%s”,“abc”);float a=567.789;printf(“%e”,a);float a=567.789;printf(“%f”,a);float a=567.789;printf(“%g”,a);printf(“%”);567ff101567aabc5.677890e+02567.789000567.789% 說明 格式字符要用小寫 格式字符與輸出項個數(shù)應(yīng)相同，按先后順序一一對應(yīng) 輸出轉(zhuǎn)換:格式字符與輸出項類型不一致,自動按指定格式輸出例 main() unsigned int u=65535; printf(”u=%dn,u

19、); 輸出結(jié)果：u=-1例 int a=3,b=4; printf(“%d %dn”,a,b); printf(“a=%d , b=%dn”,a,b); 例 int a=3,b=4; printf(“%d %dn”,a,b); printf(“a=%d , b=%dn”,a,b);輸出結(jié)果: 3 4 a=3, b=411 11 11 11 11 11 11 1165535 格式輸入函數(shù)格式格式: scanf(“: scanf(“格式控制串格式控制串”，地址表），地址表）功能：按指定格式從鍵盤讀入數(shù)據(jù)，存入地址表指定的功能：按指定格式從鍵盤讀入數(shù)據(jù)，存入地址表指定的 存儲單元中存儲單元中, ,并

20、按回車鍵結(jié)束并按回車鍵結(jié)束返值：正常，返回輸入數(shù)據(jù)個數(shù)返值：正常，返回輸入數(shù)據(jù)個數(shù) 地址表：變量的地址，常用取地址運算符& 格式字符:d,i,o,x,u,c,s,f,e例 scanf(“%d”,&a); 輸入：10 則 a=10例 scanf(“%x”,&a); 輸入：11 則 a=17 附加格式說明符（修飾符）例 scanf(“%4d%2d%2d”,&yy,&mm,&dd); 輸入 19991015 則1999yy, 10 mm, 15 dd例 scanf(“%3d%*4d%f”,&k,&f); 輸入 12345678765.43 則123k, 8765.43f例 scanf(“%2d%*3

21、d%2d”,&a,&b); 輸入 1234567 則12a, 67b例 scanf(“%3c%2c”,&c1,&c2); 輸入 abcde 則ac1, d c2l修飾符功 能hm*用于d,o,x前，指定輸入為short型整數(shù)用于d,o,x前，指定輸入為long型整數(shù)用于e,f前，指定輸入為double型實數(shù)指定輸入數(shù)據(jù)寬度，遇空格或不可轉(zhuǎn)換字符則結(jié)束抑制符，指定輸入項讀入后不賦給變量 輸入分隔符的指定 一般以空格、tab或回車鍵作為分隔符 其它字符做分隔符：格式串中兩個格式符間字符例 scanf(“%d%o%x”,&a,&b,&c); printf(“a=%d,b=%d,c=%dn”,a,b,

22、c); 輸入 123 123 123 輸出 a=123,b=83,c=291例 scanf(“%d:%d:%d”,&h,&m,&s); 輸入 12:30:45 則12 h, 30 m, 45 s例 scanf(“%d,%d”,&a,&b) 輸入 3,4 則3a, 4 b例 scanf(“a=%d,b=%d,c=%d”,&a,&b,&c); 輸入 a=12,b=24,c=36 說明： 用“%c”格式符時，空格和轉(zhuǎn)義字符作為有效字符輸入如 scanf(“%c%c%c”,&c1,&c2,&c3); 若輸入abc 則ac1, c2, b c3 輸入數(shù)據(jù)時，遇以下情況認(rèn)為該數(shù)據(jù)結(jié)束： 遇空格、tab、或

23、回車 遇寬度結(jié)束 遇非法輸入如 scanf(“%d%c%f”,&a,&b,&c); 若輸入1234a123o.26 則 1234 a, a b, 123 c 輸入函數(shù)留下的“垃圾”：例 int x; char ch; scanf(“%d”,&x); ch=getchar(); printf(“x=%d,ch=%dn”,x,ch);執(zhí)行：123輸出：x=123,ch=10例 int x; char ch; scanf(“%d”,&x); scanf(“%c”,&ch); printf(“x=%d,ch=%dn”,x,ch);執(zhí)行：123輸出：x=123,ch=10解決方法：（1）用getchar()清除（2）用函數(shù)fflush(stdin)清除全部剩余內(nèi)容 (3) 用格式串中空格或“%*c”來“吃掉”例 int x; char ch; scanf(“%d”,&x); getchar(); scanf(“ %c”,&ch);或 scanf(“%*c%c”,&ch); 注意: scanf( )函數(shù)沒有輸出功能(即不