1.4 程序設計過程

要使計算機能夠完成某個任務，必須有相應的軟件，而軟件中最主要的部分就是程序。程序是計算機完成某個任務所需要的指令集合，通常程序設計都是基于高級語言。

程序設計就是教會計算機去完成某一特定的任務，即設計出完成某個任務的程序。它包括以下四個過程。

? 算法設計：設想計算機如何一步一步地完成這個任務，即將解決問題的過程分解成程序設計語言提供的一個個基本功能。

? 編碼：將算法用某種高級語言描述出來。

? 編譯、目標程序與鏈接：高級語言寫的程序必須被翻譯成硬件認識的機器語言，這個階段稱為編譯。機器語言表示的程序稱為目標程序。一個大的程序可能由很多部分組成，把這些部分的目標程序組合在一起稱為鏈接。

? 調試與維護：編好的程序不一定能正確完成給定的任務，或許是因為算法設計有問題，也可能是有一些特殊的情況沒有處理。糾正這些問題的過程稱為調試，經過調試的程序基本上認為是一個正確的程序，但仍可能有錯誤。在使用的過程中發現錯誤并改正錯誤；增加、刪除或修改功能的過程稱為程序的維護。

1.4.1 算法設計

算法設計

1.什么是算法

算法設計是設計一個使用計算機（更確切地講是某種程序設計語言）提供的基本動作來解決某一問題的方案，是程序設計的靈魂。算法設計的難點在于計算機提供的基本功能非常簡單，而人們要它完成的任務是非常復雜的。算法設計必須將復雜的工作分解成一個個簡單的、計算機能夠完成的基本動作。

解決問題的方案要成為一個算法，必須用清楚的、明確的形式來表達，以使人們能夠理解其中的每一個步驟，無二義性。算法中的每一個步驟必須有效，是計算機可以執行的操作。例如，若某一算法包含“用π的確切值與 r 相乘”這樣的操作，則這個方案就不是有效的，因為計算機無法算出π的確切值。而且，算法不能無休止地運行下去，必須在有限的時間內給出一個答案。綜上所述，算法必須具有以下幾個特點。

（1）表述清楚、準確，無二義性。

（2）可行性，即每一個步驟都是程序設計語言可以完成的基本動作。

（3）有限性，即可在有限步驟后得到結果，例如，無法設計一個計算的算法，因為沒有辦法讓i達到無窮大，這個程序將永遠運行，無法結束。一個合理的做法是為它提供一個上限值。

（4）有零個或多個輸入，它們是算法運行時需要從外界獲得的信息。如計算，則必須輸入n的值。而對于打印九九乘法表的算法，則不需要輸入值。

（5）有一個或多個輸出，即算法運行的結果。

有些問題非常簡單，一下子就可以想到相應的算法，沒有多大的麻煩就可寫一個解決該問題的程序；而當問題變得復雜時，就需要更多思考才能想出解決它的算法。與所要解決的問題一樣，各種算法的復雜性也千差萬別。大多數情況下，一個特定的問題可以有多個不同的解決方案（即算法），在編寫程序之前需要考慮許多潛在的解決方案，最終選擇一個合適的方案。

2.算法的表示

算法可以用不同的方法表示，常用的有自然語言、傳統的流程圖、結構化流程圖、偽代碼等方法。

流程圖是早期提出的一種算法表示方法，由美國國家標準化協會 ANSI 規定。流程圖用不同的圖形表示程序中的各種不同的標準操作。流程圖用到的圖形及含義如圖1-5所示。

例1.1 設計一個算法，求兩個整數相除的商。

求兩個數相除算法的流程圖表示如圖1-6所示。

例1.2 設計一個算法，判斷輸入的整數是否為素數。

素數是只能被 1 和自身整除的數。按照定義，1 不是素數，2 是素數。判斷n是否為素數的最簡單的方法是，首先判斷 1～n所有的整數是否能整除n，其次統計能整除n的整數個數r，最后檢查r的值是否為2，r的值為2是素數，否則不是素數。該算法的流程圖表示如圖1-7所示。

用流程圖表示算法直觀清晰，能夠清楚地表現出各個處理步驟之間的邏輯關系。但由于流程圖對流程線的使用沒有嚴格的限制，使用者可以隨意使流程轉來轉去，使人很難理解算法的邏輯，而且難以保證程序的正確性，同時流程圖占用的篇幅也較大。

隨著結構化程序設計的出現，流程圖被另一種稱為 N-S 的圖所代替。結構化程序設計規定程序只能由以下3種結構：順序結構、分支結構和循環結構組成。N-S圖用3種基本的框表示3種結構，如圖1-8所示。

既然程序可以由這些基本結構順序組合而成，那么基本結構之間的流程線就不再需要了，全部的算法可以寫在一個矩形框內。例如，解決例1.1的算法的 N-S 圖如圖1-9所示，解決例1.2的算法的N-S圖如圖1-10所示。

用流程圖和 N-S 圖表示算法直觀易懂，但畫起來太費勁。另一種表示算法的工具稱為偽代碼。偽代碼是介于自然語言和程序設計語言之間的一種表示方法。通常用程序設計語言中的控制結構表示算法的流程，用自然語言表示其中的一些操作。如果采用C語言的控制結構，則稱為偽C代碼。如果采用Pascal語言的控制結構，則稱為偽Pascal代碼。例如，解決例1.1算法的偽C代碼如圖1-11所示，解決例1.2算法的偽C代碼如圖1-12所示。本書主要采用偽代碼的表示方法。

3.算法的優劣

一個算法的好壞通常從以下幾個方面來衡量。

（1）正確性

這無疑是一個最重要的指標，算法當然要能夠正確地解決問題。

（2）可讀性

算法的可讀性指的是算法是否容易理解。在計算機剛出現時，程序的可讀性并不重要。因為當時的程序一般很短，而且是量身定做的，運行了一次后可能就不用了。而現在的軟件都是產品化，可能會運行很多年。在產品工作期間，可能會發現程序的某些錯誤或者程序的某些功能需要修改。如果程序寫得晦澀難懂，將會給修改程序帶來很大的麻煩。所以算法的邏輯盡量簡明易懂。

（3）健壯性

健壯性是指當輸入的數據非法時，算法必須有相應的處理。因為軟件的用戶不一定是專業人員，也不一定會認真閱讀軟件使用指南。不管用戶輸入的是什么數據，都要保證程序不會癱瘓。

（4）時間復雜度和空間復雜度

時間復雜度是算法的計算量與處理的問題規模之間的關系。空間復雜度是算法運行時占用的空間與處理的問題規模之間的關系。在不犧牲可讀性的前提下，盡量保證好的時間復雜度和空間復雜度。

1.4.2 編碼

編碼是將算法用具體的程序設計語言的語句表達出來，所以學習程序設計必須學習一種程序設計語言。本書采用的是C語言。

用程序設計語言描述的算法稱為程序，存儲在計算機中的程序通常稱為源文件。C 語言程序的源文件名的后綴必須是“.c”。輸入程序或修改程序內容的過程稱為文件的編輯。各個計算機系統的編輯過程差異很大，不可能用一種統一的方式來描述，因此在編輯源文件之前，必須先熟悉所用的機器上的編輯方法。很多操作系統也提供一些綜合編程的環境，如 VS2010就是 Windows 系統提供的一個綜合編程環境。綜合編程環境為程序員提供了從源文件編輯到程序運行過程中的所有環節的工作支持。

1.4.3 編譯與鏈接

計算機的硬件并不認識高級語言寫的程序。為了讓用高級語言編寫的程序能夠在不同的計算機系統上運行，必須將程序翻譯成該計算機特有的機器語言。在高級語言和機器語言之間執行這種翻譯任務的程序叫作編譯器。

編譯器將源文件翻譯成中間文件，這種中間文件稱為目標文件。目標文件由特定的計算機系統的機器語言組成。但目標文件不能直接運行，這是因為在現代程序設計中，程序員在編程序時往往會用到系統提供的工具或其他程序員提供的工具。程序運行時必然會用到這些工具的代碼。于是需要將目標文件和這些工具的目標文件捆綁在一起，這個過程稱為鏈接。鏈接以后的代碼稱為一個可執行文件。這是能直接在某臺計算機上運行的程序。系統提供的工具或用戶自己寫的一些工具程序通常被組織成一個庫。一個源文件到一個可執行文件的轉換過程如圖1-13所示。

在編譯過程中，編譯器會找出源文件中的語法錯誤和詞法錯誤，即不符合程序設計語言規范的地方。程序員可根據編譯器輸出的出錯信息來修改源文件，直到編譯器生成了正確的目標代碼。

1.4.4 調試與維護

語法錯誤還不是最令人沮喪的。往往程序失敗不是因為編寫的程序包含語法錯誤，而是程序合乎語法卻給出了不正確的答案或者根本沒給出答案。檢查程序便會發現程序中存在一些邏輯錯誤，程序員稱這種錯誤為 bug。找出并改正這種邏輯錯誤的過程稱為調試（debug），它是程序設計過程中一個重要的環節。調試一般需要運行程序，通過觀察程序的階段性結果來找出錯誤的位置和原因，并作相應的修改。

邏輯錯誤非常難以察覺。有時程序員非常確信程序的算法是正確的，但隨后卻發現它不能正確處理以前忽略了的一些情況；或者也許在程序的某個地方做了一個特殊的假定，但隨后卻忘記了；又或者可能犯了一個意想不到的錯誤。

程序的調試及測試只能發現程序中的錯誤，而不能證明程序是正確的。因此，在程序的使用過程中可能會不斷發現程序中的錯誤，或者發現程序的某些功能不盡如人意，需要修改。在使用時發現問題并改正的過程稱為程序的維護。

程序的維護需要修改源程序。但修改者可能并不是原來的開發者，或者離程序的開發已經經過了很長的時間了，此時需要相應的開發文檔和良好的程序風格來幫助修改者迅速定位到程序中需要修改的部分。