算法导论第 10 章：基本数据结构

主要内容

本章介绍几种基本的数据结构：栈、队列、链表和有根树。此外还介绍由数组构造对象和指针的方法。

栈和队列

栈实现的是一种后进先出（last-in, first-out, LIFO）策略。队列实现的是一种先进先出（first-in, first-out, FIFO）策略。下面通过数组来实现它们。

栈的INSERT操作称为压入（PUSH），而无元素参数的DELETE操作称为弹出（POP）。可以用数组\(S[1..n]\)实现一个最多容纳\(n\)个元素的栈。实现代码如下：

typedef struct __stack {
    int top;             // 指向栈顶
    int capacity;        // 最大容量
    int *data;           // 数据空间
} Stack;

void StackInit(Stack *stk, int n)
{
    stk->data = malloc(n * sizeof(int));
    if (stk->data == NULL) {
        printf("Alloc failed!\n");
        exit(1);
    }
    stk->capacity = n;
    stk->top = 0;
}

int StackEmpty(Stack *stk)
{
    if (stk->top == 0) {
        return true;
    }
    return false;
}

int StackFull(Stack *stk)
{
    if (stk->top == stk->capacity) {
        return true;
    }
    return false;
}

void Push(Stack *stk, int x)
{
    if (StackFull(stk)) {
        printf("Overflow!\n");
        exit(1);
    }
    ++stk->top;
    stk->data[stk->top] = x;
}

int Pop(Stack *stk)
{
    if (StackEmpty(stk)) {
        printf("Underflow!\n");
        exit(1);
    } else {
        --stk->top;
        return stk->data[stk->top+1];
    }
}

队列上的INSERT操作称之为入队（ENQUEUE），无元素参数的DELETE操作称之为出队（DEQUEUE）。队列有队头（head）和队尾（tail），元素入队时，它被放到队尾的位置；而出队的元素总是队头的那个。可以用数组\(Q[1..n]\)实现一个最多容纳\(n-1\)个元素的环形队列。代码实现如下：

typedef struct __queue {
    int head;      // 队头
    int tail;      // 队尾
    int capacity;  // 队列容量
    int *data;     // 数据空间
} Queue;

void QueueInit(Queue *q, int n)
{
    q->data = malloc(n * sizeof(int));
    if (q->data == NULL) {
        printf("Alloc failed!\n");
        exit(1);
    }
    q->capacity = n - 1;  // 空间为n的数组只能容纳n-1个队列元素
    q->head = 0;
    q->tail = 0;
}

int QueueFull(Queue *q)
{
    if (q->head == q->tail + 1) {
        return TRUE;
    }
    return FALSE;
}

int QueueEmpty(Queue *q)
{
    if (q->head == q->tail) {
        return TRUE;
    }
    return FALSE;
}

void Enqueue(Queue *q, int x)
{
    if (QueueFull(q)) {
        printf("Overflow!\n");
        exit(1);
    }

    q->data[q->tail] = x;
    if (q->tail == q->capacity) {
        q->tail = 0;
    } else {
        ++q->tail;
    }
}

int Dequeue(Queue *q)
{
    if (QueueEmpty(q)) {
        printf("Underflow!\n");
        exit(1);
    }

    x = q->data[q->head];
    if (q->head == q->capacity) {
        q->head = 0;
    } else {
        ++q->head;
    }

    return x;
}

链表

略。

指针和对象的实现

略。

有根树的表示

略。