程序猿必修課之數據結構

程序猿必修課之數據結構

本文將「數據結構」分為 「數據」 和 「結構」 兩部分。

數據

程序設計 = 數據結構 + 演算法

數據

「數據」是描述客觀事物的符號，是計算機中可以操作的對象，是能被計算機識別，並輸入給計算機處理的符號集合。也就是說，我們這裡說的數據其實就是符號，而且這些符號必須具備兩個前提：

比如，數值、聲音、圖像、視頻等都是數據。

可以輸入到計算機中

能被計算機程序處理

數據元素

「數據元素」是組成數據的、有一定意義的基本單位，在計算機中通常作為整體處理。也被稱為記錄。

比如，在人類中，人就是數據元素。

數據項

一個數據元素可以由若干個數據項組成。數據項是數據不可分割的最小單位。

比如人這個數據元素，可以有眼、耳、嘴等這些數據項，也可以有姓名、年齡、性別等這些數據項。

數據對象

「數據對象」是性質相同的數據元素的集合，是數據的子集。

性質相同，是指數據元素具有相同數量和類型的數據項。比如人都有姓名、性別等相同的數據項。

數據結構

「數據結構」是相互之間存在一種或多種特定關係的數據元素的集合。

它們之間的關係：

數據（數據對象）

|

數據元素

|

數據項

結構

按照視點的不同，我們把數據結構分為邏輯結構和物理結構。邏輯結構是面向問題的，而物理結構是面向計算機的。

邏輯結構

「邏輯結構」是指數據對象中數據元素之間的相互關係。

邏輯分為四種：

集合結構：

集合結構中的數據元素除了同屬於一個集合外，它們之間沒有其他關係。

線性結構：

線性結構中的數據元素之間是一對一的關係。

樹形結構：

樹形結構中的數據元素之間存在一對多的層次關係。

圖形結構：

圖形結構的數據元素是多對多的關係。

物理結構

「物理結構」是指數據的邏輯結構在計算機中的存儲形式。

數據元素的存儲結構形式有兩種：順序存儲和鏈式存儲。

順序存儲結構：

把數據元素存放在地址連續的存儲單元里，其數據間的邏輯關係和物理關係是一致的。

鏈式存儲結構：

把數據元素存放在任意的存儲單元里，這組存儲單元可以是連續的，也可以是不連續的。

抽象數據類型

數據類型是指一組性質相同的值的集合及定義在此集合上的一些操作的總稱。

在C語言中，按照取值的不同，數據類型可以分為兩類：

原子類型：不可以再分解的基本類型，包括整型、實型、字元型等。

結構類型：由若干個類型組合而成，是可以再分解的。

抽象數據類型（Abstract Data Type， ADT）：是指一個數學模型及定義在該模型上的一組操作。它體現了程序設計中問題分解、抽象和信息隱藏的特性。

抽象數據類型的標準格式：

演算法

演算法是解決特定問題求解步驟的描述，在計算機中表現為指令的有限序列，並且每條指令表示一個或多個操作。

演算法的特性

演算法具有五個基本特性：輸入、輸出、有窮性、確定性、可行性。

演算法設計的要求

好的演算法，應該具有：正確性、可讀性、健壯性、高效率和低存儲量的特徵。

函數的漸近增長

輸入規模 n 在沒有限制的情況下，只要超過一個數值 N， 這個函數就總是大於另一個函數，我們稱函數是漸近增長的。

給定兩個函數 f(n) 和 g(n), 如果存在一個整數 N，使得對於所有的 n > N, f(n) 總是比 g(n) 大，那麼我們說 f(n) 的增長漸近快於 g(n)。

演算法時間複雜度

在進行演算法分析時，語句總的執行次數 T(n) 是關於問題規模 n 的函數，進而分析 T(n) 隨 n 的變化情況並確定 T(n) 的數量級。演算法的時間複雜度，也就是演算法的時間量度，記作：T(n) = O(f(n))。它表示隨問題規模 n 的增大，演算法執行時間的增長率和 f(n) 的增長率相同，稱為演算法的漸近時間複雜度，簡稱為時間複雜度。其中 f(n) 是規模 n 的某個函數。

用 O() 來體現演算法時間複雜度的記法，叫作大 O 記法。

推導大 O 階方法

用常數 1 取代運行時間中的所有加法常數。

在修改後的運行次數函數中，只保留最高階項。

如果最高階項存在且不是 1 ，則去除與這個項相乘的常數。

常數階

高斯演算法

這個演算法 的運行次數函數是 f(n) = 3。根據推導大 O 階的方法，第一步把常數項 3 改為 1。第二步保留最高階項，它沒有最高階項，所以這個演算法的時間複雜度為 T(n) = O(1)。

當 n = 1 時，演算法執行次數為 3， 當 n = 100時，演算法的執行次數還是 3，所以我們可以看出這個演算法的執行次數與 n 的規模沒關係。我們把這種與問題的大小（n 的大小）無關，執行時間恆定的演算法， 叫作常數階。

對於分支結構，無論是真還是假，執行的次數都是恆定的，不會隨著 n 的變化而變化，所以單純的分支結構（不包含在循環結構中），其時間複雜度也是 O(1)。

線性階

下面這段代碼的時間複雜度為 O(n),因為循環體中的代碼必須要執行 n 次。

對數階

由於每次 count 乘以 2 以後，就越來越接近於 n，也就是說有多少個 2 相乘後大於 n，則會退出循環。由 2x = n 等到 x = log2n。所以這個演算法的時間複雜度為 T(n) = O(logn)。

平方階

這是一個循環嵌套的代碼。

它的內循環我們已經知道，時間複雜度為 O(n)，而對於外層的循環，不過是內部這個時間複雜度為 O(n) 的語句，再循環 n 次。所以這段代碼的時間複雜度為 O(n2)

如果外循環的次數改為了 m，時間複雜度就變為 O(m*n)。

所以我們可以總結得出，循環的時間複雜度等於循環體的複雜度乘以該循環運行的次數。

下面這個循環嵌套，它的時間複雜度是多少呢？

由於當 i = 0 時，內循環執行了 n 次，當 i = 1 時，執行了 n -1 次，…… 當 i = n - 1 時，執行了 1 次。所以部的執行次數為：

n + (n-1) + (n-2) + …… + 1 = n(n+1)/2 = n2/2 + n/2。

用我們推導大 O 階的方法，第一條，沒有加法常數不考慮；第二條，只保留最高階項，因此保留 n2/2；第三條，去除這個項相乘的常數，也就是去除 1/2， 最終這個演算法的時間複雜度為 T(n) = O(n2)

常見的時間複雜度

常用的時間複雜度所耗費的時間從小到大依次是：

O(1)

演算法空間複雜度

演算法的空間複雜度通過計算演算法所需的存儲空間實現，演算法空間複雜度的計算公式：S(n) = O(f(n)),其中 n 為問題的規模，f(n)為語句關於 n 所佔存儲空間的函數。

轉發分享是一種美德

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！