数据结构与算法

# 笔记
# 数据结构

数据结构全值指南

43 mins.48k350

前言：C语言概述

C语言是一种通用的高级编程语言，广泛应用于系统软件、嵌入式系统和应用程序开发。它由Dennis Ritchie在1972年开发，具有以下特点：

高效性：C语言直接操作内存，生成的代码执行速度快。
可移植性：C语言代码可以在不同平台上编译运行，具有良好的跨平台特性。

数据结构和C语言的关系

数据结构是用于解决实际问题的工具，而C语言提供了实现这些数据结构的基础。C语言的指针、结构体和数组等特性使得实现各种数据结构变得高效和灵活。

学习数据结构时，你需要掌握的C语言知识

结构体

当一组数据有不同类型的时候，可以用结构体的方式处理数据。相当于是一种复合型的数据类型。
例子：

/* 声明 */
typedef struct student {
    char name[20];  // 姓名
    int num;        // 学号
    float a;        // 成绩
}Student;

/* 定义 */
Student s1;

/* 初始化 */
s1.name = "zhang3";
s1.num = 1;
s1.a = 60;

typedef和difine

typedef是C语言中的一个关键字，用于为已有的数据类型创建一个新的别名。它可以使代码更易读，尤其是在处理复杂数据结构时。

define是C语言中的预处理指令，用于定义宏。它可以用来定义常量或简化代码书写。
1
2
#define PI 3.14 // 定义常量PI为3.14
typedef int Integer; // 定义Integer为int的别名

数组

数组就是很多数的组合。

1	int arr[5] = {1, 2, 3, 4, 5}; // 定义一个整型数组，包含5个元素（若定义赋值不足，则默认后续元素是0）

指针

指针是C语言中一个重要的概念，它是一个变量，用于存储另一个变量的地址。指针可以直接操作内存，提供了灵活的内存管理能力。

int a = 10;
int* p = &a; // 定义一个指针p，指向变量a
printf("%d", *p); // 输出指针p所指向的值，即10
printf("%p", p); // 输出指针p的地址，即a的地址, 形如：0x7ffdfb8c4c4c

函数

函数是C语言的基本构建块，用于组织代码和实现特定功能。
函数可以接受参数并返回值，支持递归调用。
1
2
3
4
5
6
7
/* 函数声明（可省略） */
int add(int a, int b); // 声明一个函数，接受两个整数参数

/* 函数定义 */
int add(int a, int b) {
return a + b; // 返回a和b的和
}
数据结构的实现通常需要使用指针、结构体和数组等C语言特性，因此熟悉这些概念是学习数据结构的基础。

数据结构概述

什么是数据结构：

数据结构学科是研究计算机程序设计问题中*非数值*计算问题的操作对象和方法的学科。

维基百科中的定义为“**数据结构**(data structure)是计算机中**存储**、**组织**数据的方式”。这个简单的定义点出了数据结构的两个核心内容：**存储结构**和**逻辑结构**。
存储结构表示了数据在计算机内存中的物理存储方式，而逻辑结构表示了数据元素之间的关系和组织方式。

举个例子：
假设我们有一个通讯录，里面存储了姓名和电话号码。我们可以将这个通讯录看作一个数据结构。而通讯录的存储结构可以是一个数组（按姓名排序），也可以是一个链表（按插入顺序），甚至可以是一个哈希表（快速查找）。而逻辑结构则表示了姓名和电话号码之间的对应关系。

为什么学习数据结构很重要？：

目前随着深度学习和大数据领域的快速发展，算法工程在各个行业和企业中的应用逐渐广泛，作为一个学习者，学习数据结构是理解，读懂算法的基础，而作为未来的相关工作者，数据结构是提高算法效率和性能的关键。

本文目标与适用人群

本文旨在为初学者提供一个全面的数据结构入门指南，帮助读者理解数据结构的基本概念、分类和应用。适用于计算机科学专业的学生、以及对数据结构感兴趣的初学者。
本文将使用类C语言进行示例代码的编写，读者需要具备一定的C语言编程或抽象语言基础，可以参考前言部分。

什么是算法？

算法是解决特定问题的一系列步骤或规则。它可以被视为一种**数据处理方法**，通过对数据进行操作来实现特定的功能或计算。

算法具有以下特点：

输入：算法有零个或多个输入。
输出：算法有一个或多个输出。
有限性：算法在执行有限步后必然结束。
确定性：算法的每一步都必须是明确的，不能有歧义（无二义性）。
可行性：算法的每一步都必须是可行的，能够在有限时间内完成。

此概念与程序的区别在于，程序是用特定编程语言编写的代码，是算法在计算机上的体现，而算法是解决问题的逻辑步骤。一个程序可以实现多个算法，而一个算法可以用多种编程语言实现。

算法设计的要求：

正确性：算法必须能够正确地解决问题。
高效性：算法的时间复杂度和空间复杂度应尽可能低。
可读性：算法的代码应易于理解和维护。
健壮性（鲁棒性Robustness，很烂但广泛的翻译）：算法应能处理异常情况，避免错误或崩溃。

算法的时间复杂度与空间复杂度

在学习和选择数据结构时，两个核心概念至关重要：

时间复杂度（Time Complexity）

时间复杂度衡量的是算法或操作随着输入规模增长所需时间的变化趋势，通常使用大 O 表示法：

O(f(n)) 表示算法在最坏情况下，其运行时间或空间消耗最多为 f(n) 的某个常数倍。

通俗理解：它不关心具体运行了多少秒，而是关心**数量级**。也就是说，输入增加一倍，运行时间或空间增长多少。

无论是形式上还是含义和用法上，这个表示方法都和数学中的佩亚诺余项有点像（扯远了）

操作时间复杂度示例

访问数组元素 O(1)

查找链表元素 O(n)

排序数组 O(n log n)

BFS遍历图 O(V + E)

不同数据结构在插入、删除、访问等操作上，效率可能有天壤之别。比如：
- 数组访问快（O(1)），但插入慢（O(n)）；
- 链表插入快（O(1)），但访问慢（O(n)）；
- 堆适合快速取最大/最小值（O(log n)）；
- 哈希表查找非常快（O(1) 平均），但最坏情况下是 O(n)。
空间复杂度（Space Complexity）
空间复杂度关注的是算法运行所需的**额外**内存空间大小。

比如：

存储一个长度为 n 的数组需要 O(n) 空间；
使用递归时，调用栈的空间也要算进去。

合理选择数据结构，可以在时间和空间之间做出权衡。例如，如果你需要频繁访问元素，优先考虑数组或哈希表；如果你希望节省内存或者需要动态插入删除，链表可能更合适。

操作	时间复杂度示例
访问数组元素	O(1)
查找链表元素	O(n)
排序数组	O(n log n)
BFS遍历图	O(V + E)

数据结构分类

数据结构可以根据不同的标准进行分类，常见的分类方式包括：

线性结构与非线性结构：
- 线性结构：数据元素之间存在**一对一**的关系，有且仅有一个开始和终端节点，并且所有节点**最多**只有一个直接前驱和直接后继。如数组、链表、栈、队列等。
- 非线性结构：数据元素之间存在**多对多**或**一对多**的关系，一个结构可能有多个直接前驱和直接后继，如树、图等。
静态结构与动态结构：
- 静态结构：数据结构的大小在编译时确定，如数组。
- 动态结构：数据结构的大小可以在运行时动态变化，如链表、树等。
物理结构：
- 顺序存储结构：数据元素在内存中连续存储，如数组。
- 链式存储结构：数据元素通过指针或引用连接在一起，如链表、树等。
- 索引存储结构：数据元素通过索引表进行访问。
- 散列存储结构：数据元素通过哈希函数映射到存储位置，如哈希表。

数据结构的应用

查找
排序

数据结构的基本概念

数据：数据是指可以被计算机处理的符号的集合，通常包括数字、字符、图像等。
数据元素：数据元素是数据的**基本单位**，可以是单个值或多个值的组合。

提示

假如一个学校的表格中有一万个学生信息，这一万个学生信息就是数据，而每个学生的信息（姓名、学号、成绩等）就是数据元素。

数据项：一个学生可以有多个数据项，如姓名、学号、成绩等。数据项是数据元素的组成部分。是不可分割的最小单位。
数据对象：是具有相同性质的数据元素的集合，是一个数据的子集。
数据结构：具有特定关系的数据元素的集合。

🔢 1. 线性表

📘 定义

零个或多个数据元素的有限序列。
记作A = (a1, a2, …, an)。

线性表是一种线性结构，因此有一个**首元素**(a1)和一个**尾元素**(an)，并且每个元素最多只有一个直接前驱(ai-1)和一个直接后继(ai+1)。

⚙️ 存储结构

线性表的存储结构主要有两种：顺序存储和链式存储。

顺序存储：将数据全部存储到一整块连续的内存空间中，按次序存放。
链式存储：将数据元素通过指针或引用连接在一起，数据在内存中可能不连续存储。

📌 1.1 顺序表

顺序表使用一组连续的存储单元来存储数据元素。每个元素在内存中占用相同大小的空间，通常使用数组实现。逻辑上相邻的元素在物理上也相邻存储。

特点：
- 地址连续
- 随机访问
- 依次存储
- 类型相同

顺序表示例：

数组下标	顺序表	内存地址
0	a1	LOC(A)
1	a2	LOC(A) + sizeof(a1)
2	a3	LOC(A) + 2 * sizeof(a1)
…	…	…
n-1	an	LOC(A) + (n-1) * sizeof(a1)

顺序表的实现

C语言写法：

/* 静态分配 */
define MAXSIZE 100 // 定义顺序表的最大长度
typedef int ElemType; // 定义元素类型为int

typedef struct {
    ElemType elem[MAXSIZE]; // 存储空间基址
    int length;     // 当前长度
}SqList; // 顺序表类型定义

SqList A;

/* 动态分配 */
typedef struct {
    ElemType *elem; // 存储空间基址
    int length;     // 当前长度
}SqList; // 顺序表类型定义

SqList A;
A.elem = (ElemType *)malloc(MAXSIZE * sizeof(ElemType)); // 动态分配内存

动态分配的顺序表可以根据需要动态调整大小，使用malloc函数分配内存。
静态分配的顺序表在编译时确定大小，无法动态调整。

顺序表的操作

初始化

/* 为顺序表分配内存并初始化值 */
Status InitList(SqList *L) {
    L->elem = (ElemType *)malloc(MAXSIZE * sizeof(ElemType)); // 动态分配内存
    if (L->elem == NULL) {
        printf("Memory allocation failed!\n");
        exit(OVERFLOW); // 分配失败，退出程序
    }
    L->length = 0; // 初始化长度为0
    return OK; // 返回成功状态
}

销毁

/* 销毁顺序表，释放内存 */
Status DestroyList(SqList *L) {
    if (L->elem != NULL) {
        free(L->elem); // 释放内存
        L->elem = NULL; // 防止悬空指针
    }
    L->length = 0; // 重置长度
    return OK; // 返回成功状态
}

取值

/* 获取顺序表第i个元素并存在变量e中 */
Status GetElem(SqList L, int i, ElemType &e) {
    if (i < 1 || i > L.length) {
        printf("Index out of bounds!\n");
        exit(OVERFLOW); // 索引越界，退出程序
    }
    e = L.elem[i - 1]; // 返回第i个元素
    return OK;
}

查找(O(1))

/* 查找顺序表中第一个值为e的元素，返回其位置（从1开始） */
int LocateElem(SqList L, ElemType e) {
    for (i = 0; i< L.length; i++) {
        if (L.elem == e) return i + 1; // 找到元素，返回位置（从1开始）
    }
    return 0; // 未找到，返回0
}

插入(O(n))

/* 在顺序表的第i个位置插入元素e */
/* 顺序表的插入要将插入位置开始的所有元素向后移一位，来保证顺序表的顺序存储 */
Status ListInsert(SqList *L, int i, ElemType e) {
    if (i < 1 || i > L->length +1) return ERROR;
    if (L->length >= MAXSIZE) {
        printf("List is full!\n");
        return ERROR; // 顺序表已满，无法插入
    }
    for (int j = L->length-1; j >= i-1; j--) {
        L->elem[j] = L->elem[j - 1]; // 将元素后移
    }
    L->elem[i - 1] = e; // 插入新元素
    L->length++; // 更新长度
    return OK; // 返回成功状态
}

提示

若插入在首节点，则所有元素都需要后移；
若插入在尾节点，则无须移动；
平均移动次数为

1	ASL = 1/(1 + n) * sigma(i = 1 -> n+1)[n - i + 1] = [1/(1 + n)][n(n+1)/2] = n/2

删除(O(n))

/* 删除顺序表中第i个位置的元素，并将其存储在变量e中 */
/* 顺序表的删除要将删除位置开始的所有元素向前移一位，来保证顺序表的顺序存储 */
Status ListDelete(SqList *L, int i, ElemType &e) {
    if (i < 1 || i > L.Length + 1) return ERROR;
    if (L.Length == 0) return ERROR;
    
    e = L.elem[i];
    for (j = i; j <= L.Length-1 ; j++) {
        L.elem[j-1] = L.elem[j];
    }
    L.Length--;
    return OK;

}

ASL = (n-1)/2 (计算过程略)

顺序表总结

优点：
- 访问速度快：可以通过下标直接访问元素，时间复杂度为 O(1)。
- 存储密集：内存空间利用率高。
缺点：
- 插入和删除操作效率低：需要移动大量元素，时间复杂度为 O(n)。
- 固定大小：静态分配的顺序表大小固定，无法动态调整。
- 浪费存储空间：可能会造成内存碎片（内存里空着的位置，但是又不连续，不方便顺序使用）。
适用场景：适用于需要频繁访问元素而较少插入删除的场景，如查找、排序等。

📌 1.2 链表

链表是一种动态数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的特点是可以动态调整大小，插入和删除操作效率高。

特点：
- 地址不连续：链表的节点在内存中不一定是连续存储的。
- 动态存储：可以根据需要动态分配和释放内存。
- 指针连接：每个节点通过指针连接到下一个节点。
- 类型相同：链表中的所有节点通常存储相同类型的数据。
节点：
- 数据域：存储实际数据。
- 指针域：存储指向下一个节点的指针。
头指针：链表的第一个节点的指针，通常称为头指针。头指针用于访问链表的第一个节点。
头结点：链表的第一个节点，通常不存储实际数据，而是用于指向链表的第一个元素。
首元结点：链表的第一个实际存储数据的节点。

::: tip

❓ 设置头结点的好处：

便于空表和非空表的统一处理：头结点可以作为链表的起始节点，无论链表是否为空，都可以通过头结点访问。
便于插入和删除操作：头结点可以简化插入和删除操作的逻辑，特别是在处理链表的首元结点时。

:::

提示

判断链表为空：

有头结点时，头结点的指针域为空表示空表
无头结点时，头指针为空表示空表

链表的实现

C语言写法：

typedef struct LNode {
    ElemType data; // 数据域
    struct LNode *next; // 指针域，指向下一个节点
} LNode; // 链表节点类型定义

typedef struct {
    LNode *head; // 头指针，指向链表的第一个节点
} LinkList; // 链表类型定义

LinkList L; // 定义一个链表L

链表的操作

初始化


/* 初始化链表，创建一个头结点 */
Status InitList (Linklist &L) {
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    return OK;
}

取值


/* 获取链表第i个位置的元素 */
Status GetElem(LinkList L, int i, ElemType &e) {
    LinkList p = L;
    p = p->next;    // 移动到首元结点
    int n = i-1;
    while(n && p) { // 移动指针到第i个元素的位置
        n--;
        p = p->next;
    }

    if (p) {
        e = p->data;
        return OK;
    }

    return OVERFLOW;

}

查找(O(n))


/* 查找链表中元素为e的节点 */
LNode FindElem(LinkList L, ElemType e) {    // 返回目标结点
    LinkList p = L->next;
    while (p) {
        if (p->data == e) {
            return p;
        }
        i++;
        p = p->next;
    }
    if (!p || p->data != e) return NULL;
    
}

插入(O(n)) (插入操作只需要移动指针，时间复杂度是O(1)，但需要查找到插入节点位置O(n)，下同)


/* 在第i个节点之前插入一个元素值为e的节点，链表的插入和删除需要特别注意指针的处理方法 */
Status InsertList (LinkList &L, ElemType e, int i) {
    LinkList p = L;
    LinkList q = (LinkList)malloc(sizeof(LNode));    // 要插入的新节点
    q->data = e;
    q->next = NULL;

    while(i-1) {
        i--;
        p = p->next;    // 移动指针到插入位置的前缀节点
    }

    if (p) {
        q->next = p->next;
        p->next = q;
        return OK;
    }
    
    return ERROR;
}

删除(O(n))


/* 删除第i个节点 */
Status DeleteNode(LinkList &L, int i) {
    LinkList p = L;
    LinkList s;
    while (i-1) {
        i--;
        p = p->next;
    }

    if (p && p->next) {
        s = p->next;
        p ->next = s->next;
        free(s);        // 或者直接写p->next = p->next->next，如果不用管free的话，这样也不需要使用s
        return OK;
    }

    return ERROR;
}

链表的分类

单链表（只有一个指针域）

双链表（有两个指针域，一个指向前驱，一个指向后继）

插入时指针需要更多处理(建议第一次搞不懂画个图理清楚)

/* 只展示指针操作 */
// s为插入节点 p为插入位置后一个节点\
// 具体操作是先理顺p前驱和s的指针，再理顺p和s的指针（只要不断链就行，但是这样理比较清楚）
p->prep->next = s;
s->prep = p->prep;
p->prep = s;
s->next = p;

循环链表（首尾相接的链表）
- 判空
  1
  2
  p != L; // 没有头结点，非循环链表时为p != NULL
  p->next != L; // 有头结点，非循环链表时为p->next != NULL
  有些循环链表仅有尾指针（即指向最后一个节点的指针），这样的链表在执行尾部插入时更加方便（不需要进行尾部查找操作），且尾指针后移一个节点就可以找到头结点。

☁️ 2. 栈

📘 定义

只能在表的一端进行插入和删除的线性表，其中表尾成为**栈顶**（top），表头成为**栈底**（base）。

栈的实现

顺序栈：top指向栈顶元素的后一个（上一个）, base指向栈底元素, stacksize表示最大容量
- 栈空：base = top
- 栈满：top - base == stacksize
  1
  2
  3
  4
  5
  typedef struct {
  ElemType *base;
  ElemType *top;
  int stacksize;
  }SqStack;

链栈：

不用头结点（只操作栈顶，所以不需要头结点）

typedef struct StackNode{
    int data;
    struct StackNode *next;
}StackNode, *LinkStack;

栈的操作（顺序栈为例）

初始化

Status InitStack(SqStack &S) {
    S.base = (ElemType*)malloc(sizeof(ElemType));
    if (!S.base) {return OVERFLOW;}
    S.top = S.base;
    S.stacksize = MAXSIZE;
    return OK;
}

入栈

Status Push(SqStack &S, ElemType e) {
    if (S.top - S.base == S.stacksize) return ERROR;    //栈满
    *S.top = e;
    S.top++;
    return OK;
}

出栈

Status Pop(SqStack &S, ElemType &e) {
    if (S.top == S.base) return ERROR;  //栈空
    S.top--;
    e = *S.top;
    return OK;
}

拓展：共享栈

有两个相同类型的栈时，采用共享栈可以最大限度的利用开辟的空间。
两个栈分别以一块顺序空间的头和尾作为栈底，对向增长。

此时为了便于操作，top指向栈顶元素，而非栈顶的上方一个位置。

判空：top0 == -1;top1 == maxsize;
判满：top0 + 1 == top1;

⭕ 3. 队列

📘 定义

队列是一种先进先出的线性表，在表一端（队尾）进行插入，在表的另一端（对头）进行删除。

队列的实现

顺序队列

front指向**队头**元素，rear指向**队尾**元素的后一个。
由于顺序队列在出队时，front需要后移，很容易造成已经分配的空间无法使用（即front之前的空位置无法再次插入数据），我们可以通过连接队列的头尾，形成一个**循环队列**，这样就可以解决这个问题。
1
2
3
4
typedef struct {
ElemType data[MAXSIZE];
int front, rear;
}SqQueue;
- 队空：front == rear
- 队满：rear == MAXSIZE
- 循环队列由于队满和队空时都有front == rear，则可以通过牺牲一个元素空间的方法，令(rear + 1)%MAXSIZE == front时为队满。

链队列

typedef struct QNode {
    ElemType data;
    struct QNode *next;
}*QueuePoint;

typedef struct {
    QueuePoint front;
    QueuePoint rear;
}LinkQueue;

front指向头结点
判空front == rear == head

队列的操作（循环队列&链队列）

初始化

/* 循环队列 */
Status InitQueue(SqQueue &Q) {
    Q.data = (ElemType*)malloc(MAXSIZE*sizeof(ElemType));
    if (!Q) return OVERFLOW;
    Q.front = 0;
    Q.rear = 0;
    return OK;
}

/* 链队列 */
Status InitQue(LinkQueue L) {
    L.front = L.rear = (QueuePoint)malloc(sizeof(QNode));
    if (!L) return OVERFLOW;
    L.front->next = NULL;
    return OK;
}

入队

/* 循环队列 */
Status EnQueue(SqQueue &Q, ElemType e) {
    if ((Q.rear+1) % MAXSIZE == Q.front) return ERROR;    // 队满
    Q.data[Q.rear] == e;
    Q.rear = (Q.rear + 1) % MAXSIZE;
    return OK;
}

/* 链队列 */
Status EnQue(LinkQueue &L, ElemType e) {
    QueuePoint p = (QueuePoint)malloc(sizeof(QNode));
    if (!p) return OVERFLOW;
    p->data = e;
    p->next = NULL;
    L.rear->next = p;
    L.rear = p;
    return OK;
}

出队

/* 循环队列 */
Status DeQueue(SqQueue Q, ElemType &e) {
    if (Q.front == Q.rear) return ERROR;    // 队空
    e = Q.data[Q.front];
    Q.front = (Q.front + 1) % MAXSIZE;
    
    return OK;
}

/* 链队列 */
Status DeQue(LinkQueue &L, ElemType e) {
    if (L.rear == L.front) return ERROR;
    QueuePoint p = L.front->next;
    L.front->next = L.front->next->next;
    if (L.rear == p) {
        L.rear == L.front;      // 如果队列只有一个元素的时候，要确保队空
    }
    free(p);
    return OK;
}

求队长

/* 循环队列 */
int QueueLen(SqQueue) {
    return ((Q.rear - Q.front + MAXSIZE) % MAXSIZE)
}

🚢 4. 串

📘 定义

串是多个或零个字符组成的有限序列。
记作S=“a1a2…an”

子串：串中任意连续的一段字符序列。
主串：包含子串的串。
字符位置：串中字符的下标，从1开始。
子串位置：子串在主串中的起始位置。
串的长度：串中字符的个数。
空格串：由一个或多个空格组成的串。
空串：长度为0的串。

💡 串的模式匹配

模式匹配是指在主串中查找与模式串相同的子串位置。常用的模式匹配算法有：

暴力匹配：从主串的每个位置开始，逐个字符比较，直到找到匹配或主串结束。时间复杂度为 O(m*n)，其中 m 为主串长度，n 为模式串长度。
KMP算法：通过预处理模式串，减少不必要的比较，**永不回退主串中的指针**，提高匹配效率。时间复杂度为 O(m+n)。

KMP算法原理

KMP算法的核心是**部分匹配表**（也称为前缀表），它记录了模式串中每个位置的最长前缀和后缀的长度。通过这个表，可以在匹配失败时跳过一些不必要的比较，从而提高效率。

公共前后缀：
- 前缀：模式串的前缀是指从第一个字符开始，到某个位置之前的子串。
- 后缀：模式串的后缀是指从某个位置开始，到最后一个字符的子串。
- 真前缀：前缀中不包含最后一个字符的子串。
- 真后缀：后缀中不包含第一个字符的子串
- 公共前后缀：既是前缀又是后缀的子串。
next数组：记录模式串中每个位置的**最长公共真前后缀**的长度。通过这个数组，可以在匹配失败时跳过一些字符。

示例：
主串："ababcabbabbabab"
模式串："abbabba"

部分匹配表（next数组）：

位置 1 2 3 4 5 6 7

字符 a b b a b b a

next 0 1 1 1 2 3 4

位置	1	2	3	4	5	6	7
字符	a	b	b	a	b	b	a
next	0	1	1	1	2	3	4

next数组的作用是，当匹配失败时，可以根据当前匹配的位置和next数组的值，跳过一些不必要的比较，从而提高匹配效率。

kmp算法的详细介绍和实现可以参考这篇文章：KMP（Knuth-Morris-Pratt）算法详解

📚 5. 数组

📘 定义

数组是具有相同数据类型的元素的集合，元素在内存中连续存储。数组的特点是可以通过下标直接访问元素，支持随机访问。

这里我们重点探讨多维数组。

多维数组

多维数组是数组的扩展，可以看作是一个矩阵或表格。

二维数组：可以看作是一个矩阵，具有行和列的结构。
三维数组：可以看作是一个立体矩阵，具有行、列和层的结构。
n维数组：可以看作是一个多维矩阵，具有n个维度。

二维数组

二维数组是一个矩阵，可以通过行和列的下标访问元素。二维数组的存储方式有两种：行主序和列主序。

行主序：按行存储，先存储第一行的所有元素，再存储第二行的所有元素，以此类推。
列主序：按列存储，先存储第一列的所有元素，再存储第二列的所有元素，以此类推。

二维矩阵可以理解成一种矩阵，这里介绍矩阵的压缩存储方式。

矩阵的压缩存储

矩阵的压缩存储是指将稀疏矩阵（大部分元素为0的矩阵）（或者对称矩阵这种具有明显分布特征的矩阵）存储为一种更紧凑的形式，以节省存储空间。

对于稀疏矩阵，常见的压缩存储方式有：

三元组表示：将非零元素的行、列和数值存储为三个数组。

typedef struct {
    int row; // 行索引
    int col; // 列索引
    int value; // 非零元素的值
} Triple;

typedef struct {
    Triple *data; // 存储非零元素的数组
    int rows; // 矩阵的行数
    int cols; // 矩阵的列数
    int nonZeroCount; // 非零元素的个数
} SparseMatrix; // 稀疏矩阵类型定义

邻接表表示：通常适用表示图的矩阵的存储，将每个顶点的邻接边存储为一个链表。

typedef struct ArcNode {
    int adjvex; // 邻接点的下标
    struct ArcNode *next; // 指向下一条边的指针
} ArcNode;

typedef struct VNode {
    int data; // 顶点数据
    ArcNode *firstArc; // 指向第一条边的指针
} VNode;

typedef struct {
    VNode *vertices; // 存储顶点的数组
    int vertexCount; // 顶点数量
} Graph; // 图类型定义

十字链表：通常适用表示图的矩阵的存储，能够高效地表示边的起点和终点。

typedef struct OLNode {
    int ivex; // 起点顶点的下标
    int jvex; // 终点顶点的下标
    struct OLNode *ilink; // 指向同一行的下一条边
    struct OLNode *jlink; // 指向同一列的下一条边
} OLNode;

typedef struct {
    OLNode **vertices; // 存储顶点的数组
    int vertexCount; // 顶点数量
} OrthogonalList; // 十字链表类型定义

🌳 6. 树

📘 定义

树是有n个节点的有限集合，其中有且仅有一个节点称为根节点，其余节点分为m个互不相交的有限集合，每个集合又是一个树，这些集合称为根节点的子树(SubTree)。

节点：树中的每个元素称为节点。
根节点：树的第一个节点，只有一个。
子树：根节点的子节点构成的树。
叶子节点：没有子节点的节点。
度：节点的子节点个数。**树的度**是指所有节点的度的最大值。
深度：节点到根节点的路径长度。
高度：树中节点的最大深度。
路径：从一个节点到另一个节点的路径。
兄弟节点：同一个父节点的子节点称为兄弟节点。
祖先节点：从根节点到当前节点的路径上的所有节点。
孩子节点：当前节点的直接子节点。
父节点：当前节点的直接上级节点。
有序树：子节点有序的树。各节点从左到右有序，不能互换位置。
无序树：子节点无序的树。

树的存储

双亲表示法：每个节点存储其双亲节点的指针。

typedef struct PTNode {
    ElemType data; // 数据域
    int parent; // 双亲节点的下标
} PTNode;

typedef struct {
    PTNode *nodes; // 存储节点的数组
    int nodeCount; // 节点数量
} ParentTree; // 双亲表示法类型定义

孩子表示法：每个节点存储其孩子节点的指针。

typedef struct CTNode {
    int child; // 孩子节点的下标
    struct CTNode *next; // 指向下一个孩子节点的指针
} CTNode;

typedef struct {
    ElemType data; // 数据域
    CTNode *firstChild; // 指向第一个孩子节点的指针
} CNode;

typedef struct {
    CNode *nodes; // 存储节点的数组
    int nodeCount; // 节点数量
} ChildTree; // 孩子表示法类型定义

孩子兄弟表示法：每个节点存储其第一个孩子节点和下一个兄弟节点的指针。（通过这种方法可以实现将树转化为二叉树）

typedef struct CSNode {
    ElemType data; // 数据域
    struct CSNode *firstChild; // 指向第一个孩子节点的指针
    struct CSNode *nextSibling; // 指向下一个兄弟节点的指针
} CSNode;

typedef struct {
    CSNode *root; // 指向树的根节点
} ChildSiblingTree; // 孩子兄弟表示法类型定义

📖 7. 二叉树

📘 定义

二叉树是每个节点最多有两个子节点的有序树。每个节点有左子节点和右子节点，左子节点小于父节点，右子节点大于父节点。

满二叉树：每个节点都有两个子节点的二叉树。
完全二叉树：除了最后一层外，每一层的节点数都达到最大值，且最后一层的节点从左到右连续排列的二叉树。
平衡二叉树：每个节点的左子树和右子树的高度差不超过1的二叉树。
二叉搜索树：左子树的所有节点小于父节点，右子树的所有节点大于父节点的二叉树。

二叉树的性质

节点数：一个有 n 个节点的二叉树，深度至少为 log2(n+1)。
叶子节点数：一个有 n 个节点的二叉树，叶子节点数至少为 1，最多为 n/2。
度数：二叉树中度为 0 的节点数加上度为 1 的节点数加上度为 2 的节点数等于 n。
度数为 0 的节点数等于度为 2 的节点数加 1。
在第i层的节点数最多为 2^(i-1)。
深度为h的二叉树，最多有 2^h - 1 个节点。

::: details 计算推导

总度数 = 2 * (度为 2 的节点数) + (度为 1 的节点数)
总度数 = 总节点数 - 1
总节点数 = 度为 2 的节点数 + 度为 1 的节点数 + 度为 0 的节点数
度为 0 的节点数 = 总节点数 - (度为 2 的节点数 + 度为 1 的节点数)
度为 0 的节点数 = 度为 2 的节点数加 1。

:::

二叉树的存储结构

二叉树的存储结构主要有两种：顺序存储和链式存储。

顺序存储：使用数组存储二叉树，根节点存储在数组的第一个位置，左子节点存储在 2*i 位置，右子节点存储在 2*i + 1 位置。
- 特点：
- 适用于完全二叉树或满二叉树。
- 优点：存储密集，访问速度快。
- 缺点：不适用于稀疏二叉树，可能浪费大量空间。

链式存储：使用链表存储二叉树，每个节点包含数据和指向左子节点和右子节点的指针。

特点：
适用于任意形状的二叉树。
优点：节省空间，适用于稀疏二叉树。

缺点：访问速度较慢，需要遍历链表。

typedef struct BiTNode {
    ElemType data; // 数据域
    struct BiTNode *lchild; // 左子节点指针
    struct BiTNode *rchild; // 右子节点指针
} BiTNode, *BiTree; // 二叉树类型定义

拓展：二叉树的链式存储还可以使用双向链表来实现，增加了对父节点的指针，使得从子节点可以访问到父节点。

二叉树的遍历

二叉树的遍历是指按照一定的顺序访问二叉树的所有节点。常见的遍历方式有：

前序遍历：访问根节点，前序遍历*左子树*（不仅仅是左节点，后同），前序遍历右子树。
中序遍历：中序遍历左子树，访问根节点，中序遍历右子树。
后序遍历：后序遍历左子树，后序遍历右子树，访问根节点。
层序遍历：按层次从上到下、从左到右访问二叉树的节点。

示例：
        A
       / \
      B   C
     / \   \
    D   E   F

前序遍历：A B D E C F
中序遍历：D B E A C F
后序遍历：D E B F C A
层序遍历：A B C D E F

二叉树的遍历实现

前序遍历：

递归：递归的思想是将程序反复调用自身，既然递归反复调用自身，就说明每一级功能一样，我们只需要关注一级递归的解决过程就可以。

void PreOrder(BiTree T) {
    if (T == NULL) return; // 基本情况：空树
    printf("%c ", T->data); // 访问根节点
    PreOrder(T->lchild); // 前序遍历左子树
    PreOrder(T->rchild); // 前序遍历右子树
}

非递归：使用栈来模拟递归的过程。

void PreOrderNonRecursive(BiTree T) {
    Stack S; // 创建栈
    InitStack(S); // 初始化栈
    BiTree p = T; // 指向当前节点
    while (p != NULL || !IsEmpty(S)) {
        while (p != NULL) {
            printf("%c ", p->data); // 访问根节点
            Push(S, p); // 将当前节点入栈
            p = p->lchild; // 移动到左子节点
        }
        if (!IsEmpty(S)) {
            Pop(S, &p); // 弹出栈顶节点
            p = p->rchild; // 移动到右子节点
        }
    }
}

中序遍历：

递归：

void InOrder(BiTree T) {
    if (T == NULL) return; // 基本情况：空树
    InOrder(T->lchild); // 中序遍历左子树
    printf("%c ", T->data); // 访问根节点
    InOrder(T->rchild); // 中序遍历右子树
}

非递归：使用栈来模拟递归的过程。

void InOrderNonRecursive(BiTree T) {
    Stack S; // 创建栈
    InitStack(S); // 初始化栈
    BiTree p = T; // 指向当前节点
    while (p != NULL || !IsEmpty(S)) {
        while (p != NULL) {
            Push(S, p); // 将当前节点入栈
            p = p->lchild; // 移动到左子节点
        }
        if (!IsEmpty(S)) {
            Pop(S, &p); // 弹出栈顶节点
            printf("%c ", p->data); // 访问根节点
            p = p->rchild; // 移动到右子节点
        }
    }
}

后序遍历：

递归：

void PostOrder(BiTree T) {
    if (T == NULL) return; // 基本情况：空树
    PostOrder(T->lchild); // 后序遍历左子树
    PostOrder(T->rchild); // 后序遍历右子树
    printf("%c ", T->data); // 访问根节点
}

非递归：使用栈来模拟递归的过程。

void PostOrderNonRecursive(BiTree T) {
    Stack S; // 创建栈
    InitStack(S); // 初始化栈
    BiTree p = T; // 指向当前节点
    BiTree lastVisited = NULL; // 记录上一个访问的节点
    while (p != NULL || !IsEmpty(S)) {
        while (p != NULL) {
            Push(S, p); // 将当前节点入栈
            p = p->lchild; // 移动到左子节点
        }
        if (!IsEmpty(S)) {
            Pop(S, &p); // 弹出栈顶节点
            // 检查右子节点是否已被访问
            if (p->rchild == NULL || p->rchild == lastVisited) {
                printf("%c ", p->data); // 访问根节点
                lastVisited = p; // 更新上一个访问的节点
                p = NULL; // 设置当前节点为NULL，继续处理栈
            } else {
                Push(S, p); // 将当前节点重新入栈
                p = p->rchild; // 移动到右子节点
            }
        }
    }
}

线索二叉树

研究线索二叉树的原因：普通二叉树只能找到节点的左右孩子，而节点的直接前驱和直接后继只能在遍历的过程中获得，无法直接访问。线索二叉树通过增加指向前驱和后继的指针，解决了这个问题。

线索二叉树：在二叉树的基础上，为每个节点增加指向前驱和后继的指针，使得可以直接访问前驱和后继节点。
线索：指向前驱或后继的指针。
线索化：将二叉树转换为线索二叉树的过程。

线索二叉树的规则：

如果节点的左子树为空，则将左指针指向前驱节点
如果节点的右子树为空，则将右指针指向后继节点
如果节点的左子树不为空，则左指针指向左子节点

如果节点的右子树不为空，则右指针指向右子节点
为了区分线索和子树指针，通常使用一个标志位来表示指针是线索还是子树指针。

typedef struct ThreadNode {
    ElemType data; // 数据域
    struct ThreadNode *lchild; // 左子节点指针
    struct ThreadNode *rchild; // 右子节点指针
    int ltag; // 左指针标志，0表示指向左子节点，1表示指向前驱
    int rtag; // 右指针标志，0表示指向右子节点，1表示指向后继
} ThreadNode, *ThreadTree; // 线索二叉树类型定义

二叉树的线索化

线索化的过程是将二叉树转换为线索二叉树。线索化的步骤如下：（以先序线索二叉树为例）

先序遍历二叉树，访问每个节点。
在访问节点时，根据节点的左右子树是否为空，设置左指针和右指针的线索。
如果左子树为空，则将左指针指向前驱节点，并设置左指针标志为1。
如果右子树为空，则将右指针指向后继节点，并设置右指针标志为1。
如果左子树不为空，则左指针指向左子节点，并设置左指针标志为0。

如果右子树不为空，则右指针指向右子节点，并设置右指针标志为0。

void ThreadedPreOrder(ThreadTree T, ThreadTree &pre) {
    if (T == NULL) return; // 基本情况：空树
    if (T->lchild == NULL) { // 左子树为空
        T->lchild = pre; // 将左指针指向前驱节点
        T->ltag = 1; // 设置左指针标志为1
    }
    if (pre != NULL && pre->rchild == NULL) { // 前驱节点
        pre->rchild = T; // 将前驱节点的右指针指向当前节点
        pre->rtag = 1; // 设置右指针标志为1
    }
    pre = T; // 更新前驱节点
    ThreadedPreOrder(T->lchild, pre); // 线索化左子树
    ThreadedPreOrder(T->rchild, pre); // 线索化右子树
}

void CreateThreadedTree(ThreadTree &T) {
    ThreadTree pre = NULL; // 前驱节点初始化为NULL
    ThreadedPreOrder(T, pre); // 线索化二叉树
    if (pre != NULL) { // 如果最后一个节点的右子树为空
        pre->rchild = NULL; // 将最后一个节点的右指针设置为NULL
        pre->rtag = 1; // 设置右指针标志为1
    }
}

哈夫曼树

假设有n个权值为w1, w2, …, wn的叶子节点，哈夫曼树是一个带权路径长度最小的二叉树，或称为最优二叉树。
哈夫曼树的构建过程如下：

将所有叶子节点按照权值从小到大排序。
取出权值最小的两个节点，创建一个新节点，其权值为这两个节点的权值之和。
将新节点插入到原来的节点列表中，并重新排序。

重复步骤2和3，直到只剩下一个节点为止，这个节点就是哈夫曼树的根节点。

typedef struct HuffmanNode {
    ElemType data; // 数据域
    int weight; // 权值
    struct HuffmanNode *lchild; // 左子节点指针
    struct HuffmanNode *rchild; // 右子节点指针
} HuffmanNode, *HuffmanTree; // 哈夫曼树类型定义

void CreateHuffmanTree(HuffmanTree &T, int *weights, int n) {
    // 创建一个优先队列或最小堆来存储节点
    PriorityQueue pq; // 假设有一个优先队列的实现
    for (int i = 0; i < n; i++) {
        HuffmanNode *node = (HuffmanNode *)malloc(sizeof(HuffmanNode));
        node->data = 'a' + i; // 假设数据为字符'a'到'z'
        node->weight = weights[i];
        node->lchild = node->rchild = NULL;
        Enqueue(pq, node); // 将节点插入到优先队列中
    }

    while (pq.size() > 1) {
        HuffmanNode *left = Dequeue(pq); // 取出权值最小的左节点
        HuffmanNode *right = Dequeue(pq); // 取出权值次小的右节点
        HuffmanNode *newNode = (HuffmanNode *)malloc(sizeof(HuffmanNode));
        newNode->data = '\0'; // 新节点没有数据
        newNode->weight = left->weight + right->weight; // 新节点的权值为左右子节点的权值之和
        newNode->lchild = left; // 左子节点指向左节点
        newNode->rchild = right; // 右子节点指向右节点
        Enqueue(pq, newNode); // 将新节点插入到优先队列中
    }
    T = Dequeue(pq); // 最后剩下的节点就是哈夫曼树的根节点
}

哈夫曼编码

哈夫曼编码是将字符编码为二进制字符串的一种方法，使用哈夫曼树来生成编码。使用哈夫曼编码可以有效地压缩数据，将出现频率高的字符编码为短的二进制字符串，出现频率低的字符编码为长的二进制字符串。

编码规则：从根节点到叶子节点的路径上，左子节点编码为0，右子节点编码为1。
编码过程：遍历哈夫曼树，记录每个字符的编码。
解码过程：根据编码从根节点开始遍历哈夫曼树，直到到达叶子节点，输出对应的字符。
前缀编码：哈夫曼编码是一种前缀编码，即没有任何一个编码是另一个编码的前缀，这样可以保证解码的唯一性。

void GenerateHuffmanCode(HuffmanTree T, char **codes, char *code, int depth) {
    if (T == NULL) return; // 基本情况：空树
    if (T->lchild == NULL && T->rchild == NULL) { //  // 叶子节点
        code[depth] = '\0'; // 结束编码
        codes[T->data - 'a'] = strdup(code); // 保存编码
        return;
    }
    code[depth] = '0'; // 左子节点编码为0
    GenerateHuffmanCode(T->lchild, codes, code, depth + 1);
    code[depth] = '1'; // 右子节点编码为1
    GenerateHuffmanCode(T->rchild, codes, code, depth + 1);
}
void CreateHuffmanCode(HuffmanTree T, char **codes) {
    char code[100]; // 假设编码长度不超过100
    GenerateHuffmanCode(T, codes, code, 0); // 生成哈夫曼编码
}

🐰 8. 图

📘 定义

图是由顶点和边组成的集合，顶点表示实体，边表示实体之间的关系。

顶点：图中的节点，表示实体。
边：连接两个顶点的线，表示顶点之间的关系。

记作：G = (V, E)，其中V是顶点集合，E是边集合。

图的相关术语：

路径：从一个顶点到另一个顶点的边的序列。
回路：路径的起点和终点是同一个顶点的路径。
弧：有向图中的边，表示从一个顶点到另一个顶点的单向关系。
连通分量：图中任意两个顶点之间都有路径相连的最大子图。
度：顶点的度数是指与该顶点相连的边的数量。（与树区分）
- 入度：有向图中指向该顶点的边的数量。
- 出度：有向图中从该顶点出发的边的数量。
无向图：边没有方向，表示顶点之间的双向关系。
有向图：边有方向，表示顶点之间的单向关系
带权图：边有权值，表示顶点之间的关系强度或距离。
无权图：边没有权值。
连通图：任意两个顶点之间都有路径相连。
非连通图：存在至少一对顶点之间没有路径相连。
强连通图：有向图中任意两个顶点之间都有*路径*相连。
弱连通图：有向图中任意两个顶点之间在*忽略边的方向*后都有路径相连。
简单图：没有自环和重边的图。
多重图：允许有自环和重边的图。
完全图：每对顶点之间都有一条边相连的图。
子图：从原图中选取部分顶点和边构成的图。
生成树：包含图中所有顶点的子图，且是一个树。
欧拉图：存在一条经过每条边恰好一次的闭合路径的图。

图的存储结构

图的存储结构主要有两种：邻接矩阵和邻接表，链接多重表，十字链表。

邻接矩阵：使用一个*二维数组*表示图，行和列表示顶点，数组元素表示顶点之间的边。A[m][n] = L 表示顶点m和顶点n之间有边相连，且权值为L，A[m][n] = Inf 表示没有边相连。
- 无向图：邻接矩阵是对称的。
- 有向图：邻接矩阵不一定对称。
- 稀疏图：使用邻接矩阵存储时会浪费空间。
  1
  2
  3
  4
  5
  typedef struct {
  int **matrix; // 邻接矩阵
  int vertexCount; // 顶点数量
  int edgeCount; // 边数量
  } AdjMatrix; // 邻接矩阵类型定义

邻接表：使用*链表*存储图，每个顶点对应一个链表，链表中的节点表示与该顶点相连的其他顶点和边的权值。

无向图：每条边在两个顶点的链表中都存在。

有向图：每条边只在一个顶点的链表中存在，默认是记录出边。

typedef struct ArcNode {
    int adjvex; // 邻接点的下标
    int weight; // 边的权值
    struct ArcNode *next; // 指向下一条边的指针
} ArcNode;

typedef struct VNode {
    int data; // 顶点数据
    ArcNode *firstArc; // 指向第一条边的指针
} VNode;

typedef struct {
    VNode *vertices; // 存储顶点的数组
    int vertexCount; // 顶点数量
    int edgeCount; // 边数量
} AdjList; // 邻接表类型定义

十字链表：适用于有向图的存储，能够高效地表示边的起点和终点。

typedef struct OLNode {
    int ivex; // 起点顶点的下标
    int jvex; // 终点顶点的下标
    struct OLNode *ilink; // 指向同一行的下一条边
    struct OLNode *jlink; // 指向同一列的下一条边
} OLNode;

typedef struct {
    OLNode **vertices; // 存储顶点的数组
    int vertexCount; // 顶点数量
    int edgeCount; // 边数量
} OrthogonalList; // 十字链表类型定义

链接多重表：适用于多重图的存储，能够表示多条边和自环。

typedef struct ArcNode {
    int adjvex; // 邻接点的下标
    int weight; // 边的权值
    struct ArcNode *next; // 指向下一条边的指针
    struct ArcNode *prev; // 指向上一条边的指针（用于多重边）
} ArcNode;

typedef struct VNode {
    int data; // 顶点数据
    ArcNode *firstArc; // 指向第一条边的指针
} VNode;

typedef struct {
    VNode *vertices; // 存储顶点的数组
    int vertexCount; // 顶点数量
    int edgeCount; // 边数量
} MultiAdjList; // 链接多重表类型定义

图的遍历

图的遍历是指按照一定的顺序访问图中的所有顶点。常见的遍历方式有：

深度优先遍历（DFS）：从一个顶点开始，尽可能深地访问每个顶点，直到没有未访问的邻接顶点为止，然后回溯到上一个顶点继续访问。
广度优先遍历（BFS）：从一个顶点开始，访问所有直接邻接的顶点，然后再访问这些顶点的邻接顶点，层层推进。

在图的遍历中，通常需要使用一个访问标记数组(visited[])来记录哪些顶点已经被访问过，以避免重复访问。

深度优先遍历（DFS）

深度优先遍历的实现可以使用递归或栈来模拟递归的过程。

递归实现：

void DFS(AdjList G, int v, bool *visited) {
    visited[v] = true; // 标记当前顶点为已访问
    printf("%d ", G.vertices[v].data); // 访问当前顶点
    ArcNode *p = G.vertices[v].firstArc; // 获取当前顶点的第一个邻接边
    while (p != NULL) {
        if (!visited[p->adjvex]) { // 如果邻接顶点未被访问
            DFS(G, p->adjvex, visited); // 递归访问邻接顶点
        }
        p = p->next; // 移动到下一条边
    }
}

void DFSGraph(AdjList G) {
    bool *visited = (bool *)malloc(G.vertexCount * sizeof(bool)); // 创建访问标记数组
    for (int i = 0; i < G.vertexCount; i++) {
        visited[i] = false; // 初始化所有顶点为未访问
    }
    for (int i = 0; i < G.vertexCount; i++) {
        if (!visited[i]) { // 如果顶点未被访问
            DFS(G, i, visited); // 从该顶点开始深度优先遍历
        }
    }
    free(visited); // 释放访问标记数组
}

非递归实现：使用栈来模拟递归的过程。

void DFSNonRecursive(AdjList G) {
    bool *visited = (bool *)malloc(G.vertexCount * sizeof(bool)); // 创建访问标记数组
    for (int i = 0; i < G.vertexCount; i    ++) {
        visited[i] = false; // 初始化所有顶点为未访问
    }
    Stack S; // 创建栈
    InitStack(S); // 初始化栈
    for (int i = 0; i < G.vertexCount; i++) {
        if (!visited[i]) { // 如果顶点未被访问
            Push(S, i); // 将顶点入栈
            while (!IsEmpty(S)) {
                int v;
                Pop(S, &v); // 弹出栈顶顶点
                if (!visited[v]) { // 如果顶点未被访问
                    visited[v] = true; // 标记为已访问
                    printf("%d ", G.vertices[v].data); // 访问顶点
                    ArcNode *p = G.vertices[v].firstArc; // 获取当前顶点的第一个邻接边
                    while (p != NULL) {
                        if (!visited[p->adjvex]) { // 如果邻接顶点未被访问
                            Push(S, p->adjvex); // 将邻接顶点入栈
                        }
                        p = p->next; // 移动到下一条边
                    }
                }
            }
        }
    }
    free(visited); // 释放访问标记数组
}

::: tip
当使用邻接矩阵来表示图，遍历每一个图中的顶点都要从头扫过邻接矩阵的每一行，时间复杂度为**O(V^2)，其中V是顶点数量。
当使用邻接表来表示图，遍历每一个图中的顶点只需要访问每一个点和与该顶点相连的边，时间复杂度为O(E+V)**，其中E是边的数量。

结论：**邻接表**更适合**稀疏图**的存储和遍历，**邻接矩阵**更适合**密集图**的存储和遍历。
:::

广度优先遍历（BFS）

广度优先遍历的实现可以使用队列来实现。（可以用于二叉树的层次遍历）

void BFS(AdjList G, int v, bool *visited) {
    Queue Q; // 创建队列
    InitQueue(Q); // 初始化队列
    visited[v] = true; // 标记当前顶点为已访问
    Enqueue(Q, v); // 将当前顶点入队
    while (!IsEmpty(Q)) {
        int u;
        Dequeue(Q, &u); // 出队一个顶点
        printf("%d ", G.vertices[u].data); // 访问当前顶点
        ArcNode *p = G.vertices[u].firstArc; // 获取当前顶点的第一个邻接边
        while (p != NULL) {
            if (!visited[p->adjvex]) { // 如果邻接顶点未被访问
                visited[p->adjvex] = true; // 标记为已访问
                Enqueue(Q, p->adjvex); // 将邻接顶点入队
            }
            p = p->next; // 移动到下一条边
        }
    }
    FreeQueue(Q); // 释放队列
}

void BFSGraph(AdjList G) {
    bool *visited = (bool *)malloc(G.vertexCount * sizeof(bool)); // 创建访问标记数组
    for (int i = 0; i < G.vertexCount; i++) {
        visited[i] = false; // 初始化所有顶点为未访问
    }
    for (int i = 0; i < G.vertexCount; i++) {
        if (!visited[i]) { // 如果顶点未被访问
            BFS(G, i, visited); // 从该顶点开始广度优先遍历
        }
    }
    free(visited); // 释放访问标记数组
}

::: tip
与深度优先遍历相比，广度优先遍历更适合用于寻找最短路径，因为它是按层次逐层推进的。

而时间复杂度上，广度优先与深度优先相同。
当使用邻接矩阵来表示图，遍历每一个图中的顶点都要从头扫过邻接矩阵的每一行，时间复杂度为**O(V^2)，其中V是顶点数量。
当使用邻接表来表示图，遍历每一个图中的顶点只需要访问每一个点和与该顶点相连的边，时间复杂度为O(E+V)**，其中E是边的数量。

结论：**邻接表**更适合**稀疏图**的存储和遍历，**邻接矩阵**更适合**密集图**的存储和遍历。
:::

图的应用

最小生成树

前文有提到过生成树，最小生成树是生成树的一种特殊情况，它是一个包含图中所有顶点的生成树，并且边的权值之和最小。

Kruskal算法：贪心算法的思想，适用于无向图。算法步骤如下：
1. 将图的所有边按权值从小到大排序。
2. 初始化一个空的生成树。
3. 从排序后的边中依次取出边，检查是否会形成环。
4. 如果不会形成环，则将该边加入生成树。
5. 重复步骤3和4，直到生成树包含所有顶点或边的数量达到顶点数量减1。

Prim算法：**从一个顶点开始**，逐步扩展生成树，适用于无向图。算法步骤如下：

从任意一个顶点开始，将其加入生成树。
找到与生成树中顶点相连的边中权值最小的边，将该边和对应的顶点加入生成树。

重复步骤2，直到生成树包含所有顶点。

void Kruskal(AdjMatrix G) {
    Edge *edges = (Edge *)malloc(G.edgeCount * sizeof(Edge)); // 存储图的所有边
    int edgeCount = 0; // 边的数量
    for (int i = 0; i < G.vertexCount; i++) {
        for (int j = i + 1; j < G.vertexCount; j++) {
            if (G.matrix[i][j] != Inf) { // 如果有边相连
                edges[edgeCount].start = i; // 起点
                edges[edgeCount].end = j; // 终点
                edges[edgeCount].weight = G.matrix[i][j]; // 权值
                edgeCount++;
            }
        }
    }
    // 按权值从小到大排序
    qsort(edges, edgeCount, sizeof(Edge), compareEdges);
    UnionFind uf; // 并查集，用于检测环
    InitUnionFind(&uf, G.vertexCount); // 初始化并查集
    Edge *mst = (Edge *)malloc((G.vertexCount - 1) * sizeof(Edge)); // 存储最小生成树的边
    int mstCount = 0; // 最小生成树的边数量
    for (int i = 0; i < edgeCount; i++) {
        int startRoot = Find(&uf, edges[i].start); // 起点的根
        int endRoot = Find(&uf, edges[i].end); // 终点的根
        if (startRoot != endRoot) { // 如果起点和终点不在同一个集合中
            mst[mstCount++] = edges[i]; // 将边加入最小生成树
            Union(&uf, startRoot, endRoot); // 合并集合
        }
    }
    // 输出最小生成树的边
    printf("最小生成树的边：\n");
    for (int i = 0; i < mstCount; i++) {
        printf("(%d, %d) 权值: %d\n", mst[i].start, mst[i].end, mst[i].weight);
    }
    free(edges); // 释放边数组
    free(mst); // 释放最小生成树的边数组
    FreeUnionFind(&uf); // 释放并查集
}

void Prim(AdjMatrix G, int start) {
    bool *inMST = (bool *)malloc(G.vertexCount * sizeof(bool)); // 标记顶点是否在最小生成树中
    int *minEdge = (int *)malloc(G.vertexCount * sizeof(int)); // 存储每个顶点到生成树的最小边权值
    int *parent = (int *)malloc(G.vertexCount * sizeof(int)); // 存储每个顶点的父节点
    for (int i = 0; i < G.vertexCount; i++) {
        inMST[i] = false; // 初始化所有顶点不在最小生成树中
        minEdge[i] = Inf; // 初始化最小边权值为无穷大
        parent[i] = -1; // 初始化父节点为-1
    }
    minEdge[start] = 0; // 起点到自身的边权值为0
    parent[start] = -1; // 起点没有父节点

    for (int i = 0; i < G.vertexCount - 1; i++) {
        int u = -1; // 当前选中的顶点
        for (int j = 0; j < G.vertexCount; j++) {
            if (!inMST[j] && (u == -1 || minEdge[j] < minEdge[u])) {
                u = j; // 找到未在最小生成树中的最小边权值顶点
            }
        }
        inMST[u] = true; // 将选中的顶点加入最小生成树
        for (int v = 0; v < G.vertexCount; v++) {
            if (G.matrix[u][v] != Inf && !inMST[v] && G.matrix[u][v] < minEdge[v]) {
                minEdge[v] = G.matrix[u][v]; // 更新顶点v到生成树的最小边权值
                parent[v] = u; // 更新顶点v的父节点为u
            }
        }
    }

    // 输出最小生成树的边
    printf("最小生成树的边：\n");
    for (int i = 0; i < G.vertexCount; i++) {
        if (parent[i] != -1) { // 如果顶点有父节点
            printf("(%d, %d) 权值: %d\n", parent[i], i, G.matrix[parent[i]][i]);
        }
    }
    free(inMST); // 释放标记数组
    free(minEdge); // 释放最小边权值数组
    free(parent); // 释放父节点数组
}

最短路径

最短路径是指在图中从一个顶点到另一个顶点的路径，使得路径上的边的权值之和最小。常见的最短路径算法有：

Dijkstra算法：适用于非负权值的图，从一个起点到所有其他顶点的最短路径。

算法步骤如下：

初始化一个距离数组，记录从起点到每个顶点的最短距离，起点到自身的距离为0，其他顶点的距离为无穷大。
使用一个优先队列（或最小堆）来存储未访问的顶点，初始时将起点加入队列。
从队列中取出距离最小的顶点，更新其邻接顶点的距离。
如果更新后的距离小于当前记录的距离，则更新距离数组，并将邻接顶点加入队列。

重复步骤3和4，直到队列为空或所有顶点都被访问。

void Dijkstra(AdjMatrix G, int start) {
    int *dist = (int *)malloc(G.vertexCount * sizeof(int)); // 存储最短距离
    bool *visited = (bool *)malloc(G.vertexCount * sizeof(bool)); // 标记顶点是否已访问
    for (int i = 0; i < G.vertexCount; i++) {
        dist[i] = Inf; // 初始化所有顶点的距离为无穷大
        visited[i] = false; // 初始化所有顶点未访问
    }
    dist[start] = 0; // 起点到自身的距离为0
    for (int i = 0; i < G.vertexCount - 1; i++) {
        int u = -1; // 当前选中的顶点
        for (int j = 0; j < G.vertexCount; j++) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                u = j; // 找到未访问的最小距离顶点
            }
        }
        visited[u] = true; // 将选中的顶点标记为已访问
        for (int v = 0; v < G.vertexCount; v++) {
            if (G.matrix[u][v] != Inf && !visited[v] && dist[u] + G.matrix[u][v] < dist[v]) {
                dist[v] = dist[u] + G.matrix[u][v]; // 更新顶点v的最短距离
            }
        }
    }
     // 输出最短路径
     printf("从顶点 %d 到其他顶点的最短路径：\n", start);
     for (int i = 0; i < G.vertexCount; i++) {
         if (dist[i] == Inf) {
             printf("顶点 %d 到顶点 %d 的最短路径不存在\n", start, i);
         } else {
             printf("顶点 %d 到顶点 %d 的最短路径长度为 %d\n", start, i, dist[i]);
           } 
         }
     free(dist); // 释放最短距离数组
     free(visited); // 释放访问标记数组
 }

Floyd算法：适用于有负权的图，可以找到任意两个顶点之间的最短路径。
- 算法步骤如下：
  1. 初始化一个距离矩阵，记录从每个顶点到其他顶点的距离，初始时为邻接矩阵的值。
  2. 对于每一对顶点(i, j)，检查是否存在一个中间顶点k，使得从i到j经过k的距离小于直接从i到j的距离。
  3. 如果存在这样的k，则更新距离矩阵中的值。
  4. 重复步骤2和3，直到所有顶点都被考虑过。
（代码略）

拓扑排序

在项目管理中，我们可能使用有向图来描述一个工程的进行过程。只有完成了一个工程的所有子工程，才能完成一整个工程。

AOV网：用顶点表示活动的网络
AOE网：用边来表示活动的网络
具体的内容可以参考项目管理中网络计划的相关内容，在此不做赘述。

一个典型用途是大学教学计划排课：大学生需要完成本专业的教学计划的专业必修课才能毕业，不同的专业课之间可能存在依赖关系（如数据结构需要学生首先修完C语言程序设计），所以如何在不同的学期合理排课可以使用有向图结合拓扑排序来实现。

拓扑排序的原理

验证图中是否存在回路，如果存在回路，则无法拓扑排序，报错；不存在回路，转入下一步。
遍历图，找到图中一个没有前驱的节点，将节点入队。并将该节点发出的边从图中删去。
重复第2步直到所有节点入队。
队列依次出队，则为排序结果。

拓扑排序的结果是不一定的，具体结果会因为遍历图寻找无前驱顶点的实现方法不同而不同。

🍵 9. 查找

从这一节开始，我们暂时结束数据结构的逻辑结构和物理结构，来研究数据运算部分。

📘 定义

查找是指根据给定的某个值，在查找表中确定其关键字等于给定值的记录或数据元素。

若表中存在该记录，则查找成功，给出该记录的信息。
若表中不存在这样的记录，则查找不成功，给出空返回。

查找的分类

静态查找表：仅作查询操作的查询表。
动态查找表：允许作**插入**和**删除**的查询表。

查找算法的评价指标

在前文常用的时间复杂度和空间复杂度之外，我们对查找算法还有更加细致的评价指标——**评价查找长度**（ASL），这一指标在顺序表的部分有所涉及，其定义为每一个记录被查找的概率与该记录被查找需要的比较次数乘积的均值（即每次查找需要比较次数的期望值）。

顺序查找

按顺序比较查找

适用范围：静态查找表，表内元素之间无序。

int LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.length; i++) {        // for(int i = 0; L[i] != e; i++); return i;更简洁哈，但需要在表的L[0]位置放置e作为哨兵，不然在失败查询的时候会死循环。
        if (L[i] == e) {
            return i+1;
        }
    }
    return 0;
}

空间复杂度：需要一个哨兵位和一个i索引，O(1)
平均查找长度：
- 查找成功时：ASL = (n+1) / 2
- 查找失败时：ASL = n+1
总结：
- 优点：算法逻辑简单，适用于不同存储结构
- 缺点：ASL长，效率低
- 改进：在进行**非等概率**查找时可以按概率排序，从高概率位置查起。

折半查找

首先排序查找表，确保有序。
如果中间元素的元素比查找元素大，则取后半查找表中查找（降序为例子）
如果中间元素的元素比查找元素小，则取前半查找表中查找（降序为例子）

适用范围：静态查找表，顺序存储结构，元素之间有序。

int BiFind(SqList L, ElemType e, int low, int high) {
    if (low < high) return 0;
    
    int mid = (low + high) / 2;

    if (L[mid] = e) return mid;
    else if (L[mid] < e) {
        low = mid + 1;
        return BiFind(L, e, low, high);
    }
    else {
        high = mid - 1;
        return BiFind(L, e, low, high);
    }
}

空间复杂度：仅仅需要low high mid的存放，O(1).
平均查找长度
- 成功时：ASL = (n + 1) / n * log2(n + 1) - 1

分块查找

将查找表按**分块有序**排列，将各子表中的最大关键字构成一个索引表，表中还要包含子表的起始位置。首先在索引表上折半查找，找到与查找元素匹配的子表区域，然后进入子表顺序查找。

分块有序：要求每个子表中的数值都比后一块中数值小，但子表内部未必有序。

int BlockFind(SqList L, ElemType e, int blockSize) {
    int blockCount = (L.length + blockSize - 1) / blockSize; // 计算块数
    int *index = (int *)malloc(blockCount * sizeof(int)); // 创建索引表
    for (int i = 0; i < blockCount; i++) {
        index[i] = i * blockSize; // 每个块的起始位置
    }

    // 在索引表上折半查找
    int low = 0, high = blockCount - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (L[index[mid]] == e) {
            free(index);
            return index[mid]; // 找到匹配的块
        } else if (L[index[mid]] < e) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    // 如果没有找到匹配的块，返回0
    free(index);
    return 0;
}

int BlockSequentialFind(SqList L, ElemType e, int blockSize) {
    int blockCount = (L.length + blockSize - 1) / blockSize; // 计算块数
    for (int i = 0; i < blockCount; i++) {
        int start = i * blockSize; // 块的起始位置
        int end = (i + 1) * blockSize < L.length ? (i + 1) * blockSize : L.length; // 块的结束位置
        for (int j = start; j < end; j++) {
            if (L[j] == e) {
                return j + 1; // 找到元素，返回位置（从1开始）
            }
        }
    }
    return 0; // 没有找到元素，返回0
}

空间复杂度：需要一个索引表，O(n/blockSize)，其中n为查找表的长度。
平均查找长度：
- 成功时：ASL = (n + 1) / n * log2(n/blockSize + 1) - 1 + (blockSize + 1)
总结：
- 优点：适用于大规模数据的查找，查找效率高。
- 缺点：需要额外的空间存储索引表，且索引表的维护成本较高。
- 改进：可以使用哈希表来存储索引，提高查找效率。

二叉排序树

动态查找：表结构在查找过程中动态生成，给定key，如果查到key，则返回相关信息，否则插入key值。
二叉排序树具有如下特征：

若左子树非空，则左子树上所有的节点关键字小于根节点的关键字
若右子树非空，则右子树上所有的节点关键字大于根节点的关键字
左右子树自身也是一个二叉排序树

根据以上特征，如果对于二叉排序树进行中序遍历，则可以得到有序排列。

二叉排序树的操作

创建
1. 将第一个节点当作根节点
2. 后续的每一个节点跟根节点比较，若大则进入右子树，小的进入左子树
3. 和子树的根节点继续比较
4. 反复2,3直到所有节点进入树

查找

bool search(Node *root, int key) {
    while (root!=NULL) {
        if (root->data == key) {
            return true;
        }
        else if (root->data > key) {
            root = root->left;
        }
        else {
            root = root->right;
        }
    }
    return false;
}

删除
被删除的结点：

为叶子节点：从二叉表中删除即可，无影响。
被删除的节点只有一个孩子：子承父业，只需要删除节点的孩子连接到要删除节点的父亲节点上，然后删除该节点即可。
被删除的节点有两个孩子：使用右孩子顶替该节点or使用该节点左儿子的最右叶子节点顶替（即中序遍历时删除节点左右相邻的两个节点），以此保证中序遍历时仍不改变其升序排列的方式。
平均查找长度：
- 最好：ASL = log2n
- 最坏：ASL = n+1/2 (二叉树变成一条链，变成顺序查找)

二叉排序树的改进：平衡二叉树（AVL）

任意节点的子树的高度差都小于等于1的二叉排序树（为了防止出现上述最坏情况而诞生）

平衡因子BF：左子树和右子树的高度差。
当BF绝对值大于1时，平衡二叉树失衡，需要**旋转纠正**
最小不平衡子树时距离插入节点最近的，并且BF绝对值大于一的节点为根节点的子树，旋转纠正只需要纠正最小不平衡子树。

步骤：

不管什么结构，首先从叶子节点向上查找第一个失衡点，标为1；
选择1下面的点为2；
选择2下面的点为3；
123中大小为中间的做根，大的作为右孩子，小的作为左孩子
补全分支关系即可。

🃏 10. 排序

📘 定义

排序，就是整理表中的元素，使之按照关键字**递增或递减次序排列**。
排序的一个目的是便于查找（前文提到过的折半查找就需要查找表有序排列）

提示

如果待排序的表中有多个相同关键字元素，经过排序之后如果这些元素的相对次序保持不变，则称排序方法**稳定**，若不能保证则为**不稳定**。

排序的分类

内部排序
- 插入类排序：直接插入排序，折半排序，希尔排序
- 交换类排序：冒泡排序，快速排序
- 选择类排序：简单选择排序，堆排序
- 其他类排序：归并排序，*基数排序*
外部排序（由于被排序的表可能不在一个磁盘上而需要的特殊排序）

插入类排序

直接插入排序

每步将一个待排序对向按照关键码大小插入到前面已经排好的一组对象中，直到全部插入为止。

void InsertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i]; // 待插入的元素
        int j = i - 1;
        // 将大于key的元素向后移动一位
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key; // 插入key到正确位置
    }
}

性能分析：

平均时间复杂度：O(n^2)
最好情况：O(n)（当待排序表已经有序时）
最坏情况：O(n^2)（当待排序表是逆序时）
空间复杂度：O(1)（只需要常数级的额外空间）

折半排序

折半排序是直接插入排序的一种改进方法，通过二分查找来找到待插入元素的正确位置，从而减少比较次数。

int BinarySearch(int arr[], int key, int low, int high) {
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] < key) {
            low = mid + 1; // 在右半部分继续查找
        } else {
            high = mid - 1; // 在左半部分继续查找
        }
    }
    return low; // 返回插入位置
}

void BinaryInsertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i]; // 待插入的元素
        int j = i - 1;
        // 使用二分查找找到插入位置
        int pos = BinarySearch(arr, key, 0, j);
        // 将大于key的元素向后移动一位
        while (j >= pos) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[pos] = key; // 插入key到正确位置
    }
}

性能分析：

平均时间复杂度：O(n^2)
最好情况：O(n log n)（当待排序表已经有序时）
最坏情况：O(n^2)（当待排序表是逆序时）
空间复杂度：O(1)（只需要常数级的额外空间）

希尔排序

希尔排序是插入排序的一种改进方法，通过将待排序表分成若干个子表，对每个子表进行直接插入排序，从而减少比较次数。

void ShellSort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) { // 设置增量
        for (int i = gap; i < n; i++) {
            int key = arr[i]; // 待插入的元素
            int j = i;
            // 将大于key的元素向后移动一位
            while (j >= gap && arr[j - gap] > key) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = key; // 插入key到正确位置
        }
    }
}

性能分析：

平均时间复杂度：O(n^1.3)（具体取决于增量序列的选择）
最好情况：O(n log n)（当待排序表已经有序时）
最坏情况：O(n^2)（当待排序表是逆序时）
空间复杂度：O(1)（只需要常数级的额外空间）

交换类排序

冒泡排序

如果左边的数大于右边的数，进行交换，每趟结束的时候将一个最大值挤到最右的位置，一旦有一趟没有交换，可以提前结束。

bool flag = false;
for (int i = 0; i < arr.length-1; i++) {
    for (j = i; j< arr.length -1 -i; j++) {
        if (arr[i] > arr[j]) {
            flag = true;
            int temp = arr[i];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
        }
    }
    if (!flag) {
        break;
    } else {
        flag = false;
    }
}

性能分析：

时间复杂度O(n^2)
空间复杂度O(1)

快速排序

从待排序列中任取一个元素作为中点，所有比他小的数放在他左边，所有比他大的数放在右边，形成两个子表，在两个子表中分别重复，直到每个子表中只剩下一个元素。

void QuickSort (SqList &L, int low, int high) {
    if (high <= low) return;

    int p = L[low];
    
    int l = low, h = high;
    while (low < high) {
        while(low<high && L[high] >= p) --high;
        L[low] = L[high];
        while(low<high && L[low] <= p) ++low;
        L[high] = L[low];
    }
    L[low] = p;
    
    QuickSort(L, l, low -1);
    QuickSort(L, low+1, h);
}

性能分析：

时间复杂度O(nlog2n)
空间复杂度O(logn)

选择类排序

简单选择排序

每次从待排序列选出一个最小值放在开头，直到全部排完

void SelectSort(int arr) {
    for (int i=1; i<arr.length; i++) {
        int k = i;
        for (int j = i+1; j< arr.length; j++) {
            if (arr[i] > arr[j]) k = j;
        }
        if (k != i) swap(arr[i],arr[j]);
    }
}

性能分析：

时间复杂度O(n^2)
空间复杂度O(1)

堆排序

每个节点的值都大于或等于左右孩子的值，称为大根堆；反之为小根堆。（左右孩子之间无明确大小关系）

将无序序列建成堆，输出堆顶元素（最大值或最小值），然后将堆顶元素与堆的最后一个元素交换位置，减少堆的大小，然后重新调整堆，使其满足堆的性质。重复此过程直到堆的大小为1。

void Heapify(int arr[], int n, int i) {
    int largest = i; // 初始化最大值为根节点
    int left = 2 * i + 1; // 左子节点
    int right = 2 * i + 2; // 右子节点
    // 如果左子节点大于根节点
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    // 如果右子节点大于当前最大值
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    // 如果最大值不是根节点
    if (largest != i) {
        swap(arr[i], arr[largest]); // 交换根节点和最大值
        // 递归调整子树
        Heapify(arr, n, largest);
    }
}
void HeapSort(int arr[], int n) {
    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        Heapify(arr, n, i);
    }
    // 逐个提取最大值
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]); // 将最大值放到数组末尾
        Heapify(arr, i, 0); // 调整堆
    }
}

适用于n较大的情况

性能分析：

时间复杂度O(nlong2n)
空间复杂度O(1)

归并类排序

将两个或两个以上的有序表合并成一个新的有序表。
首先将原数组分成两个子数组，再将两个有序数组合并成一个更大的有序数组。
递归以上步骤直到只剩下一个子表，就是排好序的最终数组。

二路归并排序

void Merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1; // 左子数组的大小
    int n2 = right - mid; // 右子数组的大小
    int *L = (int *)malloc(n1 * sizeof(int)); // 创建左子数组
    int *R = (int *)malloc(n2 * sizeof(int)); // 创建右子数组

    // 将数据复制到临时数组中
    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }

    // 合并临时数组
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
    // 将剩余元素复制回原数组
    while (i < n1) {
        arr[k++] = L[i++];
    }
    while (j < n2) {
        arr[k++] = R[j++];
    }

    free(L); // 释放临时数组
    free(R);
}

void MergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2; // 找到中间点
        MergeSort(arr, left, mid); // 对左半部分进行归并排序
        MergeSort(arr, mid + 1, right); // 对右半部分进行归并排序
        Merge(arr, left, mid, right); // 合并两个有序数组
    }
}