第三天 抽象數據類型ADT
先給定義：抽象數據類型abstract data type是一種只通過接口訪問的數據類型（值的集合以及作用於其上的運算組合）。
A set of data values and associated Operations that are precisely specifIEd independent of any particular implementation.
主要在於這個詞abstract。它使得此data type只能通過接口來訪問數據。數據的表示法及實現的運算都存在在實現中，用戶不能通過接口看到實現。想想，有點OO的意思吧, 它和class這樣的東西有這樣的共同點（封裝怎麼也算是OO三個重要特點之一），按照我的理解來說，class便是一種ADT，或者它在語法層面更高級一點。
真正的ADT比較苛刻，我們的串不算一個。為什麼？我們都可以直接提領它和它的地址，沒有接口在中間。我們可以string str=”this is a string”；printf(“%c”, str[1]);不需要寫一個函數來代替這個運算符：printf(“%c”,str.getchar(1));當然我們可以定做一個完全ADT的string。
下面給一個熟悉的例子：下堆棧STACK。
其實就是我們說的LIFO（last in first out）的堆棧，和它對應的那個我們常叫它隊列FIFO（first in first out）。
我們假設這個抽象數據類型有這樣幾種操作:初始化、壓棧、出棧、清空。
在stack.h中我們定義下面的函數：此代碼寫在stack.h中
void stack_init( int );
Int stack_empty();
void stack_push(item);
Item stack_pop();
下面在選擇實現方式的時候，我們可以有很多種方法：自己完全定義或者拿來現成的。數組可以吧，鏈表也可以，
給一個數組的實現：
#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]; }
我使用其它的好不好？比如串?不好，串太狹隘了，字符已經局限了它的作為，此處非它擅長（並不是不行，只是在效率和實現復雜度上不可取）。
看起來一個ADT並不復雜，定義好數據和接口便可以付諸使用。現實是，這個棧的邏輯關系並不復雜，對於很有經驗的熟悉的東西作ADT可能容易。面對一個新問題，我們如何周全的設計它是關鍵。
先看看怎麼用這個stack。
逆波蘭這個名次在數據結構中一定聽說過。正是使用棧的好時候。看看這個後綴表達式：5 9 8 + 4 6 * * 7 + *
我們需要人化一下：我們容易看懂的表達式是這樣的：5*((9+8)*(4*6)+7)
這個轉換過程我們需要借助堆棧幫我們完成，讀取一個逆波蘭式，如果是數字壓入棧，如果是運算符，將前面兩個入棧的
pop出來和讀到的運算符計算，再將結果壓入棧。就是這樣一個過程，我們看看代碼如何實現：
#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());
}
Ok，看出來了為了簡便沒有給出減法和除法的運算，因為這兩個運算沒有交換率，寫出代碼可能復雜些，不利於我們理解棧的使用。
會使用現成的ADT還沒有變成英雄，我們還需要自己來規劃並實現自己想得到的ADT。參考上面已經實現的ADT，我們可以照貓畫虎，畫多了就會得心應手。既然這樣我們來畫一個FIFO。比較麻煩的是，堆棧其實就在操作一個內存地址，進去出來都是這裡，哈，這是一個只有一個門的房間。FIFO隊列有前門和後門，前門出後門進。在實現其數據操作時需要兩個內存位置，稍微復雜了一些。先自己想想怎麼做，然後看下面的代碼好了。
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; }
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;
}