【資料結構與算法】—算法與算法分析（一）
一、資料
資料是能輸入計算機且能被計算機處理的各種符号的集合；是資訊的載體，是對客觀事物符号化的表示；能夠被計算機識别，存儲和加工
資料包括：數值型的資料和非數值型的資料
數值型的資料：整數、實數。
非數值型的資料：文字、圖像、圖形、聲音等。
二、資料元素
資料元素是資料的基本機關，在計算機程式中通常作為一個整體進行考慮和處理。
資料元素也簡稱為元素、或者稱為記錄、結點或頂點。
三、資料項
資料項是構成資料元素的不可分割的最小機關。
資料、資料元素、資料項三者之間的關系
四、資料對象
資料對象是性質相同的資料元素的集合，是一個資料的子集。
資料結構：是指互相之間存在一種或者多種特定關系的資料元素的集合。
資料結構包括以下三個方面的内容：
- 資料元素之間的邏輯關系，也稱為邏輯結構
- 資料元素以及關系在計算機記憶體中的表示（又稱為映像），稱為資料的實體結構或者資料的存儲結構。
資料的運算和實作，即對資料元素可以試駕的操作以及這些操作在相應的存儲結構上的表現。
五、資料結構的兩個層次
邏輯結構
- 描述資料元素之間的邏輯關系
- 與資料的存儲無關，獨立于計算機
是從具體問題抽象出來的資料模型
實體結構
資料元素以及其關系在計算機存儲器中的結構（存儲方式）；是資料結構在計算機中的表示
邏輯結構與存儲結構的關系
存儲結構是邏輯關系的映像與元素本身的映像
邏輯結構是資料結構的抽象，存儲結構是資料結構的實作
六、 邏輯結構的種類
線性結構：有且僅有一個開始和一個終端的結點，并且所有結點都最多隻有一個直接前趨和一個直接後繼。例如：線性表、棧、隊列、串
非線性結構：一個結點可能有多個直接前趨和直接後繼。例如：樹、圖。
劃分方式二—四類基本邏輯結構
- 集合結構：結構中的元素之間除了同屬于一個集合的關系外，無任何其他關系。
- 線性關系：結構中的元素之間存在一對一的線性關系。
- 樹形結構：結構中的資料元素之間存在着一對多的層次關系。
- 圖狀結構或者網狀結構：結構中的元素之間存在着多對多的任意關系。
七、存儲結構的種類
-
順序存儲結構：用一組連續的存儲單元依次存儲資料元素，資料元素之間的邏輯關系由元素的存儲位置來表示。C語言中用數組來實作順序結構。
2.鍊式存儲結構
用一組任意的存儲單元存儲資料元素，資料元素之間的邏輯關系用指針來表示。C語言中用指針來實作鍊式存儲結構。
3.索引存儲結構
在存儲節點資訊的同時，還建立附加的索引表
4.散列存儲結構
根據節點的關鍵字直接計算出該節點的存儲位址
第二章：資料類型和抽象資料類型
資料類型：資料類型是一組性質相同的值的集合以及定義于這個值集合上的一組操作的總稱。
抽象資料類型：是指一個資料模型以及定義在此資料模型上的一組操作。
抽象資料類型的形式定義：抽象資料類型可用（D，S，P）三元組表示
其中：
- D是資料對象
- S是D上的關系集
- P是對D的基本操作集
一個抽象資料類型的定義格式如下：
資料對象，資料關系的定義用僞代碼描述
基本操作的定義格式為：
第三節：抽象資料類型的表現與實作
第四節：算法與算法分析
算法的定義：對特定問題求解方法和步驟的一種描述，它是指令的有限序列，其中每個指令表示一個或者多個操作。
算法的描述
算法的特性：一個算法必須具備以下五個重要的特性：
- 有窮性：一個算法必須總是在執行有窮步之後結束，且每一步都在有窮内完成。
- 确定性：算法中的每一條指令必須有确切的含義，沒有二義性，在任何條件下，隻有唯一的一條執行路徑，即對于相同的輸入隻能得到相同的輸出。
- 可行性：算法是可執行的，算法描述的操作可以通過已經實作的基本操作執行有限次來實作。
- 輸入：一個算法有零個或多個輸入
- 輸出：一個算法有一個或多個輸出
算法設計的要求
一個好的算法首先要具備正确性，然後是健壯性，可讀性、在幾個方面都滿足的情況下，主要考慮算法的效率
通過算法的效率來評判不同算法的優劣程度。
算法效率通過以下兩個方面來考慮：
時間效率：是指算法所耗費的時間。
空間效率：指的是算法執行過程中所耗費的存儲空間。
時間效率和空間效率有時候是沖突的。
算法時間效率的度量
算法時間效率可以依據該算法編制的程式在計算機上執行所消耗的時間來度量。
兩種度量方法
事後統計：将算法實作，測算其時間和空間開銷
缺點：編寫程式實作算法将花費較多的時間和精力，所得實驗結果依賴于計算機的軟硬體等環境因素，掩蓋算法本身的優劣。
事前分析：對算法所消耗資源的一種估算方法（一般采用事前分析）
每條語句執行一次所需的時間，一般是随機器而異的，取決于機器的指令性能，速度，以及編譯的代碼品質，是由機器本身軟硬體環境決定的，他與算法無關。
是以，我們可以假設執行每條語句所需要的時間均為機關時間，此時對算法的運作時間的讨論就可以轉化為該算法中所有語句的執行次數，即頻度之和。
為了便于比較不同算法的時間效率，我們僅比較他們的數量級
數量級越大的越不好
分析算法時間複雜度的基本方法
分析算法時間複雜度的基本方法
- 找出語句頻度最大的那條語句作為基本語句
- 計算基本語句的頻度得到問題規模n的某個函數f(n)
- 取其數量級用符号"O"表示
算法的時間複雜度：
- 最壞時間複雜度：指在最壞的情況下，算法的時間複雜度
- 平均複雜度：指在所有可能輸入執行個體在等機率出現的情況下，算法的期望運作時間。
- 最好時間複雜度：指在最好情況下，算法的時間複雜度
- 一般總是考慮在最壞情況下的時間複雜度，以保證算法的運作時間不會比它更長。
時間複雜度T(n)按數量級遞增順序為：
漸進空間複雜度
漸進空間複雜度：算法所需存儲空間的度量