C語言算法和基本程序設計

一個著名的公式

數據結構+算法=程序數據：計算機所能識別、存儲和處理的對象。數據的動態(tài)性。數據結構：確定數據對象及其存儲方式，并定義在這些數據對象上的運算集合。算法：為解決一個問題而采取的方法和步驟。第1頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第1頁。

算法的特性1有窮性

操作步驟是有限的，不是無限的。2確定性

每個步驟是確定的，無歧義性。3有零個或多個輸入4有一個或多個輸出5有效性

每一步驟能有效執(zhí)行，并得到確定結果。第2頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第2頁。3.1.2算法的評價標準1.正確性對任何合法的輸入，算法都會得出正確的結果。2.可讀性可讀性指算法被理解的難易程度。3.健壯性（魯棒性）健壯性即對非法輸入的抵抗能力。4.高效率與低存儲量需求通常，效率指的是算法執(zhí)行時間；存儲量指的是算法執(zhí)行過程中所需的最大存儲空間，兩者都與問題的規(guī)模有關。二者往往是一對矛盾，常?？梢杂每臻g換時間，也可以用時間換空間。第3頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第3頁。

怎樣表示一個算法用自然語言表示算法用流程圖表示算法用N-S流程圖表示算法用偽代碼表示算法用計算機語言表示算法

歧義性，描述分支、循環(huán)算法不方便第4頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第4頁。第5頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第5頁。起止框輸入輸出框處理框判斷框流程線連接點第6頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第6頁。【例3.1】求三個整數的和。求三個整數和的算法流程圖如圖所示。開始x+y+z=>sum輸出sum的值結束輸入x,y,z圖3.2求三個整數和的算法第7頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第7頁?！纠?.2】求最大公約數。m,n為正整數開始結束輸入m,n求m/n的余數rr=0?n=>m,r=>n輸出n是否第8頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第8頁。最大公因數的算法求最大公因數的最普遍的算法是歐幾里得算法，它最初是公元前由歐幾里得提出來的，有時也稱它為輾轉相除法．表述如下：

設給定m，n(m＞n)，令r0=m，r1=n，有

則得rk=gcd(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的倍數，b是a的約數rk-2=

qk-1qkrk+rk=(qk-1qk+1)rk第9頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第9頁。S1:求1×2=2S2:求2×3=6S3:求6×4=24??????天??！共需999個步驟，太可怕了。案例求1×2×3×4×······×1000S1:1p(p:被乘數)S2:2i(i:乘數)S3:p×ipS4:i+1iS5:若i≤1000,返回S3；否則，結束。只需5個步驟，簡單。第10頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第10頁。3.2結構化程序設計的方法

結構化程序設計思想采用了模塊分解與功能抽象和自頂向下、分而治之的方法，從而有效地將一個較復雜的程序系統設計任務分解成許多易于控制和處理的子程序，便于開發(fā)和維護，減少程序的出錯概率和提高軟件的開發(fā)效率。采用結構化程序設計方法應遵循以下原則。1.自頂向下即在程序設計時，先考慮總體，做出全局設計，然后再考慮細節(jié)進行局部設計，逐步實現精細化。這種方法稱為“自頂向下，逐步細化”的方法。2.模塊化就是將一個大任務分成若干個較小的部分，每一部分承擔一定的功能，稱為“功能模塊”。每個模塊可以分別編程和調試，然后組成一個完整的程序。模塊的劃分應遵循一些基本原則，如模塊內部聯系要緊密，關聯程度要高；模塊間的接口要盡可能簡單，以減少模塊間的數據傳遞。3.限制使用GOTO語句第11頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第11頁。

結構化的程序設計方法基本思路:把一個復雜問題的求解過程分階段進行,每個階段處理的問題都控制在人們容易理解和處理的范圍內.采用的方法:1自頂而下2逐步細化3模塊化設計4結構化編碼第12頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第12頁。三種基本結構1順序結構2選擇結構3循環(huán)結構3.3程序的基本結構第13頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第13頁。三種基本結構的特點1只有一個入口2只有一個出口pA3結構內的每一部分都有機會被執(zhí)行到AB4結構內沒有死循環(huán)第14頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第14頁。順序結構的流程圖符號ABabAB傳統流程圖N-S流程圖第15頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第15頁。選擇結構的流程圖符號Ap成立不成立BAp成立不成立傳統流程圖第16頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第16頁。選擇結構的流程圖符號（續(xù)）成立不成立ApBN-S流程圖第17頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第17頁。循環(huán)結構的流程圖符號Ap1成立不成立ab不成立Ap2成立ab傳統流程圖While型Until型第18頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第18頁。循環(huán)結構的流程圖符號（續(xù)）直到p1成立A當p1成立AWhile型Until型N-S流程圖第19頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第19頁。一個有用的結論已經證明：

三種基本結構的順序組成可以表示任何復雜的算法結構。由基本結構構成的算法，屬于“結構化”算法。第20頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第20頁。有關結構化算法的總結一個結構化的算法是由一些基本結構順序組成的；基本結構之間不存在向前或向后的跳轉，流程的轉移只存在于一個基本結構的范圍之內（如循環(huán)中的流程跳轉）；一個非結構化算法可以用一個等價的結構化算法代替，其功能不變。如果一個算法不能分解為若干個節(jié)本結構，則它必然不是一個結構化算法。第21頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第21頁。3.4順序結構程序設計1.表達式語句表達式語句是在各種表達式后加一個分號(；)形成一個表達式語句。2.空語句空語句直接由分號(；)組成，常用于控制語句中必須出現語句之處。它不做任何操作，只在邏輯上起到有一個語句的作用。例如：

;空語句也是一個語句，不產生任何動作?？照Z句常用于構成標號語句，標識程序中相關位置；循環(huán)語句中空循環(huán)體；模塊化程序中未實現的模塊及暫不鏈入的模塊。第22頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第22頁。3.函數調用語句由函數調用加上分號組成。4.復合語句是由一對花括號{}括起的若干個語句，語法上可以看成是一個語句。復合語句中最后一個語句的分號不能省略。例如下面是一個復合語句：{z=x；

x=y；

y=z;}凡是單一語句可以存在的位置，均可以使用復合語句。復合語句用在語法上是單一語句，而相應操作需多條語句描述的情況。

第23頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第23頁。5.控制語句控制語句有條件判斷語句(if、switch)，循環(huán)語句(for、while、do-while)，轉移語句(goto、continue、break、return)?？刂普Z句根據控制條件決定程序的執(zhí)行流程，控制語句不是順序執(zhí)行的。順序結構是C語言的基本結構，除非指示轉移，否則計算機自動以語句編寫的順序一句一句地執(zhí)行C語句。第24頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第24頁。C語言無I/O語句，I/O操作由函數實現#include<stdio.h>★字符輸出函數3.5數據的輸入與輸出

格式:putchar(c)參數:c為字符常量、變量或表達式功能：把字符c輸出到顯示器上返值：正常，為顯示的代碼值；出錯，為EOF(-1)第25頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第25頁?！纠?.3】

字符數據的輸出。#include<stdio.h>main(){chara,b;a=′r′;b=′e′;putchar(a);putchar(b);putchar(′d′);putchar(′\n′)；}運行后，在屏幕上顯示：red

第26頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第26頁。數據輸入★字符輸入函數

格式:getchar()功能：從鍵盤讀一字符返值：正常，返回讀取的代碼值；出錯,返回EOF(-1)注意：getchar()函數的括號中沒有參數，該函數的輸入一直到“回車”才結束?；剀嚽暗乃休斎胱址紩饌€顯示在屏幕上，但只有第一個字符作為函數的返回值。

第27頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第27頁。運行時，輸入xxx<回車>，在屏幕上顯示：x【例3.4】

單個字符的輸入和輸出。#include<stdio.h>main(){charch;/*從鍵盤上讀入字符直到“回車”結束*/ch=getchar(); /*顯示輸入的第一個字符*/putchar(ch); putchar(′\n′); /*換行*/}第28頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第28頁。【例3.5】

將小寫字母轉換成大寫。#include<stdio.h>main(){charch;ch=getche();putchar(ch-32);}若輸入b，在屏幕上顯示：

bB

第29頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第29頁。3.字符串輸入/輸出函數

字符串輸入函數gets()用來從鍵盤讀入一串字符。函數的調用形式：

gets(字符串變量名)；在輸入字符串后，必須用回車作為輸入結束。該回車符并不屬于這串字符，由一個“空操作字符(′\0′)”在串的最后來代替它。此時空格不能結束字符串的輸入，gets函數返回一個指針。字符串輸出函數puts()，將字符串數據(可以是字符串常量、字符指針或字符數組名)顯示在屏幕上并換行。函數的調用形式是：

puts(字符串數據)；第30頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第30頁?！纠?.6】

字符串的輸入和輸出。#include<stdio.h>main(){charstr［80］;gets(str);puts(str);}當輸入為“Howareyou?”，則輸出為：Howareyou?第31頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第31頁。格式：printf(“格式控制串”，輸出表)功能：按指定格式向顯示器輸出數據返值：正常，返回輸出字節(jié)數；出錯，返回EOF(-1)3.5.3格式輸入與輸出___格式輸出函數輸出表：要輸出的數據（可以沒有，多個時以“,”分隔）格式控制串：包含兩種信息格式說明：

%[修飾符]格式字符

，用于指定輸出格式普通字符或轉義序列：原樣輸出格式字符第32頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第32頁。d,ix,Xoucse,Efg%%格式字符：十六進制無符號整數不帶符號十進制整數十進制整數指數形式浮點小數單一字符字符串八進制無符號整數小數形式浮點小數e和f中較短一種百分號本身inta=567;printf(“%d”,a);inta=255;printf(“%x”,a);inta=65;printf(“%o”,a);inta=567;printf(“%u”,a);chara=65;printf(“%c”,a);printf(“%s”,“ABC”);floata=567.789;printf(“%e”,a);floata=567.789;printf(“%f”,a);floata=567.789;printf(“%g”,a);printf(“%%”);567ff101567AABC5.677890e+02567.789000567.789%說明 格式字符要用小寫格式字符與輸出項個數應相同，按先后順序一一對應輸出轉換:格式字符與輸出項類型不一致,自動按指定格式輸出例

main(){unsignedintu=65535;printf(”u=%d\n",u);}

輸出結果：u=-1例inta=3,b=4;printf(“%d%d\n”,a,b);printf(“a=%d,b=%d\n”,a,b);

例inta=3,b=4;printf(“%d%d\n”,a,b);printf(“a=%d,b=%d\n”,a,b);輸出結果:34a=3,b=4111111111111111165535第33頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第33頁。格式輸入函數格式:scanf(“格式控制串”，地址表）功能：按指定格式從鍵盤讀入數據，存入地址表指定的存儲單元中,并按回車鍵結束返值：正常，返回輸入數據個數地址表：變量的地址，常用取地址運算符&格式字符:d,i,o,x,u,c,s,f,e例scanf(“%d”,&a);

輸入：10

則a=10例scanf(“%x”,&a);

輸入：11

則a=17第34頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第34頁。附加格式說明符（修飾符）例scanf(“%4d%2d%2d”,&yy,&mm,&dd);

輸入19991015

則1999yy,10mm,15dd例scanf(“%3d%*4d%f”,&k,&f);

輸入12345678765.43則123k,8765.43f例scanf(“%2d%*3d%2d”,&a,&b);

輸入1234567則12a,67b例scanf(“%3c%2c”,&c1,&c2);

輸入abcde

則‘a’c1,‘d’c2l修飾符功能hm*用于d,o,x前，指定輸入為short型整數用于d,o,x前，指定輸入為long型整數用于e,f前，指定輸入為double型實數指定輸入數據寬度，遇空格或不可轉換字符則結束抑制符，指定輸入項讀入后不賦給變量第35頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第35頁。輸入分隔符的指定一般以空格、TAB或回車鍵作為分隔符其它字符做分隔符：格式串中兩個格式符間字符例scanf(“%d%o%x”,&a,&b,&c);printf(“a=%d,b=%d,c=%d\n”,a,b,c);

輸入123123123

輸出a=123,b=83,c=291例scanf(“%d:%d:%d”,&h,&m,&s);

輸入12:30:45則12h,30m,45s例scanf(“%d,%d”,&a,&b)

輸入3,4

則3a,4b例scanf(“a=%d,b=%d,c=%d”,&a,&b,&c);

輸入a=12,b=24,c=36第36頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第36頁。說明：用“%c”格式符時，空格和轉義字符作為有效字符輸入如scanf(“%c%c%c”,&c1,&c2,&c3);

若輸入abc

則ac1,

c2,bc3輸入數據時，遇以下情況認為該數據結束：遇空格、TAB、或回車遇寬度結束遇非法輸入如scanf(“%d%c%f”,&a,&b,&c);

若輸入1234a123o.26

則1234a,‘a’b,123c輸入函數留下的“垃圾”：例intx;charch;scanf(“%d”,&x);ch=getchar();printf(“x=%d,ch=%d\n”,x,ch);執(zhí)行：123輸出：x=123,ch=10例intx;charch;scanf(“%d”,&x);scanf(“%c”,&ch);printf(“x=%d,ch=%d\n”,x,ch);執(zhí)行：123輸出：x=123,ch=10解決方法：（1）用getchar()清除（2）用函數fflush(stdin)清除全部剩余內容(3)用格式串中空格或“%*c”來“吃掉”例intx;charch;scanf(“%d”,&x);

getchar();

scanf(“%c”,&ch);或scanf(“%*c%c”,&ch);

第37頁/共43頁C語言算法和基本程序設計全文共43頁，當前為第37頁。注意:

scanf()函數沒有輸出功能(即不會向屏幕顯示任何字符)也不能規(guī)定小數位數(m.n)典型錯誤:scanf(“a=%d,b=%d,c=%d

\n”,&a,&b,&c);scanf(“%5.2f“,&x);正確語句:

printf(“Inputa,b,c=“);scanf(“%d,%d,%d”,&a,&b,&c);printf(“\n”);/*不必要,因為x為實數格式輸入*/scanf(“%5f“,&x);第38頁/共43頁C