这是本节的多页打印视图。 点击此处打印.

返回本页常规视图.

线性数据结构

本章以选择题形式考察，需要熟练掌握栈和队列的操作以及应用，另外还需要了解如何用数组实现栈和队列，可能会在代码题中考察。

学习思维导图：

# 栈、队列和数组

## 栈和队列基本概念

## 栈和队列的顺序存储结构

## 栈和队列的链式存储结构

## 多维数组的存储

## 特殊矩阵的压缩矩阵

## 栈、队列和数据的应用

1 - 栈

需熟练掌握栈的定义、操作和实现方式。

定义

栈是一个元素的集合，加入元素的操作叫做“压栈”（push），而移除元素的操作叫做“出栈”（pop）。它遵循后进先出（LIFO, Last In First Out）的原则。这意味着最后被压入栈的元素是第一个被弹出的元素。

dépilerPopempilerPush

基本操作

  • push(element): 将元素添加到栈的顶部。
  • pop(): 移除并返回栈顶的元素。如果栈为空，这个操作可能会抛出一个错误或返回特定的值（例如null或undefined），具体取决于实现。
  • peek() 或 top(): 返回栈顶的元素但不移除它。这只是一个查看操作，栈的内容不会改变。如果栈为空，这个操作可能会抛出一个错误或返回特定的值。
  • isEmpty(): 判断栈是否为空。如果栈为空，返回true；否则返回false。
  • size() 或 length(): 返回栈中元素的数量。

实现

顺序栈

顺序栈是使用数组来实现的栈，利用数组的索引来模拟栈的操作。

#define MAX_SIZE 100 // 定义栈的最大容量

// 定义顺序栈的结构
typedef struct {
    int data[MAX_SIZE]; // 使用数组存储数据
    int top;            // 栈顶指针
} SeqStack;
// 初始化栈
SeqStack* initStack() {
    SeqStack* stack = (SeqStack*)malloc(sizeof(SeqStack));
    if(!stack) {
        printf("Failed to allocate memory for stack\n");
        exit(1);
    }
    stack->top = -1;  // 栈顶指针初始化为-1，表示栈为空
    return stack;
}
// 入栈操作
bool push(SeqStack* stack, int value) {
    if (isFull(stack)) {
        printf("Stack is full!\n");
        return false;
    }
    stack->data[++stack->top] = value; // 先移动栈顶指针，再存放元素
    return true;
}
// 出栈操作
bool pop(SeqStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    *value = stack->data[stack->top--]; // 先取出元素，再移动栈顶指针
    return true;
}
// 获取栈顶元素
bool peek(SeqStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    *value = stack->data[stack->top];
    return true;
}
// 判断栈是否为空
bool isEmpty(SeqStack* stack) {
    return stack->top == -1;
}

// 判断栈是否已满
bool isFull(SeqStack* stack) {
    return stack->top == MAX_SIZE - 1;
}

链式栈

栈的链式存储结构通常是使用单链表来实现。在这种实现中，链表的头部代表栈顶，这样可以确保入栈和出栈操作的时间复杂度为O(1)。

// 定义链式栈的节点结构
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 定义链式栈的结构
typedef struct {
    Node* top;
} LinkedStack;
// 初始化栈
LinkedStack* initStack() {
    LinkedStack* stack = (LinkedStack*)malloc(sizeof(LinkedStack));
    if(!stack) {
        printf("Failed to allocate memory for stack\n");
        exit(1);
    }
    stack->top = NULL; // 栈顶指针初始化为NULL，表示栈为空
    return stack;
}
// 入栈操作
void push(LinkedStack* stack, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if(!newNode) {
        printf("Failed to allocate memory for new node\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = stack->top;
    stack->top = newNode;
}
// 出栈操作
bool pop(LinkedStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    Node* temp = stack->top;
    *value = temp->data;
    stack->top = temp->next;
    free(temp);
    return true;
}
// 获取栈顶元素
bool peek(LinkedStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    *value = stack->top->data;
    return true;
}
// 判断栈是否为空
bool isEmpty(LinkedStack* stack) {
    return stack->top == NULL;
}

2 - 队列

需熟练掌握队列的定义、操作和实现方式，尤其是循环队列。

定义

队列是一种遵循先入先出 (FIFO, First In First Out) 原则的线性数据结构。元素在队尾添加，在队首删除。

Back
Front
Enqueue
Dequeue

基本操作

  • enqueue(element): 将元素添加到队列的尾部。
  • dequeue(): 从队列的头部移除并返回元素。如果队列为空，此操作可能会返回特定的值或引发错误。
  • front() 或 peek(): 返回队首的元素但不移除它。
  • isEmpty(): 判断队列是否为空。
  • size(): 返回队列中元素的数量。

实现

顺序队列

顺序队列通常是指使用固定大小的数组来存储队列中的元素。在顺序队列中，通常有两个指标：一个是队头（front），另一个是队尾（rear）。当插入（入队）或删除（出队）元素时，这两个指标会移动。

front
rear
front
a
b
c
d
e
rear
front
e
rear
空队
5个元素入队
出队4次
再出队一次
会出现
“假溢出”

顺序队列有一个明显的问题：随着时间的推移，队列中的元素可能向数组的末尾移动，即使队列并不满，也可能无法再插入新的元素，因为队尾已经达到了数组的末尾。这种现象称为"假溢出"。

循环队列

为了解决上述问题，可以使用循环队列（也称为环形队列）。循环队列是顺序队列的一个变种，它把数组视为一个循环的结构。当队尾指标达到数组的最后一个位置并且还需要进一步移动时，它会回到数组的起始位置。

0
1
2
3
4
front
rear
0
1
2
3
4
a
b
c
d
front
rear
队空
入队4个元素，队满

需要注意的是，在循环队列中需要牺牲一个存储单元以区分队空和队满的情况。

  • 当 front == rear 时，队列为空
  • 当 (rear + 1) % size == front 时，队列为满
#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front, rear;
} CircularQueue;

// 初始化队列
void initQueue(CircularQueue* q) {
    q->front = q->rear = 0;
}
// 入队操作
bool enqueue(CircularQueue* q, int value) {
    if (isFull(q)) return false;
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_SIZE;
    return true;
}
// 出队操作
bool dequeue(CircularQueue* q, int* value) {
    if (isEmpty(q)) return false;
    *value = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return true;
}
// 获取队首元素
bool front(CircularQueue* q, int* value) {
    if (isEmpty(q)) return false;
    *value = q->data[q->front];
    return true;
}

// 获取队尾元素
bool rear(CircularQueue* q, int* value) {
    if (isEmpty(q)) return false;
    *value = q->data[(q->rear - 1 + MAX_SIZE) % MAX_SIZE];
    return true;
}
// 判断队列是否为空
bool isEmpty(CircularQueue* q) {
    return q->front == q->rear;
}

// 判断队列是否满
bool isFull(CircularQueue* q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

链式队列

链式队列是使用链表结构来实现的队列。它充分利用了链表的动态性质，允许队列在运行时动态地增长或缩小。链式队列通常有两个指针：一个指向队头，另一个指向队尾。

链式队列通常使用一个简单的单链表来实现，但与普通的单链表不同的是，链式队列有两个指针：一个指向链表的头部（队头），另一个指向链表的尾部（队尾）。

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct {
    Node* front, *rear;
} LinkedQueue;

// 初始化队列
void initLinkedQueue(LinkedQueue* q) {
    q->front = q->rear = NULL;
}
// 入队操作
void enqueueLinked(LinkedQueue* q, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    if(isEmptyLinked(q)) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}
// 出队操作
bool dequeueLinked(LinkedQueue* q, int* value) {
    if (isEmptyLinked(q)) return false;
    Node* temp = q->front;
    *value = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;  // 当队列中最后一个元素被出队后
    free(temp);
    return true;
}
// 获取队首元素
bool frontLinked(LinkedQueue* q, int* value) {
    if (isEmptyLinked(q)) return false;
    *value = q->front->data;
    return true;
}
// 判断队列是否为空
bool isEmptyLinked(LinkedQueue* q) {
    return q->front == NULL && q->rear == NULL;
}

3 - 栈和队列的应用

需能够手工模拟中序和后序表达式的计算过程，包括两者之间的转换，常常在选择题中出现。

表达式种类

前序表达式（Preorder，也叫做波兰表示法）、中序表达式（Infix）和后序表达式（Postorder, 也称为逆波兰表示法）都是二叉树的遍历策略，通常用于算术表达式的表示。不同的表示方法对操作符和操作数的顺序有不同的规定。

表达式类型描述示例表达式对应的公式
前序操作符位于其操作数之前* + A B C(A + B) * C
中序操作符位于其两个操作数之间，最常见的表示法(A + B) * C(A + B) * C
后序操作符位于其操作数之后A B + C *(A + B) * C
*
+
A
B
C

上图是表达式 (A + B) * C 对应的二叉树，前序、后序表达式分别是对这棵树的 前序遍历和后序遍历。

中序表达式求值

中序表达式求值涉及到两个主要的数据结构：操作符栈与操作数栈。其核心思路是逐个读取中序表达式的字符，根据字符的类型（操作数、操作符、括号）进行不同的处理，最终得到表达式的值。

  1. 初始化两个栈：
    • 操作数栈：用来存储数字。
    • 操作符栈：用来存储操作符和左括号。
  2. 逐个读取中序表达式的字符：
    • 如果是 操作数（数字），则直接压入操作数栈。
    • 如果是 左括号，则直接压入操作符栈。
    • 如果是 右括号，则：
      • 从操作符栈中弹出一个操作符。
      • 从操作数栈中弹出所需的操作数。
      • 执行该操作符对应的运算。
      • 将结果压入操作数栈。
      • 重复以上步骤，直到从操作符栈中弹出一个左括号。
    • 如果是操作符（如+、-、*、/等）：
      • 如果操作符栈为空，或栈顶是左括号，或当前操作符优先级高于栈顶操作符的优先级，则直接压入操作符栈。
      • 否则：
        • 从操作符栈中弹出一个操作符。
        • 从操作数栈中弹出所需的操作数。
        • 执行该操作符对应的运算。
        • 将结果压入操作数栈。
        • 重复以上步骤，直到满足上述的压栈条件。
  3. 处理完所有字符后：
    • 如果操作符栈不为空，则：
      • 从操作符栈中弹出一个操作符。
      • 从操作数栈中弹出所需的操作数。
      • 执行该操作符对应的运算。
      • 将结果压入操作数栈。
      • 重复以上步骤，直到操作符栈为空。
  4. 得到结果：
    • 此时，操作数栈中仅存一个数字，这就是整个中序表达式的值。

以表达式 3 + (5 * 2 - 8) 说明计算过程：

步骤输入字符操作操作符栈数据栈
13压入数据栈3
2+压入操作符栈+3
3(压入操作符栈+, (3
45压入数据栈+, (3, 5
5*压入操作符栈+, (, *3, 5
62压入数据栈+, (, *3, 5, 2
7-* 比 - 优先级高，直接压入操作符栈+, (, *, -3, 5, 2
88压入数据栈+, (, *, -3, 5, 2, 8
9)处理到(之前的所有操作符+3, 9
10用 + 运算符计算12

后序表达式求值

后序表达式求值主要依赖一个操作数栈。其核心思路是逐个读取后序表达式的元素，并根据元素的类型（操作数或操作符）进行处理。

  1. 初始化一个操作数栈：
    • 用于存储后序表达式中的数字。
  2. 逐个读取后序表达式的元素：
    • 如果是操作数，则直接压入操作数栈。
    • 如果是操作符（如+、-、*、/等）：
      • 从操作数栈中弹出所需的操作数。注意，因为操作符是后置的，所以先弹出的数字是第二操作数，后弹出的是第一操作数。
      • 根据操作符执行相应的运算。
      • 将计算结果压入操作数栈。
  3. 完成后序表达式的读取：
    • 操作数栈中的顶部元素即为整个后序表达式的值。

以表达式 3 5 2 * 8 - + 说明计算过程：

步骤输入字符操作操作数栈
13压入操作数栈3
25压入操作数栈3, 5
32压入操作数栈3, 5, 2
4*弹出两个操作数并相乘，结果压入操作数栈3, 10
58压入操作数栈3, 10, 8
6-弹出两个操作数并相减，结果压入操作数栈3, 2
7+弹出两个操作数并相加，结果压入操作数栈5

4 - 数组和特殊矩阵

掌握多维数组的存储方式，了解特殊矩阵的压缩存储，可能在选择题中出现概念考察以及某个矩阵元素下标的计算。

多维数组的存储

如果数组的第一个元素位于内存地址 $A$，且每个元素占用 $B$ 个字节，行列总数分别为 $R$ 和 $C$，那么数组的 $(i, j)$ 元素（其中 $i$ 是行号，$j$ 是列号）的内存地址可以计算为 $A + (i \times C + j) * B$。

例子：

在C语言中定义定义如下多维数组

int a[2][3] = {{1, 2, 3}, {4, 5, 6}};

这个数组的内存布局可以视为一个一维数组，如下所示：

  +---------+---------+---------+---------+---------+---------+
  | a[0][0] | a[0][1] | a[0][2] | a[1][0] | a[1][1] | a[1][2] |
  +---------+---------+---------+---------+---------+---------+
0x100      0x104    0x108     0x10C     0x110     0x114

特殊矩阵的压缩存储

对称矩阵

什么是对称矩阵：对于矩阵$A$中的任意一个元素$a_{i, j}$都有 $a_{i, j} = a_{j ,i}$，

Produced by GNUPLOT 4.4 patchlevel 0

所以为了节省存储空间，可以使用一位数组$B$进行存储

symmtry_matrix_storage

如何计算对称矩阵中元素的下标

$A$ 中的元素 $a_{i, j}$ 在数组 $B$ 的下标

$$k = 1 + 2 + \cdots + (i-1) + j - 1 = i(i-1)/2+j-1$$

元素为

$$a_{i, j} = \begin{cases} \frac{i(i-1)}{2}+j-1,\text{ } i \ge j \\ \frac{j(j-1)}{2}+i-1,\text{ } i \lt j \end{cases}$$

三角矩阵

{\displaystyle \mathbf {L} ={\begin{bmatrix}l_{1,1}&&\cdots &&0\\l_{2,1}&l_{2,2}&&(0)&\\l_{3,1}&l_{3,2}&\ddots &&\vdots \\\vdots &\vdots &\ddots &\ddots &\\l_{n,1}&l_{n,2}&\ldots &l_{n,n-1}&l_{n,n}\end{bmatrix}}}

下三角矩阵

{\displaystyle \mathbf {U} ={\begin{bmatrix}u_{1,1}&u_{1,2}&u_{1,3}&\ldots &u_{1,n}\\&u_{2,2}&u_{2,3}&\ldots &u_{2,n}\\\vdots &&\ddots &\ddots &\vdots \\&(0)&&\ddots &u_{n-1,n}\\0&&\cdots &&u_{n,n}\end{bmatrix}}}

上三角矩阵
  • 下三角矩阵也是一个方阵，其主对角线及其以下（右下部分）的所有元素都不为零，而主对角线以上的所有元素都为零。
  • 上三角矩阵是是一个方阵，其主对角线及其以上（左上部分）的所有元素都不为零，而主对角线以下的所有元素都为常数。

如何计算三角矩阵中元素的下标

以上三角矩阵$A$为例，上半部分元素首先按序存储在一位数组$B$中，在最后一个位置添加一个元素，用于存储下三角位置对应的元素

$A$ 中的元素 $a_{i, j}$ 在数组 $B$ 的下标

$$k = n + (n+1) _ \cdots + (n-i+2) + (j-i+1) - 1 = (i-1)(2n-i+2)/2 + (j-i)$$

元素为

$$a_{i, j} = \begin{cases} \frac{(i-1)(2n-i+2)}{2}+(j-i),\text{ } i \le j（上三角区和对角线元素） \\ \frac{n(n+1)}{2},\text{ } i \gt j（下三角区元素） \end{cases}$$

三对角矩阵

$$\begin{vmatrix} a_{1,1} & a_{1,2} & & & & \\ a_{2,1} & a_{2,2} & a_{2,3} & & & \\ & a_{3,2} & a_{3,3} & a_{3,4} & & \\ & & \ddots & \ddots & \ddots & \\ & & & a_{n-1,n-2} & a_{n-1,n-1} & a_{n-1,n}\\ & & & & a_{n,n-1} & a_{n,n} \end{vmatrix}$$

三对角矩阵可以使用压缩存储，将3条对角线上的元素按照行优先的方式存放在一位数组B中。

稀疏矩阵

稀疏矩阵中非零元素的个数相比矩阵元素的总个数非常少，通常，稀疏矩阵中的非零元素的分布是没有规律的。因此，非零元素可以用一个三元组来存储（行，列，值），使用三元组组成的线性表来存储稀疏矩阵中南欧给所有的元素。

矩阵

$$M = \begin{vmatrix} 4 & 0 & 0 & 0\\ 0 & 0 & 6 & 0\\ 0 & 9 & 0 & 0\\ 0 & 23 & 0 & 0 \end{vmatrix}$$