数据结构

---

时间轴

2025-09-28

add 绪论

2025-09-28

add 线性表，栈，队列，数组，串

---

绪论

数据的逻辑结构

数据的逻辑结构是指数据元素之间的关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的

• 线性结构
  • 线性表
    • 数组
    • 栈
    • 队列
• 非线性结构
  • 集合
  • 树形结构
    • 一般树
    • 二叉树
  • 图状结构
    • 有向图
    • 无向图

数据的存储结构

存储结构是指数据结构在计算机中的表示，也称物理结构

• 顺序存储

顺序存储是指把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中；

• 链式存储

链式存储借助指示元素存储地址的指针来表示元素之间的逻辑关系；

• 索引存储

索引存储是指在存储元素信息的同时，还建立附加的索引表。索引表中的每项都称为索引项，索引项的一般形式是(关键字 key，地址 address);

• 散列存储

散列存储是根据元素的关键字直接计算出该元素的存储地址，又称哈希(Hash)存储。

算法的基本概念

• 有穷性

有穷性是指一个算法必须总在执行有穷步后结束，且每一步都在有穷时间内完成；

• 确定性

确定性是指算法中每条指令都必须有正确的含义，对于相同的输入只能得出相同的输出；

• 可行性

可行性是指算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现；

• 输入

输入是指一个算法有0或多个输入，这些输入取自于某个特定的对象的集合

• 输出

输出是指一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

算法效率的度量

时间复杂度

$$T(n) = O(f(n))$$

加法规则：

$$T(n) = T_1(n)+T_2(n)=O(f(n)) + O(g(n)) = O(max(f(n),g(n)))$$

常见的渐进时间复杂度

$$O(1) < O(log_2^n) < O(n) < O(nlog^n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$$

空间复杂度

$$S(n) = O(g(n))$$

线性表

定义：线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列。

线性表一般表示为：

$$L = (a_1,a_2,a_3,...,a_i,a_{i+1}, ..., a_n)$$

线性表的顺序表示

线性表的顺序存储也称顺序表，其特点是表中元素的逻辑顺序与其物理顺序相同。线性表是一种随机存取的存储结构

C语言描述

• 静态分配

#define MAX_SIZE 50
typedef struct{
  ElemType data[MaxSize];
  int length;
}SqList;

• 动态分配

#define InitSize 100
typedef struct{
    ElemType *data;
    int capacity;
    int length;
}SeqList;

C++描述

一般使用标准库vector，也可以自定义

template <typename T>
class LinearList {
private:
    T *data;  
    int length;
    int capacity;

    void resize(size_t new_capacity) {
        T* new_data = new T[new_capacity];
        for (size_t i = 0; i < size; i++) {
            new_data[i] = data[i];
        }
        delete[] data;
        data = new_data;
        capacity = new_capacity;
    }

public:
    SeqList() : data(nullptr), size(0), capacity(0) {}

    ~SeqList() {
        delete[] data;
    }

};

Rust描述

Rust中一般用标准库的Vec，自己写要用许多unsafe API

基本操作时间复杂度

操作	最好情况	最坏情况	平均情况	备注
按位置插入	O(1)（表尾）	O(n)（表头）	O(n)	表尾插入均摊 O(1)
按位置删除	O(1)（表尾）	O(n)（表头）	O(n)	表尾删除 O(1)
按下标访问	O(1)	O(1)	O(1)	数组随机访问
查找（顺序）	O(1)	O(n)	O(n)	如果无序只能顺序查找

经典题目

对长度为n的顺序表L，编写一个时间复杂度为O(n)，空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素

一种解法：用k记录顺序表L中不等于x的元素的个数，扫描时将不等于x的元素移动到下标k的位置，并更新k值。扫描结束后修改L的长度。

void del_x(Sqlist &L, ElemType x){
    int k = 0, i;
    for(i = 0 ; i < L.length ; i++){
        if(L.data[i] != x){
            L.data[k] = L.data[i];
            k++;
        }
    }
    L.length = k;
}

线性表的链式表示

单链表

线性表的链式存储又称单链表。

C语言描述

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

这个C语言定义的效果是

部分	含义
struct Node { ... };	定义了一个结构体类型，标签名是 Node（即 struct Node）
LNode	给 struct Node 起了一个类型别名
*LinkList	给 struct Node*（即该结构体指针）起了一个别名为LinkList

C++描述

TODO

Rust描述

TODO

头结点

通常用头指针来标识一个单链表，头指针为NULL时表示一个空表。此外，为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头节点。

• 头节点的数据域可以不设置任何信息，也可以记录表长等信息。

• 引入头节点可以带来两个优点：

  • 由于第一个数据节点的位置被放在头节点的指针域中，因此在链表上的第一个位置上的操作和在表的其他位置上的操作一致，无需进行特殊处理
  • 无论链表是否为空，其头指针都是指向头节点的非空指针（空表中头节点的指针域为NULL）,因此空表和非空表的处理也就得到了统一。

头插法建立单链表

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

#define ElemType int

typedef struct LNode {
  ElemType data;
  struct LNode *next;
} LNode, *LinkList;

// 头插法建立单链表
LinkList LinkListInit_HeadInsert(void) {
  LinkList L;
  LNode *node;
  int x;

  L = (LNode *)malloc(sizeof(LNode));
  L->next = NULL;

  while (scanf("%d", &x) != EOF) {
    node = (LNode *)malloc(sizeof(LNode));
    node->data = x;
    node->next = L->next;
    L->next = node;
  }
  return L;
}

尾插法建立单链表

双链表

单链表中只有一个指向其后继的指针，使得单链表只能从头节点依次顺序地向后遍历。双链表节点中有两个指针prior和next，分别指向前驱节点和后继节点。

C语言描述

typedef struct DNode{
    ElemType data;
    struct DNode *prior, *next;
}DNode, *DLinkList;

C++描述

TODO

Rust描述

TODO

循环链表

循环单链表

循环单链表和单链表的区别在于，表中的最后一个节点的指针不是NULL，而改为指向头节点，从而整个链表形成一个环。

C语言描述

C++描述

Rust描述

循环双链表

循环双链表相比于循环单链表，其头节点的prior指针要指向尾节点

C语言描述

C++描述

Rust描述

静态链表

静态链表借助数组来描述线性表的链式存储结构，节点也有数据域data和指针域next，与前面的链表中的指针不同的是，这里的指针是节点的相对地址（数组下标），又称游标。和顺序表相同，静态链表也要预先分配一块连续的内存地址空间。

例如：

下标	data	next
0		4
1	头结点	2
2	10	3
3	20	5
4		6
5	30	-1
6		-1

主链表部分：
┌──────┬──────┬──────┐      ┌──────┬──────┬──────┐      ┌──────┬──────┬──────┐
│ idx=1│ data │ next │ ---> │ idx=2│  10  │ next │ ---> │ idx=3│  20  │ next │ ---> [idx=5│ 30 │ -1│]
└──────┴──────┴──────┘      └──────┴──────┴──────┘      └──────┴──────┴──────┘

空闲链表部分：
┌──────┬──────┬──────┐      ┌──────┬──────┬──────┐
│ idx=0│  —   │  4   │ ---> │ idx=4│  —   │  6   │ ---> [idx=6│ — │ -1│]
└──────┴──────┴──────┘      └──────┴──────┴──────┘

C语言描述

#define MaxSize 50
typedef struct{
    ElemType data;
    int next;
}SLinkList[MaxSize];

C++描述

Rust描述

经典题目

检测单链表是否存在环

单链表有环是指单链表的最后一个结点的指针指向了链表中的某个节点（通常单链表的最后一个节点的指针是空的）。试编写算法判断单链表是否存在环

求两个单链表的公共节点

栈，队列和数组

栈

栈（Stack）是只允许在一端进行插入或删除操作的线性表。

• 栈顶（Top） 线性表允许进行插入删除的那一端
• 栈底（Bottom） 固定的。不允许进行插入和删除的另外一端

栈的特性可以明显的概括为后进先出（Last In First Out，LIFO）

栈的数学性质：

n 个不同元素进栈，其可能的出栈序列个数为第 n 个 Catalan 数（卡特兰数）

公式为：

$$C_n = \frac{1}{n+1} C_{2n}^n = \frac{(2n)!}{n! (n+1)!}$$

栈的顺序存储结构

C语言描述

#define MaxSize 50
typedef struct{
	ElemType data[MaxSize];
    // 栈顶指针
	int top;
}SqStack;

C++描述

TODO

Rust描述

TODO

共享栈

利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。

下标:   0   1   2   3   4   5   6   7   8   9
        ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
Stack1→ │10 │20 │30 │   │   │   │   │   │40 │50 │ ←Stack2
        └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
         ↑                   ↑                   ↑
       base1                mid                base2
         ↑                                       ↑
       top1=2                               top2=8

共享栈是为了更有效地利用地址空间。当且仅当两个栈相邻时发生栈满上溢。

栈的链式存储结构

采用链式存储的栈称为链栈，链栈的优点

• 便于多个栈共享存储空间和提高效率
• 不存在栈满上溢的情况

链栈通常采用单链表实现，并规定所有操作都是在表头进行。

C语言描述

这里规定链栈没有头节点

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}*LiStack;

C++描述

TODO

Rust描述

TODO

经典应用

括号匹配

表达式求值

递归转为栈实现

队列

队列（Queue）也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的一端进行删除。

• 队头（Front） 允许删除的一端，也称队首

• 队尾（Rear） 允许插入的一端

• 入队（EnQueue） 向队尾插入元素

• 出队（DeQueue） 队头删除元素

队列的特性可简单概括为先进先出（First In First Out，FIFO）

队列的顺序存储结构

C语言描述

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int front, rear;
}SqQueue;

C++描述

TODO

Rust描述

判断队空

Q.rear == Q.front==0

判断队满

由于：

• 进队操作：队不满时，先送值到队尾元素，再将队尾指针+1
• 出队操作：队不为空时，先取队头元素值，再将队头指针+1

因此不能用“Q.rear==MaxSize ”作为队列满的条件，整个问题使用循环队列来解决

循环队列

将顺序队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列

• 当队首指针 Q.front == MaxSize -1后，再前进一个位置到0
• 初始化：Q.front = Q.rear = 0
• 队首指针进1：Q.front = (Q.front + 1) % MaxSize
• 队尾指针进1：Q.rear = (Q.rear + 1) % MaxSize

• 判断队满三种方式

  • 牺牲一个单元来区分队空队满，入队时少用一个队列单元，这是较为普遍的做法，约定以”队头指针在队尾指针的下一位置作为队满的标志”

    • 队满条件 : (Q.rear + 1) % MaxSize == Q.front
    • 队空条件: (Q.front == Q.rear)
    • 队列中元素的个数: (Q.rear - Q.front + MaxSize) % MaxSize

  • 新增一个表示元素个数的数据成员size，这样队空队满的情况下都有Q.rear == Q.front

    • 队满条件 : Q.size == MaxSize
    • 队空条件: Q.size = 0
    • 队列中元素的个数: size

  • 新增tag数据成员。tag为0时表示最近执行了一次删除；tag为1时表示最近执行了一次插入

    • 队满条件 : 当tag等于0时，若因删除导致Q.front == Q.rear则队空；
    • 队空条件: 当tag等于1时，因插入导致Q.front == Q.rear则为队满；

    • 队列中元素个数

      $$\text{队列中元素个数} = \begin{cases} 0, & \text{if } (front == rear \text{ and } tag == 0) \\ MaxSize, & \text{if } (front == rear \text{ and } tag == 1) \\ (rear - front + MaxSize) \% MaxSize, & \text{otherwise} \end{cases}$$

队列的链式存储结构

通常将链式队列设计成一个带头结点的单链表。

C语言描述

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct{
    LinkNode *front,*rear;
}*LinkQueue;

C++描述

TODO

Rust描述

TODO

双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列。将队列的两端称为前端和后端。

输入受限的双端队列

允许在一端进行插入和删除，但在另一端只允许插入。

输出受限的双端队列

允许在一端进行插入和删除，但在另一端只允许删除。

经典应用

层次遍历

数组与特殊矩阵

数组

大多数语言都提供了数组数据类型。

特殊矩阵的压缩

对称矩阵（Symmetric Matrix）

• 性质：矩阵 $A = [a{ij}]$ 满足 $a{ij} = a_{ji}$。
• 压缩方法：只存储矩阵的上三角或下三角部分，例如存储上三角（包括对角线）的元素。

如果矩阵是 $n \times n$，元素按行存储上三角：

$$\text{存储顺序： } a_{11}, a_{12}, \dots, a_{1n}, a_{22}, a_{23}, \dots, a_{2n}, \dots, a_{nn}$$

• 下标映射公式（存储到一维数组 B[k]）：

$$k = \frac{i(i-1)}{2} + j - 1 \quad (i \le j)$$

其中 $i, j$ 从 1 开始计数。

• 存储空间：$\frac{n(n+1)}{2}$ 个元素。

三角矩阵（Triangular Matrix）

• 性质：
  • 上三角矩阵：所有元素 $a_{ij} = 0$ 当 $i > j$
  • 下三角矩阵：所有元素 $a_{ij} = 0$ 当 $i < j$
• 压缩方法：只存储非零的三角部分。

上三角矩阵按行存储公式：

$$k = \frac{i(i-1)}{2} + j - 1 \quad (i \le j)$$

下三角矩阵按行存储公式：

$$k = \frac{i(2n-i+1)}{2} + (j-i) \quad (i \ge j)$$

• 存储空间：$\frac{n(n+1)}{2}$ 个元素。

---

三对角矩阵 / 带状矩阵（Tridiagonal / Banded Matrix）

• 性质：矩阵只有主对角线、上对角线和下对角线有非零元素，其余为 0。

$$A = \begin{bmatrix} a_1 & b_1 & 0 & \dots & 0 \\ c_1 & a_2 & b_2 & \dots & 0 \\ 0 & c_2 & a_3 & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & b_{n-1} \\ 0 & 0 & 0 & c_{n-1} & a_n \end{bmatrix}$$

• 压缩方法：存三个一维数组：
  • A[1..n] 存主对角线 $a_i$
  • B[1..n-1] 存上对角线 $b_i$
  • C[1..n-1] 存下对角线 $c_i$
• 访问公式：

$$a_{i,i} = A[i], \quad a_{i,i+1} = B[i], \quad a_{i+1,i} = C[i]$$

• 存储空间：$3n - 2$ 个元素，比普通 $n^2$ 大幅节省。

稀疏矩阵

矩阵中非零元素的个数t，相对矩阵元素的个数s来说非常少，即$s \gg t$的矩阵称为稀疏矩阵。

若采用常规方法存储稀疏矩阵相当浪费空间，因此仅存储非零元素。但通常非零元素的分布非常没有规律，所以还要存储非零元素的行和列。

因此，将非零元素及对应的行和列构成一个三元组

$$(\text 行标, 列标, 值)$$

然后按某种规律存储这个三元组。稀疏矩阵压缩存储后失去了随机存取的特性。

稀疏矩阵的三元组既可以采用数组存储，也可以采用十字链表法存储。

三元组顺序表（数组存储）

• 将稀疏矩阵中的非零元素按照行优先或列优先顺序存储为三元组 (行标, 列标, 值)。
• 常用顺序：
  • 行优先：按行从上到下、每行从左到右存储。
  • 列优先：按列从左到右、每列从上到下存储。
• 适用于矩阵非零元素不频繁修改的情况。

十字链表存储（Cross Linked List / Orthogonal List）

• 对于动态修改的稀疏矩阵较适用。
• 每个非零元素节点包含：
  • 值
  • 行标
  • 列标
  • 行指针（指向同一行的下一个非零元素）
  • 列指针（指向同一列的下一个非零元素）
• 可以实现行和列的快速遍历，适合矩阵乘法和转置等操作。

串

串的模式匹配

子串的定位操作通常称为串的模式匹配，它求的是子串（通常称为模式串）在主串中的位置。

朴素模式匹配算法

模式串 p 与主串 s

#include <stdio.h>
#include <string.h>

int naive_match(const char *s, const char *p) {
    int i=0,j=0;
    int s_len = strlen(s);
    int p_len = strlen(p);

	while(i<s_len && j<p_len){
        if(s[i]==p[j]){
            i++;
            j++;
        }else{
            i = i - j + 1;//退回去重新匹配
            j = 0;
        }
    }
    if(j == p_len){
        return i - j;
    }
    return -1; 
}

最坏情况：$O(n \cdot m)$，其中 $n$ 是主串长度，$m$ 是模式串长度。

• 例如主串 "aaaaaaab" 和模式串 "aaaab"，每次匹配失败都需要回溯多个字符。

平均情况：通常小于最坏情况，但仍然可能接近 $O(n \cdot m)$。

KMP算法

树与二叉树