第三天的主題是抽象資料型別(Abstract Data Type,ADT)。這是資料結構課程裡一個容易被快速帶過、卻決定後續所有實作品質的概念。
先給定義:抽象資料型別是一種只能透過介面存取的資料型別——它是「值的集合」加上「作用於這些值上的運算組合」,而這一切與任何特定實作無關。英文的說法更精準:a set of data values and associated operations that are precisely specified independent of any particular implementation。
重點在 abstract 這個詞。它使得這個型別只能透過介面存取資料:資料的表示法與運算的實作都藏在實作裡,使用者從介面看不到。
想一下,這是不是有點物件導向的味道?封裝本來就是 OO 的三個重要特點之一,所以 ADT 與 class 有共同點——按照我的理解,class 就是一種 ADT,只不過它在語法層面更高階一點。
不過嚴格定義下的 ADT 比我們平常想的苛刻。我們熟悉的 string 其實不算一個真正的 ADT。為什麼?因為我們可以直接對它取值、取它的位址,中間沒有介面隔著:
string str = "this is a string";
printf("%c", str[1]);
真要符合 ADT 的形式,就得寫成 printf("%c", str.getchar(1));——由一個函式代替運算子。我們當然可以自己定義一個完全 ADT 化的 string,只是標準庫沒這麼做。
堆疊就是 LIFO(Last In First Out),與它相對的是佇列 FIFO(First In First Out)。
我們假設這個 ADT 有四種操作:初始化、壓棧、出棧、清空。先在 stack.h 中宣告介面:
void stack_init(int); int stack_empty(); void stack_push(Item); Item stack_pop();
接著才是選實作方式。陣列可以,鏈表也可以,甚至自己完全定義一種結構。這就是 ADT 的意義:介面先定下來,實作可以替換。
#include <stdlib.h>
#include "Item.h"
#include "STACK.h"
static Item *s;
static int N;
void STACKinit(int maxN)
{ s = malloc(maxN * sizeof(Item)); N = 0; }
int STACKempty()
{ return N == 0; }
void STACKpush(Item item)
{ s[N++] = item; }
Item STACKpop()
{ return s[--N]; }
要不要改用 string 之類現成的東西?不好。字串太狹隘了——它已被字元這個前提局限住,在這裡並非它所擅長(不是不能做,而是效率與實作複雜度都不划算)。選實作的判斷標準,是看它與問題本質的契合度。
資料結構課一定聽過「逆波蘭」這個名字,而它正是堆疊最漂亮的應用場景。看這個後綴表達式:
5 9 8 + 4 6 * * 7 + *
我們人腦容易讀的形式是:
5 * ((9 + 8) * (4 * 6) + 7)
兩者之間的轉換,可以借助堆疊完成。演算法很簡單:掃過整個逆波蘭式,遇到數字就壓棧;遇到運算子就把棧頂兩個元素弹出來做運算,再把結果壓回去。掃完之後,棧裡剩下的唯一值就是答案。
#include <stdio.h>
#include <string.h>
#include "Item.h"
#include "STACK.h"
main(int argc, char *argv[])
{
char *a = argv[1];
int i, N = strlen(a);
STACKinit(N);
for (i = 0; i < N; i++)
{
if (a[i] == '+')
STACKpush(STACKpop() + STACKpop());
if (a[i] == '*')
STACKpush(STACKpop() * STACKpop());
if ((a[i] >= '0') && (a[i] <= '9'))
{
STACKpush(0);
while ((a[i] >= '0') && (a[i] <= '9'))
STACKpush(10 * STACKpop() + (a[i++] - '0'));
}
}
printf("%d \n", STACKpop());
}
注意多位数字的處理:內層那個 while 用 10 * STACKpop() + (a[i++] - '0') 逐位組出完整數字,這是個很常被忽略的細節。
程式中刻意沒有實作減法與除法,因為這兩個運算沒有交換律——兩個 pop 的順序會影響結果,程式碼得先暫存再運算,寫起來複雜些,反而不利於理解堆疊本身。這裡只保留加法與乘法,把焦點放在資料結構上。
會用現成的 ADT 還不算真本事,真正的考驗是自己規劃並實作一個新的 ADT。參照上面已完成的堆疊照貓畫虎,畫多了自然得心應手。
那就來畫一個 FIFO 佇列。堆疊其實只操作一個記憶體位置,進去出來都是同一處——像一個只有一道門的房間。佇列有前後兩道門:前門出、後門進,實作時需要兩個指標(head 與 tail),稍微複雜一些。
介面宣告:
void QUEUEinit(int); int QUEUEempty(); void QUEUEput(Item); Item QUEUEget();
#include <stdlib.h>
#include "Item.h"
#include "QUEUE.h"
typedef struct QUEUEnode* link;
struct QUEUEnode { Item item; link next; };
static link head, tail;
link NEW(Item item, link next)
{
link x = malloc(sizeof *x);
x->item = item;
x->next = next;
return x;
}
void QUEUEinit(int maxN)
{ head = NULL; }
int QUEUEempty()
{ return head == NULL; }
void QUEUEput(Item item)
{
if (head == NULL)
{ head = (tail = NEW(item, head)); return; }
tail->next = NEW(item, tail->next);
tail = tail->next;
}
Item QUEUEget()
{
Item item = head->item;
link t = head->next;
free(head);
head = t;
return item;
}
這裡有個值得留意的細節:佇列用鏈表實作時,QUEUEinit 的 maxN 參數實際上沒被用到——鏈表按需配置,不需要預先指定容量。這正是 ADT 介面設計的常見張力:介面要同時服務多種實作,難免會有某些參數在某種實作下是多餘的。設計介面時要在「通用性」與「精確性」之間拿捏。
一個 ADT 看起來並不複雜:定義好資料與介面就能付諸使用。堆疊的邏輯關係很單純,對於熟悉的東西做 ADT 相對容易;真正的難點是面對新問題時,如何周全地設計它——哪些操作該放進介面、哪些細節該藏起來、介面要抽象到什麼程度才既通用又不失真。這個判斷力沒有捷徑,只能透過反覆實作累積。