資料結構筆記(三):抽象資料結構(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 一定要講到 typedeftypedef 可以用來為資料型態或自訂的結構建立別名,例如把剛剛建立的 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$ 次才能找到。

延伸閱讀

資料結構筆記 目錄

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