链表

Marcus

2025-02-12

algorithms

这节我们讲讲链表，书籍是Weiss的《数据结构与算法分析》

抽象数据类型

一个好的程序之一是每个模块都应该尽量的小而美，换句话说，每个模块是一个逻辑单位并执行某个特定的任务，它将通过调用其他模块而使本身变得很小。模块化有一些优点，比如调试小程序总比调试大程序容易得多；第二，多个人对一个模块化程序编程要简单一些；第三，一个写得好的模块化程序把某些以来关系只局限在某个例程中，修改调试会很方便。

抽象数据类型（ADT:abstract data type）是一些操作的集合，我们可以理解为数学上的抽象。例如将等式1+2=3改写为用未知量替代的方程x+y=z。也就是写成一些比较通用的形式。一般来说，在ADT中定义我们是不涉及如何实现操作的集合，所以这可以看作是模块化设计的扩充。因为我们正在设计一些通用程序。

对表、集合、图和他们的操作可以看作是抽象数据类型，就像整数、实数和布尔值是数据类型一样，它们各自有各自相关的操作。而抽象数据类型也有它们自己相关的操作，对集合ADT，我们可以有交、并、测量大小以及取余（取补集）的操作。或者，我们也可以只有两种操作：并和查找。这两种操作也在集合上定义了一种不同的ADT。

现在我们有一种简单的思想，重复的模块运用十分的讨厌，为此我们只将这些操作编写一遍，而在程序中如何部分需要在该ADT上运行其中一种函数的时候，我们就通过调用适当的函数来解决问题。如果有一些其他的细节，我们可以简单的修改该模块实现。本章我们将讨论几种最基本的数据结构：

表 ADT

现在，我们将处理一般形如$A_1,A_2,\cdots, A_n$的表，我们说这个表的大小为$n$。而$n=0$的情况下，也就是大小为0的表我们称为空表。

除空表以外，我们对$ 1< i < n$中的元素$A_{i+1}$称为是$A_i$的后继元，而$A_{i-1}$称为$A_{i}$的前驱元。表中的第一个元素是$A_1$，最后一个元素是$A_n$。对于这两个元素，前者不定义前驱元，后者不定义后继元，因为这是没有意义的。为了简单的讨论，我们现在只假设表中的元素是整数。

跟这些定义相关的是我们要在表ADT上就行的操作的集合，例如 PrintList和MakeEmpty。第一个是打印表的元素，第二个是创造一个空表。接着我们定义Find 表示返回特定关键字首次出现的位置。而Insert和Delete表示插入元素在指定位置和删除某个关键字。接着，我们记 FindKth返回某个元素的位置，例如FindKth($A_3$)返回3。若34,12,52,16,12是一个表，则Find(52)返回3；Insert(X,3)则把表变为34,12,X,52,16,12。而Delet(52)则把表变成34,12,X,16,12。

表的简单数组实现

对表的所有操作都可以通过数组来实现，虽然数组是动态指定的，但我们还是得对表的最大值进行估计。

数组的实现使得 PrintList和 Find是呈线性时间运行的，而 FindKth花费常数时间。但是插入和删除则花费更多的时间。比如插入，我们在位置0插入一个值，则首先需要将数组后移一个位置空出空间，而删除第一个元素需要将表中的元素全部向前移动一个单位，所以这两种最坏的情况都是O(N)的。所以在数组上建表其实是一种比较浪费资源的事情。

链表

为了避免插入和删除的线性开销，我们需要允许表可以不连续储存。否则表的部分或者全部都需要整体移动。现在给出一个链表（ linked list）的一般想法：

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

若P声明为指向一个结构的指针，那么P中的值就是主存中的一个位置，通过该位置就可以找到一个结构，该结构可以通过P -> FieldName访问。其中FieldName是我们想要考察的域的名字。例如上图，这个表有5个结构，恰好内存中分配的地址是1000,800,712,992,692.第一个结构的指针含有800，它提供了第二个指针的位置。其余每个结构也也有一个指针用于类似的目的，而指针只是一个数，在后面我们用箭头画出指针即可，因为这样更直观。

删除命令可以通过修改一个指针实现，例如下图：

而插入命令需要通过一次 malloc 调用动态的从系统得到一个新单元，如何执行两次指针调整，一般想法如下图给出：

程序的设计细节

我们现在开始按照上述一般想法来编写一些程序。我们使用一些标志来做识别，例如表的第一个元素，我们记为 Header（表头）或哑结点（Dummy node）。不过至于要不要使用表头则是个人的兴趣问题。

我们定义一些抽象函数，一般来说我们会有2个文件.h和.c的文件，原型我们存放在所谓的.h头文件中，而具体的函数声明存放在.c文件中。

#ifndef _List_H  // 防止头文件被多次重复定义
#define _List_H 

struct Node; //声明Node结构体
typedef struct Node *PtrToNode; //声明一个定位到Node结构的指针 PtrToNode
typedef PtrToNode List; //定义链表类型List，表示指向表中的元素
typedef PtrToNode Position; //定义链表的位置，表示表中某个元素的节点。

List MakeEmpty(List L); //创建空列表
int IsEmpty(List L); //判断列表是否为空
int IsLast(Position P, List L); //是否为表中最后一个元素
Position Find(ElementType X, List L); //查找是否含有元素X并返回位置
void Delete(ElementType X, List L); //删除特定元素X
Position FindPrevious(ElementType X, List L); //查找元素X的前一个元素
void Insert(ElementType X, List L, Position P); //插入X在表中的位置P
void DeleteList(List L); //删除整个表
Position Header(List L); //返回头的位置
Position First(List L); //返回第一个元素的位置
Position Advance(Position P); //返回P的下一个位置
ElementType Retrieve(Position P); //返回位置P的元素

#endif /* _List_H */ //结束头文件保护
/* Place in the implementation file */
struct Node //具体Node的实现：
{
    ElementType Element; //该结构包含一个元素Element和指向下一个节点位置的指针Next
    Position Next;
};

首先第一个函数是测试表是否是空的。

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

若表L的表头下一个元素为Null，则我们知道L是空的。

接着我们编写一个测试元素是否在表的末尾的函数

/* Return true if 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;
}

该函数定义了两个输入，一个是位置P，一个是表L，若L的第P个位置的下一个指针是Null，则说明P位置的元素是最后的一个元素。

若我们递归的定义Find函数，则我们必须想办法避免冗长的终止条件，我们可以使用 &&符号，若前半部分为假，则自动终止函数。

/* 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，一个是表L。给定位置P，并定义P是L表头的下一个元素的地址。现在通过条件判断P是否导向NUll或者P处的元素是否等于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)) /* Assumption of header use */
    {
        TmpCell = P->Next;
        P->Next = TmpCell->Next; /* Bypass deleted cell */
        free(TmpCell);
    }
}

给定位置P和Tmpceli，后者为储存被删除函数的临时变量。现在，定义P为X在L中的前一个元素（若存在的话），若P不是L中最后一个元素，则我们储存P的下一个元素的指针在TmpCeli。现在，重新令P的下一个元素链接到P的下一个元素再下一个元素的地址。最后删除元素X，释放TmpCeli的内存即可完成操作。

上述的 FindPrevious函数如下所示：

/* If X is not found, then Next field of returned */
/* Position is NULL */
/* Assumes 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;
}

最后一段代码是插入例程，我们将传入3个参数，要插入表中的元素X，表L和要插入的位置P

为了精准插入，我们需要调用 FindPrevious函数得知前一个值是什么。

/* Insert (after legal position P) */
/* Header implementation assumed */
/* Parameter L is unused in this implementation */

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;
}

该函数接受三个参数，要插入表的元素X，表L，还有要插入的位置P。定义临时变量TmpCeli的位置。首先，动态的分配一块内存给新的节点TmpCeli，若该元素分配为NULL，则返回分配错误。接着把X的指针储存在TmpCeli中，现在，为了完成插入操作，我们把原本在位置P的元素的下一个元素的指针分配给TmpCeli，这样就完成了对P的替换，接着，只需要把P的下一个指针指向Tmpceli，这样表就链接起来了。就成功的把X插入到P和P-next的中间。

常见的错误

在实际的编程中，也许我们会遇到一些诸如 memory access violation 或者 segmentation violation的报错，通常情况下，这意味着指针包含了伪地址。而这样的结果来源自初始化变量失败，例如下述代码的第一行若遗漏，则P就是未定义的，的人也不可能指向内存的有效部分。

/* Incorrect DeleteList algorithm */

void DeleteList(List L)
{
    Position P;

    P = L->Next; /* Header assumed */
    L->Next = NULL;
    while (P != NULL)
    {
        free(P);
        P = P->Next;
    }
}

另一个典型的错误是上述 Insert函数遗漏了最后一行代码，若P是NULL，该指向就是非法的。但函数知道P不是NULL，所以例程不会有问题。一些编译器可能会给你做隐式检查，不过这不是c标准的一部分。所以有时候你可以在一个编译器上运行程序，在另一个编译器上则不行。

第二种错误涉及何时使用或者不使用malloc来获取一个新的单元。声明一个指向某结构的指针并不创建该结构，而只是给出足够的空间容纳结构可能会使用的地址。而创建尚未被声明过的记录的唯一方法就是使用malloc库函数，它会迫使系统创建一个新的结构并返回该结构的指针。

当你不需要这些东西的时候，你可以使用free函数来回收这段空间，free(P) 的结果是：P指向的数据是无定义的，但指针还存在。

当我们把free应用在链表中，那么调用free的次数应该对于表的大小，若表头存在就再加1，否则你会得到一个错误的程序。多一点你就会浪费空间也浪费时间。也许你在使用了大量空间之后，新单元的申请会返回NULL。

在执行一次删除表后，我们应该需要一个临时变量来储存被放弃的单元，因为你在删除后将不能引用它。所以上述free的例子不太完整，我们现在给出较完整的代码：

/* Correct DeleteList algorithm */

void DeleteList(List L)
{
    Position P, Tmp;

    P = L->Next; /* Header assumed */
    L->Next = NULL;
    while (P != NULL)
    {
        Tmp = P->Next; // 先保存下一个节点
        free(P);       // 释放当前节点
        P = Tmp;       // 移动到下一个节点
    }
}

最后提一个警告，malloc(sizeof(PtrToNode))是合法的，但是它并不给结构体分配足够的空间，它只会给指针分配一个空间。

双链表

在某些时候，倒序扫描链表是很方便的，标准实现方法在这时候不能发挥作用，但是解决方法异常的简单，只需要在结构上附加一个域，它包含一个指向前一个单元的指针。但开销是一个附加的链。增加了空间的需求且使得插入和删除的开销增加一倍，因为有更多的指针需要定位，但简化了删除操作，因为你不再被迫使用一个指向前驱元的指针来访问一个关键字。

循环链表

另一个思想是，将最后一个单元反过来直指第一个单元。它可以有表头，也可以没有表头。（若存在表头，则最后的单元就指向它）并且还可以是双向的链表。下面是一个简单的流程图：

1	A <--> B <--> C <--> A

例子

我们提供三个使用链表的例子，第一个是表示一元多项式的简单方法，第二个是在某些情况下以线性时间进行排序的方法。最后我们介绍一个复杂的例子，它讲述链表如何用于大学的课程注册。

多项式 ADT

我们可以用表定义一种关于一元（具有非负次幂）多项式的抽象数据类型。令$f(x) = \sum^n_{i=0} a_ix^i$。若大部分系数非零，则我们可以用一个简单的数组来储存这些系数（更数学的来说，可以当作是多项式域里面的一个向量来看），然后我们可以编写一些对多项式进行加、减、乘、微分等其他操作的例程，我们将忽略初始化多项式为零的时间，则乘法例程的运行时间将和两个多项式的次数的乘机成正比。另一个问题接踵而至，若$P_1(x)$是次数为1000的多项式，而$P_2(x)$是次数为1990的多项式，那么这个时间就可能不太能接受了。因为大部分的时间都花费在了乘以0和单步调试两个输入多项式的大量不存在的部分上。

typedef struct
{
    int CoeffArray[MaxDegree + 1];
    int HighPower;
} *Polynomial;

我们定义了一个数组，它用来储存系数，一个是存储多项式的最高次幂。

然后我们来定义初始化多项式的函数：


void ZeroPolynomial(Polynomial Poly)
{
    int i;
    for (i = 0; i <= MaxDegree; i++)
        Poly->CoeffArray[i] = 0;
    Poly->HighPower = 0;
}

该函数体通过指针设定Poly里面的数组都是0，然后初始化最高次幂为0.

然后我们定义多项式加法，对任意两个多项式$f,g$，则$f+g$就是对应幂次的多项式的加法：$f=10x^2+6,g=5x^2+10x+7$，则$f+g = (10+5)x^2 + 10x + (6+7)$

void AddPolynomial(const Polynomial Poly1, const Polynomial Poly2, Polynomial PolySum)
{
    int i;
    ZeroPolynomial(PolySum);
    PolySum->HighPower = Max(Poly1->HighPower, Poly2->HighPower);
    for (i = PolySum->HighPower; i >= 0; i--)
        PolySum->CoeffArray[i] = Poly1->CoeffArray[i] + Poly2->CoeffArray[i];
}

这个模块首先引入三个参数，多项式1，多项式2，还有多项式sum，最后是用来储存结果的多项式。接着调用zeroPolynomial函数初始化PolySum多项式。第二步，由于多项式的和最高次幂取决于谁的次数高，所以Max函数在2个幂次里面返回一个值最大的。最后是加法，把每个位置上的系数一一配对然后加起来，接着存储到PolySum里面就结束了。

然后是乘法：

void MultiPolynomial(const Polynomial Poly1, const Polynomial Poly2, Polynomial PolyProd)
{
    int i, j;

    ZeroPolynomial(PolyProd);
    PolyProd->HighPower = Poly1->HighPower + Poly2->HighPower;

    if (PolyProd->HighPower > MaxDegree)
        Error("Exceeded array size");
    else
    {
        for (i = 0; i <= Poly1->HighPower; i++)
            for (j = 0; j <= Poly2->HighPower; j++)
                PolyProd->CoeffArray[i + j] += Poly1->CoeffArray[i] * Poly2->CoeffArray[j];
    }
}

对于乘法，若$P_1(x) = 10x^2+2x+1$，而$P_2(x) =x^2+x+1$，则$P_1 \times P_2 = 10x^2(x^2+x+1) + 2x(x^2+x+1) + (x^2+x+1)$，即把每一个$P_1$的项都去乘整个$P_2$，然后加起来。显然的事情是，若$P_1$有n个项，而$P_2$有$m$个，则$P_1 \times P_2$的项的个数就取决于$P_2$到底有多少个项。

另一种实现方法是用单链表，我们可以把多项式的每一项存在一个单元内，然后让这些单元按照次数递减的方式排序。例如下述例子，令$P_1 = 10x^2+2x+1$，$P_2 = x^2 + 3x + 7$，那么两个链表可以如下表示：

1 2	P_1 : (2) 10 --> (1) 2 --> (0) 1 P_2 : (2) 1 --> (1) 3 --> (0) 7

代码：

typedef struct Node *PtrToNode;

struct Node
{
    int Coefficient; # 系数
    int Exponent; #多项式的指针
    PtrToNode Next; #下一个节点的指针
};

typedef PtrToNode Polynomial; /* Nodes sorted by exponent */

利用链表的一个难点是如何合并同类项。

# 定义结构体

typedef struct {
    PolynomialNode* head;
    int degree;
} Polynomial

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构
typedef struct Node {
    int Coefficient; // 系数
    int Exponent;    // 指数
    struct Node* Next; // 指向下一个节点的指针
} Node, *Polynomial;

// 创建新节点
Node* CreateNode(int coeff, int exp) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        fprintf(stderr, "内存分配失败\n");
        exit(1);
    }
    newNode->Coefficient = coeff;
    newNode->Exponent = exp;
    newNode->Next = NULL;
    return newNode;
}

// 插入节点（按指数排序）
void InsertNode(Polynomial* P, int coeff, int exp) {
    // 创建一个新节点，存储系数和指数
    Node* newNode = CreateNode(coeff, exp);

    // 如果链表为空，直接将新节点作为头节点
    if (*P == NULL) {
        *P = newNode;
    } else {
        // 初始化 current 为链表的头节点，prev 为 NULL
        Node* current = *P;
        Node* prev = NULL;

        // 遍历链表，找到插入位置
        // 按指数降序排列，找到第一个小于等于 exp 的节点
        while (current != NULL && current->Exponent > exp) {
            prev = current;          // 保存当前节点
            current = current->Next; // 移动到下一个节点
        }

        // 如果找到相同指数的节点，合并同类项
        if (current != NULL && current->Exponent == exp) {
            current->Coefficient += coeff; // 合并系数
            free(newNode);                // 释放新节点，因为不需要插入
        } else {
            // 如果没有找到相同指数的节点，插入新节点
            if (prev == NULL) {
                // 插入到链表头部
                newNode->Next = *P;
                *P = newNode;
            } else {
                // 插入到 prev 和 current 之间
                newNode->Next = current;
                prev->Next = newNode;
            }
        }
    }
}

// 多项式乘法
Polynomial MultiplyPolynomials(Polynomial Poly1, Polynomial Poly2) {
    Polynomial result = NULL;
    Node* p1 = Poly1;
    Node* p2 = Poly2;

    while (p1 != NULL) {
        p2 = Poly2; // 重置 p2
        while (p2 != NULL) {
            int coeff = p1->Coefficient * p2->Coefficient;
            int exp = p1->Exponent + p2->Exponent;
            InsertNode(&result, coeff, exp); // 插入结果多项式
            p2 = p2->Next;
        }
        p1 = p1->Next;
    }

    return result;
}

// 打印多项式
void PrintPolynomial(Polynomial P) {
    while (P != NULL) {
        printf("%dx^%d", P->Coefficient, P->Exponent);
        if (P->Next != NULL) {
            printf(" + ");
        }
        P = P->Next;
    }
    printf("\n");
}

// 释放多项式内存
void FreePolynomial(Polynomial P) {
    Node* temp;
    while (P != NULL) {
        temp = P;
        P = P->Next;
        free(temp);
    }
}

基数排序

链表的第二个例子是基数排序，有时候也叫卡式排序，因为直到现代计算机的出现之前，它一直用于对老式穿孔卡的排序

若现在我们存在$n$个整数，范围在$1$到$M$（或者$0 $到$M-1$。那么我们可以用这个信息得到一种快速排序，或者叫桶式排序。我们设一个数组，叫 Count，大小为M，并初始化为0。于是Count存在M个单元（或者叫桶），开始时它们是空的，当$A_i$被读入时，Count[$A_i$]+1，在所有的输入读入之后，扫描数组Count并打印排好序的表，该算法花费$O(M+n)$，若$M = \Theta (N)$，则桶式排序是O(N)的。

证明如下：我们假设排序方法是快速排序，快速排序的时间复杂度在$O(N\log(N))$，再设存在$m$个桶，则每个桶里面存在$n/m$个元素，排序后花费的时间是$(n/m)\log(n/m)$，一共有m个桶，所以总的排序花费$O(m\times (n/m)\log(n/m) = n(\log(n)-\log(m))$，把排序后的数据合并成一个数组花费大概$O(N)$，因为桶的数量是常数，所以$mN = O(N)$，加起来就是$O(2n+c)$，$c = n(\log(n)-\log(m))$，现在，数据限定的是整数，所以范围$M \geq N$。最终复杂度就是$O(N+M)$，若$M = \Theta(N)$，这时候$O(2N) = O(N)$。

多重表

最后我们说一个复杂的实现，一所有4万名学生和2千5百门课程的大学需要生成两种类型的报告，一是列出每个班的注册者，而是报告列出每个学生注册的班级。

常见的方法是使用二维数组，而这样的数据大概能有一亿个，但平均一个学生注册3门课，所以真正有意义的数据只有12万项，大概占里面的0.1%。

该链表具体情况如下：首先学生自己选择的课是一个循环列表，而每门课的数据也是用循环列表储存，若c1有一个学生s1，则c1和s1指向的数据包含至少4个指针，一个是指向前驱元s1的指针和指向前驱元c1的指针，接着是指向下一门课和选择了c1的同学的指针：

具体的实现情况如下，例如我们查询$c_3$学生的信息，由于我们需要这门课包含了多少学生，以及该学生选了多少门课，所以首先再c3表头开始找数据，直到发现第一个选择该门课的学生si，这个时候停止搜索c3中其他学生的信息，转而找学生si的选课情况知道返回si单元，然后跳转回c3重新寻找下一个选了c3的学生sj，

栈 ADT

栈模型

栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈的顶（Top），栈的基本操作有2个，Push（进栈）和 Pop（出栈）。前者相当于是插入元素，后者是删除最后插入的元素。最后插入的元素可以通过使用Top例程在执行Pop之前考察。对空栈执行pop可能会导致错误，这一般是ADT的错误，另一方面，若运行push的时候空间用尽是一个实现错误，不是ADT错误。

一个简单的栈结构和操作可以这样描述：

| Top |           | es  |        |Top|
| en  |  Push(es) | Top |  Pop   | en|
| en-1|   ---->   | en  | ---->  |...|
| ... |           | ... |        |e1 |
| e1  |           | e1  |

所以栈有时叫LIFO（后进先出）表。普通的清空栈的操作和判断是否空栈的测试都是栈的操作指令系统的一部分，但是对栈能做的基本上只有pop和push操作。

栈的实现

栈是一个表，所以实际上实现表的方法都能实现栈。我们给出2个方法，一个是指针，一个是数组。

链表实现

栈的第一种实现方法是使用单链表。我们通过在表顶插入实现push，删除表的顶端元素实现Pop。Top操作只是考察顶端元素并返回他的值。有时候需要Pop和Top操作合二为一。

#include <Stack_h>

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode Stack;

int IsEmpty(Stack S);
Stack CreateStack(void);
void DisposeStack(Stack S);
void MakeEmpty(Stack S);
void Push(ElementType X, Stack S);
ElementType Top(Stack S);
void Pop(Stack S);

#endif /* _Stack_h */

/* Place in implementation file */
/* Stack implementation is a linked list with a header */
struct Node
{
    ElementType Element;
    PtrToNode Next;
};

和之前一样，我们依然声明Node（节点）为一个结构，在结尾的Node给出了详细的结构，包含一段数据和一个指向下一个元素的指针Next。typedef定义了一个指向结构的指针PtrToNode。接着定义Stack也是PtrToNode的结构。可以直接用Stack定义所需的链表结构。

1	Stack myStack; // 等价于 struct Node* myStack;

其他的是一些函数，等一下讲实现的时候说明。

首先是第一个函数。

int IsEmpty(Stack S)
{
    return S->Next == NULL;
}

该函数接收一个栈结构S，若S表头的下一个元素为空，则返回1。

Stack CreateStack(void)
{
    Stack S;
    S = malloc(sizeof(struct Node));
    if (S == NULL)
        FatalError("Out of space!!!");
    S->Next = NULL;
    MakeEmpty(S);
    return S;
}

void MakeEmpty(Stack S)
{
    if (S == NULL)
        Error("Must use CreateStack first");
    else
        while (!IsEmpty(S))
            Pop(S);
}

该代码创建了一个空栈的例程,MakeEmpty函数是用来确保栈是空的。它会一直pop栈中的元素，直到栈是空的。

void Pop(Stack S)
{
    PtrToNode FirstCell;
    if (IsEmpty(S))
        Error("Empty stack");
    else
    {
        FirstCell = S->Next;
        S->Next = S->Next->Next;
        free(FirstCell);
    }
}

Pop函数是通过删除表的前端元素实现的。

void Push(ElementType X, Stack S) {
    PtrToNode TmpCell;

    TmpCell = malloc(sizeof(struct Node));
    if (TmpCell == NULL)
        FatalError("Out of space!!!");
    else
    {
        TmpCell->Element = X;
        TmpCell->Next = S->Next;
        S->Next = TmpCell;
    }
}

该函数接受2个参数，元素X和栈S。

首先给定一个临时变量TmpCell用来储存临时变量。接着申请一个Node结构大小的内存。若临时变量为空，返回插入失败。否则，令临时变量的内容为X，令Tmpcell下一个指针指向表头的下一个单元。接着令表头的下一个元素指向Tmpcell就完成了压栈操作。

ElementType Top(Stack S)
{
    if (!IsEmpty(S))
        return S->Next->Element;
    Error("Empty stack");
    return 0; /* Return value used to avoid warning */
}

Top函数用来检查栈顶元素。

所有的操作均花费常数时间，比较花费的地方主要在于free和malloc函数，可以通过使用第二个栈去避免，第二个栈初始化为空，当一个单元要从第一个栈弹出时，它只是被丢在第二个栈中。此后，当第一个栈需要新单元，它首先去检查第二个栈。

数组实现栈

数组的使用方法可能是更好的结果，缺点是需要提前声明一个数组的大小。

用数组实现栈稍微简单些，每一个栈都有一个栈顶的索引，称它为TopOfStack。而空栈的索引是-1，为了将一个元素压栈。则将需要将索引+1.然后令Stack[TopOfStack] = X。其中Stack是一个具体的数组。

一个影响栈的执行效率的问题是错误检测，我们的链表实现是有仔细的检查错误的，比如，对空栈的pop和push或者是对满栈的push都会引起程序崩溃。显然我门不希望出现这种情况。数组去做检查效率非常的慢，一半来说除非在重要场合，否则一般会省去这种检查。

#ifndef _Stack_h

struct StackRecord;
typedef struct StackRecord *Stack;

int IsEmpty(Stack S);
int IsFull(Stack S);
Stack CreateStack(int MaxElements);
void DisposeStack(Stack S);
void MakeEmpty(Stack S);
void Push(ElementType X, Stack S);
ElementType Top(Stack S);
void Pop(Stack S);
ElementType TopAndPop(Stack S);

#endif /* _Stack_h */

/* Place in implementation file */
/* Stack implementation is a dynamically allocated array */
#define EmptyTOS (-1)
#define MinStackSize (5)

struct StackRecord
{
    int Capacity;
    int TopOfStack;
    ElementType *Array;
};

数组的实现需要的东西如上。Stack被定义为一个指向结构体的指针，其包含TopOfStack的大小和Capcity的大小。也叫做域。一旦知道最大容量，则栈可以被动态的确定。

在CreatStack中，我们将创建一个具有给定最大值的栈。

Stack CreateStack(int MaxElements)
{
    Stack S;

    if (MaxElements < MinStackSize)
        Error("Stack size is too small!");

    S = malloc(sizeof(struct StackRecord));
    if (S == NULL)
        FatalError("Out of space!!!");

    S->Array = malloc(sizeof(ElementType) * MaxElements);
    if (S->Array == NULL)
        FatalError("Out of space!!!");
    S->Capacity = MaxElements;
    MakeEmpty(S);

    return S;
}

函数接受一个最大元素数量的参数，一开始我们定义MinStackSize = 5，若低于这个数量，则栈太小。需要重新配置。

在DisposeStack中，该函数用于释放一个栈结构。该程序首先释放栈数组，然后释放栈结构体。

void DisposeStack(Stack S)
{
    if (S != NULL)
    {
        free(S->Array);
        free(S);
    }
}

接着是检测一个空栈，生成空栈和push操作的例子

int IsEmpty(Stack S)
{
    return S->TopOfStack == EmptyTOS;
}

void MakeEmpty(Stack S)
{
    S->TopOfStack = EmptyTOS;
}

void Push(ElementType X, Stack S)
{
    if (IsFull(S))
        Error("Full stack");
    else
        S->Array[++S->TopOfStack] = X;
}

接着是返回栈顶的例子

ElementType Top(Stack S)
{
    if (!IsEmpty(S))
        return S->Array[S->TopOfStack];
    Error("Empty stack");
    return 0; /* Return value used to avoid warning */
}

然后是Pop操作

void Pop(Stack S)
{
    if (IsEmpty(S))
        Error("Empty stack");
    else
        S->TopOfStack--;
}

++表示+1，—表示-1，这是直接将栈的空间减小1。

ElementType TopAndPop(Stack S)
{
    if (!IsEmpty(S))
        return S->Array[S->TopOfStack--];
    Error("Empty stack");
    return 0; /* Return value used to avoid warning */
}

该例子是给出栈顶并pop元素的例子。