线性结构

线性结构介绍线性表的抽象定义，并分别讨论基于顺序存储和链式存储的线性表的实现方法。同时将介绍两种典型且应用广泛的线性表：堆栈和队列。

线性表的基本操作是插入和删除，堆栈是插入和删除只发生在同一端的线性表，而队列的插入和删除则分别发生在有序序列的两端，即一端只做插入，一端只做删除。

线性表的定义与实现

线性表的定义

线性表(Linear List)是由同一类型的元素构成的有序序列的线性结构。线性表的抽象数据描述为：

类型名称：线性表(List)

数据对象集: 线性表是由 n 个元素构成的有序序列。

操作集： 线性表 L∈List，整数 i 表示位置，元素 X∈ElementType，线性表的主要操作有：

1. List MakeEmpty()：初始化一个空的线性表；

2. ElementType FindKth(List L,int i)：根据位序 i 返回相应元素；

3. Position Find(List L,ElementType X)：在线性表 L 中查找 X 第一次出现的位置；

4. bool Insert(List L,ElementType X,int i)：在 L 的指定位序 i 之前插入一个新元素 X；

5. bool Delete(List L, int i)：从 L 中删除指定位序 i 的元素；

6. int Length(List L)：返回线性表 L 的长度。

线性表的顺序存储实现

线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素。因此可以用一维数组来表示顺序存储的数据区域。

考虑到线性表的运算有插入、删除操作，即表的长度是动态变化的，因此数组的容量需要设计得足够大，可以根据实际情况来定义一个 MAXSIZE 表示数组的最大容量。

#define ERROR -1
#define MAXSIZE 1000            /* 线性表的最大容量 */
typedef int ElementType;        /* 线性表中数据类型 */
typedef int Position;           /* 线性表中每个位置类型 */

typedef struct LNode* PtrToLNode;   /* 定义指向线性表每个结点的指针 */
typedef PtrToLNode List;            /* 定义线性表 */
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last;
};
List MakeEmpty() {
    List L = (List)malloc(sizeof(struct LNode));
    L->Last = -1;
    return L;
}
ElementType FindKth(List L, int i) {
    if(i > L->Last || i < 0)
        printf("无该元素");
    else
        return L->Data[i];
    return ERROR;
}
Position Find(List L,ElementType X) {
    Position i = 0;
    while(i <= L->Last && L->Data[i] != X)
        i++;
    if(i > L->Last) return ERROR;
    else return i;
}
bool Insert(List L,ElementType X, int i) {
    /* 在 L 的指定位序 i 前插入一个元素，位序 i 的元素数组下标为 i ，需要把i之后的元素全部后移一位*/

    if(L->Last == MAXSIZE-1) {
        printf("线性表已满");
        return false;
    }
    if (i < 0 || i > L->Last + 1) {
        printf("插入位置不合法");
        return false;
    }
    Position j;
    for(j = L->Last+1; j > i; j--)
        L->Data[j] = L->Data[j-1];
    L->Data[j] = X;
    L->Last ++;
    return true;
}
bool Delete(List L, int i) {
    /* 删除位序为i的元素，对应数组下标为i ，需要把i之后的元素全部前移一位*/

    if(L->Last==-1) {
        printf("线性表为空");
        return false;
    }
    if(i < 0 || i > L->Last) {
        printf("删除位置不合法");
        return false;
    }
    Position j;
    for(j=i; j<L->Last; j++)
        L->Data[j] = L->Data[j+1];
    L->Last--;
    return true;
}
int Length(List L) {
    return L->Last + 1;
}

由上可知顺序表的删除或插入操作的时间复杂度为 O(N)，查找第 i 个元素的时间复杂度为 O(1)。

线性表的链式存储实现

为提高线性表的插入或删除效率，可以使用链式存储结构即链表，它不需要用连续的地址来存储单元，它是通过”链”建立起数据元素之间的逻辑关系，因此对链表的插入或删除操作不需要移动元素，只需要修改”链”。

因此链表的结构定义如下：

#define ERROR NULL;
typedef int ElementType;
typedef struct LNode* PtrToLNode;
struct LNode {
    ElementType Data;   /* 链表每个结点的数据项 */
    PtrToLNode Next;    /* 指向下一个结点的指针 */
};
typedef PtrToLNode Position;
typedef PtrToLNode List;

链表名即链表第一个结点的指针。

1.求表长
在顺序表中求表长是一件很容易的事，但是在链表里面，我们需要将整个链表遍历一遍，使用一个指向链表头的指针，从前往后移动，再使用计数器count记录移动次数，直到链表结束为止。

int Length(List L) {
    PtrToLNode p = L;   /* 指向链表头 */
    int count = 0;
    while(p) {
        p = p->Next;
        count++;
    }
    return count;
}

2.查找

PtrToLNode FindKth(List L, int K) {
    /* 查找位序为 k 的元素 */
    PtrToLNode p = L;
    int count = 0;  /* 位序从0开始 */
    while(p && count < K) {
        p = p->Next;
        count ++;
    }
    if(p && (count == K))
        return p;
    else
        return ERROR;
}
Position Find(List L, ElementType X) {
    /* 查找X在链表中的位置 */
    Position p = L;
    while(p && p->Data != X)
        p = p->Next;
    if(p)
        return p;
    else
        return ERROR;
}

查找的时间复杂度为 O(N)。

3.插入

bool Insert(List L, ElementType X, int i) {
    /* 在第i个结点前插入一个结点 */
    PtrToLNode p ,s;
    // 如果插入结点在表头
    if(i == 0) {
        s = (PtrToLNode)malloc(sizeof(struct LNode));
        s->Data = X;
        s->Next = L;
        L = s;
        return true;
    }
    // 否则找到第 i 个结点的前一个结点
    p = FindKth(L,i-1);
    if(p == NULL) {
        printf("插入位置不合法");
        return false;
    } else {
        s = (PtrToLNode)malloc(sizeof(struct LNode));
        s->Data = X;
        s->Next = p->Next;
        p->Next = s;
        return true;
    }
}

在上述的实现中我们将表头插入作为一种特殊的情况处理，为避免这种情况我们一般为链表增加一个空的“头结点”，真正的元素链接在这个空结点之后。这样做的好处是无论在哪里删除，L 的值一直指向固定的空结点。

因此需要理解以下三个概念：

• 头结点：链表首元结点前的一个空结点。
• 首元结点：链表中存储线性表中第一个数据元素的结点。
• 头指针：指向链表中第一个结点（或为头结点或为首元结点）的指针。

假设链表有头结点，则插入操作如下：

bool Insert(List L, ElementType X, int i) {
    /* 假设链表有头结点，在第i个结点前插入一个结点 */
    PtrToLNode p ,s;
    // 找到第 i 个结点的前一个结点
    p = FindKth(L,i-1);
    if(p == NULL) {
        printf("插入位置不合法");
        return false;
    } else {
        s = (PtrToLNode)malloc(sizeof(struct LNode));
        s->Data = X;
        s->Next = p->Next;
        p->Next = s;
        return true;
    }
}

4.删除
这里假设链表有头结点。

bool Delete(List L, int i) {
    /* 删除第i个结点 */
    PtrToLNode p,tmp;
    p = FindKth(L,i-1);
    if(p == NULL || p->Next == NULL) {
        printf("删除位置参数错误");
        return false;
    } else {
        tmp = p->Next;
        p->Next = tmp->Next;
        free(tmp);
        return true;
    }
}

链表的插入和删除操作其时间复杂度也为 O(N)。

堆栈的定义与实现

思考：计算机如何进行表达式求值？

• 中缀表达式：运算符号位于两个运算数之间，如 a + b*c - d/e
• 后缀表达式：运算符位于两个运算数之后，如 a b c * + d e / -

计算机首先将中缀表达式转换成对应的后缀表达式，然后对后缀表达式进行求值，因此这里有两个问题，如何将中缀表达式转换成后缀表达式？如何对后缀表达式进行求值？

例如：求后缀表达式 6 2 / 3 - 4 2 * + 的值。

策略：从左向右扫描，遇到运算数，先存放起来，遇到运算符计算刚刚存放的两个元素的值（即后进先出），再将值存放起来。

因此这就要利用堆栈进行求值。

堆栈的定义

堆栈(Stack)可以认为是具有一定约束的线性表，插入和删除操作作用在一个称为栈顶(Top)的端点位置。正是堆栈所具有的这种特性，通常把数据插入称为入栈(Push)，数据删除操作称为出栈(Pop)。

也正是由于这一特性，最后入栈的数据将会被最先弹出，所以堆栈也叫后入先出(Last In First Out,LIFO)表。

堆栈的抽象数据定义为：

类型名称：堆栈(Stack)。

数据对象集：一个有0个或多个元素的有穷线性表。

操作集：对于一个具体长度为正整数 MaxSize 的堆栈 S∈Stack，记栈中的任一元素 X∈ElementType，堆栈的基本操作有：

1. Stack CreateStack(int MaxSize)：创建一个最大长度为 MaxSize 的堆栈；

2. bool IsFull(Stack S)：检查堆栈是否已满；

3. bool Push(Stack S, ElementType X)：将 X 入栈；

4. bool IsEmpty(Stack S)：检查堆栈是否为空；

5. ElementType Pop(Stack S)：弹出栈顶元素。

堆栈的顺序存储实现

栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成，另外我们还需要知道栈的最大容量，这样方便我们判断栈什么时候是满的。因此栈的顺序存储结构定义如下：

typedef int ElementType;
typedef int Position;
typedef struct SNode* PtrToSNode;
struct SNode {
    ElementType *Data;  /* 存储元素的数组 */
    Position Top;            /* 栈顶指针 */
    int MaxSize;        /* 栈的最大容量 */
};
typedef PtrToSNode Stack;

以下是创建一个空堆栈的实现：

Stack CreateStack(int MaxSize) {
    Stack S = (Stack)malloc(sizeof(struct SNode));
    S->Data = (ElementType*)malloc(sizeof(ElementType)*MaxSize);
    S->MaxSize = MaxSize;
    S->Top = -1;
    return S;
}

入栈：

bool IsFull(Stack S) {
    return S->Top == S->MaxSize-1;
}
bool Push(Stack S, ElementType X) {
    if(IsFull(S)){
        printf("栈已满");
        return false;
    } else {
        S->Data[++(S->Top)] = X;
        return true;
    }
}

出栈：

bool IsEmpty(Stack S) {
    return S->Top == -1;
}
ElementType Pop(Stack S) {
    if(IsEmpty(S)) {
        printf("栈为空");
        return ERROR;       /* 特殊值，标记错误 */
    } else {
        return S->Data[(S->Top)--];
    }
}

堆栈的链式存储实现

栈的链式存储结构实际上就是一个单链表，插入和删除只能在链栈的栈顶进行。栈顶指针 Top 指向链表头，删除和插入操作都在链表头部进行，因为在尾部无法进行删除操作。

因此为了简便算法，为链栈增加一个空的头结点。因此其实现如下：

Stack CreateStack() {
    Stack S = (Stack)malloc(sizeof(struct SNode));
    S->Next = NULL;
    return S;
}
bool IsEmpty(Stack S) {
    return S->Next == NULL;
}
bool Push(Stack S, ElementType X) {

    PtrToSNode node = (PtrToSNode)malloc(sizeof(struct SNode));
    node->Data = X;
    node -> Next = S->Next;
    S->Next = node;
    return true;
}
ElementType Pop(Stack S) {
    ElementType X;
    if(IsEmpty(S)) {
        printf("堆栈为空");
        return ERROR;
    } else {
        PtrToSNode temp = S->Next;
        X = temp->Data;
        S->Next = temp->Next;
        free(temp);
        return X;
    }
}

堆栈的应用

前面提到的问题我们解决了后一部分，接下来解决如何将中缀表达式转为后缀表达式？

算法描述：

从头到尾读取中缀表达式的每个元素，对不同元素按照不同情况进行处理：

1.运算数： 直接输出

2.左括号： 入栈

3.右括号： 将栈顶元素弹出并输出，直到遇见左括号（出栈，不输出）

4.运算符： 若运算符的优先级大于栈顶符号优先级，则入栈；

若运算符号优先级小于栈顶符号优先级，则将栈顶符号出栈并输出；再比较新的栈顶符号，直到新的栈顶符号优先级小于该运算符优先级为止，然后将该运算符入栈

5.所有元素处理完毕，则把堆栈中存留的运算符一并输出。

队列的定义与实现

队列的定义

多个数据构成一个有序序列，而对这个序列的操作有一定要求：只能在一端插入，另一端删除，这样的数据组织方式就是“队列”，队列具有先进先出（First In First Out,FIFO）的特点队列(Queue)也是一个有序线性表。

队列的抽象数据类型定义为：

类型名称：队列(Queue)。

数据对象集：有一个或多个元素的有穷线性表。

操作集：对于一个长度为正整数 MaxSize 的队列 Q∈Queue，记队列中的任一元素 X∈ElementType，队列的基本操作有：

1.Queue CreateQueue(int MaxSize)：生成最大长度为 MaxSize 的空队列；

2.bool IsFull(Queue Q)：判断队列是否已满；

3.bool AddQ(Queue Q, ElementType X)：将元素 X 压入队列；

4.bool IsEmpty(Queue Q)：判断队列是否为空；

5.ElementType DeleteQ(Queue Q)：删除并返回队列头元素。

队列的顺序存储实现

为了充分利用数组空间，一般在队列的顺序存储结构中采用循环队列的方式。

当队列头 Front 和 队列尾 Rear 相等时，我们无法判断队列是空的还是满的。其根本原因是 Rear 和 Front 的差值最多有 n 种情况（n为数组的大小），而队列元素的个数却又 n+1 种（0,1,2,…,n），所以仅依靠 Front 和 Raer 是无法区分这 n+1 种情况的。

因此我们有两种解决方法：

1.设置一个从额外标记记录最后一次操作是入队还是出队。如果是入队导致 Front==Rear 说明队列满，如果是出队导致 Front==Rear 说明队列空
2.仅使用 n-1 个数组空间，如下图所示表示队列满，因此队列满的条件是 (Rear+1)%数组长度等于Front 。队列空的条件依然是 Front== Rear。

使用第二种方法来实现循环队列，因此队列的顺序存储实现结构可以是：

typedef int ElementType;
typedef int Position;

typedef struct QNode* PtrToQNode;
struct QNode {
    ElementType* Data;      /* 存储元素的数组 */
    Position Front,Rear;    /* 队列的头尾指针 */
    int MaxSize;            /* 队列的最大容量 */
};
typedef PtrToQNode Queue;

Queue CreateQueue(int MaxSize) {
    Queue Q = (Queue)malloc(sizeof(struct QNode));
    Q->Data = (ElementType*)malloc(sizeof(ElementType)*MaxSize);
    Q->Front = Q->Rear = -1;
    Q->MaxSize = MaxSize;
    return Q;
}
bool IsFull(Queue Q) {
    return (Q->Rear+1)%(Q->MaxSize) == Q->Front;
}
bool AddQ(Queue Q, ElementType X) {

    if(IsFull(Q)) {
        printf("队列已满");
        return false;
    } else {
        Q->Rear = (Q->Rear+1)%(Q->MaxSize);
        Q->Data[Q->Rear] = X;
        return true;
    }

}
bool IsEmpty(Queue Q) {
    return Q->Front == Q->Rear;
}
ElementType DeleteQ(Queue Q) {
    if(IsEmpty(Q)) {

        printf("队列为空");
        return ERROR;
    } else {
        Q->Front = (Q->Front+1)%Q->MaxSize;
        return Q->Data[Q->Front];
    }
}

队列的链式存储实现

队列的链式存储结构也可以用一个单链表来实现。插入和删除操作分别在链表的两头进行：队列的 front 和 rear 应该分别指向链表的哪一头？

由于在链表尾部无法进行删除操作，因此删除操作在链表头部，插入操作在链表尾部，所以 front 指向链表头部，rear 指向链表尾部。

因此其不带头结点的链式队列可以定义为：

typedef int ElementType;

typedef struct Node* PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode Next;
};
typedef PtrToNode Position;
struct QNode {
    Position rear;
    Position front;
};
typedef struct QNode* Queue;

bool IsEmpty(Queue Q) {
    return Q->front == NULL;
}
bool AddQ(Queue Q, ElementType X) {
    PtrToNode node = (PtrToNode)malloc(sizeof(struct Node));
    node->Data = X;
    node->Next = NULL;
    Q->rear->Next = node;
    return true;
}
ElementType DeleteQ(Queue Q) {
    if(IsEmpty(Q)) {
        printf("队列为空");
        return ERROR;
    } else {
        PtrToNode node = Q->front;
        ElementType temp = node->Data;
        if(Q->front == Q->rear) /* 如果队列只有一个元素 */
            Q->front = Q->rear = NULL;
        else
            Q->front = Q->front->Next;
        free(node);
        return temp;
    }
}