一、資料結構緒論

1、資料與資料結構

資料:資料是可被計算機識别并加工處理的對象。資料不僅包括整型、實型等數值資料，還包括音頻、圖檔、視訊等非數值資料。

資料元素:由資料組成的具有一定意義的基本機關。

資料項:組成資料元素的不可分割的最小機關。

資料結構:由某一資料對象及該對象中所有資料元素之間的關系組成的。資料結構包括資料的邏輯結構、存儲結構及資料的運算三方面。

2、資料結構:包括資料的邏輯結構、存儲結構及資料的運算

①資料的邏輯結構:指資料元素之間的内在關系，從邏輯上描述資料。資料存在着4種基本的邏輯結構。

Ⅰ線性結構:資料元素之間存在一對一的關系。

Ⅱ樹形結構:資料元素之間存在一對多的關系。

Ⅲ圖結構:資料元素之間存在多對多的關系。

Ⅳ集合結構:資料元素之間除了"屬于同一集合"的聯系之外沒有其他關系。

以上4種基本的邏輯結構還可進一步分類:線性結構和非線性結構。樹形、圖、集合結構統一歸入非線性結構。

②資料的存儲結構:指資料元素之間的關系在計算機内的表示形式。常見基本存儲結構是順序存儲和鍊式存儲。還有索引存儲結構和散列存儲結構。

Ⅰ順序存儲結構:在相關資料元素依次存儲在位址連續的存儲空間中。Loc(a k _{k} k​)=Loc(a s t a r t {_{start}} start​)+機關元素存儲單元×k

Ⅱ鍊式存儲結構:其存儲位置不能展現它們之間的邏輯關系，為存儲一個元素，需要存放的資料元素本身和與該邏輯上相關的相鄰元素的位址，這兩部分資訊組成一個結點。

Ⅲ索引存儲結構:建立附加索引表辨別結點位址。

Ⅳ散列存儲結構:将資料元素的關鍵字與存儲位置之間建立散清單。

③資料的運算:資料的邏輯結構描述了資料的靜态特性，資料運算施加在資料上的操作描述了資料的動态特性。資料結構中，常見的運算有:搜尋運算、插入運算、删除運算、更新運算。

2、抽象資料類型(Abstract Data Type):一種數學模型以及在其上定義的運算的集合。主要特征:資料封裝和資訊隐蔽。資料封裝就是把資料和操縱資料的運算組合在一起的機制；資訊屏蔽就是指資料的使用者隻需要知道這些運算的定義(規範)便可通路資料。

規定抽象資料類型定義格式:

ADT 抽象資料類型名{
	資料:
		資料元素及其之間關系的定義
	運算:
		運算1(參數表):運算功能的描述
		…
		運算n(參數表):運算功能的描述
}
           

3、算法與算法分析

算法:計算機科學中基本概念，是對特定問題的求解步驟。算法具有以下5個特征:

①輸入:一個算法有0個或若幹個輸入。

②輸出:一個算法産生一個或多個輸出，作為算法運算結果。

③可行性:算法每個步驟都可以通過基本運算實作。

④确定性:算法每個步驟都可以通過基本運算來實作。

⑤有窮性:算法必須能在執行有窮步後終止。

算法可以使用自然語言、流程圖、程式設計語言或僞代碼來描述。

衡量一個算法的優劣，主要有以下4個基本标準:

①正确性:在合理的輸入資料情況下，算法能夠在有限的實踐内達到預先規定的功能和性能要求。

②可讀性:一個好的算法應當思路清晰、簡單明了。可讀性高的算法便于人們閱讀、了解和交流。

③健壯性:一個好的算法在輸入不合法的資料時，應當作出适當處理，而不至于産生異常或崩潰等嚴重後果。

④高效性:一個算法的效率主要包括時間和空間兩方面。好算法應具備執行效率高和占用空間少的特點。

算法的複雜度:複雜度包括時間複雜度和空間複雜度。

①時間複雜度:指程式運作從開始到結束所需的時間。度量算法執行時間通常有兩種方法:事後統計法和事前估計法。影響算法時間效率最主要因素是問題規模。一個算法中語句執行次數稱為語句頻度。

一般情況下，令算法中基本運算執行次數用T(n)表示，若有問題規模n的某個函數f(n)，使得存在自然數 n 0 n_{0} n0​，正常數c，當n≥ n 0 n_{0} n0​時，T(n)≤cf(n)，稱f(n)是T(n)的漸近上界，記為O(f(n))。

常見的漸近時間複雜度從小到大:O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)

②空間複雜度:指對應的程式從運作開始到結束所需的存儲空間。

程式運作所需的存儲空間包括兩部分:固定部分和可變部分。

固定部分:與問題規模無關，主要包括程式代碼、常量、簡單變量等所占用的空間。

可變部分:與問題規模有關。主要包括資料元素所占用的空間、算法執行的額外空間等。

③最好、最壞、平均時間複雜度:算法時間複雜度不僅與問題規模有關，也與輸入的資料有關。如在包含n個元素的數組中查找給定元素x，假定算法從左向右搜尋，若待搜尋元素x正好為第一個元素，則所需的查找時間最短，稱之為最好情況；相反的，若待搜尋元素x是最後一個元素或不存在于數組中，則所需的查找時間最長，稱之為最壞情況；若需要多次在數組中查找元素，假定以相等的機率檢驗每個數組元素，則為算法的平均情況。