Zi 字媒體

資料結構還有一個很重要的東西，這次把它放在最後講，也就是抽象資料結構。 抽象資料型態 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 是說念完資料結構的你有什麼感覺呢？