數據結構是指相互之間存在著一種或多種關系的數據元素的集合和該集合中數據元素之間的關系組成。數據結構包括三個方面的內容，數據的邏輯結構，數據的存儲結構和數據的運算。數據的邏輯結構和存儲（物理）結構是密不可分的兩個方面，一個算法的設計取決于所選定的邏輯結構，而算法的實現依賴于所采用的存儲結構。 ## 一.數據結構的三要素 ### 1.1數據的邏輯結構 數據的邏輯結構是指數據元素之間的邏輯關系，即從邏輯關系上描述數據，它與數據的存儲無關，獨立于計算機。 常見的邏輯結構主要分為線性關系和非線性關系，其中線性表是典型的線性結構；集合，二叉樹，圖時典型的非線性結構 - 線性結構：數據結構中的元素存在一對一的相互關系； - 樹形結構：數據結構中的元素存在一對多的相互關系； - 圖（網）狀結構：數據結構中的元素存在多對多的相互關系 ### 1.2數據的存儲（物理）結構 數據的存儲結構是指數據結構在計算機中的表示（又稱映像），也稱為物理結構。它包括數據元素的表示和關系的表示。數據的存儲結構是邏輯結構用計算機語言的實現，依賴于計算機語言。 常見的物理結構主要有：順序存儲，鏈式存儲，索引存儲和散列存儲。 - 順序存儲：把邏輯上相鄰的元素存儲在物理位置相鄰的存儲單元里，元素間的邏輯關系由存儲單元的鄰接關系來體現，由此得到的存儲表示稱為順序存儲結構。順序存儲結構是一種最基本的存儲表示方法，通常借助于程序設計語言中的數組來實現。 優點是可以實現隨機存取，每個元素占用最少的存儲空間； 缺點是只能使用相鄰的一整塊存儲單元，因此可能產生較多的外部碎片。 - 鏈接存儲：不要求邏輯上相鄰的元素在物理位置上亦相鄰，元素間的邏輯關系是由附加的指針字段表示的。由此得到的存儲表示稱為鏈式存儲結構，鏈式存儲結構通常借助于程序設計語言中的指針類型來實現。 優點是不會出現碎片現象，充分利用所有存儲單元； 缺點是每個元素因存儲指針而占用額外的存儲空間，并且只能實現順序存取。 - 索引存儲：在存儲元素信息的同時，還建立附加的索引表來標識元素的地址。索引表中的每一項稱為索引項，索引項的一般形式是：（關鍵字，地址）。 優點是檢索速度快； 缺點是增加了附加的索引表，會占用較多的存儲空間，此外，在增加和刪除數據時要修改索引表，因此會花費較多的時間。 - 散列存儲：根據元素的關鍵字直接計算出該元素的存儲地址，又稱為Hash存儲。 優點是檢索，增加和刪除元素的操作都很快； 缺點是如果選擇的散列函數不當，會造成元素存儲單元的沖突，而解決沖突又會增加額外的時間和空間開銷。 ### 1.3數據的運算 施加在數據上的運算包括運算的定義和實現。運算的定義是針對于邏輯結構的，指出運算的功能；運算的實現時針對于存儲結構的，指出運算的具體步驟。 ## 二.數據結構三要素小結 如下圖所示：  ## 三.算法 ### 3.1算法的基本概念 算法（Algorithm）是對特定問題求解步驟的一種描述，是指令的有限序列，其中每一條指令表示一個或多個操作。 ### 3.2算法的特性 1. 有窮性：一個算法必須總是（對于任何合法的輸入值）在執行有限步驟后結束，且每一步都可在有窮時間內完成。 1. 確定性：算法的每一條指令必須有確切的含義，讀者理解時不會產生二義性。即對相同的輸入只能得到相同的輸出。 1. 可行性：一個算法是可執行的，即算法中描述的操作都可以通過已經實現的基本運算執行有限次來實現（也稱之為有效性）。 1. 輸入：一個算法有零個或多個輸入，這些輸入取自某個特定的對象的集合。 1. 輸出：一個算法有一個或多個輸出，這些輸出是同輸入有著某種特定關系的量。 ### 3.3算法的目標 1. 正確性：算法應當能夠正確的解決所需求解的問題。 1. 可讀性：算法應當具有良好的可讀性，以助于人們理解。 1. 健壯性：當輸入非法數據時，算法也能適當的做出反應或進行處理，而不會產生莫名其妙的輸出結果。 1. 效率與低存儲量需求：效率是指算法執行的時間，存儲量是指算法執行過程中所需的最大存儲空間，這兩者均與問題的規模有關。 ### 3.4算法效率的度量 算法效率的度量時通過時間復雜度和空間復雜度來描述的。 ### 3.4.1時間復雜度 算法的時間復雜度是指算法需要消耗的時間資源。一般來說，計算機算法是問題規模n的函數f(n)，算法的時間復雜度也因此記做T(n)=O(f(n)),算法執行時間的增長率與f(n)的增長率正相關，稱作漸近時間復雜度，簡稱時間復雜度。 這里應該注意到時間復雜度有三種： - 最壞時間復雜度：最壞情況下，算法的時間復雜度； - 平均時間復雜度：所有可能輸入實例在等概率出現的情況下，算法的期望運行時間； - 最佳時間復雜度：在最佳情況下，算法的時間復雜度。 此處應該注意，我們一般所說的時間復雜度其實是指最壞時間復雜度。 在考慮一個算法的時間復雜度時，有以下兩條規則： > a) 加法規則 T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n))) b) 乘法規則 T(n)=T1(n)×T2(n)=O(f(n))×O(g(n))=O(f(n)×g(n)) 常見的漸近時間復雜度有： > O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn) ### 3.4.1空間復雜度 算法的空間復雜度是指算法需要消耗的空間資源。其計算和表示方法與時間復雜度類似，一般都用復雜度的漸近性來表示。同時間復雜度相比，空間復雜度的分析要簡單得多。一般記作S(n)=O(g(n))。 算法原地工作是指算法所需輔助空間是常量，即O(1)。 ### 3.5算法的小結 具體小結如下圖所示：