第2章算法與C語言程序PPT課件

1、第第2章章 算法與算法與C語言程序語言程序程序程序（1）數(shù)據(jù)的描述：數(shù)據(jù)的類型和組織形式（）數(shù)據(jù)的描述：數(shù)據(jù)的類型和組織形式（數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)） （2）操作的描述：操作步驟（）操作的描述：操作步驟（算法算法) 沃思指出：沃思指出： 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)+算法算法=程序程序 確切的說，除上述要素外，還要采取結(jié)構(gòu)化程序設(shè)計的方法和確切的說，除上述要素外，還要采取結(jié)構(gòu)化程序設(shè)計的方法和用何種語言來設(shè)施。用何種語言來設(shè)施。 程序程序=數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)+算法算法 +程序設(shè)計方法程序設(shè)計方法+語言工具及環(huán)境語言工具及環(huán)境數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)： 反映各種類型數(shù)據(jù)的構(gòu)造形式，是計算機加工處理的對象反映各種類型數(shù)據(jù)的

2、構(gòu)造形式，是計算機加工處理的對象算法：算法： 為解決某一特定問題而采取的確定的有限的步驟，它是程序為解決某一特定問題而采取的確定的有限的步驟，它是程序設(shè)計的靈魂，解決做什么和怎么做設(shè)計的靈魂，解決做什么和怎么做 程序設(shè)計方法：程序設(shè)計方法： 根據(jù)數(shù)據(jù)類型和算法用計算機語言加以實現(xiàn)，程序中的操作根據(jù)數(shù)據(jù)類型和算法用計算機語言加以實現(xiàn)，程序中的操作語句實際上是算法的具體體現(xiàn)，不了解算法就談不上程序設(shè)計語句實際上是算法的具體體現(xiàn)，不了解算法就談不上程序設(shè)計 語言工具和環(huán)境：語言工具和環(huán)境： 用計算機語言編制的程序需相應(yīng)的編譯系統(tǒng)和硬件環(huán)境加以用計算機語言編制的程序需相應(yīng)的編譯系統(tǒng)和硬件環(huán)境加以實施實

3、施計算機求解問題的步驟計算機求解問題的步驟問題定義問題定義 - 明確問題明確問題需求分析需求分析 - 精確描述精確描述系統(tǒng)設(shè)計系統(tǒng)設(shè)計 - 模型或算法模型或算法系統(tǒng)實現(xiàn)系統(tǒng)實現(xiàn) - 程序編制程序編制系統(tǒng)運行系統(tǒng)運行 - 運行、求解運行、求解2.2 算法的概念算法的概念 做事情都有做事情都有方法、步驟（順序）方法、步驟（順序）決定事情成決定事情成敗敗1、算法：計算機求解末個問題而采用的具體方法、步驟、算法：計算機求解末個問題而采用的具體方法、步驟2、兩大類計算機算法：、兩大類計算機算法： 數(shù)值運算算法：求數(shù)值解、成熟數(shù)值運算算法：求數(shù)值解、成熟 非數(shù)值運算算法：事務(wù)管理、廣泛非數(shù)值運算算法：事務(wù)

4、管理、廣泛3、算法的特性（、算法的特性（p18）：有窮性、確定性、有效性等）：有窮性、確定性、有效性等4、算法的描述：有多種、算法的描述：有多種 歸納為兩大類：文字歸納為兩大類：文字 圖形（符號）圖形（符號）2.3 算法的描述算法的描述算法常用的方法：算法常用的方法： 自然語言、傳統(tǒng)流程圖、結(jié)構(gòu)化流程圖、偽代碼等自然語言、傳統(tǒng)流程圖、結(jié)構(gòu)化流程圖、偽代碼等 2.3.1用自然語言表示算法用自然語言表示算法 自然語言：自然語言： 人們?nèi)粘Ｊ褂玫恼Z言，可以是英、中、中英文結(jié)合人們?nèi)粘Ｊ褂玫恼Z言，可以是英、中、中英文結(jié)合 特點：特點： 通俗易懂通俗易懂 缺點：缺點： 文字冗長，易出現(xiàn)岐義性，表示算法的

5、含義不太嚴格文字冗長，易出現(xiàn)岐義性，表示算法的含義不太嚴格，根據(jù)上下文才能判斷其含義。，根據(jù)上下文才能判斷其含義。2.3.2用流程圖表示算法用流程圖表示算法 ANSI規(guī)定的流程圖符號，已為世界各國采用，用圖框表示規(guī)定的流程圖符號，已為世界各國采用，用圖框表示操作，用圖形表示算法。操作，用圖形表示算法。 特點：直觀、形象、靈活、易于理解，可表示任何算法。特點：直觀、形象、靈活、易于理解，可表示任何算法。 起止框：起止框： 輸入輸出框：輸入輸出框： 判別框：判別框： 處理框：處理框： 流程線：流程線： 注釋框：注釋框： 連接點：連接點： 2.3.3 用用N-S流程圖表示算法流程圖表示算法 1973

6、年美國學(xué)者年美國學(xué)者I.Nassi和和B.Shneiderman提出了一種新的流程提出了一種新的流程圖形式圖形式 特點：去掉帶箭頭的流程線，全部算法在一個矩形框內(nèi)，在特點：去掉帶箭頭的流程線，全部算法在一個矩形框內(nèi)，在該框內(nèi)還可包含從屬于它的框，這種流程圖稱為該框內(nèi)還可包含從屬于它的框，這種流程圖稱為N-S結(jié)構(gòu)化結(jié)構(gòu)化流程圖，受到人們歡迎。流程圖，受到人們歡迎。 AB成立成立 A B不成立不成立P當當P1成立成立AA直到直到P1成立成立2.3.4 用偽代碼表示算法用偽代碼表示算法 它是介于自然語言和計算機語言之間的文字和符號它是介于自然語言和計算機語言之間的文字和符號來描述算法。來描述算法。

7、特點：自上而下書寫，每行表示一個基本操作，可特點：自上而下書寫，每行表示一個基本操作，可用中、英、中英書寫。用中、英、中英書寫。 原則：意思要表達清楚，格式要清晰易懂。原則：意思要表達清楚，格式要清晰易懂。 例：求例：求 5!用流程圖算法用流程圖算法開始開始1 t2 iti ti+1 ii 5打印打印 t結(jié)束結(jié)束NY2i1 tt i ti +1 i直到直到 i 5打印打印t用用N-SN-S圖圖 表示算法表示算法用偽代碼表示用偽代碼表示 BEGIN（算法開始）（算法開始） 1t 2i While i501 igi 80 打印打印ni和和gii+1 ii 50結(jié)束結(jié)束開始開始NNNYYY用流程圖算

8、法用流程圖算法用用N-S流程圖表示流程圖表示1i輸入輸入ni , gii+1i直到直到i501i gi =80 是是否否輸出輸出ni , gii+1i直到直到 i 50例：例： 將將50名學(xué)生中成績在名學(xué)生中成績在80分以上者的學(xué)號、成績打印出來分以上者的學(xué)號、成績打印出來 BEGIN（算法開始）（算法開始） 1i While i=50 input ni and gi i+1 i 1i While i=80 print ni and gi i+1i END（算法結(jié)束）（算法結(jié)束）用偽代碼表示用偽代碼表示例例 用流程圖算法判斷從用流程圖算法判斷從2000-2500年每一年是否是閏年年每一年是否是

9、閏年 開始開始2000 yy不能被不能被 4整除整除y不能被不能被 100整除整除y不能被不能被 400整除整除打印打印y“是閏年是閏年”打印打印y“不是閏年不是閏年”打印打印y“是閏年是閏年”打印打印y“不是閏年不是閏年”y+1 yy2500結(jié)束結(jié)束YYYYNNNN例例 判定閏年的算法用判定閏年的算法用N-S圖表示圖表示 2000 yy / 100 的余數(shù)不為的余數(shù)不為 0是是否否y / 4 的余數(shù)為的余數(shù)為 0是是否否打印打印Y “是閏年是閏年”打印打印Y “非閏年非閏年”y / 400 的的 余數(shù)為余數(shù)為 0是是否否打印打印Y “是閏年是閏年”打印打印Y “非閏年非閏年”y+1 y直到直

10、到 y2500例例 用流程圖算法求用流程圖算法求： 開開 始始1 sum2 deno1 sign(-1)signsignsign(1/deno)termsum+termsumdeno+1denodeno100結(jié)結(jié) 束束NY1001991.4131211例例 求求 算法用算法用N-S流程圖表示流程圖表示 1sum2deno1sign(-1)signsignSum+termsumdeno+1deno直到直到 deno 100打印打印 sum1001991.4131211termdenosign1例例 求求 用偽代碼表示算法用偽代碼表示算法 BEGIN （算法開始）（算法開始） 1sum 2deno

11、 1sign While deno 打印打印n”是素數(shù)是素數(shù)”結(jié)結(jié) 束束NNYY三種基本結(jié)構(gòu)和改進的流程圖三種基本結(jié)構(gòu)和改進的流程圖1966年年Bohra和和Jacopini提出的三種基本結(jié)構(gòu)，表示良好結(jié)構(gòu)算法提出的三種基本結(jié)構(gòu)，表示良好結(jié)構(gòu)算法（1）順序結(jié)構(gòu)）順序結(jié)構(gòu)（2）選擇（選取、分支）結(jié)構(gòu)）選擇（選取、分支）結(jié)構(gòu)（3）循環(huán)（重復(fù)）結(jié)構(gòu)）循環(huán)（重復(fù)）結(jié)構(gòu) 當（當（while）型循環(huán)結(jié)構(gòu)）型循環(huán)結(jié)構(gòu) 功能：給定條件功能：給定條件P1成立時，執(zhí)行成立時，執(zhí)行A， 執(zhí)行完后再判斷條件是否成立，如執(zhí)行完后再判斷條件是否成立，如 此反復(fù)，直到某次此反復(fù)，直到某次P1條件不成立為止條件不成立為止 例

12、：用當型循環(huán)實現(xiàn)例：用當型循環(huán)實現(xiàn)5個數(shù)的打印個數(shù)的打印 輸出用傳統(tǒng)流程圖算法實現(xiàn)輸出用傳統(tǒng)流程圖算法實現(xiàn) bP1A成立成立ax+1 x0 xX 5 ?打印打印x值值NY直到型（直到型（Until）循環(huán)）循環(huán) 功能：先執(zhí)行功能：先執(zhí)行A，然后判斷給定的條件，然后判斷給定的條件P2是是 否成立，若成立，再執(zhí)行否成立，若成立，再執(zhí)行A，如此反復(fù)，直到，如此反復(fù)，直到 P2成立為止，此時不在執(zhí)行成立為止，此時不在執(zhí)行A，從，從b點結(jié)束。點結(jié)束。 例：用直到型循環(huán)實現(xiàn)例：用直到型循環(huán)實現(xiàn)5個數(shù)個數(shù)的打印輸出的打印輸出 用傳統(tǒng)流程圖算法實現(xiàn)用傳統(tǒng)流程圖算法實現(xiàn) 0 xx+1 x打印打印 xx 5NYAP

13、2不成立不成立成立成立ab三種結(jié)構(gòu)的共點：三種結(jié)構(gòu)的共點： (1)只有一個入口只有一個入口 (2)只有一個出口，選擇框上的兩個出口不代表結(jié)構(gòu)只有一個出口，選擇框上的兩個出口不代表結(jié)構(gòu) (3)結(jié)構(gòu)內(nèi)的每一部分都有機會被執(zhí)行到，結(jié)構(gòu)內(nèi)的每一部分都有機會被執(zhí)行到， 每一框內(nèi)都應(yīng)有一條從入口到出口的路徑通過它。每一框內(nèi)都應(yīng)有一條從入口到出口的路徑通過它。 右圖的結(jié)構(gòu)中沒有一條入口到出口通過右圖的結(jié)構(gòu)中沒有一條入口到出口通過A框?？颉?(4)結(jié)構(gòu)內(nèi)不能存在死循環(huán)結(jié)構(gòu)內(nèi)不能存在死循環(huán) 結(jié)構(gòu)化程序設(shè)計的優(yōu)點結(jié)構(gòu)化程序設(shè)計的優(yōu)點 用三種基本結(jié)構(gòu)組成的程序是結(jié)構(gòu)化程序用三種基本結(jié)構(gòu)組成的程序是結(jié)構(gòu)化程序優(yōu)點：優(yōu)

14、點：易易編、編、易易讀、讀、易易懂、懂、易易維護維護強調(diào)程序設(shè)計風(fēng)格和程序結(jié)構(gòu)的規(guī)范化強調(diào)程序設(shè)計風(fēng)格和程序結(jié)構(gòu)的規(guī)范化核心思想：核心思想：自頂向上，逐步細化，模塊化設(shè)計，結(jié)構(gòu)化編碼自頂向上，逐步細化，模塊化設(shè)計，結(jié)構(gòu)化編碼P1AAB實踐證明：實踐證明：由三種結(jié)構(gòu)組成的算法結(jié)構(gòu)可以解決任何復(fù)雜問題。由三種結(jié)構(gòu)組成的算法結(jié)構(gòu)可以解決任何復(fù)雜問題。 結(jié)論：結(jié)論：基本結(jié)構(gòu)所構(gòu)成的算法，屬結(jié)構(gòu)化算法，它不存在無基本結(jié)構(gòu)所構(gòu)成的算法，屬結(jié)構(gòu)化算法，它不存在無規(guī)律的轉(zhuǎn)向，只在基本結(jié)構(gòu)內(nèi)才允許存在分支和向前規(guī)律的轉(zhuǎn)向，只在基本結(jié)構(gòu)內(nèi)才允許存在分支和向前或向后跳轉(zhuǎn)?；蛳蚝筇D(zhuǎn)。 以上所述的四個基本特點，人們還

15、可自己定義基本結(jié)以上所述的四個基本特點，人們還可自己定義基本結(jié)構(gòu)，并由這些基本結(jié)構(gòu)組成結(jié)構(gòu)化程序，如多分支選構(gòu)，并由這些基本結(jié)構(gòu)組成結(jié)構(gòu)化程序，如多分支選擇結(jié)構(gòu)等，但它們都是由三種基本結(jié)構(gòu)派生出來的。擇結(jié)構(gòu)等，但它們都是由三種基本結(jié)構(gòu)派生出來的。 用計算機語言表示算法用計算機語言表示算法 要完成一項工作：要完成一項工作： （1）設(shè)計算法）設(shè)計算法 （2）實現(xiàn)算法）實現(xiàn)算法 設(shè)計算法的目的：是實現(xiàn)算法設(shè)計算法的目的：是實現(xiàn)算法 實現(xiàn)算法的一般方式：實現(xiàn)算法的一般方式： （1）人工心算）人工心算 （2）筆算、算盤）筆算、算盤 （3）計算器）計算器計算機無法識別流程圖和偽代碼計算機無法識別流程圖和偽

16、代碼 計算機實現(xiàn)算法的過程：計算機實現(xiàn)算法的過程： 用計算機語言編寫的程序才能被計算機識別、用計算機語言編寫的程序才能被計算機識別、解釋、執(zhí)行（編輯、編譯、連接，生成可執(zhí)行程序解釋、執(zhí)行（編輯、編譯、連接，生成可執(zhí)行程序） 用計算機語言表示算法必須嚴格遵循所用語言用計算機語言表示算法必須嚴格遵循所用語言的語法規(guī)則的語法規(guī)則 下面用下面用C語言討論兩個簡例：語言討論兩個簡例： 例例 求求 5！ 前面討論前面討論的算法，用的算法，用C語言表語言表示示 main( ) int i,t; t=1; i=2; while(i=5) t=t*i; i=i+1; printf(“%d”,t); 用偽代碼表示

17、用偽代碼表示 BEGIN（算法開始）（算法開始） 1t 2i While i5打印打印t用用N-SN-S圖圖 表示算法表示算法細化細化變量定義與初始化變量定義與初始化內(nèi)循環(huán)內(nèi)循環(huán)賦值賦值選擇語句選擇語句3.2 C語句概述語句概述C程序：可由若干程序：可由若干源程序文件源程序文件組成，一個源文件可由若干組成，一個源文件可由若干函數(shù)函數(shù)和和預(yù)處理命令預(yù)處理命令及及全局變量聲明全局變量聲明部分組成。部分組成。 聲明部分：指出數(shù)據(jù)結(jié)構(gòu)，定義數(shù)據(jù)類型。聲明部分：指出數(shù)據(jù)結(jié)構(gòu)，定義數(shù)據(jù)類型。 函數(shù)函數(shù) 執(zhí)行部分：由語句組成，稱數(shù)據(jù)操作，對提供的數(shù)執(zhí)行部分：由語句組成，稱數(shù)據(jù)操作，對提供的數(shù) 據(jù)進行加工。據(jù)

18、進行加工。 語句：語句： 編譯指令，向計算機發(fā)布相應(yīng)的操作命令。編譯指令，向計算機發(fā)布相應(yīng)的操作命令。C程序組成的示意圖程序組成的示意圖 函數(shù)函數(shù) 1預(yù)處理命令預(yù)處理命令函數(shù)函數(shù) n全局變量聲明全局變量聲明函數(shù)首部函數(shù)首部函數(shù)體函數(shù)體局部變量聲明局部變量聲明執(zhí)行語句執(zhí)行語句C程序程序源程序文件源程序文件2源程序文件源程序文件 1源程序文件源程序文件 n文件：文件：存儲在存儲在磁盤磁盤上的信息集合，可以是上的信息集合，可以是一段程序一段程序，一一組數(shù)據(jù)組數(shù)據(jù)。 C源程序文件源程序文件：存儲在磁盤上的函數(shù)的集合，包括程序：存儲在磁盤上的函數(shù)的集合，包括程序執(zhí)行中用到的數(shù)。執(zhí)行中用到的數(shù)。注：注： （1）所有源程序文件中，只有）所有源程序文件中，只有一個源程序文件一個源程序文件中包含中包含一個主函數(shù)一個主函數(shù)main( ) ， 其余文件中包含的都是被調(diào)用函數(shù)。其余文件中包含的都是被調(diào)用函數(shù)。 （2）當各源文件獨自