[考研系列之資料結構]資料結構概述 1.腦圖 2.資料結構 3.算法

表示法:

(D,S,P)

D:資料對象

S:D上的關系集

P:對D的基本操作集

ADT格式

<code></code>

ADT 抽象資料類型名{

    資料對象:&lt;資料對象定義&gt;

    資料關系:&lt;資料對象的定義&gt;

    基本操作:&lt;基本操作的定義&gt;

}ADT 抽象資料類型名

基本操作的格式:

基本操作名(參數表)

    初始條件:&lt;初始條件描述&gt;

    操作結構:&lt;操作結果描述&gt;

原子類型的值是不能分解的，如C中基本資料類型

結構類型的值是可分解的，是由結構類型和原子類型聚合成的

而結構類型中按照值的成分是不是可變又分成:固定聚合類型&amp;可變聚合類型

固定聚合類型如複數，它是由&lt;a,b&gt;兩個實數組成

可變聚合類型如字元串，它是由n個char類型字元組成

順序映像就如同數組，是一塊連續的空間，由頭指針和尾指針就可以指定這段空間

非順序映像如同連結清單，是n塊不連續空間，每塊空間有一個指針指向下一個空間(也有雙向指針)

首先，我們看看什麼是前驅後繼

前驅:某資料元素在此資料類型中的上一個資料元素

後繼:某資料元素在此資料類型中的下一個資料元素

如果一個資料類型中所有資料元素沒有前驅也沒有後繼，那麼每個元素之間就沒沒有關聯，這種結構稱之為集合；

如果每個元素都有一個前驅和一個後繼(其實這麼說不對，因為第一個元素沒有前驅，最後一個元素沒有後繼)，那麼他們就形成了一個線性的結構，稱之為線性表

再如果每個元素都有一個前驅，但是有多個後繼(這麼說也不對，因為第一個元素是沒有前驅，而葉子節點是沒有後繼)，那麼他們就成了一個樹

最後，n個前驅n個後繼的話，就形成了圖。

我們的資料結構主要就是以前驅後繼的形式去分類學習的，再輔以順序映像和非順序映像的表示就衍生了更多的資料結構，這個接下來會逐漸講述。

算法是對特定問題求解的步驟的描述，是指令的有限序列。

[1] 有窮性

兩點含義:

(1) 算法必須是在有窮步後結束，如無限循環就不是有窮的。

(2) 每步算法必須是在有窮時間内完成

[2] 确定性

(1) 每一條指令都不能有二義性

(2) 相同的輸入隻能有相同的輸出

[3] 可行性

算法中描述的操作都能通過有限次基本運算實作

[4] 輸入

一個算法有0個以上輸入

[5] 輸出

一個算法有1個以上輸出

[1] 正确性

四個層次:

a.不含文法錯誤

b.對于幾組輸入的輸出正确

c.程式對于精心選擇的輸入能得出正确的輸出

d.程式對于一切合法輸入都有正确的輸出

[2] 可讀性

算法代碼可被人閱讀

[3] 健壯性

代碼在面對異常時處理

[4] 效率與低儲存量需求

算法的時間和空間代價

算法的效率從耗費的時間和空間上劃分:

[1] 時間複雜度

時間複雜度一般使用大O表示法，它表示算法的時間效率的下限，按照函數增長趨勢又分為常量階、線性階、平方階、對數階、指數階(算法的效率逐漸降低，複雜度逐漸升高)。

[2] 空間複雜度

指的是算法運作期間占用的記憶體大小，一般也用大O表示法表示最差情況。