DIV CSS 佈局教程網

您现在的位置: DIV+CSS佈局教程網 >> 網頁腳本 >  >> JavaScript入門知識 >> AJAX入門 >> AJAX詳解
和 arden 一起學算法(第三天):抽象資料型別 ADT 與堆疊、佇列的實作
編輯:AJAX詳解     

第三天的主題是抽象資料型別(Abstract Data Type,ADT)。這是資料結構課程裡一個容易被快速帶過、卻決定後續所有實作品質的概念。

一、什麼是 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,只是標準庫沒這麼做。

二、經典範例:堆疊 STACK

堆疊就是 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 還不算真本事,真正的考驗是自己規劃並實作一個新的 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 相對容易;真正的難點是面對新問題時,如何周全地設計它——哪些操作該放進介面、哪些細節該藏起來、介面要抽象到什麼程度才既通用又不失真。這個判斷力沒有捷徑,只能透過反覆實作累積。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved