第三天 抽象数据类型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;
}
