資料結構筆記(三)：抽象資料結構(ADT)與Struct
資料結構還有一個很重要的東西，這次把它放在最後講，也就是抽象資料結構。
資料結構還有一個很重要的東西，這次把它放在最後講，也就是抽象資料結構。
抽象資料型態 ADT
首先，抽象資料型態（Abstract Data Type，光聽就很抽象），是一種只定義數學觀念，將資料和操作一起思考的觀念。這種資料型態著重於資料的運算，並不考慮實作時的細節或資料本身的性質。
例如我們可以很簡單的寫出正整數的 ADT：
物件定義：正整數是指從零開始一直到 INT_MAX 的有順序整數。
方法定義：
Zero()：即整數 0Equal(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$ 次才能找到。
延伸閱讀
資料結構筆記 目錄
- 資料結構筆記(一)：演算法、時間複雜度、空間複雜度
- 資料結構筆記(二)：陣列、字串與指標
- 資料結構筆記(三)：抽象資料結構(ADT)與 Struct
是說念完資料結構的你有什麼感覺呢？