表

抽象数据类型

程序设计的基本法则之一是例程不应超过一页。
可以通过把程序分割为一些模块来实现。

模块化的优点：

• 调试容易
• 多个人同时对一个模块式程序编程要更容易
• 修改容易。

<i>抽象数据类型</i>是一些操作的集合。

表ADT

我们称大小为0的表为空表(empty list)。
对于除空表外的任何表，我们说A_i+1后继A_i(或继A_i之后)并称A_i-t(i<N)前驱A_i(i>1)。

表中的第一个元素是A₁，而最后一个元素是A_N。我们将不定义A₁的前驱元，也不定义A_N的后继元。元素A_i在表中的位置为i。

表的简单数组实现

对表的所有操作都可以通过使用数组来实现。

数组是动态指定的，我们需要对表的大小进行估计，通常需要估计得大一些，从而会浪费大量的空间。

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

链表

链表由一系列不必在内存中相连的结构组成。
每一个结构均含有表元素和指向包含该元素后继元的结构的指针。我们称之为Next指针。最后一个单元的Next指针指向NULL。

程序设计细节

有几处地方可能会出问题。

• 并不存在从所给定义出发在表的前面插入元素的真正线性的方法。
• 从表的前面实行删除是一个特殊情况，因为他改变了表的起始端。
• 删除算法要求我们记住被删除元素前面的表元。

事实上，稍作一个简单的变化就能够解决所有这三个问题。
我们将留出一个标志结点，有时候称之为表头(header)或哑节点(dummy node)。我们约定，表头在位置0处。
使用表头你能使我们能够表达最基本的指针操作且又不致使特殊情形的代码含混不清。

#ifndef _List_H

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;

List MakeEmpty(List L);
int IsEmpty(List L);
int Islast( Position P, List L );
Position Find( ElmenetType X, List L );
void Insert( ElementType X, List L, Posistion P );
void DeleteList( List L );
Position Header( List L );
Position First( List L );
Position Advance( Position P );
ElementType Retrieve( Position P );

#endif

struct Node
{
    ElementType Element;
    Position Next;
};

/* Return true if L is Empty */
int IsEmpty(List L)
{
    return L->Next == NULL;
}

/* Return true is P is the last position in list L */
/* parameter L is unused in this implementation */
int IsLast( Position P, List L )
{
    return P->Next == NULL;
}

/* Return Position of X in L; NULL if not found */
Position Find(ElementType X, List L)
{
    Position P;
    P = L->Next;
    while(P != NULL && P->Element != X)
        P = P->Next;
    return P;
}

删除某个元素X，我们需要考虑：如果X出现不止一次或者根本就没有，那么我们做什么？我们的例子就会删除第一次出现的X，如果X不在表中我们就什么也不做。
为此，我们通过调用FindPrevious函数(类似与Find函数)找出含有X的表元的前驱元P。

/* Delete first occurrence of X from a list */
/* Assume use of a header node */
void Delete(ElementType X, List L)
{
    Position P,TmpCell;
    P = FindPrevious(X, L)
    if (!IsLast(P, L))
    {
        TmpCell = P->Next;
        P->Next = TmpCell->Next;
        free(TmpCell);
    }
}

/* if x is not found, then next field of returned */
/* Position is NULL */
/* Assume a header */

Position FindPrevious(ElementType X, List L)
{
    Position P;
    P = L;
    while(P->Next != NULL && P->Next->Element != X)
        P = P->Next;
    return P;
}

插入程序，将要插入的元素与表L和位置P一起传入。

void Insert(ElementType X, List L, Position P)
{
    Position TmpCell;
    TmpCell = malloc(sizeof(struct Node));
    if(TmpCell == NULL)
        FatalError("Out of space!!");
    TmpCell->Element= X;
    TmpCell->Next = P->Next;
    P->Next = TmpCell;
}

常见的错误

最常遇到的错误是你的程序因来自系统的棘手的错误信息而崩溃。