数据结构

• 1: 绪论
• 1.1: 数据结构基本概念
• 1.2: 算法基本概念
• 2: 线性表
• 2.1: 定义和基本操作
• 2.2: 顺序表示
• 2.3: 链式表示
• 3: 线性数据结构
• 3.1: 栈
• 3.2: 队列
• 3.3: 栈和队列的应用
• 3.4: 数组和特殊矩阵
• 4: 字符串
• 4.1: 定义和实现
• 4.2: 模式匹配
• 5: 树与二叉树
• 5.1: 树
• 5.2: 二叉树
• 5.3: 树的应用
• 6: 图
• 6.1: 定义和操作
• 6.2: 算法和应用
• 7: 查找
• 7.1: 数组查找
• 7.2: 树形查找
• 7.3: 散列表查找
• 8: 排序
• 8.1: 内部排序
• 8.2: 外部排序

1 - 绪论

1.1 - 数据结构基本概念

什么是数据结构

数据结构是数据对象的集合，以及数据对象之间的关系和在数据上的操作。

分类

1. 线性结构：
   • 数组：具有固定大小的数据元素的集合，这些元素在存储中是连续的，并可以通过索引访问。
   • 链表：由节点组成，每个节点包含数据部分和指向下一个节点的指针。
   • 栈：后进先出 (LIFO) 的数据结构，只允许在顶部添加或删除元素。
   • 队列：先进先出 (FIFO) 的数据结构，允许在一端添加元素，并在另一端删除元素。
2. 非线性结构
   • 树：由节点组成的分层结构，其中有一个根节点，其他节点分为多个子树。
     • 二叉树：每个节点最多有两个子节点。
     • 平衡树、搜索树、红黑树 等是树的特殊类型。
   • 图：由节点（或称为顶点）和边组成的结构。
3. 散列结构：使用哈希函数将键转换为数组的索引，以便能够在常数时间内找到相关的值。

数据结构和算法

有效的算法通常依赖于选择合适的数据结构，而数据结构的实现和操作往往需要算法。

数据结构的选择直接影响到算法的性能。例如，数据的搜索在哈希表中可能是 O(1) 的复杂度，而在数组或链表中可能是 O(n) 的复杂度。

1.2 - 算法基本概念

什么是算法

算法 (Algorithm) 是一个明确规定了操作步骤的有限指令集，用于计算函数、处理数据、解决一个特定问题或执行某个任务。

算法的基本属性：

1. 明确性：每一步骤必须有明确且不含糊的定义。
2. 有输入和输出：算法应有0个或更多的输入和1个或更多的输出。输入是在算法开始之前提供的，而输出是在算法结束时产生的。
3. 有限性：如果算法在执行完有限步骤后终止，那么它就是有限的。换句话说，一个算法必须总是在执行有限次操作后结束。
4. 可行性：算法中的每一步都应该是简单且基本的，这样它们可以在有限的时间内完成并由计算机执行。
5. 独立性：算法的指令应该有普适性，也就是说，它们不应依赖于任何特定的编程语言或模型。相反，算法应该足够通用，可以在任何编程环境中实现。

效率度量

时间复杂度

时间复杂度（Time Complexity）描述的是执行某个算法所需要的时间如何随着输入数据量的增长而变化。这是一个估计，通常只考虑最高阶的项，并忽略常数因子。常见的时间复杂度（按增长速度排序）有：

• $O(1)$：常数时间。无论输入数据有多大，算法都在恒定的时间内完成。
• $O(\log n)$：对数时间。例如：二分搜索。
• $O(n)$：线性时间。例如：简单的搜索算法。
• $O(n \log n)$：线性对数时间。例如：高效的排序算法，如归并排序。
• $O(n^2)$、$O(n^3)$ …：多项式时间。例如：冒泡排序、插入排序和选择排序是 (O(n^2)$。
• $O(2^n)$：指数时间。例如：计算斐波那契数列的递归实现。
• $O(n!)$：阶乘时间。例如：旅行商问题的暴力解决方法。

空间复杂度

空间复杂度（Space Complexity）描述的是执行某个算法所需要的存储空间如何随着输入数据量的增长而变化。与时间复杂度类似，我们只关心增长的速度，并通常只考虑最高阶的项。

例如：

• $O(1)$：算法使用恒定的额外空间。
• $O(n)$：算法的存储需求与输入数据的大小成线性关系。

2 - 线性表

学习思维导图：

# 线性表

## 线性表的基本概念

## 线性表的实现

- 顺序存储
- 链式存储

## 线性表的应用

2.1 - 定义和基本操作

线性表定义

线性表是L数据结构中的一种基本结构。它是零个或多个数据元素的有限序列。通常，线性表中的数据元素之间是有序的，它们之间存在着前驱和后继的关系。

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

特点：

• 个数有限
• 表中元素数据类型都相同，每个元素占有相同大小的存储空间
• 仅讨论元素间的逻辑关系，表中元素有先后顺序

操作

• 初始化 (InitList): 创建一个空的线性表。
• 插入 (Insert): 在线性表的指定位置插入一个新的元素。
• 删除 (Delete): 删除线性表中的指定位置的元素。
• 查找 (LocateElem): 根据给定的条件查找线性表中的元素。
• 获取元素 (GetElem): 获取线性表中指定位置的元素。
• 设置元素 (SetElem): 修改线性表中指定位置的元素的值。
• 长度 (Length): 返回线性表中的元素数量。
• 判空 (IsEmpty): 判断线性表是否为空。
• 清空 (ClearList): 清除线性表中的所有元素。
• 遍历 (Traverse): 对线性表中的每个元素执行某种操作。

2.2 - 顺序表示

顺序表定义

顺序表（Sequential List） 是一种常见的数据结构，用于存储一组元素，并按照它们在内存中的物理顺序来排列和访问这些元素。顺序表通常由一个数组或列表构成，其中每个元素都占据一个连续的内存位置，并且可以通过索引值来访问。

假设线性表 A 存储的其实位置为LOC(A)，每个元素占用的存储空间的大小为sizeof(Elem)，则 A 所对应的顺序存储结构为：

• 顺序表 优点：
  • 随机访问性强：顺序表支持通过索引直接访问元素，访问速度快，时间复杂度为O(1)。
  • 空间使用连续：顺序表中的元素存储在连续的内存块中，这有助于提高缓存的局部性，从而提高访问速度。
  • 操作简单：无需处理复杂的指针操作。
• 顺序表 缺点：
  • 固定大小或调整大小的开销：对于静态数组，大小是固定的，如果预分配的空间不足或过大，会导致内存浪费或数组溢出。动态数组可以重新分配大小，但这会增加时间和空间开销。
  • 插入和删除的时间开销：如果要在顺序表的中间插入或删除元素，可能需要移动大量的元素，时间复杂度为O(n)。

操作

• 定义
• 插入
• 删除
• 查找操作
• 获取元素
• 判空
• 清空
• 长度

#define MAXSIZE 100
typedef struct {
    ElementType data[MAXSIZE];
    int length;
} SeqList;

void InitList(SeqList *L) {
    L->length = 0;
}

bool Insert(SeqList *L, int pos, ElementType e) {
    if (L->length == MAXSIZE || pos < 1 || pos > L->length + 1) {
        return false;
    }
    for (int i = L->length; i >= pos; i--) {
        L->data[i] = L->data[i - 1];
    }
    L->data[pos - 1] = e;
    L->length++;
    return true;
}

bool Delete(SeqList *L, int pos, ElementType *e) {
    if (pos < 1 || pos > L->length) {
        return false;
    }
    *e = L->data[pos - 1];
    for (int i = pos; i < L->length; i++) {
        L->data[i - 1] = L->data[i];
    }
    L->length--;
    return true;
}

int LocateElem(SeqList L, ElementType e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i + 1;  // 返回元素位置，而不是下标
        }
    }
    return 0;  // 未找到返回0
}

bool GetElem(SeqList L, int pos, ElementType *e) {
    if (pos < 1 || pos > L.length) {
        return false;
    }
    *e = L.data[pos - 1];
    return true;
}

bool IsEmpty(SeqList L) {
    return L.length == 0;
}

void ClearList(SeqList *L) {
    L->length = 0;
}

int Length(SeqList L) {
    return L.length;
}

2.3 - 链式表示

单链表定义

线性表的链式表示通常指的是使用链表来实现线性表。链表是由一系列节点组成的，每个节点都包含一个数据元素和一个指向下一个节点的指针。这种结构允许我们动态地插入和删除元素，而不需要移动其他元素。

• 单链表的优点：
  • 动态分配存储空间：链表的节点是在需要时动态分配的，因此在使用过程中不需要提前分配固定大小的存储空间。这使得内存利用率更加高效，可以减少内存浪费。
  • 插入和删除方便：只要知道了某个节点的位置，就可以在O(1)的时间复杂度内插入或删除该节点。而顺序表可能需要移动大量的元素。
  • 无需预估数据大小：链表可以灵活地增长，而顺序表需要预先定义一个固定大小，或者使用动态数组实现，但重新分配和拷贝的开销可能会很大。
• 单链表的缺点：
  • 空间开销较大：除了数据元素的存储外，每个节点还需要额外的空间存储一个指针，这增加了链表的存储开销。
  • 随机访问较慢：链表不支持直接通过索引进行随机访问，必须从头部开始逐个遍历节点，直到找到所需的节点，所以访问链表中的元素需要O(n)的时间复杂度。
  • 复杂的操作：链表需要处理更多的指针操作，容易出错。

为了方便链表的操作，常常在单链表中常常引入头结点，头结点中的指针为头指针，指向链表中的第一个结点，如果头指针指向NULL的话，则表示链表为空。

操作

• 定义
• 插入
• 删除
• 查找
• 获取元素
• 判空
• 清空

// 链表定义
typedef struct Node {
    ElementType data;
    struct Node *next;
} Node;

typedef Node *LinkList;

// 初始化
LinkList InitList() {
    LinkList L = (Node *)malloc(sizeof(Node));  // 创建头结点
    if (L == NULL) exit(1);  // 内存分配失败
    L->next = NULL;  // 初始为空链表
    return L;
}

bool Insert(LinkList L, int pos, ElementType e) {
    Node *p = L;
    int i = 0;
    while (p && i < pos - 1) {  // 找到第pos-1个节点
        p = p->next;
        i++;
    }
    if (!p || i > pos - 1) return false;

    Node *s = (Node *)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

bool Delete(LinkList L, int pos, ElementType *e) {
    Node *p = L;
    int i = 0;
    while (p->next && i < pos - 1) {  // 找到第pos-1个节点
        p = p->next;
        i++;
    }
    if (!(p->next) || i > pos - 1) return false;

    Node *q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);
    return true;
}

int LocateElem(LinkList L, ElementType e) {
    Node *p = L->next;
    int i = 1;
    while (p) {
        if (p->data == e) return i;
        p = p->next;
        i++;
    }
    return 0;  // 未找到返回0
}

bool GetElem(LinkList L, int pos, ElementType *e) {
    Node *p = L->next;
    int i = 1;
    while (p && i < pos) {
        p = p->next;
        i++;
    }
    if (!p || i > pos) return false;

    *e = p->data;
    return true;
}

bool IsEmpty(LinkList L) {
    return L->next == NULL;
}

void ClearList(LinkList L) {
    Node *p = L->next, *q;
    L->next = NULL;
    while (p) {
        q = p->next;
        free(p);
        p = q;
    }
}

3 - 线性数据结构

学习思维导图：

# 栈、队列和数组

## 栈和队列基本概念

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

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

## 多维数组的存储

## 特殊矩阵的压缩矩阵

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

3.1 - 栈

定义

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

基本操作

• 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;
}

3.2 - 队列

定义

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

基本操作

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

实现

顺序队列

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

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

循环队列

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

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

• 当 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.3 - 栈和队列的应用

表达式种类

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

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

中序表达式求值

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

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

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

后序表达式求值

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

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

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

3.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}$，

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

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

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

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

元素为

三角矩阵

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

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

以上三角矩阵$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)$$

元素为

三对角矩阵

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

稀疏矩阵

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

矩阵

4 - 字符串

4.1 - 定义和实现

串的定义

字符串是计算机科学中的一个基本概念，通常被定义为有限序列中字符的有序集合。

形式定义：

字符串 $S$ 时字符集 $\Sigma$ 上的一个有限序列：$S = a_1 a_2 \cdots a_n$，其中 $a_i \in \Sigma$，且 $n$ 为字符串的长度， 当 $n = 0$ 时，称为空字符串。

串的存储结构

1. 定长顺序存储表示

在定长顺序存储表示中，每个字符串都有固定的长度，通常用一个预定义的最大大小来表示。这种表示方法使用一个一维数组，数组的大小等于预定的最大长度。

在某些语境中（例如C语言），使用特殊字符（如 '\0'）来标识字符串结束。

#define MAX_SIZE 100 // 预定义的最大大小

typedef struct {
    char data[MAX_SIZE];  // 字符数组
    int length;           // 当前字符串的长度
} FixedString;

2. 堆分配存储表示

在堆分配存储表示中，每个字符串具有其自己的长度，因此可以动态地分配存储空间。字符串在堆中分配空间，只需要那么多的空间来存储实际的字符以及结束字符或长度信息。

typedef struct {
    char *data;           // 指向动态分配空间的指针
    int length;           // 字符串的长度
} HeapString;

// 创建一个新的字符串
void initHeapString(HeapString *s, const char *str) {
    s->length = strlen(str);
    s->data = (char *)malloc((s->length + 1) * sizeof(char));
    if (s->data == NULL) {
        exit(1);  // 分配失败
    }
    strcpy(s->data, str);
}

// 释放字符串
void freeHeapString(HeapString *s) {
    free(s->data);
    s->length = 0;
}

3. 块链存储表示

块链存储表示是结合了链表与块存储的思想。串分为较小的块，每个块存储一部分字符。块之间使用指针链接。这样，整个字符串就变成了一个字符块的链表。

#define BLOCK_SIZE 4 // 为了简单起见，设块大小为4

typedef struct StringBlock {
    char data[BLOCK_SIZE];   // 块中的字符数据
    struct StringBlock *next;  // 指向下一个块的指针
} StringBlock;

typedef struct {
    StringBlock *head;      // 指向第一个块的指针
    int length;             // 字符串的总长度
} BlockString;

// 初始化块链字符串
void initBlockString(BlockString *s) {
    s->head = NULL;
    s->length = 0;
}

// 为了简化，这里只展示了数据结构定义和初始化函数。实际应用中还需要考虑其他函数，如插入、删除、销毁等。

串的基本操作

• 赋值（Assign）：
  • 将一个串的内容复制到另一个串。
• 比较（Compare）：
  • 根据字符的字典顺序比较两个串。可以判断两个串是否相等，或者一个串是否小于或大于另一个串。
• 长度（Length）：
  • 返回串的长度，即串中字符的数目。
• 连接（Concat）：
  • 将两个串连接成一个新的串。例如，将串"Hello"和串"World"连接为"HelloWorld"。
• 子串提取（Substr）：
  • 从串中提取某个指定位置开始的指定长度的字符序列作为一个新的串。例如，从串"HelloWorld"中提取从位置1开始的5个字符，得到"Hello"。
• 插入（Insert）：
  • 在串的指定位置插入另一个串。例如，在串"HelloWorld"的第6个位置插入串"Beautiful", 得到"HelloBeautifulWorld"。
• 删除（Delete）：
  • 从串中删除从指定位置开始的指定长度的字符。
• 替换（Subsititude）：
  • 将串中某个子串的所有出现替换为另一个子串。例如，将串"apple, banana, apple"中的"apple"替换为"orange"，得到"orange, banana, orange"。
• 模式匹配（Index）：
  • 在串中查找另一个子串的位置。这通常使用算法如KMP、BM或Sunday来加速查找。
• 清空（Clear）：
  • 释放串的存储空间并将其设置为空串。

4.2 - 模式匹配

字符串模式匹配是计算机科学中的基础问题，主要是在一个主字符串中查找一个子字符串模式。

简单模式匹配算法

简单模式匹配算法通常指的是暴力方法（或称为朴素算法），其基本思想是逐个检查主字符串的每一个位置是否开始与子字符串匹配。

算法描述：

1. 从主字符串的第一个字符开始匹配。
2. 如果第一个字符匹配，那么匹配下一个字符，依此类推。
3. 如果在任何时刻字符不匹配，重新从主字符串的下一个字符开始匹配。
4. 如果子字符串完全匹配，返回主字符串中的开始位置。
5. 如果到达主字符串的末尾都没有完全匹配的子字符串，则返回-1。

int simplePatternMatching(const char* mainStr, const char* pattern) {
    int m = strlen(mainStr);
    int n = strlen(pattern);

    // 如果主字符串的长度小于模式字符串的长度，直接返回-1
    if (m < n) return -1;

    for (int i = 0; i <= m - n; i++) {
        int j;
        for (j = 0; j < n; j++) {
            if (mainStr[i + j] != pattern[j]) {
                break;
            }
        }
        // 如果j等于模式串的长度，说明已经找到匹配
        if (j == n) return i;
    }
    return -1;  // 没有找到匹配
}

这个简单模式匹配算法的时间复杂度是 $O(mn)$ ，其中 $m$ 是主字符串的长度， $n$ 是模式字符串的长度。

KMP算法

与简单模式匹配算法不同，KMP算法在发现不匹配的字符时能够避免不必要的比较，从而提高效率。

基本原理：

简单模式匹配时间复杂度过高，因为每一次匹配失败都得从下一个位置重新开始。这就没有充分应用模式串的特性，比如对于字符串 abcdabc，我们可以发现：

• 其前缀包含a, ab, abc, abcd等
• 起后缀包含c, bc, abc, dabc等

abc是在其前缀和后缀中都包含的部分，在字符串匹配时，我们可以充分利用该信息，匹配失败时，我们可以不用从下一个位置开始，而是从模式串内部的某个位置开始。

KMP算法就是基于这个思想，其核心是一个称为“部分匹配表”或“前缀函数”的辅助数组（通常称为next数组），该数组用于确定当模式串与主串不匹配时应该如何有效地移动模式串。

算法描述：

• 根据模式串计算next数组。
• 使用next数组，对主串和模式串进行比较。
• 在发现不匹配的情况下，利用next数组调整模式串的位置。

next数组计算

next数组的计算方式如下：

如果模式串为pattern，用通俗的话来说，next[j]就是字串pattern[0:k]（pattern的前k个字符构成的子串）的最长相同前缀和后缀的长度。

根据next数组调整位置

用i表示主串当前下标，用j表示模式串当前下标：

• 如果main[i] == pattern[j]，将i和j向后向后移动一位。
• 如果main[i] != pattern[j]：
  • 如果j == 0，将i向后移动一位。
  • 如果j != 0，将j移动到next[j-1]。

以下图为例，说明主串 “ababcabcabababd” 和 模式串 “ababd” 的匹配过程。

void computeNextArray(const char* pattern, int m, int* next) {
    int len = 0;
    next[0] = 0;
    int i = 1;

    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            next[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = next[len - 1];
            } else {
                next[i] = 0;
                i++;
            }
        }
    }
}

int KMP(const char* mainStr, const char* pattern) {
    int m = strlen(mainStr);
    int n = strlen(pattern);

    int next[n];
    computeNextArray(pattern, n, next);

    int i = 0, j = 0;
    while (i < m) {
        if (pattern[j] == mainStr[i]) {
            i++;
            j++;
        }

        if (j == n) {
            return i - j;
        } else if (i < m && pattern[j] != mainStr[i]) {
            if (j != 0)
                j = next[j - 1];
            else
                i++;
        }
    }

    return -1; // 没有找到匹配
}

视频讲解

5 - 树与二叉树

学习思维导图

# 树和二叉树

## 树的基本概念

## 二叉树

- 定义和主要特性
- 顺序存储结构和链式存储结构
- 遍历
- 线索二叉树的基本概念和构造

## 树、森林

- 树的存储结构
- 森林和二叉树的转化
- 树和森林的遍历

## 树和二叉树的应用

- 哈夫曼树和哈夫曼编码
- 并查集及其应用

5.1 - 树

基本概念

1. 双亲、兄弟、孩子
2. 结点的度：结点的孩子数量
3. 树的度：等于树中所有结点度的最大值
4. 分支结点（非终端结点）：度大于0的结点
5. 叶子结点（终端结点）：度等于0的结点
6. 树的高度：树的结点有几层
7. 节点间路径长度：从一个结点到另一个结点需要经过的边的个数（用边连接两个结点）
8. 森林：m (m ≥ 0) 颗互不相交的数的集合

树的存储结构

1. 双亲表示法

双亲表示法主要是使用一个数组，其中每个结点都有一个指示其双亲结点在数组中位置的索引。

#define MAXSIZE 100
typedef struct {
    int data;         // 节点数据
    int parent;       // 双亲的位置
} PTNode;

typedef struct {
    PTNode nodes[MAXSIZE];  // 结点数组
    int n;                  // 结点数
} PTree;