C語言常用演算法
一個程序主要由數據和操作兩部分組成。數據作為程序操作的對象，而操作是對數據進行加工處理，加工處理的步驟就是演算法。本章主要講述程序的靈魂——演算法，演算法同人的靈魂一樣，是一個很抽象的名詞，人們不會將其與具體的物體建立聯繫。由演算法被稱作程序的靈魂，可見其重要性。那麼演算法到底為何物呢?為什麼稱演算法為程序的靈魂呢?通過本章的學習您將會解決這些疑問。
第一章、程序之魂——演算法
1.1 魂 之 說
很多人認為演算法只存在於那些數學家或計算機專業人士的腦海中，其實不然，演算法無 處不在，只是由於它不是看得見、摸得著的具體物體，所以人們常常忽略它的存在。
演算法其實就是為解決一個問題而採取的方法和步驟。例如，洗臉可以簡單地分成如下 幾步:
(1)將清水倒入盆中。
(2)擠上洗面奶，清洗臉部。
(3)用水洗凈臉上的洗面奶。
(4)用毛巾擦乾臉。
以上這4步就稱為解決洗臉這個問題的演算法。 著名科學家沃思提出一個公式:
數據結構+演算法=程序 在計算機程序設計中，數據結構是操作的對象，演算法是對對象進行加工處理，用以得到程序的運行結果，程序中的操作語句，實際上就是演算法的體現。 如果將計算機程序比喻成有生命的人，那麼數據結構是人的軀體，演算法就是人的靈魂。只有軀體與靈魂相互結合，才能組成一個完整的有生命、有思想的人。因此，演算法具有程序的靈魂之說。下面通過一個簡單的C語言程序來體會一下什麼是演算法以及演算法的重要性。
題目:一個整數，它加上100後是一個完全平方數，再加上168又是一個完全平方數， 請問該數是多少?
程序分析:
(1)隨意擬定一個整數範圍，對該範圍內的整數判斷是否滿足題中所述條件，在此 例中所取範圍是100000以內的整數。
(2)先將該數加上100後開方。 (3)再將加上100後的該數加上168後開方。 (4)若開方後滿足條件，則輸出結果。 源代碼:
#include "math.h" main
{
long int i,x,y,z; for(i=1;i
x=sqrt(i+100);
y=sqrt(i+268);/*y為加上100再加上168開方後的結果*/
if(x*x==i+100&&y*y==I+268)/*滿足條件輸出結果*/
}
}
運行結果:輸出1~100000內所有滿足條件的整數。
在這個程序中，程序分析部分是對問題進行分析從而設計出解決這個問題採取的方 法，這就稱之為演算法，而源代碼部分是通過代碼對演算法進行體現，最終得出正確的運行 結果。
1.2 演算法的特性
演算法是解決「做什麼」和「怎麼做」的問題，解決一個問題可能有不同的方法，但是 演算法分析最為核心的是演算法的速度。因此解決問題的步驟需要是在有限時間內能夠完成 的，並且操作步驟中不可以有可能導致步驟無法繼續進行下去的歧義性語句。通過對演算法 概念的分析，可以總結出一個演算法必須滿足如下五個特性。
1.有窮性
一個演算法在執行有限步驟後在有限時間內能夠實現的，就稱該演算法具有有窮性。例如， 在1.1節的學習園地中，若for循環中沒有i++語句，就不會使i在有限步驟後不滿足i小於 100000這個條件，而結束循環，否則會無休止地執行for循環中的語句，這樣程序就進入了 死循環，不滿足演算法的有窮性。
有的演算法在理論上滿足有窮性的，在有限的步驟後能夠完成，但是實際上計算機可能 會執行一天、一年、十年等，那麼這個演算法也就沒有意義了，因為這樣就忽視了一個概念， 即演算法的核心是速度。總而言之，有窮性沒有特定的限度，取決於實際需要。
2.確定性
一個演算法中的每一個步驟的表述都應該是確定的、沒有歧義的語句。在人們的日常生
活中，遇到歧義性語句，可以根據常識、語境等理解，然而還有可能理解錯誤。例如，將 1.1節學習園地中程序分析的第二步，描述成「該數加100開方」，要如何解釋這個步驟呢? 是先將100開方，然後加上該數，還是加上100後再開方呢?計算機不比人腦，不會根據算 法的意義來揣測每個步驟的意思，所以演算法的每一步都要有確定的含義。
3.有零個或多個輸入
一個程序中的演算法和數據是相互聯繫的，演算法中需要輸入的是數據的量值。輸入可以 是多個也可以是零個，零個輸入並不是這個演算法沒有輸入，而是這個輸入沒有直觀地顯現 出來，隱藏在演算法本身當中。例如，1.1節中的例題沒有明顯的輸入數據，真正的輸入隱藏 在i=1中，輸入的第一個值就是1，根據條件對輸入的數值進行判斷。
4.有一個或多個輸出
輸出就是演算法實現所得到的結果，是演算法經過數據加工處理後得到的結果。沒有輸出的演算法是沒有意義的。有的演算法輸出的是數值，有的是圖形，有的輸出並不是顯而易見的。
5.可行性
演算法的可行性就是指每一個步驟都能夠有效地執行，並且得到確定的結果，同時能夠
用來方便地解決一類問題。
1.3 演算法的表示方式
一個演算法有多種表述方式，常見的有自然語言、流程圖、N-S圖、偽代碼、計算機語言等。
1.3.1 用自然語言描述演算法
用自然語言表示演算法就是用日常生活中使用的語言來描述演算法的步驟。自然語言通俗 易懂，但是在描述上容易出現歧義。此外，用自然語言描述計算機程序中的分支和多重循 環等演算法，容易出現錯誤，描述不清。因此，只有在較小的演算法中應用自然語言描述，才 方便簡單。
1.3.2 用流程圖描述演算法
簡單的演算法可以用自然語言來描述，但是較為複雜的演算法要如何描述呢?在計算機程 序中經常會出現很多多分支選擇結構的語句，這樣的語句很容易產生歧義。而計算機程序 需要每一步都是確切的，因此，流程圖成了描述演算法最為常見的方法。
1.流程圖基本符號
流程圖是由一些簡單的框圖組成表示解題步驟及順序的方法。美國國家標準化協會(ANSI)規定了一些常用的流程圖符號。
(1)起止框:表示一個演算法的開始和結束。
(2)處理框:將要進行的操作內容簡潔明了地寫到框中。
(3)判斷框:在判斷框中寫入演算法中需要判斷的條件。滿足條件，執行一條路徑;
不滿足條件則執行另一條路徑。
(4)輸入/輸出框:記錄從外部輸入數據到計算機內部或者從計算機內部中輸出數據
到計算機外部。
(5)流程線:指向演算法即將運行的方向。
2.種基本控制結構
在程序人員編寫程序時，為了滿足某些需求，會強製程序在某些地方跳轉，即進行控 制轉移，這樣使得程序的可讀性降低，使本身讓人望而生畏的演算法更加複雜、難於理解。 為了改善此問題，人們規定了3種基本控制結構，將這3種基本結構作為設計和理解演算法的 基本單元(如同一棟大樓中的幾個單元)。
(1)順序結構
順序結構是最為簡單的一種基本結構，就是由上至下、按先後順序依次執行程序語句。 順序結構的流程。
(2)選擇結構
選擇結構也稱為分支結構，是根據給定的條件進行判斷的一種結構。此結構流程圖中 必定包括一個判斷框，滿足條件執行一個處理框，不滿足條件執行另一個處理框。
(3)循環結構
循環結構是一種重複某一部分的操作的結構，它可以簡化程序的難度，將大工作量拆 分成小工作量，並對小工作量進行重複操作，這種方法充分利用了計算機運算速度快、自 動化的優點。有兩種典型的循環結構:while型循環和do-while型循環。
while型循環採取先判斷表達式，後執行語句的方式。當判斷框中的表達式為非0值時， 執行while語句中的內嵌語句，如此往複，直到表達式為0值，結束循環。do-while型循環採用先執行循環體，再判斷循環條件是否成立的方式。其執行過程為 先執行一次循環體語句，然後判斷表達式，當表達式為非0值時，返回重新執行循環體語 句，如此循環，直到表達式為0值時跳出循環。
1.3.3 用計算機語言描述演算法
在對演算法的一系列描述分析上，最終的目的就是對演算法進行實現，得到演算法的解。例 如，菜譜是講述一個做菜的步驟，這是在用自然語言描述演算法，但是人們學習菜譜的目的 並不僅僅是了解這個步驟，而是要根據描述的演算法進行操作，做出一道實實在在的美味這 就是演算法的實現，而那一道出鍋的菜就是演算法的解。
因此，程序員對演算法的所有描述都是在為實現演算法作出分析，最終應用計算機語言實 現演算法。本書中要介紹的是如何應用C語言來實現演算法。
1.演算法性能分析與度量
演算法是解決問題的方法，但是解決一個問題的方法不止一個，方法多了，自然而然地 就有了優劣之分。例如，當一個人在掃地的時候，人們不會發現這個人掃的好與壞;然而， 若有兩三個人同時做這個工作的時候，人們就有了比較，就可以根據不同的評定標準評價 出好壞，有人認為A好，因為他掃得快，有人認為B好，因為他掃得乾淨，等等。那麼， 對於演算法的優劣該如何來評定呢?同樣有很多標準。然而，演算法作為程序之魂，它的核心 是什麼呢?這才是評定一個演算法優劣的重要指標。在前面對演算法的描述中，已經指出了算 法的核心就是速度。速度並不只是演算法的核心，在計算機功能日益強大的時代，速度已經 成為一切事物的追求。
1.3.4 演算法的性能指標
評定一個演算法的優劣，主要有以下幾個指標。
(1)正確性:
一個演算法必須正確才有存在的意義，這是最重要的指標，要求編程人 員應用正確的計算機語言實現演算法的功能。
(2)友好性:
演算法實現的功能是給用戶使用的，自然要具有良好的使用性，即用戶 友好性。
(3)可讀性:
演算法的實現可能需要多次的修改，也可能被移植到其他的功能中，因 此演算法應當是可讀的、可以理解的，方便程序人員對其分析、修改移植到自己的程序中， 實現某些功能。
(4)健壯性:
在一個演算法中，經常會出現不合理的數據或非法的操作，所以一個算 法必須具有健壯性，能夠對這些問題進行檢查、糾正。演算法具有健壯性是一個升華，當用 戶剛開始學習寫演算法時可以忽略它的存在，在逐漸的學習中要努力讓演算法更加完美。
(5)效率:
演算法的效率主要是指執行演算法時計算機資源的消耗，包括計算機內存的 消耗和計算機運行時間的消耗。這兩個消耗可以統稱為時空效率。一個演算法只有正確性而 無效率是沒有意義的，通常，效率也可以評定一個演算法是否正確。如果一個演算法需要執行 幾年甚至幾百年，那麼無疑這個演算法會被評為是錯誤的。
1.3.5 演算法效率的度量
度量演算法效率的方法有兩種:
第一種是事後計算的方法，先實現演算法，然後運行程序，測算其時間和空間的消耗。 這種度量方法有很多弊端，由於演算法的運行與計算機的軟硬體等環境因素有關，不容易發 現演算法本身的優劣。同樣的演算法用不同的編譯器編譯出的目標代碼數量不同，完成演算法所 需的時間也不同;若計算機的存儲空間較小，演算法運行時間也就會延長。第二種是事前分析估算的方法，這種度量方法是通過比較演算法的複雜性來評價演算法的 優劣，演算法的複雜性與計算機軟硬體無關，僅與計算時間和存儲需求有關。演算法複雜性的度量可以分為空間複雜度度量和時間複雜度度量。
1.3.6 演算法的時間複雜度
演算法的時間複雜度度量主要是計算一個演算法所用的時間，演算法所用的時間主要包括程 序編譯時間和運行時間。由於一個演算法一旦編譯成功可以多次運行，因此忽略編譯時間， 在這裡只討論演算法的運行時間。
演算法的運行時間依賴於加減乘除等基本的運算以及參加運算的數據的大小和計算機 硬體和操作環境等。要想準確地計算時間是不可行的，而影響演算法時間最為主要的因素是 問題的規模，即輸入量的多少。同等條件下，問題的規模越大，運行的時間也就越長。例 如，求1+2+3+...+n的演算法，即n個整數的累加求和，這個問題的規模為n。因此，運行演算法 所需的時間T是問題規模n的函數，記作T(n)。
為了客觀地反映一個演算法的執行時間，通常用演算法中基本語句的執行次數來度量演算法 的工作量。而這種度量時間複雜度的方法得出的不是時間量，而是一種增長趨勢的度量， 即當問題規模n增大時，T(n)也隨之變大。換言之，當問題規模充分大時，演算法中基本語句 的執行次數為在漸進意義下的階，稱為演算法的漸進時間複雜度，簡稱時間複雜度，通常用 大O記號表示。用數學語言通常描述為:若當且僅當存在正整數O和n0，對於任意n≥n0， 都有T(n)≤c×f(n)，則稱該演算法的漸進時間複雜度為T(n)=O(f(n))(或稱演算法在O(f(n))中)。
對於某些演算法即使問題規模相同，如果輸入數據不同，則演算法運行時間也不同，因此 要全面分析一個演算法，需要考慮演算法在最好、最壞、平均情況下的時間消耗。由於最好情 況出現的概率太小，因此不具代表性，但是，當最好情況出現的概率大時，應該分析最好 情況;雖然最壞情況出現的概率也太小，不具代表性，但是分析最壞情況能夠讓人們知道 演算法的運行時間最壞能到什麼程度，這一點在實時系統中很重要;分析平均情況是比較普 遍的，特別是同一個演算法要處理不同的輸入時，通常假定輸入的數據是等概率分布的。
通過對演算法時間複雜度的分析，總結出這樣一條結論，在計算任何演算法的時間複雜度 時，可以忽略所有低次冪和最高次冪的係數，這樣可以簡化演算法分析，並使注意力集中在 增長率上。
第二章、數據結構基礎
2.1 數據結構概述
2.1.1 數據結構的發展
隨著計算機科學技術的不斷發展，計算機應用已經從最初的科學計算髮展到控制、 管理等各處理領域。從而使計算機處理的數據從單純的數值發展到字元、圖像、聲音、 文件等具有一定結構的數據，而且處理的數據量也不斷增加。這就需要對計算機處理的 這些數據進行有效的管理，使其能夠滿足各項處理要求。這樣便產生了「數據結構」這 門學科。1968年美國克努思教授開創了數據結構的最初體系，他的《計算機程序設計藝術》第 一卷《基本演算法》是第一本比較系統地闡述數據邏輯結構和存儲結構及其相關操作的著作。 20世紀70年代初，美國一些大學計算機系把「數據結構」規定為一門課程。
多學兩招
克努思(Donald.E.Knuth，1938—)1963年在加利福尼亞理工學院任教，1968年成為 斯坦福大學教授;1992年榮譽退休，保留教授頭銜，集中精力寫作。他的《計算機程序設 計藝術》叢書對計算機科學的發展產生了深遠的影響。「從某種意義上說，克努思就意味 著計算機程序設計藝術，也就意味著數據結構和演算法這一類問題的答案。」到目前為止，數據結構的發展有3個階段，即程序設計發展的3個階段——無結構階段、 結構化階段和面向對象階段。
2.1.2 數據結構的研究對象
數據結構在計算機科學領域是一門綜合性學科，其研究涉及計算機硬體、軟體的各 個方面。一般來說，計算機解決問題包括以下幾個步驟:首先需要從具體問題抽象出一 個計算機理解的模型，然後設計演算法解出該模型的解，最後編程得到答案。例如，線性 方程組數學模型、微分方程數學模型。但是更多的數據處理是非數值的，無法用數學方 程加以描述。
2.1.3 數據結構與演算法的關係
「數據結構+演算法=程序」這個公式在前面已經提到過，它表示了組成程序的兩個基本 要素是數據結構和演算法。在這個公式中沒有涉及到代碼，只是程序設計的思想。在計算機 程序設計中，數據結構是操作的對象，演算法是對對象進行加工處理，用以得到程序的運行 結果。數據結構是軀體，演算法是靈魂，二者組成程序，缺一不可。
演算法是對一個程序的邏輯實現的描述，而數據結構是邏輯所依附的實體。只要程序員設計 出了程序的演算法，確定了數據結構，那麼這個程序就已經基本成型，剩下的就是填充代碼了。
2.2 數據結構的基本概念
數據的主要功能就是傳遞信息，例如思想交流、商業交易、經營管理等，這些信息都
需要以數據的形式在計算機中進行處理。
? 數據(data):信息的載體，是能夠輸入到計算機中並被計算機識別和處理的符 號的總稱。
在實際應用中數據可以是數值，也可以是字元串、表、圖、聲音等，這些都是可 以通過編碼方式使用計算機進行操作的對象。學生基本信息管理程序操作對象是 學生基本信息表;公司部門信息管理程序操作對象是部門信息表。
? 數據元素(data element):數據的基本單位，構成數據元素的不可分割的最小單 位是數據項。例如，學生信息管理程序的每個學生信息就是一個數據元素，而表 中學生的學號、性別、姓名等就是數據項。討論數據結構一般針對數據元素進行 討論，數據項一般不予考慮。數據元素在計算機程序中通常作為一個整體進行操 作，其具有廣泛的含義，一般來說，計算機中抽象出的，能夠獨立、完整地描述 問題世界的一切實體都是數據元素。例如學生的信息、部門信息、銷售情況、城 市地圖都是數據元素。
? 數據對象(data object):具有相同性質的數據元素的集合，是數據的子集。數據 元素是數據對象的子集。在實際應用中把相同性質的數據元素集合到一起，就構 成了數據對象，例如每個學生信息是數據元素，而所有的學生信息就構成了一個 學生信息的對象，這裡以表的形式表示。
? 數據結構(data structure):相互之間存在一種或者多種數據關係的數據元素的 集合。這種數據元素之間的關係，通常被稱為結構。例如，學生信息表中各學生 信息元素之間的關係是簡單的線性結構;部門信息表中各數據之間的關係是樹形 結構。根據各數據元素不同的關係類型，通常將結構分為4類:集合、線性結構、 樹形結構和圖結構(或者網狀結構)。這4類關係的示意圖如圖2.2所示。
? 集合:數據元素同屬於一個範圍，除此之外沒有其他關係。例如，一個整數 的集合。
? 線性結構:數據元素之間存在著一對一的線性關係。例如，學生信息的線性 關係。
? 樹結構:數據元素之間存在著一對多的層次關係。例如，部門信息的層次關係。
? 圖結構:數據元素之間存在著多對多的任意關係
數據存儲在計算機中的存儲結構又如何描述呢。如果直接以內存地址來描述存儲結構 又會使操作很不方便。在高級語言中會提供「數據類型」來描述存儲結構。例如，C語言 中的「數組」類型用以描述順序存儲結構，「指針」類型用以描述鏈式存儲結構。
數據類型(date type)用以描述數據在計算機上的存儲結構，通過數據類型可以顯示 或者隱式地表示對象的取值範圍，以及在這些對象上允許進行的操作。因此數據類型可以 定義為:一個值的集合和定義在這個值集上的一組操作的總稱。
2.3 C語言常見數據結構
2.3.1 數組
在編寫程序的過程中，經常會遇到使用大量數據的時候，處理一個數據就要有一個相 對應的變數，如果每一個變數都要單獨進行定義就會很煩瑣，使用數組就可以解決這種情 況。數組將一些有關聯的相同的數據類型集合到一個數組變數中，方便數據的存儲和使用。
數組是在程序開發中應用十分廣泛的一種數據類型，屬於線性結構，可以分為一維數 組和多維數組。一個數組可以分解為多個數組元素，這些數組元素可以是基本數據類型或 是構造類型。因此按數組元素的類型不同，數組又可分為數值數組、字元數組、指針數組、 結構數組等各種類別，數組元素佔用內存中一塊連續的地址空間。
數組中的每一個元素都屬於同一個數據類型，用一個統一的數組名和下標來確定數組 的元素。例如一個車庫，車庫裡面存的都是車，就好像數組中存著同類型的數據，車庫有 一個統一的名稱，並且有車位編號。例如，一號車庫二號車位，通過這個編號就能找到對 應的車。
最常用的是一維數組和二維數組。下面介紹一維數組和二維數組的定義和引用。
1.一維數組
(1)一維數組的定義
一維數組是用以存儲一維數列中數據的集合。其一般形式如下:
類型說明符 數組標識符[常量表達式];
? 類型說明符表示數組中的所有元素類型。
? 數組標識符就是這個數組型變數的名稱，命名規則與變數名一致。
? 常量表達式定義了數組中存放的數據元素的個數，即數組長度。例如iArray[5]，5
表示數組中有5個元素，下標從0開始，到4結束。
(2)一維數組的引用 數組定義完成後就要使用該數組，可以通過引用數組元素的方式，使用該數組中的元素。 表示數組元素的一般形式如下:數組標識符[下標];
2.二維數組
(1)二維數組的定義
二維數組的聲明和一維數組相同，其一般形式如下:
數據類型 數組名[常量表達式1][常量表達式2];
(2)二維數組的引用
二維數組元素的一般形式為
數組名[下標][下標];
2.3.2 結構體
「結構體」是一種構造類型，它是由若干「成員」組成的。其中的每一個成員可以是 一個基本數據類型或者又是一個構造類型。既然結構體是一種新的類型，那麼就需要先對 其進行構造，這裡稱這種操作為聲明一個結構體。聲明結構體的過程就好比生產商品的過 程，只有商品生產出來才可以使用。假如在程序中就要使用「商品」這樣一個類型。那麼商品具有哪些特點呢?商品有形 狀、顏色、功能、價格、產地和產品標號。
商品這種類型並不能使用之前學過的任何一種類型來表示，這個 時候就要自己定義一種新的類型，將這種自己指定的結構稱為結構體。聲明一種結構體的一般形式為:
struct 結構體名 {
成員表列
};
關鍵字struct表示聲明結構，其後的結構體名表示該結構的類型名。大括弧中的變數構 成結構的成員，也就是聲明結構體一般形式中的「成員列表」處。
2.3.3 鏈表
鏈表是一種常見的數據結構。之前介紹過使用數組存放數據，但是使用數組時要先指定 數組中包含元素的個數，即為數組的長度。但是如果要向這個數組中加入的元素個數超過了 數組的大小時，便不能將內容完全保存。例如在定義一個班級的人數時，如果小班是30人， 普通班級是50人，定義班級人數時若使用的是數組，那麼就要定義數組的個數為最大，也就 是最少50個元素，否則就不滿足最大時的情況。這樣的存儲方式非常浪費空間。
這個時候就希望有一種存儲方式——其存儲元素的個數是不受限定的，當添加元素時 存儲的個數就會隨之改變。這種存儲方式就是鏈表。而且相對於數組來說，鏈表在插入和 刪除結點時，比數組元素的插入和刪除要簡單而且開銷更小。
在鏈表中有一個頭指針變數，圖中head表示的就是頭指針，在這個指針變數保存一個 地址。從圖2.5中的箭頭可以看到該地址為一個變數的地址，也就是說頭指針指向一個變數。 這個變數稱為元素，在鏈表中每一個元素包括兩個部分:數據部分和指針部分。數據部分 用來存放元素所包含的數據，而指針部分就用來指向下一個元素。最後一個元素的指針指 向NULL，表示指向的地址為空，鏈表到此結束。
從鏈表的示意圖中可以看到head頭結點指向第一個元素，第一個元素中的指針又指向 第二元素，而第二個元素的指針又指向第三個元素的地址，第三個元素的指針就指向為空。
根據對鏈表的描述，可以想像鏈表就像一個鐵鏈一樣一環扣一環，然後通過頭指針尋 找鏈表中的元素。這就好比在幼兒園中，老師拉著第一個小朋友的手，第一個小朋友又拉 著第二個小朋友的手，這樣下去在幼兒園中的小朋友就連成了一條線，最後一個小朋友沒 有拉著任何人，他的手是空著的，這就好像是鏈表中的鏈尾，而老師就是頭指針，通過老 師就可以找到這個隊伍中的任何一個小朋友。
關注微信公號「書問」免費領取萬本好書
書名：C語言常用演算法分析
作者：明日科技, 編著
出 版 社：清華大學出版社
定價：￥39.80
TAG:書問科普 |