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

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

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

4、管理、廣泛3、算法的特性（、算法的特性（p18）：有窮性、確定性、有效性等）：有窮性、確定性、有效性等4、算法的描述：有多種、算法的描述：有多種 歸納為兩大類：文字歸納為兩大類：文字 圖形（符號）圖形（符號）2.3 算法的描述算法的描述算法常用的方法：算法常用的方法： 自然語言、傳統流程圖、結構化流程圖、偽代碼等自然語言、傳統流程圖、結構化流程圖、偽代碼等 2.3.1用自然語言表示算法用自然語言表示算法 自然語言：自然語言： 人們日常使用的語言，可以是英、中、中英文結合人們日常使用的語言，可以是英、中、中英文結合 特點：特點： 通俗易懂通俗易懂 缺點：缺點： 文字冗長，易出現岐義性，表示算法的

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

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

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

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

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

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

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

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

13、2不成立不成立成立成立ab三種結構的共點：三種結構的共點： (1)只有一個入口只有一個入口 (2)只有一個出口，選擇框上的兩個出口不代表結構只有一個出口，選擇框上的兩個出口不代表結構 (3)結構內的每一部分都有機會被執行到，結構內的每一部分都有機會被執行到， 每一框內都應有一條從入口到出口的路徑通過它。每一框內都應有一條從入口到出口的路徑通過它。 右圖的結構中沒有一條入口到出口通過右圖的結構中沒有一條入口到出口通過A框。框。 (4)結構內不能存在死循環結構內不能存在死循環 結構化程序設計的優點結構化程序設計的優點 用三種基本結構組成的程序是結構化程序用三種基本結構組成的程序是結構化程序優點：優

14、點：易易編、編、易易讀、讀、易易懂、懂、易易維護維護強調程序設計風格和程序結構的規范化強調程序設計風格和程序結構的規范化核心思想：核心思想：自頂向上，逐步細化，模塊化設計，結構化編碼自頂向上，逐步細化，模塊化設計，結構化編碼P1AAB實踐證明：實踐證明：由三種結構組成的算法結構可以解決任何復雜問題。由三種結構組成的算法結構可以解決任何復雜問題。 結論：結論：基本結構所構成的算法，屬結構化算法，它不存在無基本結構所構成的算法，屬結構化算法，它不存在無規律的轉向，只在基本結構內才允許存在分支和向前規律的轉向，只在基本結構內才允許存在分支和向前或向后跳轉。或向后跳轉。 以上所述的四個基本特點，人們還

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

16、代碼 計算機實現算法的過程：計算機實現算法的過程： 用計算機語言編寫的程序才能被計算機識別、用計算機語言編寫的程序才能被計算機識別、解釋、執行（編輯、編譯、連接，生成可執行程序解釋、執行（編輯、編譯、連接，生成可執行程序） 用計算機語言表示算法必須嚴格遵循所用語言用計算機語言表示算法必須嚴格遵循所用語言的語法規則的語法規則 下面用下面用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圖圖 表示算法表示算法細化細化變量定義與初始化變量定義與初始化內循環內循環賦值賦值選擇語句選擇語句3.2 C語句概述語句概述C程序：可由若干程序：可由若干源程序文件源程序文件組成，一個源文件可由若干組成，一個源文件可由若干函數函數和和預處理命令預處理命令及及全局變量聲明全局變量聲明部分組成。部分組成。 聲明部分：指出數據結構，定義數據類型。聲明部分：指出數據結構，定義數據類型。 函數函數 執行部分：由語句組成，稱數據操作，對提供的數執行部分：由語句組成，稱數據操作，對提供的數 據進行加工。據

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