做任何事情都要有一定的步驟，為了解決一個問題而采取的方法和步驟就稱為算法。C語言的算法是計算機算法，即計算機能夠執行的算法。只有明確了算法后，才能使應用程序實現某些功能。所以，通常人們會將算法稱為程序的靈魂。本文將詳細介紹C語言算法的基礎知識。

我們對算法的理解

一個程序應包括對數據的描述。在程序中要指定數據的類型和數據的組織形式（即數據結構，對操作的描述（即操作步驟），也就是算法（algorithm）。Wirth曾經提出了一個經典的公式：數據結構+算法=程序。而譚浩強的總結為：程序=算法+數據結構+程序設計方法+語言和環境

1.1　算法是程序的靈魂

當重新審視自己走過的路時，我越來越能理解算法的重要性。算法不僅是工具，而且還是程序的靈魂。在初涉這一領域時，就多次看過Wirth教授的《算法+數據結構=程序》一書。后來思想慢慢轉移到了方法論上，對OO、GP或者IoC這些知識超乎尋常地關心，卻冷落了程序的本質。很多實際問題還是要靠精心設計的算法才能有效解決。

作者曾發現一本比較有趣的書，它是由Udi Manber所寫的Introduction to Algorithms——A Creative Approach。此書的最大特點就是數學歸納法貫穿全文，我的理解就是“由一粒沙看世界”。復雜的問題，應如何對其分解？在這本書中，不僅給出了一些具體算法，更重要的是它要培養讀者設計算法的能力。而這種能力的核心，在作者看來，就是對歸納的理解和靈活運用。

算法是計算機處理信息的本質，因為計算機程序本質上是一個算法，所以應告訴計算機確切的步驟以執行一個指定的任務，如計算職工的薪水或打印學生的成績單。一般，當算法在處理信息時，數據會從輸入設備上讀取，寫入至輸出設備，保存起來供以后使用。

著名計算機科學家Wirth提出一個公式。

數據結構+算法=程序

實際上，一個程序還應當采用結構化程序設計方法進行程序設計，并且用某一種計算機語言來表示。因此，它可以這樣表示。

程序=算法+數據結構+程序設計方法+語言和環境

以上4個方面是一門程序設計語言所應具備的基本知識。其中，算法是靈魂，數據結構是加工對象，語言是工具。算法解決“做什么”和“怎么做”的問題。

程序中的操作語句實際上就是算法的體現。顯然，不了解算法就談不上程序設計。本書雖然不是專門講解算法的，但不會算法就達不到我們的目的——用C語言進行程序設計。

數據是操作對象，操作的描述即是操作步驟，操作目的是對數據進行加工處理以得到期望的結果。打個比方，廚師做菜肴，需要有菜譜。菜譜上一般應包括配料（數據）與操作步驟（算法）。

這樣，對于同一些原料就可以加工出不同風味的菜肴。

1.2　何謂算法

做任何事情都要有一定的步驟。為解決一個問題而采取的方法和步驟稱為算法。計算機能夠執行的算法稱為計算機算法。計算機算法可分為如下兩大類。

• 數值運算算法：求解數值。
• 非數值運算算法：事務管理領域。

看下面的運算。

1×2×3×4×5

為了計算上述運算，通常需要按照如下步驟來操作。

第1步：求1×2，得到結果2。

第2步：將第1步得到的乘積乘以3，得到結果6。

第3步：將6再乘以4，得24。

第4步：將24再乘以5，得120。

上述過程就是一個算法，雖然過程有點復雜。而計算機程序對上述算法進行了改進，它使用如下算法。

第1步：令t=1。

第2步：令i=2。

第3步：計算t×i，乘積仍然放在變量t中，可表示為t×i→t。

第4步：會i的值+1，即i+1→i。

第5步：如果i≤5，則返回重新執行步驟3以及步驟4和步驟5；否則，算法結束。

上述算法就是數學中的“n!”公式。

看下面的數學應用題。

（1）有80個學生，要求將他們中成績在60分以上的姓名和成績打印出來。

在此設n表示學生的學號，ni表示第i個學生的學號；cheng表示學生成績，chengi表示第i個學生成績。則對應算法表示如下。

第1步：令i=1。

第2步：如果chengi≥60，則輸出ni和chengi；否則不輸出。

第3步：i+1→i。

第4步：若i≤80，則返回步驟2；否則，結束。

（2）判定在1900～2000年中哪一年是閏年，并輸出結果。

閏年需要滿足的條件如下所示。

• 能被4整除，但不能被100整除的年份。
• 能被100整除，又能被400整除的年份。

在此可以設y為被檢測的年份，則對應算法如下所示。

第1步：令y=1900。

第2步：若y不能被4整除，則輸出y“不是閏年”，然后轉到第6步。

第3步：若y能被4整除，不能被100整除，則輸出y“是閏年”，然后轉到第6步。

第4步：若y能被100整除，又能被400整除，則輸出y“是閏年”；否則，輸出y“不是閏年”，然后轉到第6步。

第5步：輸出y“不是閏年”。

第6步：y+1→y。

第7步：當y≤2000時，返回第2步繼續執行；否則，結束。

19.1.3　算法的特性

對于程序設計人員來說，必須會設計算法，并根據算法寫出程序。算法的特性如下所示。

• 有窮性，一個算法應包含有限的操作步驟而不能是無限的。
• 確定性，在算法中每一個步驟都應當是確定的，而不能是含糊的、模棱兩可的。
• 有零個或多個輸入。
• 有一個或多個輸出。
• 有效性，在算法中每一個步驟都應當能有效地執行，并得到確定的結果。

1.2　算法表示法——流程圖

算法的表示方法為算法的描述和外在表現，上節的算法都是通過語言描述來體現的。除了語言描述外，還可以通過流程圖來描述。在日常應用中，流程圖的描述格式如圖19-1所示。

圖1-1　流程圖標識說明

例如，有80個學生，要求將他們之中成績在60分以上的姓名和成績打印出來。上述問題的算法可使用圖19-2所示的流程圖來表示。

圖1-2　算法流程圖

在日常流程設計中，流程圖通常包含如下3種結構。

• 順序結構：順序結構如圖19-3所示，其中A和B兩個框是順序執行的。即在執行完A的操作以后再執行B的操作。順序結構是一種基本結構。

圖1-3　順序結構

• 選擇結構：選擇結構也稱為分支結構，如圖19-4所示。在此結構中必含一個判斷框，根據給定條件是否成立而選擇是執行 A框還是B框。無論條件是否成立，都只能執行A框或B框之一，也就是說A、B兩個框只有一個，也必須有一個被執行。

圖1-4　選擇結構

• 循環結構：循環結構分為兩種，一種是當型循環，另一種是直到型循環。當型循環是先判斷條件P是否成立，若成立才執行A操作，而直到型循環則相反，先執行A操作再判斷條件P是否成，當條件不滿足時執行循環體，滿足時則停止，如圖19-5所示。

圖1-5　循環結構

在上述3種基本結構中，有以下4個共同點。

• 只有一個入口。
• 只有一個出口。
• 結構內的每個部分都有機會執行。
• 結構內不存在“死循環”。