第5章 程序的組織結(jié)構(gòu)ppt課件

1、5.3 自定義函數(shù)5.2 規(guī)范函數(shù)5.1 函數(shù)概述5.4 函數(shù)與數(shù)組的運(yùn)用實(shí)例 5.5 遞歸算法與遞歸函數(shù) 第5章 程序的組織構(gòu)造 5.1 函數(shù)概述構(gòu)造化程序設(shè)計(jì)方法的中心是自頂向下，逐漸求精，詳細(xì)的實(shí)現(xiàn)戰(zhàn)略是將復(fù)雜的問題逐漸分解成相對(duì)簡(jiǎn)單的子問題，這樣將有利于降低處理問題的難度，提高程序開發(fā)的效率。將一個(gè)問題分解成假設(shè)干個(gè)子問題的過程稱為模塊化。 在C程序中，模塊用函數(shù)實(shí)現(xiàn)。函數(shù)是構(gòu)成C程序的根本單位。它由函數(shù)首部和函數(shù)體兩個(gè)部分組成，函數(shù)首部包含函數(shù)的前往類型、函數(shù)稱號(hào)和參數(shù)表的聲明，函數(shù)體包含實(shí)現(xiàn)特定功能所需求執(zhí)行的語(yǔ)句序列。 5.2 規(guī)范函數(shù)C言語(yǔ)提供了很多規(guī)范函數(shù)，它們被放置在一同，

2、構(gòu)成了一個(gè)規(guī)范函數(shù)庫(kù)。 函數(shù)原型 函數(shù)原型是指不包含函數(shù)體的函數(shù)聲明。 C言語(yǔ)規(guī)定，一切的函數(shù)必需先定義后調(diào)用。對(duì)于規(guī)范函數(shù)而言，由于它們的定義曾經(jīng)在C言語(yǔ)提供的規(guī)范函數(shù)庫(kù)中，所以，人們?cè)谡{(diào)用它們的時(shí)候，只需求在程序的前面利用編譯預(yù)處置命令include將相應(yīng)的函數(shù)原型參與到程序中就可以了。例1：根據(jù)給定的兩個(gè)坐標(biāo)點(diǎn)x1,y1和x2，y2，計(jì)算兩點(diǎn)之間的間隔。 問題分析計(jì)算兩點(diǎn)之間間隔的公式為 d=在這個(gè)公式中含有平方和開平方的運(yùn)算，可以直接利用C言語(yǔ)提供的規(guī)范函數(shù)實(shí)現(xiàn)這兩個(gè)運(yùn)算。 算法描畫 #include #include main( ) int x1, y1, x2, y2; doubl

3、e distance; printf(nEnter 2 coordinates(x1,y1,x2,y2)n); scanf(%d%d%d%d, &x1, &y1, &x2, &y2); printf(nThe first coordinate is (%d,%d), x1, y1); printf(nThe second coordinate is (%d,%d), x2, y2); distance = sqrt(pow(x2-x1, 2) + pow(y2-y1, 2); printf(nThe distance is %f, distance); 程序代碼例2：擲骰子游戲。骰子是一個(gè)有六

4、個(gè)面的正方體，每個(gè)面分別印有16之間的小圓點(diǎn)代表點(diǎn)數(shù)。假設(shè)這個(gè)游戲的規(guī)那么是：兩個(gè)人輪番擲骰子6次，并將每次投擲的點(diǎn)數(shù)累加起來。點(diǎn)數(shù)多者獲勝；點(diǎn)數(shù)一樣平局。請(qǐng)編寫程序，模擬這個(gè)游戲的過程，并給出玩100盤之后,誰(shuí)是最終的獲勝者。 隨機(jī)數(shù)的產(chǎn)生及運(yùn)用實(shí)例 問題分析由于每個(gè)人擲骰子所得到的點(diǎn)數(shù)是隨機(jī)的，所以需求借助隨機(jī)數(shù)發(fā)生器，每次產(chǎn)生一個(gè)16之間的整數(shù)，以此模擬玩者擲骰子的點(diǎn)數(shù)。為了計(jì)算在每盤中，甲、乙兩人所擲的點(diǎn)數(shù)，需求定義兩個(gè)int型變量d1，d2，用于作為記錄每個(gè)人投擲點(diǎn)數(shù)的累加器。為了記錄每個(gè)人的獲勝盤數(shù)，需求再定義兩個(gè)int型變量c1，c2，用于記錄每個(gè)人獲勝的盤數(shù)。算法描畫 #inc

5、lude #include main() int d1, d2, c1, c2, i, j; c1 = c2 = 0; /* 初始化 */ randomize( ); /* 初始化隨機(jī)數(shù)產(chǎn)生器 */ for (i=1; i=100; i+) /* 模擬游戲過程 */ d1 = d2 = 0; for (j=1; jd2) c1+; /* 累加獲勝盤數(shù) */ else if (d1c2) /* 輸出最終獲勝者信息 */ printf(nThe first win.); else if (c1c2) printf(nThe second win.); else printf(They tie.);

6、程序代碼5.3 自定義函數(shù) 函數(shù)的定義 根本格式 ； 例: double distance(int x, int y) double d; d = sqrt(x*x+y*y); return d; C言語(yǔ)規(guī)定，一個(gè)函數(shù)可以有前往值，也可以沒有前往值。假設(shè)有前往值，前往值的類型在函數(shù)名前聲明，并在函數(shù)體中利用return 語(yǔ)句將前往值前往；假設(shè)沒有前往值，在函數(shù)名前聲明void。默許的前往類型是int。 函數(shù)名不但應(yīng)該符合C言語(yǔ)的自定義標(biāo)識(shí)符命名規(guī)范，還應(yīng)該“見名知意。參數(shù)表是函數(shù)之間交換信息的接口。既可以經(jīng)過它將外界的數(shù)據(jù)傳送給函數(shù)，也可以經(jīng)過它將函數(shù)的操作結(jié)果帶出函數(shù)。假設(shè)方式參數(shù)屬于一維數(shù)

7、組類型，無(wú)須指出一維數(shù)組的元素個(gè)數(shù)。函數(shù)體是函數(shù)的中心部分，在這里列出了需求執(zhí)行的語(yǔ)句序列。 函數(shù)的調(diào)用 函數(shù)調(diào)用語(yǔ)句的根本格式為： ；真實(shí)參數(shù)與方式參數(shù)的數(shù)據(jù)類型和個(gè)數(shù)一一對(duì)應(yīng)。 函數(shù)的前往值在聲明函數(shù)的時(shí)候，函數(shù)名前運(yùn)用了保管字void，闡明這個(gè)函數(shù)沒有前往值；否那么，這個(gè)函數(shù)執(zhí)行終了后，應(yīng)該前往一個(gè)相應(yīng)類型的數(shù)值。 return 表達(dá)式；參數(shù)的傳送 定義函數(shù)時(shí)所給的參數(shù)被稱為方式參數(shù)，這是由于當(dāng)函數(shù)沒有處于執(zhí)行形狀時(shí)，系統(tǒng)并不為這些參數(shù)分配存儲(chǔ)空間，換言之，這些參數(shù)此時(shí)并不存在，只是用來闡明在調(diào)用這個(gè)函數(shù)時(shí)需求在這個(gè)位置向函數(shù)提供的數(shù)據(jù)類型，因此，在調(diào)用函數(shù)之后，參數(shù)傳送需求閱歷兩個(gè)根本

8、步驟：首先，根據(jù)方式參數(shù)的聲明格式，為每一個(gè)方式參數(shù)分配存儲(chǔ)空間；然后再將真實(shí)參數(shù)的值賦給對(duì)應(yīng)的方式參數(shù)。 例3：輸出乘法口訣表。乘法口訣表又被稱為“九九表，是一種小學(xué)生在學(xué)習(xí)乘法運(yùn)算時(shí)需求熟背的一個(gè)口訣表。它是一個(gè)9行9列的二維表格，加上一個(gè)行標(biāo)題和一個(gè)列標(biāo)題，顯示出來應(yīng)該是10行10列。自定義函數(shù)的運(yùn)用實(shí)例 問題分析行與行之間可以采用假設(shè)干個(gè)“=或“-字符表示表格之間的線段，為此，可以定義一個(gè)函數(shù)，專門用來延續(xù)地顯示假設(shè)干個(gè)字符，以防止在每次需求顯示線段的時(shí)候，都反復(fù)地書寫相應(yīng)的語(yǔ)句序列。 #include void drawLine(int n,char ch); /* 延續(xù)顯示n個(gè)ch

9、字符 */main() int i,j; printf(n 9.9 tablen); /* 顯示表名 */ drawLine(30, =); /* 顯示每列的標(biāo)題 */ printf(n 1 2 3 4 5 6 7 8 9); drawLine(30, =); for (i=1; i=9; i+) /* 顯示每行的內(nèi)容 */ printf(n%3d, i); for (j=1; j=9; j+) printf(%3d, i*j); if (i9) drawLine(30, -); else drawLine(30, =); void drawLine(int n, char ch) /*延續(xù)顯

10、示n個(gè)ch字符*/ int i; putchar(n); /*換行*/ for (i=1; i=n; i+) putchar(ch); /*延續(xù)顯示n個(gè)字符ch*/ 例4：計(jì)算要求準(zhǔn)確度到達(dá)10-6。 問題分析在這個(gè)公式中，第i項(xiàng)的分子是xi；分母是i！。為了便于計(jì)算每一項(xiàng)的數(shù)值，設(shè)計(jì)了兩個(gè)函數(shù)power( )和factorial( ) 分別用來完成計(jì)算xi和i!的義務(wù)。另外，為了更好地表達(dá)模塊化的設(shè)計(jì)思緒，再設(shè)計(jì)一個(gè)函數(shù)e( ) 用于計(jì)算ex。 算法描畫 #include long power(int x, int y);long factorial(int n);double e(int

11、x);main( ) int x; printf(nEnter x:); scanf(%d, &x); printf(ne%d=%f, x, e(x);long power(int x, int y) /* 計(jì)算xy */ long p = 1; int i; for (i=1; i=y; i+) p = p*x; return p;程序代碼long factorial(int n) /* 計(jì)算n! */ int i; long f = 1; for (i=2; i= 1E-6 ); /* 精度的檢查 */ return result;程序代碼5.4函數(shù)與數(shù)組的運(yùn)用實(shí)例 計(jì)算最長(zhǎng)文本行 所謂文

12、本行是指以換行符n作為終了標(biāo)志的文本序列。 例5：從鍵盤輸入一組文本行，求出最長(zhǎng)行并且輸出。 問題分析從問題的求解要求可知，沒有必要保管輸入的一切文本行。只需保管曾經(jīng)輸入各行中的最長(zhǎng)行，以及剛輸入的當(dāng)前行。設(shè)計(jì)一個(gè)專門用于計(jì)算最長(zhǎng)文本行的函數(shù)void readline(char maxline )。其實(shí)現(xiàn)過程為：一邊輸入文本行保管于數(shù)組line、一邊與當(dāng)前最長(zhǎng)的文本行長(zhǎng)度進(jìn)展比較。假設(shè)新輸入的文本行更長(zhǎng)，那么更新記錄最長(zhǎng)文本行的信息，最后得到的最長(zhǎng)文本行將經(jīng)過參數(shù)帶出去。算法描畫 #include #include void readline(char maxline );main() cha

13、r maxline80=; readline(maxline);/* 輸入并計(jì)算最長(zhǎng)行 */ printf(nThe longest line is:n); puts(maxline);/* 輸出最長(zhǎng)行 */程序代碼void readline(char maxline ) /* 輸入并計(jì)算最長(zhǎng)文本行 */ char line80; int maxlength; int n; maxlength=0; /*初始化*/ line0=0; printf(nEnter text lines:n); do gets(line); /*輸入文本行*/ n = strlen(line); if (nstrl

14、en(maxline) /*與記錄的最長(zhǎng)文本行進(jìn)展比較*/ maxlength = n; /*更新記錄最長(zhǎng)文本行的信息*/ strcpy(maxline, line); while (n0);程序代碼冒泡排序?yàn)榱吮阌诓檎摇⒔y(tǒng)計(jì)，排序是一種經(jīng)常需求進(jìn)展的操作。排序的方法有很多種，上一章中引見的簡(jiǎn)單項(xiàng)選擇擇排序是一種基于選擇手段實(shí)現(xiàn)的排序方法。冒泡排序的根本思緒是不斷地將一切相鄰數(shù)據(jù)進(jìn)展比較，假設(shè)前面的數(shù)據(jù)大于后面的數(shù)據(jù)ajaj+1，就將兩個(gè)位置的數(shù)據(jù)進(jìn)展交換，最終實(shí)現(xiàn)將一切的數(shù)據(jù)按照非遞減的順序重新陳列的目的。 問題分析將整個(gè)待排序的數(shù)據(jù)序列劃分成有序區(qū)域和無(wú)序區(qū)域。初始形狀有序區(qū)域?yàn)榭?，無(wú)序區(qū)

15、域包括一切待排序的數(shù)據(jù)。對(duì)無(wú)序區(qū)域從前向后依次對(duì)相鄰的兩個(gè)數(shù)據(jù)進(jìn)展比較，假設(shè)逆序那么將其交換，從而使得較小的數(shù)據(jù)像泡沫一樣“飄浮向前，較大的數(shù)據(jù)“下沉向后。每經(jīng)過一趟冒泡排序，都會(huì)使無(wú)序區(qū)域中的最大數(shù)據(jù)進(jìn)入有序區(qū)域。假設(shè)有n個(gè)數(shù)據(jù)等待排序，那么最多經(jīng)過n-1趟冒泡排序就可以將一切的數(shù)據(jù)陳列好。 例6：冒泡排序。 算法描畫 #include #include #define NUM 10void input(int value ); void output(int value );void sort(int value );main( ) int valueNUM; /* 存儲(chǔ)待排序的數(shù)據(jù)數(shù)列

16、*/ input(value); output(value); sort(value); output(value);void input(int value ) /* 輸入待排序數(shù)據(jù) */ int i; printf(nEnter %d integers:,NUM); for (i=0; iNUM; i+) scanf(%d, &valuei);程序代碼void output(int value ) /* 輸出顯示數(shù)據(jù)數(shù)列 */ int i; printf(n); for (i=0; i=1; i-) /* 控制排序趟數(shù) */ for (j=0; jvaluej+1) /* 假設(shè)兩個(gè)相鄰數(shù)據(jù)

17、逆序，交換 */ temp = valuej; valuej = valuej+1; valuej+1 = temp; 程序代碼5.5 遞歸算法與遞歸函數(shù) 概述n!其含義為1234(n-1) n。從這個(gè)數(shù)學(xué)公式中可以發(fā)現(xiàn)， n!等于n與n-1！的乘積。即將計(jì)算n! 的過程分解成n與n-1！的乘積；這樣分解的子問題除了n的值以外，與原問題具有一樣的特征，所以求解子問題的根本方法與求解整個(gè)問題所采用的方法一樣。具有這種特征的求解算法被稱為遞歸算法， 實(shí)現(xiàn)階乘遞歸算法的遞歸函數(shù) long fact(int n) if (n=0) return 1;else return n* fact(n-1);

18、y=fact(3) 3*fact(2)2*fact(1)1*fact(0)111*112*123*26遞歸函數(shù)的調(diào)用過程 問題分析處理這個(gè)問題似乎有些復(fù)雜，但采用遞歸方式就簡(jiǎn)單多了。3個(gè)數(shù)的全陳列是每個(gè)數(shù)輪番充任一次第一個(gè)數(shù)，再加上后面n-1個(gè)數(shù)的全陳列，而求解n-1個(gè)數(shù)的全陳列方法與求解n個(gè)數(shù)的全陳列方法完全一樣，因此，可以設(shè)計(jì)一個(gè)遞歸函數(shù)，實(shí)現(xiàn)求n個(gè)數(shù)全陳列的操作。思索到每次遞歸過程中，將針對(duì)n個(gè)數(shù)據(jù)進(jìn)展陳列，而這些數(shù)據(jù)來自同一數(shù)據(jù)序列，故設(shè)置數(shù)組保管數(shù)據(jù)序列，以數(shù)組名和數(shù)據(jù)個(gè)數(shù)作為函數(shù)的參數(shù)。 例7：求解n個(gè)數(shù)據(jù)的全陳列。#include #define NUM 3void anagra

19、m(int , int);void print(int );main( ) int dNUM; int i; for (i=0; i=0; i-) printf(%d ,di); 程序代碼void anagram(int d , int n) /* 求解n的全陳列 */ int i, j, temp; if (n=1) /* n=1直接輸出 */ print(d); return; for (i=0; in; i+) anagram(d, n-1);/* 對(duì)后面n-1個(gè)數(shù)全陳列 */ temp = d0; /* 輪換第一個(gè)位置的數(shù) */ for (j=1; j=n-1; j+) dj-1 =

20、dj;/* 將每個(gè)數(shù)據(jù)向前移 */ dn-1 = temp; 程序代碼用遞歸函數(shù)實(shí)現(xiàn)二分查找二分查找的問題，它是對(duì)有序數(shù)列進(jìn)展查找操作的一種有效方法。實(shí)踐上，這種查找方法是一個(gè)遞歸的過程。 問題分析二分查找也是信息處置中常用的一個(gè)算法。為了提高這個(gè)算法的重用性，單獨(dú)設(shè)置一個(gè)函數(shù)來實(shí)現(xiàn)該算法是適當(dāng)?shù)?。二分查找算法可以描畫為：針?duì)一個(gè)曾經(jīng)從小到大排序的數(shù)據(jù)序列，用給定數(shù)據(jù)key與查找區(qū)間中央位置的數(shù)據(jù)比較，假設(shè)相等那么闡明查找勝利；否那么，假設(shè)key比中央位置的數(shù)據(jù)小，那么在前半個(gè)區(qū)間用同樣的方法繼續(xù)查找；否那么在后半個(gè)區(qū)間用同樣的方法繼續(xù)查找。因此，這是一個(gè)遞歸的過程。當(dāng)查找區(qū)間的長(zhǎng)度為0時(shí)，闡

21、明查找不勝利。 例8：采用遞歸方式實(shí)現(xiàn)二分查找。 #include #include #define NUM 10void input(int value );void output(int value );int search(int value , int key, int low, int high);main( ) int valueNUM, result, key; input(value); /* 輸入有序序列 */ output(value); /* 輸出有序數(shù)列 */ printf(nEnter a key:); /* 輸入待查找的數(shù)值 */ scanf(%d, &key);

22、result = search(value, key, 0, NUM-1); /* 調(diào)用二分查找函數(shù)進(jìn)展查找 */ if (result!=-1) /* 輸出查找結(jié)果 */ printf(nThe %d is the %dth element, key, result); else printf(nFail to find %d, key);程序代碼void input(int value ) /* 創(chuàng)建有序數(shù)列 */ int i; for (i=0; iNUM; i+) scanf(%d, &valuei);void output(int value ) /* 輸出數(shù)列 */int i;pr

23、intf(n);for (i=0; ihigh) return -1;/* 查找區(qū)間為空 */ mid = (low+high)/2;/* 求中間位置 */ if (valuemid=key)return mid;/* 得到查找的數(shù)據(jù)位置 */ if (keyvaluemid) return search(value, key, low, mid-1);/* 在下半?yún)^(qū)查找 */ else return search(value, key, mid+1, high);/* 在上半?yún)^(qū)查找 */ 程序代碼變量的生存期與作用域變量是存儲(chǔ)空間在程序中的一種表示，它承當(dāng)著存儲(chǔ)操作數(shù)據(jù)和結(jié)果的重?fù)?dān)，是程序中不可短少的主要元素。C言語(yǔ)規(guī)定，每個(gè)變量必需先定義后援用。人們將變量占據(jù)存儲(chǔ)空間的時(shí)間稱為變量的生存期，將變量可以援用的區(qū)域稱為變量的作用域。從作用域角度劃分全局變量：在函數(shù)外部定義的變量被稱為全局變量。部分變量：在函數(shù)內(nèi)部定義的變量，包括參數(shù)表中定義的方式參數(shù)被稱為部分變量。 在復(fù)合語(yǔ)句中定義的變量被稱為塊變量。 生存期在復(fù)合語(yǔ)句中定義的變量，其生存期為所在的復(fù)合語(yǔ)句塊中。 在函數(shù)內(nèi)部和方式參數(shù)表中定義的變量都屬于部分變量。作用域是定義這些變量的函數(shù)。全局變量的生存期是定義這個(gè)變量的程序文件，作用域是從定義處開場(chǎng)到程序文件的終了處為止。假設(shè)程序文件中的某些部分變量與之同名