資料結構筆記(三)：抽象資料結構(ADT)與Struct

資料結構還有一個很重要的東西，這次把它放在最後講，也就是抽象資料結構。

抽象資料型態 ADT

首先，抽象資料型態（Abstract Data Type，光聽就很抽象），是一種只定義數學觀念，將資料和操作一起思考的觀念。這種資料型態著重於資料的運算，並不考慮實作時的細節或資料本身的性質。

例如我們可以很簡單的寫出正整數的 ADT：

物件定義：正整數是指從零開始一直到 INT_MAX 的有順序整數。

方法定義：

• Zero()：即整數 0
• Equal(x, y)：整數 x 和整數 y 是否相等。
• Add(x, y)：把整數 x 和整數 y 相加（在不超過 INT_MAX 的情況下）。
• Sub(x, y)：拿整數 x 減掉整數 y （在不小於零的情況下）。

有一點像 Java 在寫類別的感覺。寫 ADT 時沒有特別的規範，只需要將概念清楚表達出來即可，也不需要特別寫出它的演算法是什麼。

Struct

寫完 ADT 後就要寫正規的 struct 了。struct 是 C 語言的結構，如果要使用多種資料型態來做運算，而且資料間又有關係，就可以用 struct 來包裝不同型態的資料。基本的 struct 宣告語法如下：

struct 結構名稱{ 資料型態 變數名稱; };

舉個例子，你可以這樣定義一個學生的資料，別忘了再最後加上分號：

struct Student{
    char name[10];
    int age;
    int gender;
    char studentid[10];
    char dept[10];
};

struct Student Noob; // 宣告一個學生 Noob

大概用這樣就可以宣告完一個結構了。

另外提到 struct 一定要講到 typedef，typedef 可以用來為資料型態或自訂的結構建立別名，例如把剛剛建立的 Student 建立別名為 stu 後，就可以不用 struct 來宣告變數了，例如：

typedef Student stu;
stu Noob;

二分搜尋法

學完這些東西，最後來看一下二分搜尋法吧。

有玩過終極密碼嗎？想要快速的把遊戲玩完，方法就是一直喊中間的數：50、25、38、44、46、48、49、BOOM！這個概念其實就是二分搜尋法。

二分搜尋法適用於已經由小排到大的數列。每次都從數列的中間開始搜尋，如果中間這個數大於我們所要找的目標數，那就往左邊找；反之，再往右邊找。每次都可以把數列砍半，是很有效率的方式。

最快的情況下，若一次就找到，所需次數是 $1$。

若最慢的情況下，需要花多少時間呢？

假設我們花了 x 次才找到，也就是說 $1 - \frac{N}{2^{x}}$。

經過化減：

$2^{x} = N$
$log_{2}(2^{x}) = log_{2}N$
$x \times log_{2}2 = log_{2}N$
$x \times 1 = log_{2}N$

也就是說，最慢的情況下需要花 $log_{2}N$ 次才能找到。

延伸閱讀

• C語言-struct、union、enum | 鋼彈盪單槓
• about ADT @ 空中咖啡豆 :: 痞客邦 PIXNET ::

資料結構筆記 目錄

• 資料結構筆記(一)：演算法、時間複雜度、空間複雜度
• 資料結構筆記(二)：陣列、字串與指標
• 資料結構筆記(三)：抽象資料結構(ADT)與 Struct

是說念完資料結構的你有什麼感覺呢？