基本概念和術(shù)語

數(shù)據(jù)

數(shù)據(jù)-> 多個數(shù)據(jù)元素 -> 多個數(shù)據(jù)項
數(shù)據(jù)對象 是 性質(zhì)相同的數(shù)據(jù)元素的集合

結(jié)構(gòu)

數(shù)據(jù)元素相互之間的關(guān)系成為結(jié)構(gòu)

• 集合
• 線性結(jié)構(gòu)
• 樹形結(jié)構(gòu)
• 圖狀結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是一個二元組 定義形式為 Data_Structure = ( D, S ), 其中D是元素有限集，S 是D上的關(guān)系有限集。

邏輯結(jié)構(gòu)

對操作對象的數(shù)學描述，即從操作對象抽象出來的數(shù)學模型稱為邏輯結(jié)構(gòu)。
一般來說，數(shù)據(jù)結(jié)構(gòu)代指邏輯結(jié)構(gòu)

物理結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)在計算機的表示（又稱映像）稱為物理結(jié)構(gòu)，又叫做存儲結(jié)構(gòu)。用由若干個位組合起來形成的一個位串表示一個數(shù)據(jù)元素。這個位串稱為元素，也叫做結(jié)點。
當數(shù)據(jù)元素由多個數(shù)據(jù)項組成時，位串中對應于各個數(shù)據(jù)項的子位串稱為數(shù)據(jù)域。

數(shù)據(jù)元素之間關(guān)系的表示方法

1. 順序映像
2. 非順序映像

由此得到兩種不同的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu) 和 鏈式存儲結(jié)構(gòu)

順序映像

借助元素在存儲器中的相對位置來表示元素之間的邏輯關(guān)系

非順序映像

借助指針

虛擬存儲結(jié)構(gòu)

用一維數(shù)組描述順序存儲結(jié)構(gòu)，用指針描述鏈式存儲結(jié)構(gòu)

任何一個算法的設(shè)計取決于選定的邏輯結(jié)構(gòu)
算法的實現(xiàn)則依賴于采用的存儲結(jié)構(gòu)

數(shù)據(jù)類型

int a
數(shù)據(jù)類型決定取的字節(jié)數(shù)，變量名決定起始位置

按“值”的特性不同，數(shù)據(jù)類型可分為兩類

• 非結(jié)構(gòu)的原子類型
• 結(jié)構(gòu)類型

原子類型

原子類型的值不可分解，例如基本類型（整型、實型、字符型和枚舉型）、指針類型和空類型。

結(jié)構(gòu)類型

結(jié)構(gòu)類型的值是由若干成分按某種結(jié)構(gòu)組成的，因此是可以分解的，并且他的成分可以是非結(jié)構(gòu)的，也可以是結(jié)構(gòu)的。

某種意義上，數(shù)據(jù)結(jié)構(gòu)（邏輯結(jié)構(gòu)）可以看成是一組具有相同結(jié)構(gòu)的值
結(jié)構(gòu)類型可以看成由一種數(shù)據(jù)結(jié)構(gòu)和定義在其上的一組操作組成

抽象數(shù)據(jù)類型（Abstract Data Type, ADT）

指一個數(shù)學模型以及定義在其上的一組操作，與數(shù)據(jù)類型相似?！俺橄蟆钡囊饬x在于數(shù)據(jù)類型的數(shù)學抽象特性

抽象數(shù)據(jù)類型可細分為三種類型：

• 原子類型
  不可分解。一般來說，此類型較少，因為原有固有類型足以滿足需求。但有時也有必要定義新的原子數(shù)據(jù)類型，例如數(shù)位為100的整數(shù)。
• 固定聚合類型
  其值由確定數(shù)目的成分按某種結(jié)構(gòu)組成，例如復數(shù)是由兩個實數(shù)依確定次序關(guān)系構(gòu)成。
• 可變聚合類型
  與固定聚合類型相比，其值的數(shù)目不確定。

顯然后兩種類型統(tǒng)稱結(jié)構(gòu)類型

抽象數(shù)據(jù)類型的形式定義

抽象數(shù)據(jù)類型用三元組表示 ADT = (D, S, P),其中D是數(shù)據(jù)對象，S是D上的關(guān)系集，P是對D的基本操作集。
采用如下格式定義抽象數(shù)據(jù)類型：

ADT抽象數(shù)據(jù)類型名{
    數(shù)據(jù)對象:(數(shù)據(jù)對象的定義)
    數(shù)據(jù)關(guān)系:(數(shù)據(jù)關(guān)系的定義)
    基本操作:(基本操作的定義)
}ADT抽象數(shù)據(jù)類型名

其中，數(shù)據(jù)對象和數(shù)據(jù)關(guān)系的定義用偽代碼描述，基本操作的定義格式為

基本操作名(參數(shù)表)
    初始條件:<初始條件描述>
    操作結(jié)果:<操作結(jié)果描述>

基本操作有兩種參數(shù)，形參和引用，引用參數(shù)以&打頭。
初始條件描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應滿足的條件，若不滿足則操作失敗并返回出錯信息。
操作結(jié)果說明操作完成后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應返回的結(jié)果。

• 抽象類型三元組的定義

ADT Triplet{
  數(shù)據(jù)對象:D = {e1,e2,e3|e1,e2,e3∈（定義了關(guān)系運算符的某個集合）}
  數(shù)據(jù)關(guān)系:R1 = {<e1,e2>,<e2,e3>}
  基本操作:
        InitTriplet(&T, v1, v2, v3)
           操作結(jié)果：構(gòu)造了三元組T，元素e1, e2, e3分別被賦以參數(shù)v1, v2, v3的值
        Get(T, i, &e)
           初始條件：三元組T已經(jīng)存在, 1≤i≤3
           操作結(jié)果：用e返回T的第i個元素的值
        Put(&T, i ,e)
           初始條件：三元組T已經(jīng)存在, 1≤i≤3
           操作結(jié)果：改變T的第i個元素的值為e
        ......
}ADT Triplet

算法和算法分析

• 算法的五個特性
  1. 有窮性
  2. 確定性：算法指令具有明確的含義，閱讀時不會出現(xiàn)二義性，且算法只有唯一的一條執(zhí)行路徑，即對于相同的輸入只能得出相同的輸出
  3. 可行性
  4. 輸入
  5. 輸出

算法效率的度量

一般情況下，算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n),算法的時間量度記作 T(n) = O(f(n))，稱作時間復雜度。多數(shù)情況下，問題的基本操作指最深層循環(huán)內(nèi)的語句中的原操作。

語句的頻度

1. {++x; s = 0; }
2. for (i=1;i<=n; ++i) {++x; s += x;}
3. for (j=1; j<=n; ++j)
   for (k=1; k<=n; ++k) {++x; s+=x;}

以上x自增一的頻度分別為1、n和n^2，他們的時間復雜度分別為O(1)、O(n)和O(n2)、分別稱為常量階，線性階和平方階。類似的，還有對數(shù)階O(log n)、多項式階O(n^k)和指數(shù)階O(2^n)。