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

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

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

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

4、述分支、循環(huán)算法不方便歧義性，描述分支、循環(huán)算法不方便起止框起止框輸入輸出框輸入輸出框處理框處理框判斷框判斷框流程線流程線連接點(diǎn)連接點(diǎn) 【例3.1】 求三個(gè)整數(shù)的和。 求三個(gè)整數(shù)和的算法流程圖如圖所示。開始x+y+z = sum輸出sum 的值結(jié)束輸入x,y,z圖3.2 求三個(gè)整數(shù)和的算法【例3.2】 求最大公約數(shù)。m,n為正整數(shù)開始結(jié)束輸入m,n求m/n的余數(shù)rr = 0 ?n =m, r =n輸出n是否最大公因數(shù)的算法求最大公因數(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個(gè)步驟，太可個(gè)步驟，太可怕了。怕了。案例案例 求求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個(gè)步驟，簡單。個(gè)步驟，簡單。3.2 結(jié)構(gòu)化程序設(shè)計(jì)的方法 結(jié)構(gòu)化程序設(shè)計(jì)思想采用了模塊分解與功能抽象和自頂向下、分而治之的方法，從而有效地將一個(gè)較復(fù)雜的程序系統(tǒng)設(shè)計(jì)任務(wù)分解成許多易于控制和處理的子程序，便于開發(fā)和維護(hù)，減少程序的出錯(cuò)概率和提高軟件的開發(fā)效率。 采用結(jié)構(gòu)化程序設(shè)計(jì)方法應(yīng)遵循以下原則。 1. 自頂向下 即在程序設(shè)計(jì)時(shí)，先考慮總體，做出全局設(shè)計(jì)，然后再考慮細(xì)節(jié)進(jìn)行局部設(shè)計(jì)，逐步實(shí)現(xiàn)精細(xì)化。這種方法稱為“自頂向下，逐步細(xì)化”的方法。 2. 模塊化 就是將一個(gè)大任務(wù)分成若干個(gè)較小的部分，每一部分承擔(dān)一定的功能，稱為“功能模塊”。每個(gè)模塊可以分別編程和調(diào)試，然后組成一

7、個(gè)完整的程序。模塊的劃分應(yīng)遵循一些基本原則，如模塊內(nèi)部聯(lián)系要緊密，關(guān)聯(lián)程度要高；模塊間的接口要盡可能簡單，以減少模塊間的數(shù)據(jù)傳遞。 3. 限制使用goto語句 結(jié)構(gòu)化的程序設(shè)計(jì)方法結(jié)構(gòu)化的程序設(shè)計(jì)方法 基本思路基本思路: 把一個(gè)復(fù)雜問題的求解過把一個(gè)復(fù)雜問題的求解過程分階段進(jìn)行程分階段進(jìn)行, ,每個(gè)階段處理的問題每個(gè)階段處理的問題都控制在人們?nèi)菀桌斫夂吞幚淼姆抖伎刂圃谌藗內(nèi)菀桌斫夂吞幚淼姆秶鷥?nèi)圍內(nèi). . 采用的方法采用的方法: 1 1 自頂而下自頂而下 2 2 逐步細(xì)化逐步細(xì)化 3 3 模塊化設(shè)計(jì)模塊化設(shè)計(jì) 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)的特點(diǎn)三種基本結(jié)構(gòu)的特點(diǎn) 1 1 只有一個(gè)入口只有一個(gè)入口 2 2 只有一個(gè)出口只有一個(gè)出口pa 3 3 結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會(huì)被執(zhí)行到結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會(huì)被執(zhí)行到ab 4 4 結(jié)構(gòu)內(nèi)沒有死循環(huán)結(jié)構(gòu)內(nèi)沒有死循環(huán)順序結(jié)構(gòu)的流程圖符號(hào)順序結(jié)構(gòu)的流程圖符號(hào)ababab傳統(tǒng)流程圖傳統(tǒng)流程圖n-s流程圖流程圖選擇結(jié)構(gòu)的流程圖符號(hào)選擇結(jié)構(gòu)的流程圖符號(hào)ap成立不成立bap成立不成立傳統(tǒng)流程圖傳統(tǒng)流程圖選擇結(jié)構(gòu)的流程圖符號(hào)（續(xù)）選擇結(jié)構(gòu)的流程圖符號(hào)（續(xù)）成立不成立apbn-s流程圖流程圖循環(huán)結(jié)構(gòu)的流程圖符號(hào)循環(huán)結(jié)

9、構(gòu)的流程圖符號(hào)ap1成立不成立ab不成立ap2成立ab傳統(tǒng)流程圖傳統(tǒng)流程圖while型型until型型循環(huán)結(jié)構(gòu)的流程圖符號(hào)（續(xù)）循環(huán)結(jié)構(gòu)的流程圖符號(hào)（續(xù)）直到直到p1成立成立a當(dāng)當(dāng)p1成立成立awhile型型until型型n-s流程圖流程圖一個(gè)有用的結(jié)論一個(gè)有用的結(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é) 一個(gè)結(jié)構(gòu)化的算法是由一些基本結(jié)構(gòu)順一個(gè)結(jié)構(gòu)化的算法是由一些基本結(jié)構(gòu)順序組成的；基本結(jié)

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

11、；)組成，常用于控制語句中必須出現(xiàn)語句之處。它不做任何操作，只在邏輯上起到有一個(gè)語句的作用。例如： ; 空語句也是一個(gè)語句，不產(chǎn)生任何動(dòng)作?？照Z句常用于構(gòu)成標(biāo)號(hào)語句，標(biāo)識(shí)程序中相關(guān)位置；循環(huán)語句中空循環(huán)體；模塊化程序中未實(shí)現(xiàn)的模塊及暫不鏈入的模塊。 3. 函數(shù)調(diào)用語句 由函數(shù)調(diào)用加上分號(hào)組成。 4.復(fù)合語句是由一對(duì)花括號(hào) 括起的若干個(gè)語句，語法上可以看成是一個(gè)語句。復(fù)合語句中最后一個(gè)語句的分號(hào)不能省略。例如下面是一個(gè)復(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)移，否則計(jì)算機(jī)自動(dòng)以語句編寫的順序一句一句地執(zhí)行c語句。 5c語言無i/o語句，i/o操作由函數(shù)實(shí)現(xiàn)5 #include 字符輸出函數(shù)3.5 數(shù)據(jù)的輸入與輸出 格式格式: putchar( c ): putchar( c )參數(shù)參數(shù): c: c為字符常量、變量或表達(dá)式為字符常量、變量或表達(dá)式功能：把字符功能：把字符c c輸出到顯示器

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

14、函數(shù)的括號(hào)中沒有參數(shù)，該函數(shù)的輸入一直到“回車”才結(jié)束。回車前的所有輸入字符都會(huì)逐個(gè)顯示在屏幕上，但只只有第一個(gè)字符作為函數(shù)的返回值有第一個(gè)字符作為函數(shù)的返回值。 運(yùn)行時(shí)，輸入xxx ，在屏幕上顯示：x【例3.4】 單個(gè)字符的輸入和輸出。#include main() char ch; /*從鍵盤上讀入字符直到從鍵盤上讀入字符直到“回車回車”結(jié)束結(jié)束*/ ch= getchar(); /*顯示輸入的第一個(gè)字符顯示輸入的第一個(gè)字符*/ 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é)束。該回車符并不屬于這串字符，由一個(gè)“空操作字符( 0 )”在串的最后來代替它。此時(shí)空格不能結(jié)束字符串的輸入，gets函數(shù)返回一個(gè)指針。字符串輸出函數(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ù)；出錯(cuò)，返回返值：正常，返回輸出字節(jié)數(shù)；出錯(cuò)，返回eof(-1)eof(-1)3.5.3 格式輸入與輸出_格式輸出函數(shù) 輸出表：要輸出的數(shù)據(jù)（可以沒有，多個(gè)時(shí)以輸出表：要輸出的數(shù)據(jù)（可以沒有，多個(gè)時(shí)以“,”分隔）分隔）

17、格式控制串：包含兩種信息格式控制串：包含兩種信息格式說明：格式說明： %修飾符修飾符格式字符格式字符 ，用于指定，用于指定輸出格式輸出格式普通字符或轉(zhuǎn)義序列：原樣輸出普通字符或轉(zhuǎn)義序列：原樣輸出 格式字符格式字符d,ix,xoucse,efg%格式字符：十六進(jìn)制無符號(hào)整數(shù)不帶符號(hào)十進(jìn)制整數(shù)十進(jìn)制整數(shù)指數(shù)形式浮點(diǎn)小數(shù)單一字符字符串八進(jìn)制無符號(hào)整數(shù)小數(shù)形式浮點(diǎn)小數(shù)e和f中較短一種百分號(hào)本身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% 說明 格式字符要用小寫 格式字符與輸出項(xiàng)個(gè)數(shù)應(yīng)相同，按先后順序一一對(duì)應(yīng) 輸出轉(zhuǎn)換:格式字符與輸出項(xiàng)類型不一致,自動(dòng)按指定格式輸出例 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ù)，存入地址表指定的 存儲(chǔ)單元中存儲(chǔ)單元中, ,并

20、按回車鍵結(jié)束并按回車鍵結(jié)束返值：正常，返回輸入數(shù)據(jù)個(gè)數(shù)返值：正常，返回輸入數(shù)據(jù)個(gè)數(shù) 地址表：變量的地址，常用取地址運(yùn)算符& 格式字符: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ù)指定輸入數(shù)據(jù)寬度，遇空格或不可轉(zhuǎn)換字符則結(jié)束抑制符，指定輸入項(xiàng)讀入后不賦給變量 輸入分隔符的指定 一般以空格、tab或回車鍵作為分隔符 其它字符做分隔符：格式串中兩個(gè)格式符間字符例 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”格式符時(shí)，空格和轉(zhuǎn)義字符作為有效字符輸入如 scanf(“%c%c%c”,&c1,&c2,&c3); 若輸入abc 則ac1, c2, b c3 輸入數(shù)據(jù)時(shí)，遇以下情況認(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ù)沒有輸出功能(即不