抽象数据类型 （abstract data type，ADT）

抽象数据类型是一些操作的集合。抽象数据类型是数学中的定义，在ADT中，我们不关心操作是如何被实现的。因此，这可以看做是模块化的扩充。

例如表，树，图和它们的操作一起可以看做是抽象数据类型，就想整数，实数和布尔变量是数据类型一样。整数，实数和布尔变量有它们的操作，抽象数据类型也有它们自己的操作。

表 ADT

我们将形如A1，A2，A3，...，An的一列数称为表。

表的大小：表中的元素的个数称为表的大小，大小为0的表称为空表。

对于除空表外，我们称Ai+1是Ai的后继，Ai-1是Ai的前驱，其中表的第一个元素A1不定义前驱，最后一个元素An不定义后继。

表的数组实现

对于表的所有操作都可以通过数组来实现，数组使得PrintList和Find以线性的时间执行，而FindIndex则花费常数的执行时间。然而，插入和删除的代价是昂贵的，例如在第一个元素位置插入，需要将后面的所有元素往后移一个位置出来，同理删除也是如此。因此这两种操作的最坏情况是O(N)。平均来看，这两种运算都要移动表的一半的元素，仍然需要线性时间。

因为插入和删除的运行时间是如此的慢，而且表的大小还需要事先知道，所以简单数组一般不用来实现表的结构。

链表

为了避免插入和删除的线性开销，我们需要运行表可以不连续存储，否则表的部分或全部需要整体移动，而如图表达了链表的一般想法。

在链表中，每个结构均包含有表元素和指向包含包含该元素后继元素的结构的指针，我们称之为next指针，最后一个元素的next指针指向null，ANSI C规定NULL为0。

程序设计细节

为了更方便的实现链表中的操作，我们通常会增加一个头结点，并将它指向第一个元素。

1 //链表的结构 2 struct Node; 3 typedef struct Node *ptrToNode ; 4 typedef ptrToNode List ; 5 typedef ptrToNode Position; 6  7 struct Node{ 8     ElementType Element; 9     Position Next;10 };11 12 //判断表是否为空13 int IsEmpty(List L){14     return L->Next == NULL;15 }16 17 //判断当前是否为链表的末尾18 int IsLast(Position P,List L){19     return P->Next == Null;20 }21 22 //查找函数23 Position Find(Element X,List L){24     Position P;25     P = L->Next;26     while(P != NULL && P->Element != X){27         P = P->Next;28     }29     return P;30 }31 32 //删除元素33 void Delet(ElementType X,List L){34     Position P, TempNode;35      P = FindPrevious(X, L);36      if(!IsLast(P,L)){37          TempNode = P->Next;38          P->Next = TempNode->Next;39          free(TmpNode);40      }41 }42 43 //查找某元素的前一个元素44 Position FindPrevious(ElementType X,List L){45     Position P;46     P = L;47     while(P->Next != NULL && P->Next->Element != X){48         P = P->Next;49     }50     return P;51 }52 53 //插入元素54 void Insert(ElementType X,List L,Position P){55     Position TempNode ;56     TempNode = malloc(sizeof(struct Node));57     if(TempNode == NULL){58         printf("malloc error")；59         return ;60     }61     TempNode->Element = x;62     TempNode->Next = P->Next;63     p->Next = TempNode;64 }65 66 //删除链表67 void DeleteList(List L){68     Position P,Tmp;69     p = L->Next;70     L->Next = NULL;\71     while(p != NULL){72         Tmp = P->Next;73         free(p);74         p = Tmp;75     }76 }

双链表

当涉及到倒序扫描链表时，双链表就非常方便了。双链表和单链表的区别就是：双链表中存在两个指针域，一个指向当前元素的前驱，另一个指向当前元素的后继。有了双向链表，可以不用在访问当前元素的前一个元素了，不过，双链表方便的同时，增加了空间的开销。

循环链表

让最后的单元指向第一个单元构成循环，这样的链表被称为循环链表。它既可以有表头，也可以没有表头（若有表头，则最后一个元素指针指向表头）。

案例实战

一元多项式

我们可以用表来定义模拟一元多项式的抽象数据类型。对于大多数系数非零的多项式，我们可以采用一个简单的数组来进行存储，数组的下标表示多项式的次幂，下标的值表示多项式的系数。但是对于系数相差较大，大部分的系数为0的多项式，采用数组将会浪费极大的空间。下面我们就采用数组的方法来定义多项式的抽象数据类型。

1 typddef struct{ 2     int CoeffArray[ MaxDegree + 1 ]; 3     int HighPower; 4 }* Polynomial; 5  6 //多项式初始化为0 7 void ZeroPolynomial(Polynomial Poly){ 8     int i; 9     for( i=0; i <= MakDegree; i++){10         Poly->CoeffArray[i] = 0;11     }12     Poly->HighPower = 0;13 }14 15 //两个多项式相加16 void AddPolynomial(const Polynomial poly1, const Polynomial poly2, Polynomial polysum){17     int i;18     ZeroPolynomial(polysum);19     polysum->HighPower = Max(poly1->HighPower，poly2->HighPower);20     for( i = polysum->HighPower; i>=0; i--){21         polysum->CoeffArray[i] = poly1->CoeffArray[i] + poly2->CoeffArray[i];22     }23 }24 25 //两个多项式的乘法26 void MultPolynomial(const Polynomial poly1, const Polynomial poly2, Polynomial polymult){27     int i,j;28     ZeroPolynomial(polymult);29     polymult->HighPower = poly1->HighPower + poly2->HighPower;30     if(polymult->HighPower > MaxDegree){31         printf("MaxDegree ERROR");32     }else{33         for( i=0; i <= poly1->HighPower; i++ ){34             for( j=0; poly2->HighPower; j++){35                 polysum->CoeffArray[i+j] = poly1->CoeffArray[i] * poly2->CoeffArray[i];36             }37         }38     }39 }