My-Project

Appearance

02331 数据结构 ✒️ ​

概论 ​

什么是数据结构 ​

算法 + 数据结构 = 程序

  • 算法：对数据运算的描述
  • 数据结构：数据的逻辑结构和存储结构
  • 程序设计：针对实际问题选择一种好的数据结构和设计一个好的算法

基本概念和术语 ​

  • 数据（Data)
    • 信息的载体
    • 能输入到计算机中被计算机程序处理的符号集
  • 数据元素（Data Element)
    • 数据的基本单位
    • 在计算机程序中作为一个整体进行考虑和处理
    • 一个数据元素可以由若干数据项（Data Item）组成
    • 数据项是具有独立含义的最小标识单位
  • 数据对象（Data Object)
    • 性质相同的数据元素的集合
  • 数据结构（Data Structure)
    • 形式定义带有结构的数据元素的集合
    • 结构：数据元素之间的关系
    • 结构中的数据元素称为结点
结构说明
线性结构结点之间存在一对一的关系且结构中仅有一个开始结点和终端结点，其余的结点仅有一个直接前驱结点和一个直接后继结点
非线性结构结点之间存在一对多或多对多的关系，即一个结点可以有多个直接前驱结点和多个直接后继结点
顺序存储结构逻辑上相邻的结点存储在物理位置相邻的存储单元
链式存储结构用一组不一定连续的存储单元存储逻辑上相邻的元素
索引存储结构存储元素的同时，建立附加的索引表，索引的一般形式：（关键字，address）
散列（hash）存储结构根据元素的关键字，直接计算出该元素的存储address

数据的运算

  • 对数据元素施加的操作：插入，删除，更新，检索
  • 给定数据的逻辑结构和存储结构之后，定义不同的运算会导致完全不同的数据结构
不同的数据结构

抽象数据类型（ADT）：一个数学模型及定义在该模型上的一组操作

算法 & 算法分析 ​

算法：对特定问题的求解步骤的一种描述，指令的有限序列

特性说明
有穷性算法在执行有穷步后能结束
确定性每一指令有确切的含义，无二义
可行性每一操作都可以通过已经实现的基本运算执行有限次来实现
输入零个或多个输入
输出一个或多个输出

算法评价标准

判定点说明
正确性程序不含语法错误
对于几组输入数据能够得出满足要求的结果
对于精心挑选的典型、苛刻的几组输入数据
对于一切合法的输入数据
时间复杂性执行算法所耗费的时间
空间复杂性执行算法所耗费的存储空间
易于理解、易于编程、易于调试

时间复杂度 ​

  • 运行时间 = 算法中每条语句执行时间之和
  • 每条语句执行时间 = 频度 * 语句执行一次所需时间
  • 不同计算机系统执行一次基本操作的时间是千差万别的，不能用一个统一的标准来衡量
  • 渐进时间复杂度： T(n)=O(f(n))T(n) = O(f(n))

两重for循环嵌套，T(n)=O(n2)T(n) = O(n^2)

三重for循环嵌套，T(n)=O(n3)T(n) = O(n^3)

空间复杂度 ​

线性表 ​

线性表的定义和基本运算 ​

定义：n(≥0)n(\geq 0)个数据元素的有限序列，记作a1,...ai−1,ai+1...,an)a_1,...a_{i-1},a_{i+1}...,a_n)

其中，a是表中数据元素，n是表长度（n=0时称为空表）

  • initList() 初始化一个空表
  • ListLength() 返回线性表的长度
  • GetNode(L, i) 返回线性表第i个元素的值
  • LocateNode(L,x) 返回线性表中第一个值为x的元素的位置
  • InsertList(L,i,x) 在第i个位置插入元素x
  • DeleteList(L,i) 删除第i个位置的元素

例：已知AB是两个线性表，求AB的并集

C
void Union(Linear_List A, Linear_List B) {
    // 1. 遍历A表
    for (int i = 1; i <= ListLength(A); i++) {
        int n = ListLength(A);
        int x = GetNode(A, i);
        // 2. 判断B表是否包含x
        if (!LocateNode(B, x)) {
            // 3. 如果不包含，就插入A表（在A表的末尾插入）
            InsertList(A, n + 1, x);
        }
    }
}

例：删除线性表A中重复的元素

C
void DeleteRepeat(Linear_List A) {
    int i, j;
    while (i <= ListLength(A)) {
        int x = GetNode(A, i);
        j = i + 1;
        while (j <= ListLength(A)) {
            if (GetNode(A, j) == x) {
                DeleteList(A, j);
            } else {
                j++;
            }
        }
        i++;
    }
}

顺序存储和基本运算实现 ​

  • 定义：用一组address连续的存储单元依次存储线性表中的数据元素
  • 特点：逻辑上相邻，物理上也相邻
  • LOC(ai)=LOC(a1)+(i−1)∗lLOC(a_i) = LOC(a_1) + (i-1) * l
    • ll 是每个元素占用的存储单元数
    • LOC(ai)LOC(a_i) 是第i个元素的存储address
    • LOC(a1)LOC(a_1) 是第一个元素的存储address

顺序表的定义 ​

c
#define LIST_SIZE 100
typedef int DataType;

typedef struct {
    DataType data[LIST_SIZE];
    int length;
} SeqList;

插入元素 & 时间复杂度 ​

  • 最好情况（插入末尾）：O(1)O(1)
  • 最坏情况（插入开头）：O(n)O(n)
  • 平均情况：O(n)O(n)
c
void InsertList(SeqList *L, int i, DataType x) {
    int j;
    if (i < 1 || i > L->length + 1) {
        return;
    }
    if (L->length >= LIST_SIZE) {
        return;
    }
    // 1. 往后移动元素
    for (j = L->length - 1; j >= i - 1; j--) {
        L->data[j + 1] = L->data[j];
    }
    // 插入元素
    L->data[i - 1] = x;
    // 长度加1
    L->length++;
}

删除元素 & 时间复杂度 ​

  • 最好情况（删除末尾）：O(1)O(1)
  • 最坏情况（删除开头）：O(n)O(n)
  • 平均情况：O(n)O(n)
c
DataType DeleteList(SeqList *L, int i) {
    int j;
    DataType x;
    if (i < 1 || i > L->length) {
        return;
    }
    // 1. 往前移动元素
    x = L->data[i - 1];
    for (j = i; j < L->length - 1; j++) {
        L->data[j - 1] = L->data[j];
    }
    // 长度减1
    L->length--;
    return x;
}

线性表逆置 ​

c
SeqList Reverse(SeqList L) {
    DataType x;
    int k = L.length / 2;
    for (int i = 1; i < k; i++) {
        x = L.data[i];
        L.data[i] = L.data[L.length - i - 1];
        L.data[L.length - i - 1] = x;
    }
    return L;
}

链式存储结构 ​

  • 定义：结点中包括数据域和指针域
  • 特点：逻辑上相邻的元素，物理上未必相邻

链表的定义 ​

c
typedef struct Node {
    DataType data;
    struct Node *next;
} ListNode;

typedef ListNode *LinkList;
ListNode *p;   // 定义一个指向节点的指针变量
LinkList head; // 定义一个指向单链表的头指针

创建链表 ​

头插法 & 尾插法 & 带头结点的尾插法

c
LinkList CreateListF() {
    LinkList head = NULL;
    ListNode *p;
    char ch = getchar();
    while (ch != '\n') {
        p = (ListNode *)malloc(sizeof(ListNode)); // 申请新节点空间
        p->data = ch;                             // 数据域赋值
        p->next = head;                           // 指针域赋值
        head = p;                                 // 头指针指向新结点
        ch = getchar();                           // 读取下一个字符
    }
    return head; // 返回头指针
}
c
LinkList CreateListR() {
    LinkList head = NULL, near = NULL;
    ListNode *p;
    char ch = getchar();
    while (ch != '\n') {
        p = (ListNode *)malloc(sizeof(ListNode)); // 申请新节点空间
        p->data = ch;                             // 数据域赋值
        if (head == NULL) {
            head = p;
        } else {
            near->next = p;
        }
        near = p;
        ch = getchar(); // 读取下一个字符
        if (near != NULL) {
            near->next = NULL; // 终结点指向NULL
        }
    }
    return head; // 返回头指针
}
c
LinkList CreateListR1() {
    LinkList head = (ListNode *)malloc(sizeof(ListNode));
    ListNode *p, *r;
    r = head;
    char ch = getchar();
    while (ch != '\n') {
        p = (ListNode *)malloc(sizeof(ListNode)); // 申请新节点空间
        p->data = ch;                             // 数据域赋值
        r->next = p;
        r = p;
    }
    r->next = NULL;
    return head; // 返回头指针
}

链表查找 ​

c
ListNode *GetNode(LinkList head, int i) {
    ListNode *p = head->next;
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (j == i) {
        return p;
    }
    return NULL;
}
c
ListNode *LocateNode(LinkList head, DataType k) {
    ListNode *p = head->next;
    while (p && p->data != k) {
        p = p->next;
    }
    return p;
}

插入 & 删除运算 ​

c
void insertList(LinkList head, int i, DataType x) {
    ListNode *p, *s;
    int j = 0;
    p = head;
    // 找到这个p，也就是要插入的位置
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p) {
        s = (ListNode *)malloc(sizeof(ListNode));
        s->data = x;
        s->next = p->next;
        p->next = s;
    }
}
c
void deleteList(LinkList head, int i) {
    ListNode *p, *s;
    DataType x;
    int j = 0;
    p = head;
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }

    if (p) {
        s = p->next;
        p->next = s->next;
        x = s->data; // 保存被删除节点的数据
        free(s);     // 释放被删除节点的内存
        return x;    // 返回被删除节点的数据
    }
}

循环链表 ​

最后一个结点的指针域指向头结点，从表中的任意一个结点开始，都可以访问到表中的其他结点

从大到小顺序排列的头结点指针为L的非空单循环链表，插入一个结点（x）并保持有序

  • 第1个结点开始往后查找，找到第一个小于x的结点，用指针g指向该结点，并用指针p指向该结点的前驱结点
  • 在结点p和结点q之间插入结点x
c
void insertList(LinkList L, int x) {
    ListNode *s, *p, *q;
    s = (ListNode *)malloc(sizeof(ListNode));
    s->data = x;
    p = L;

    q = p->next; // p指向头结点，q指向第一个节点
    while (p->data > x && q != L) {
        p = p->next;
        q = p->next; // p q同时往后移动
    }
    p->next = s; // 插入s
    s->next = q;
}

双向链表 ​

可以直接找到一个结点的直接前驱和后继

顺序表和链表的比较 ​

顺序表链表
时间性能适合做查找运算适合做插入、删除运算
空间性能是静态分配的，容易造成空间浪费是动态分配的

堆栈 & 队列 ​

栈 ​

  • 定义：
    • 是限定仅在表尾进行插入或删除操作的线性表
    • 允许插入、删除的一端称为栈顶（top），另一端称为栈底
  • 逻辑特征：后进先出（LIFO）

栈的主要运算 ​

  • InitStack(&S)：初始化栈
  • StackEmpty(S)：判断栈是否为空
  • StackFull(S)：判断栈是否已满
  • Push(&S, x)：入栈
  • Pop(&S)：出栈
  • GetTop(S)：获取栈顶元素

顺序栈及其基本运算 ​

c
#define STACK_SIZE 100
typedef char DataType;
typedef struct {
    DataType data[STACK_SIZE];
    int top;
} SqStack;
c
void initStack(SqStack *s) {
    s->top = -1;
}
c
int stackEmpty(SqStack *s) {
    return s->top == -1;
}
c
int stackFull(SqStack *s) {
    return s->top == STACK_SIZE - 1;
}
c
void push(SqStack *s, DataType x) {
    if (stackFull(s)) {
        printf("栈已满！\n");
        return;
    }
    s->top++;
    s->data[s->top] = x;
}
c
void pop(SqStack *s) {
    if (stackEmpty(s)) {
        printf("栈已空！\n");
        return;
    }
    s->top--;
}
c
DataType getTop(SqStack *s) {
    if (stackEmpty(s)) {
        printf("栈已空！\n");
        return '\0';
    }
    return s->data[s->top];
}

链栈及其基本运算 ​

c
typedef struct stackNode {
    DataType data;
    struct stackNode *next;
} StackNode;

typedef StackNode *LinkStack;
LinkStack top;
c
int stackEmpty(LinkStack top) {
    return top == NULL;
}
c
LinkStack push(LinkStack top, DataType x) {
    StackNode *p = (StackNode *)malloc(sizeof(StackNode));
    p->data = x;
    p->next = top;
    top = p;
    return top;
}
c
LinkStack pop(LinkStack top, DataType *x) {
    StackNode *p = top;
    // 判断栈空
    *x = top->data;
    top = top->next;
    free(p);
    return top;
}

栈的应用举例 ​

定义栈结构及其公共方法
c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 100

// 栈的结构定义
typedef struct {
    char data[MAX_SIZE];
    int top;
} Stack;

// 初始化栈
void initStack(Stack *s) {
    s->top = -1;
}

// 判断栈是否为空
int isEmpty(Stack *s) {
    return s->top == -1;
}

// 入栈
int push(Stack *s, char c) {
    if (s->top >= MAX_SIZE - 1) {
        return 0; // 栈满
    }
    s->data[++(s->top)] = c;
    return 1;
}

// 出栈
char pop(Stack *s) {
    if (isEmpty(s)) {
        return '\0'; // 栈空
    }
    return s->data[(s->top)--];
}

数制转换 ​

  • 以十进制转二进制为例
  • 每次取余数入栈，出栈时顺序输出即为二进制数
c
// 数制转换函数：将十进制数转换为二进制
void convert(int decimal) {
    Stack s;
    initStack(&s);

    // 步骤1：不断除以 base，余数入栈
    while (decimal > 0) {
        push(&s, decimal % 2);
        decimal /= 2;
    }

    // 步骤2：依次出栈，得到逆序结果
    while (!isEmpty(&s)) {
        printf("%c", pop(&s));
    }
}

括号匹配 ​

  • 遍历字符串，遇到左括号入栈，遇到右括号出栈
  • 最后判断栈是否为空，为空则匹配成功，否则匹配失败
c
// 括号匹配函数（只处理 ()）
int isBalanced(char *str) {
    Stack s;
    initStack(&s);
    int len = strlen(str);

    for (int i = 0; i < len; i++) {
        char ch = str[i];

        if (ch == '(') {
            push(&s, ch);  // 左括号入栈
        }
        else if (ch == ')') {
            if (isEmpty(&s)) {
                return 0; // 没有左括号可以匹配
            }
            pop(&s); // 匹配一个左括号
        }
        // 其他字符（如字母、数字等）直接忽略
    }

    return isEmpty(&s); // 栈为空说明全部匹配
}

递归 ​

c
// 用栈模拟阶乘：n!
long factorial_with_stack(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }

    Stack s;
    initStack(&s);

    // ==================== 第一阶段：入栈（模拟递归“深入”）====================
    int temp = n;
    while (temp > 1) {
        push(&s, temp);
        temp--;
    }

    long result = 1;
    // ==================== 第二阶段：出栈（模拟递归“回溯”）====================
    while (!isEmpty(&s)) {
        int current = pop(&s);
        result *= current;
    }
    return result;
}

队列 ​

  • 定义：只允许在一端进行插入，而在另一端删除元素，允许插入的一端为队尾（rear），允许删除的一端为队头（front）
  • 逻辑特征：先进先出（FIFO)

队列的主要运算 ​

  • initQueue(Q)：初始化队列
  • queueEmpty(Q)：判断队列是否为空
  • queueFull(Q)：判断队列是否已满
  • enQueue(Q, x)：入队
  • deQueue(Q)：出队
  • getQueueHead(Q)：获取队头元素

顺序队列及其基本运算 ​

c
#define QUEUE_SIZE 100
typedef struct {
    DataType data[QUEUE_SIZE];
    int front;
    int rear;
} SeqQueue;
c
void enQueue(SeqQueue Q, DataType x) {
    Q.data[Q.rear] = x;
    Q.rear = Q.rear + 1;
}
c
DataType deQueue(SeqQueue Q) {
    DataType x = Q.data[Q.front];
    Q.front = Q.front + 1;
    return x;
}

顺序循环队列 ​

当Q.front或Q.rear指向数组上界（QueueSize-1）时，再加1则指向数组下界0

  • 出队：front += 1;
  • 入队：rear += 1;
c
#define QUEUE_SIZE 100
typedef struct {
    DataType data[QUEUE_SIZE];
    int front;
    int rear;
} CirQueue;

CirQueue Q;
c
void initQueue(CirQueue *Q) {
    Q->front = Q->rear = 0;
}
c
int queueEmpty(CirQueue Q) {
    return Q.front == Q.rear;
}
c
int queueFull(CirQueue *Q) {
    return Q->front == (Q->rear + 1) % QUEUE_SIZE;
}
c
void enQueue(CirQueue *Q, DataType x) {
    if (queueFull(Q)) {} // 省略
    Q->data[Q->rear] = x;
    Q->rear = (Q->rear + 1) % QUEUE_SIZE;
}
c
void deQueue(CirQueue *Q) {
    if (queueEmpty(Q)) { } // 省略
    int x = Q->data[Q->front];
    Q->front = (Q->front + 1) % QUEUE_SIZE;
}
c
DataType getQueueHead(CirQueue *Q) {
    if (queueEmpty(Q)) { } // 省略
    return Q->data[Q->front];
}

链队列及其基本运算 ​

c
typedef struct QueueNode {
    DataType data;
    struct QueueNode *next;
} QueueNode;

typedef struct {
    QueueNode *front;
    QueueNode *rear;
} LinkQueue;
c
void initQueue(LinkQueue *Q) {
    Q->front = (QueueNode *)malloc(sizeof(QueueNode));
    Q->rear = Q->front;
    Q->rear->next = NULL;
}
c
int queueEmpty(LinkQueue *Q) {
    return Q->front == Q->rear;
}
c
void enQueue(LinkQueue *Q, DataType x) {
    QueueNode *p = (QueueNode *)malloc(sizeof(QueueNode));

    p->data = x;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
}
c
void deQueue(LinkQueue *Q) {
    if (queueEmpty(Q)) { } // 省略
    QueueNode *p = Q->front->next;
    Q->front->next = p->next;
    free(p);
}
c
DataType getQueueHead(LinkQueue *Q) {
    if (queueEmpty(Q)) { } // 省略
    return Q->front->next->data;
}

栈和队列的应用实例 ​

表达式求值（波兰表达式） ​

使用栈实现表达式的计算前缀、中缀、后缀表达式（逆波兰表达式）

把(3+4)*5-6转成后缀表达式

步骤当前字符操作输出队列
从左到右		操作符栈
栈顶在右
1(左括号，压栈(
23操作数，加入输出3(
3+操作符，压栈（栈顶是(，直接压）3(+
44操作数，加入输出3 4(+
5)右括号，弹出直到 (3 4 +
6*操作符，压栈（栈空）3 4 +*
75操作数，加入输出3 4 + 5*
8-操作符，* 优先级 ≥ -，弹出 *；再压入 -3 4 + 5 *-
96操作数，加入输出3 4 + 5 * 6-
10（结束）栈中还有 -，弹出3 4 + 5 * 6 -
中缀表达式转后缀表达式
c
int precedence(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}

// 判断是否是操作符
int isOperator(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/');
}

// 中缀转后缀
void infixToPostfix(const char* infix) {
    int len = strlen(infix);
    char output[MAX * 2];  // 存储输出（带空格）
    int outIdx = 0;

    for (int i = 0; i < len; i++) {
        char c = infix[i];

        // 1. 如果是空格，跳过
        if (c == ' ') continue;

        // 2. 如果是数字或字母（操作数），直接加入输出
        if (isdigit(c) || isalpha(c)) {
            output[outIdx++] = c;

            // 如果下一个还是数字（比如10, 23），继续加
            while (i + 1 < len && isdigit(infix[i + 1])) {
                i++;
                output[outIdx++] = infix[i];
            }
            // 操作数后加空格，便于阅读
            output[outIdx++] = ' ';
        }

        // 3. 左括号：直接入栈
        else if (c == '(') {
            push(c);
        }

        // 4. 右括号：弹出直到遇到左括号
        else if (c == ')') {
            while (peek() != '(' && top != -1) {
                output[outIdx++] = pop();
                output[outIdx++] = ' ';
            }
            pop(); // 弹出 '('
        }

        // 5. 操作符 +, -, *, /
        else if (isOperator(c)) {
            // 弹出优先级 >= 当前操作符的
            while (top != -1 && peek() != '(' &&
                   precedence(peek()) >= precedence(c)) {
                output[outIdx++] = pop();
                output[outIdx++] = ' ';
            }
            push(c); // 当前操作符入栈
        }
    }

    // 6. 表达式结束，弹出所有剩余操作符
    while (top != -1) {
        output[outIdx++] = pop();
        output[outIdx++] = ' ';
    }

    // 去掉末尾多余的空格
    if (outIdx > 0 && output[outIdx - 1] == ' ') {
        outIdx--;
    }

    output[outIdx] = '\0'; // 字符串结束
    printf("后缀表达式: %s\n", output);
}

多维数组 & 广义表 ​

多维数组和运算 ​

二维数组顺序存储 ​

数组的顺序存储结构有两种：

  • 按行序存储，如高级语言BASIC、COBOL和PASCAL语言都是以行序为主
  • 按列序存储，如高级语言中的FORTRAN语言就是以列序为主

存储运算 ​

以二维数组AmnA_{mn}为例，假设每个元素只占一个存储单元，以行为主存放数组，下标从1开始， 首元素a00a_{00}的address为Loc[a00]Loc[a_{00}]，每个元素占d个存储单元，求任意元素a的address，可由如下计算公式得到：

Loc(aij)=Loc(a00)+(i∗n+j)∗dLoc(a_{ij})=Loc(a_{00})+(i*n+j) * d

同理，以三维数组AmnpA_{mnp}为例，假定每个元素占d个存储单元，采用以行为主序的方法存放 首元素a000a_{000}的address为Loc[a000]Loc[a_{000}]，任意元素aijka_{ijk}的address计算公式为：

Loc(aijk)=Loc(a000)+(i∗n∗p+j∗p+k)∗dLoc(a_{ijk})=Loc(a_{000})+(i * n * p + j * p + k) * d

算法运算 ​

c
void transposition(int a[][8], int b[][5], int m, int n) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            b[j][i] = a[i][j];
        }
    }
}
c
// 即某个元素值在行中是最小的、在列中最大
void macMin(int A[4][5], int m, int n) {
    int max[5], min[4];
    for (int i = 0; i < m; i++) {
        min[i] = A[i][0];
        for (int j = 0; j < n; j++) {
            if (A[i][j] < min[i]) {
                min[i] = A[i][j];
            }
        }
    }

    for (int k = 0; k < n; k++) {
        max[k] = A[0][k];
        for (int l = 0; l < m; l++) {
            if (A[l][k] > max[k]) {
                max[k] = A[l][k];
            }
        }
    }

    for(int x = 0; x < m; x++) {
        for(int y = 0; y < n; y++) {
            if(min[x] == max[y]) {
                printf("A[%d][%d] = %d\n", x, y, A[x][y]);
            }
        }
    }
}

矩阵的压缩存储 ​

特殊矩阵压缩存储的压缩原则是：对有规律的元素和值相同的元素只分配一个存储单元，对于零元素不分配空间

对称矩阵 ​

  • 矩阵的元素在矩阵的左下角和右上角有相同的值【Aij=AjiA_{ij} = A_{ji}】
  • 存储的时候只要存下三角或上三角

下（上）三角矩阵 ​

主对角线下（上）方为常数c或零

稀疏矩阵 ​

矩阵中大多数元素为零的矩阵

三元组表示法：

  • 该非零元素所在的行号
  • 该非零元素所在的列号值
  • 该非零元素的值

广义表 ​

是线性表的推广，也称为列表（Lists）。它允许表中的元素既可以是原子（单个数据元素），也可以是子表（另一个广义表）

  • 长度：是指广义表中元素的个数
  • 深度：是指子表最大的嵌套次数
c
B = (a);
head(B) = a;
tail(B) = ();

C = (a, (b, c));
head(C) = a;
tail(C) = (b, c);

存储结构 ​

链式结构：每个元素用一个结点表示

  • tag=0，表示是原子结点；tag=1，表示是子表
  • data，表示元素；slink，指向子表结点
  • link，指向下一个元素对应的结点
c
typedef enum { ATOM, LIST } NodeTag;
typedef int DataType;
typedef struct {
    NodeTag tag;
    union {
        DataType atom;
        GList *slink;
    } atom_hp;

} *GList;

树 & 二叉树 ​

树的定义与基本术语 ​

是n(n≥0)n(n \ge 0)个结点的有限集合T。当n=0n=0时为空树；当n>0n \gt 0时，该集合满足如下条件：

  • 其中必有一个称为根[root]的特定结点，它没有直接前驱，但有零个或多个直接后继
  • 其余n−1n-1个结点可以划分成m(m≥0)m(m \ge 0)个互不相交的有限集T1,T2,T3,...,TmT_1,T_2,T_3,...,T_m，其中TiT_i又是一棵树，称为根[root] 的子树。每棵子树的根结点有且仅有一个直接前驱，可有零个或多个直接后继
基本术语说明
结点包含一个数据元素及若干指向其它结点的分支信息
结点的度一个结点的子树个数称为此结点的度
叶结点度为0的结点，即无后继的结点，也称为终端结点
分支结点度不为0的结点，也称为非终端结点
结点的层次从根结点开始定义，根结点的层次为1，根的直接后继的层次为2，依此类推
结点的层次编号将树中的结点按从上层到下层、同层从左到右的次序排成一个线性序列，依次给它们编以连续的自然数
树的度树中所有结点的度的最大值
树的高度（深度）树中所有结点的层次的最大值
有序树在树T中，如果各子树TiT_i之间是有先后次序的，则称为有序树
森林m(m>0)m(m \gt 0)棵互不相交的树的集合，将一棵非空树的根结点删去，树就变成一个森林
反之给森林增加一个统一的根结点，森林就变成一棵树
孩子结点一个结点的直接后继称为该结点的孩子结点
双亲结点一个结点的直接前驱称为该结点的双亲结点
兄弟结点同一双亲结点的孩子结点之间互称兄弟结点
堂兄弟父亲是兄弟关系或堂兄关系的结点称为堂兄弟结点
祖先结点一个结点的祖先结点是指从根结点到该结点的路径上的所有结点
子孙结点一个结点的直接后继和间接后继称为该结点的子孙结点
前（后）辈层号比该结点小（大）的结点，都称为该结点的前（后）辈

二叉树 ​

定义 ​

把满足以下两个条件的树型结构叫做二叉树 （Binary Tree ）:

  • 每个结点的度都不大于2
  • 每个结点的孩子结点次序不能任意颠倒

性质 ​

  • 在二叉树的第i层上至多有2i−12^{i-1}个结点(i≥1)(i \ge 1)
  • 深度为k的二叉树至多有2k−12^k-1个结点(k≥1)(k \ge 1)
  • 对任意一棵二叉树T，若终端结点数为n0n_0，而其度数为2的结点数为n2n_2，则n0=n2+1n_0=n_2+1
  • 具有n个结点的完全二叉树的深度为L=⌊log2n⌋+1L= \lfloor log_2 n \rfloor+ 1

满二叉树 & 完全二叉树 ​

  • 满二叉树
    • 深度为k且有2k−12^k-1个结点的二叉树，每层结点都是满的[每层结点都具有最大结点数]
  • 完全二叉树
    • 深度为k，结点数为n的二叉树，如果其结点1~n的位置序号分别与满二叉树的结点1~n的位置序号一一对应

顺序存储 ​

  • 将二叉树的节点按照层序遍历的顺序存储在一维数组中
  • 通常适用于完全二叉树或满二叉树，因为非完全二叉树会造成大量空间浪费

链式存储 ​

使用链表结构，每个节点包含：数据域（data）、左指针域（left）、右指针域（right）

c
typedef struct TreeNode {
    char data;  // 假设数据为字符类型
    struct TreeNode* left;
    struct TreeNode* right;
    struct TreeNode* parent;  // 三叉链表
} TreeNode;

二叉树的遍历 ​

  • 先序遍历（DLR）根 → 左子树 → 右子树
  • 中序遍历（LDR）左子树 → 根 → 右子树
  • 后序遍历（LRD）左子树 → 右子树 → 根
  • 先序遍历：A B D F G C E H
  • 中序遍历：B F D G A C E H
    • 先看B子树，左子树为空，所以先输出B，
    • 然后看B的右子树，右子树有值按照左，右，根的顺序遍历，即F，D，G
  • 后序遍历：F G D B H E C A

反向渲染二叉树

  • 前序遍历：A B D E G H C F I
  • 中序遍历：D B G E H A C I F

分析：

  • 由前序遍历可以确定A是根节点，再根据中序遍历可以确定D B G E H是左子树，C I F是右子树
  • 前序遍历A的左子树为B，中序遍历B的左子树为D，B的右子树为G E H
  • 前序遍历可以确定E G H，其中E是B的右子树的根节点
  • 中序遍历G E H可以得到G是E的左子树，H是E的右子树
  • 前序遍历C F I，则C为A的右子树的根节点，同时中序遍历C I F表示C没有左子树
  • 前序遍历F I，则F为C的右子树，在中序遍历是I F，则I是F的左子树

查找节点

c
int findLevel(TreeNode *root, int x, int level) {
    if (root == NULL) {
        return 0;
    }

    if (root->data == x) {
        return level;
    }

    int leftLevel = findLevel(root->left, x, level + 1);
    if (leftLevel != 0) {
        return leftLevel;
    }

    return findLevel(root->right, x, level + 1);
}

线索二叉树 ​

是对普通二叉树的一种改进，目的是利用二叉树中的空指针域来指向某种遍历顺序下的前驱或后继结点，从而加快遍历速度，避免使用递归或栈

c
typedef struct ThreadNode {
    int data;
    struct ThreadNode *left, *right;
    int ltag;  // 标志位 0: left 指向左孩子；1: left 指向前驱（线索）
    int rtag;  //
} ThreadNode;
txt
    A
     \
      B
     / \
    D   C
  • 中序遍历：D → B → C → A
    • D left = Null 没有左孩子，也没有前驱
    • D right = B 中序后继是 B
    • D ltag = 1 指向前驱，前驱为Null
    • D rtag = 1 指向后继

树和森林 ​

树的三种主要存储表示方法

表示法说明优点✅缺点❌
双亲每个结点记录
其父结点的位置		查找父结点非常快(O(1))(O(1))
存储紧凑，适合静态树		查找孩子结点慢
插入删除不方便
孩子记录其所有孩子结点查找所有孩子非常方便
适合需要频繁
访问孩子的操作		查找父结点困难
存储开销较大
孩子兄弟记录第一个孩子和第一个兄弟结构统一，易于递归操作
将任意树->二叉树结构处理
特别适合树与森林的转换		查找父结点仍然困难
c
struct Node {
    int data;       // 数据
    int parent;     // 父结点在数组中的下标
};
c
// 孩子链表结点
struct ChildNode {
    int childIndex;           // 孩子在数组中的下标
    struct ChildNode *next;
};

// 主结点
struct Node {
    int data;
    struct ChildNode *firstChild;  // 指向第一个孩子的链表
};
c
struct Node {
    int data;
    struct Node *firstChild;   // 第一个孩子
    struct Node *nextSibling;  // 下一个兄弟
};

树➡️二叉树 ​

  • 树中所有相邻兄弟之间加一条连线
  • 对树的每个结点，只保留其与第一个孩子结点间的连线，删去其与其它孩子结点之间的连线
  • 以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明

森林➡️二叉树 ​

  • 将森林中的每棵树转换成相应的二叉树
  • 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后所得到的二叉树就是由森林转换得到的二叉树

二叉树➡️树&森林 ​

  • 若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子、......都与该结点的双亲结点用线连起来
  • 删掉原二叉树中所有双亲结点与右孩子结点的连线
  • 整理前两步所得到的树或森林，使之结构层次分明

树的遍历 ​

  • 先根遍历
    • 访问根结点
    • 从左到右，依次先根遍历根结点的每一棵子树
  • 后根遍历
    • 从左到右，依次后根遍历根结点的每一棵子树
    • 访问根结点

森林的遍历 ​

  • 先序遍历
    • 访问森林中第一棵树的根结点
    • 先序遍历第一棵树的根结点的子树森林
    • 先序遍历除去第一棵树之后剩余的树构成的森林
  • 中序遍历
    • 中序遍历森林中第一棵树的根结点的子树森林
    • 访问第一棵树的根结点
    • 中序遍历除去第一棵树之后剩余的树构成的森林
  • 后序遍历
    • 后序遍历森林中第一棵树的根结点的子树森林
    • 后序遍历除去第一棵树之后剩余的树构成的森林
    • 访问第一棵树的根结点

哈夫曼树 ​

  • 路径：指从一个结点到另一个结点之间的分支序列
  • 路径长度：指从一个结点到另一个结点所经过的分支数目
  • 结点的权：给树的每个结点赋予一个具有某种实际意义的实数，该实数为这个结点的权
  • 带权路径长度：路径长度乘以该路径的权

哈夫曼树又叫最优二叉树，它是由n个带权叶子结点构成的所有二叉树中带权路径长度WPL最短的二叉树

图 ​

图的定义与基本术语 ​

图（Graph）是一种网状数据结构，Graph=(V,E)Graph = (V, E)

  • CreateGraph(G)：创建图
  • DestroyGraph(G)：销毁图
  • LocateVertex(G, v)：定位顶点v
  • GetVertex(G, i)：返回图的的第i个顶点
  • FirstAdjVertex(G, v)：返回顶点v的第一个邻接顶点
  • NextAdjVertex(G, v, w)：返回顶点v的下一个邻接顶点
  • InsertVertex(G, v)：插入顶点v
  • DeleteVertex(G, v)：删除顶点v
  • InsertEdge(G, v, w)：插入边<v, w>
  • DeleteEdge(G, v, w)：删除边<v, w>
  • TraverseGraph(G)：遍历图G

基本术语 ​

  • 无向完全图：有n(n−1)2\frac{n(n-1)}{2}条边（图中每个顶点和其余n−1n-1个顶点都有边相连）的无向图
  • 有向完全图：有n∗(n−1)n*(n-1)条边（图中每个顶点和其余n−1n-1个顶点都有弧相连）的有向图
  • 子图：设有两个图G=(V,E)G=(V,{E})和图G′=(V′,E′)G'=(V',{E'})， 若V′⊆VV'\subseteq V且E′⊆EE'\subseteq E，G′G'为GG的子图
  • 邻接点
    • 无向图G=(V,E)G=(V,{E})，如果边(v,v′)∈E(v,v')\in E，则称顶点v,v′v,v'互为邻接点
    • 有向图G=(V,A)G=(V,{A})，若弧(v,v′)∈A(v,v')\in A，则称顶点vv邻接到顶点v′v'，顶点v′v'邻接顶点vv
  • 无向图的度：顶点v的度是指和v相关联的边的数目
  • 有向图的度
    • 出度：从顶点v出发，能到达的顶点的数目
    • 入度：有向图中以顶点v为终点的弧的数目
  • 权：每一条边都有与它相关的数，这个数叫做权
  • 网：带权的图
  • 路径：指从一个结点到另一个结点之间的分支序列
  • 路径长度：指路径上经过的弧或边的数目
  • 回路或环：在一个路径中，若其第一个顶点和最后一个顶点是相同的，即v=v′v=v'
  • 简单路径：若表示路径的顶点序列中的顶点各不相同
  • 简单回路：除了第一个和最后一个顶点外，其余各顶点均不重复出现的回路
  • 连通图：在无向图G=(V,E)G=(V,{E})中，若从vi→vjv_i \rightarrow v_j有路径相通，则称顶点vi,vjv_i,v_j是连通的 如果对于图中的任意两个顶点vi,vj∈V，vi,vjv_i,v_j \in V，v_i,v_j都是连通的，则称该无向图G为连通图
  • 连通分量：无向图中的极大连通子图
  • 强连通图：在有向图G=(V,A)G=(V,{A})中，若对于每对顶点vi,vj∈Vv_i,v_j \in V且vi≠vjv_i \neq v_j，从viv_i到vjv_j和从vjv_j到viv_i都有路径
  • 强连通分量：有向图的极大强连通子图称作有向图的强连通分量

图的存储结构 ​

邻接矩阵 ​

采用两个数组来表示图：

  • 用于存储顶点信息的一维数组
  • 用于存储图中顶点之间关联关系的二维数组

这个有向图对应的二维矩阵为：(无向图也是一样的)

[0110000000011000]\begin{bmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ \end{bmatrix}

带权图的二维矩阵：用权值代替1，0用无穷∞\infty表示

邻接表 ​

一个n个顶点的图的邻接表表示由表头结点表与边表两部分构成

txt
// 顶点 A=0, B=1, C=2, D=3
邻接表表示为：
A (0): 1 → 2 → NULL
B (1): NULL
C (2): 3 → NULL
D (3): 0 → NULL

图的遍历 ​

深度优先 ​

  1. 从图中某个顶点v出发，首先访问v0v_0
  2. 找出刚访问过的顶点v的第一个未被访问的邻接点，然后访问该顶点。重复此步骤，直到当前的顶点没有未被访问的邻接点为止
  3. 返回前一个访问过的顶点，找出该顶点的下一个未被访问的邻接点，访问该顶点。转2
c
int visited[20];

void DFS(Graph G, int i, int n) {
    visited[i] = 1;
    for (int j = 0; j < n; j++) {
        // ==1表示有边相邻，!visited[j]表示未访问
        if (G.arcs[i][j] == 1 && !visited[j]) {
            DFS(G, j, n);
        }
    }
}
c
int visited[20];

void DFS(Graph G, int i) {
    EdgeNode *p;
    int j;
    visited[i] = 1;
    p = G[i].link;
    while (p != NULL) {
        j = p->adjvex;
        if (!visited[j]) {
            DFS(G, j);
        }
        p = p->next;
    }
}

广度优先 ​

  1. 从图中某个顶点v。出发，首先访问v0v_0
  2. 依次访问v的各个未被访问的邻接点
  3. 分别从这些邻接点出发，依次访问它们的各个未被访问的邻接点
c
int visited[20];

void BFS(Graph G, int i, int n) {
    CirQueue Q;
    int k, j;
    InitQueue(&Q);
    visited[i] = 1;
    EnQueue(&Q, i);
    while (!QueueEmpty(Q)) {
        k = DeQueue(&Q);
        for (j = 0; j < n; j++) {
            if (G.arcs[k][j] == 1 && !visited[j]) {
                visited[j] = 1;
                EnQueue(&Q, j);
            }
        }
    }
}
c
void BFS(Graph G, int i) {
    CirQueue Q;
    int k, j;
    InitQueue(&Q);
    visited[i] = 1;
    EnQueue(&Q, i);
    while (!QueueEmpty(Q)) {
        k = DeQueue(&Q);
        p = G[k].link;
        while(p){
            j = p->adjvex;
            if (!visited[j]) {
                visited[j] = 1;
                EnQueue(&Q, j);
            }
            p = p->next;
        }
    }
}

图的应用 ​

最小生成树 ​

Prim算法：

  • 从一个顶点开始，逐步扩展生成树
  • 每次选择一条连接已选顶点集合和未选顶点集合之间的最小权值边，将其加入生成树
  • 类似于“贪心”策略，每次局部最优，最终得到全局最优
c
void Prim(MGraph G, int start) {

    int lowcost[100];   // lowcost[i] 表示顶点i到U的最短距离
    int closest[100];   // closest[i] 表示i在U中的最近邻接点
    int U[100] = {0};   // 标记顶点是否已加入生成树（1表示已加入）

    // 初始化
    for (int i = 0; i < G.vexNum; i++) {
        lowcost[i] = G.arcs[start][i];
        closest[i] = start;
    }
    U[start] = 1;  // 起始点加入集合U

    for (int i = 1; i < G.vexNum; i++) {  // 需要选择n-1条边
        int min = INF;
        int k = -1;

        // 找出最小的lowcost[k]
        for (int j = 0; j < G.vexNum; j++) {
            if (!U[j] && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }
        
        printf("(%c, %c) = %d\n", G.vexs[closest[k]], G.vexs[k], lowcost[k]);
        U[k] = 1;  // 将k加入U

        // 更新lowcost和closest
        for (int j = 0; j < G.vexNum; j++) {
            if (!U[j] && G.arcs[k][j] < lowcost[j]) {
                lowcost[j] = G.arcs[k][j];
                closest[j] = k;
            }
        }
    }
}

Kruskal算法： 见离散数学-最小生成树

单源最短路径 ​

Dijkstra算法： 求最短路径-Java

  • 设置出发顶点为v，顶点集合V{v1,v2.,v3…}, v到V中各顶点的距离构成距离集合Dis{d1,d2.,d3…}，Dis集合记录着v到图中各项点的距离( 到自身为0，v到viv_i距离为did_i)
    • 从Dis中选择值最小的did_i并移出Dis集合，同时移出V中的点viv_i，此时的v到viv_i即为最短路径
    • 更新Dis集合， 更新规则为:比较v到V集合中顶点的距离值，与v通过viv_i到V集合中顶点的距离值,保留值较小的一个( 同时也应该更新顶点的前驱节点为viv_i，表明是通过viv_i到达的)
    • 重复执行两步骤，直到最短路径项点为目标顶点即可结束
迭代当前选中的顶点已访问集合Sdis[2]dis[3]dis[4]dis[5]
初始-{1}10∞30100
12{1,2}106030100
24{1,2,4}10503090
33{1,2,4,3}10503060
45{1,2,4,3,5}10503060
顶点最短距离最短路径
2101→21 \rightarrow 2
3502→32 \rightarrow 3
4301→41 \rightarrow 4
5601→4→3→51 \rightarrow 4 \rightarrow 3 \rightarrow 5
代码实现：
c
#include <stdbool.h>
int maxint = 9999999;

/**
 * @param n 图的顶点数
 * @param v 源顶点
 * @param dis 源顶点到各个顶点的最短距离
 * @param prev 记录最短路径上的前驱顶点
 * @param c 图的邻接矩阵
 */
void dijkstra(int n, int v, int dis[], int prev[], int **c) {
    // s[i]记录顶点i是否并入结合S
    bool s[n];

    // 初始化最短距离
    for (int i = 1; i <= n; i++) {
        dis[i] = c[v][i]; // 记录最短距离
        s[i] = false;     // 清空该集合，表示所有顶点都没加入S
        if (dis[i] == maxint) {
            prev[i] = 0; // 源顶点和顶点i之间没有直接边相连
        } else {
            prev[i] = v; // 有直接边相连
        }
    }

    // 初始化源顶点
    dis[v] = 0;
    s[v] = true;

    for (int i = 1; i < n; i++) {
        int temp = maxint;
        int u = v;

        for (int j = 1; j <= n; j++) {
            // 在V-S中选择一个距离源顶点最近的顶点u
            if (!s[j] && dis[j] < temp) {
                u = j;
                temp = dis[j];
            }
        }
        
        // 把顶点u并入集合S
        s[u] = true;

        // 更新顶点u的相邻顶点的最短距离
        for (int j = 1; j <= n; j++) {
            // 表示c、j之间有边相连
            if (!s[j] && c[u][j] < maxint) {
                int newDis = dis[u] + c[u][j];
                if (newDis < dis[j]) {
                    dis[j] = newDis;
                    prev[j] = u;
                }
            }
        }
    }
}

有向无环图 ​

  • AOV-网（Activity On Vertex Network）：用顶点表示活动，用弧表示活动间的优先关系的有向无环图，称为顶点表示活动的网，简称为AOV-网
  • 拓扑序列：在有向图G=(V,E)G=(V,{E})中，将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)(u,v) \in E(G) ，则u在线性序列中出现在v之前
拓扑排序

那么它的拓扑排序为：C1，C2，C3，C4，C8，C9，C7，C5，C6

求拓扑排序的基本思想：

  • 从有向图中选一个无前驱的顶点输出
  • 将此顶点和以它为起点的弧删除
  • 重复前两步，直到不存在无前驱的顶点
    • 若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路
    • 否则输出的顶点的顺序即为一个拓扑序列

基于 邻接表 表示的存储结构，算法的基本思想：

  • 用一个含n个元素的一维数组index存储每个点的入度
  • 设一个栈保存所有入度为0的顶点
  • 扫一遍，把入度为0的点加入queue
  • 每次从栈顶拿出一个元素，并删除这个元素，然后把以这个元素为起点的弧头v的入度减1，若vi的入度为Q，则入栈。重复这个操作，直到栈为空。
邻接表表示求拓扑排序
c
#include <stdbool.h>
#define N 20

void topsort(Graph G, int n) {
    int index[N];

    EdgeNode *p;
    // 初始化入度数组
    for (int i = 0; i < n; i++) {
        index[i] = 0;
    }

    // 计算每个顶点的入度
    for (int i = 0; i < n; i++) {
        p = G[i].link;
        while (p) {
            index[p->adjvex]++;
            p = p->next;
        }
    }

    SeqStack S;
    InitStack(&S);
    int j, m;
    for (int i = 0; i < n; i++) {
        // 入度为0的顶点入栈
        if (index[i] == 0) {
            push(&S, i);
        }
        while (!StackEmpty(S)) {
            // 出栈（取栈顶）
            i = pop(&S);
            printf("%d ", i);
            m++;
            p = G[i].link;
            while (p) {
                j = p->adjvex; // 找到邻接点
                index[j]--;    // 入度减1
                if (index[j] == 0) {
                    push(&S, j);
                }
                p = p->next;
            }
        }
    }
}

排序 ​

插入类排序 ​

基本思想：在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序插入到已排好序的记录子集中，直到将所有待排记录全部插入为止

插入排序 ​

  • 基本思想：将数组分为已排序和未排序两部分，每次从未排序部分取一个元素插入到已排序部分的正确位置
  • 时间复杂度： O(n2)O(n^2)
  • 空间复杂度：O(1)O(1)
  • 稳定性：稳定排序算法

希尔排序 ​

  • 基本思想：是插入排序的一种改进版本，也称为"缩小增量排序"。它通过将原始数组分割成若干个子序列来进行排序，每个子序列使用插入排序
  • 核心概念：
    • 间隔(gap)：决定哪些元素被分到同一子序列中
    • 先用较大的间隔进行排序，然后逐渐缩小间隔
    • 最后一次排序间隔为1，即对整个数组进行一次直接插入排序
  • 时间复杂度：
    • 取决于间隔序列的选择
    • 使用Knuth序列(N2,N4,...,1)(\frac{N}{2},\frac{N}{4},...,1)时约为O(n1.5)O(n^{1.5})
    • 平均情况：O(n1.25)O(n^{1.25})到O(n1.5)O(n^{1.5})
  • 空间复杂度：O(1)O(1)
  • 稳定性：不稳定排序算法
c
void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        
        // 将大于key的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}
c
void shellSort(int arr[], int n) {
    // 初始间隔为数组长度的一半，然后逐渐减半
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 对每个间隔进行直接插入排序
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            
            // 在间隔为gap的子序列中进行插入排序
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

交换类排序 ​

冒泡排序 ​

  • 基本思想：重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就交换它们。遍历数列的工作是重复进行的，直到没有再需要交换的元素为止。
  • 时间复杂度：O(n2)O(n^2)
  • 空间复杂度：O(1)O(1)
  • 稳定性：稳定排序算法

快速排序 ​

  • 基本思想：采用分治法策略，选择一个基准元素，通过一趟排序将待排序序列分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序。
  • 时间复杂度：O(nlogn)O(n log n)
  • 空间复杂度：
    • 最好：O(logn)O(log n)
    • 最坏：O(n)O(n)
  • 稳定性：不稳定排序算法

交换排序 ​

  • 基本思想：通过不断比较和交换数组中的元素来实现排序。它遍历数组，将每个元素与后续所有元素进行比较，如果顺序不正确就交换它们
  • 时间复杂度：O(n2)O(n^2)
  • 空间复杂度：O(1)O(1)
  • 稳定性：稳定排序算法
c
void bubbleSort(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - i - 1; j++) {
            // 如果前一个元素大于后一个元素，则交换
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
c
// 交换两个元素的函数
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 分区函数 - 快速排序的核心
int partition(int arr[], int low, int high) {
    // 选择最后一个元素作为基准(pivot)
    int pivot = arr[high];
    int i = (low - 1); // 较小元素的索引
    
    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于基准
        if (arr[j] <= pivot) {
            i++; // 较小元素的索引增加
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// 快速排序主函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 获取分区索引
        int pi = partition(arr, low, high);
        
        // 分别对基准元素左右两部分进行递归排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
c
void exchangeSort(int arr[], int n) {
    int i, j, temp;
    
    // 遍历所有元素
    for (i = 0; i < n - 1; i++) {
        // 将当前元素与后面所有元素比较
        for (j = i + 1; j < n; j++) {
            // 如果前面的元素大于后面的元素，则交换
            if (arr[i] > arr[j]) {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

选择类排序 ​

选择排序 ​

  • 基本思想：每次从未排序的部分中找到最小（或最大）元素，将其放到已排序部分的末尾
  • 时间复杂度：O(n2)O(n^2)
  • 空间复杂度：O(1)O(1)
  • 稳定性：不稳定排序算法

堆排序 ​

  • 基本思想

    • 构建最大堆
      • 从最后一个非叶子节点开始，自底向上调整
      • 确保每个节点都满足堆的性质
    • 排序过程
      • 将堆顶元素（最大值）与末尾元素交换
      • 减少堆的大小，重新调整堆
      • 重复直到堆大小为1

  • 时间复杂度

    • 构建堆：O(n)O(n)
    • 排序过程：O(nlogn)O(n log n)
    • 总体：O(nlogn)O(n log n)

  • 空间复杂度：O(1)，只使用常数额外空间

  • 稳定性：不稳定排序算法

c
void selectionSort(int arr[], int n) {
    int i, j, minIndex, temp;
    
    // 遍历所有数组元素
    for (i = 0; i < n - 1; i++) {
        // 找到未排序部分的最小元素索引
        minIndex = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        // 将找到的最小元素与未排序部分的第一个元素交换
        if (minIndex != i) {
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}
c
/**
 * 调整堆，使其满足最大堆性质
 * @param arr - 待调整的数组
 * @param n - 堆的大小
 * @param i - 需要调整的节点索引
 */
void heapify(int arr[], int n, int i) {
    int largest = i;        // 初始化最大值为根节点
    int left = 2 * i + 1;   // 左子节点索引
    int right = 2 * i + 2;  // 右子节点索引
    int temp;

    // 如果左子节点存在且大于根节点
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // 如果右子节点存在且大于当前最大值
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大值不是根节点，则交换并继续调整
    if (largest != i) {
        // 交换元素
        temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        // 递归调整受影响的子树
        heapify(arr, n, largest);
    }
}

/**
 * 堆排序主函数
 * @param arr - 待排序数组
 * @param n - 数组长度
 */
void heapSort(int arr[], int n) {
    int i, temp;

    // 1. 构建最大堆（从最后一个非叶子节点开始）
    for (i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 2. 逐个提取元素进行排序
    for (i = n - 1; i > 0; i--) {
        // 将堆顶（最大值）与末尾元素交换
        temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // 重新调整堆（堆大小减1）
        heapify(arr, i, 0);
    }
}

归并排序 ​

  • 基本思想：采用分治策略，将数组不断二分直到只有一个元素，然后将两个已排序的子数组合并成一个有序数组
  • 时间复杂度：O(nlogn)O(n log n)
  • 空间复杂度：O(n)O(n)
  • 稳定性：稳定排序算法
c
/**
 * 分：递归地将数组分解到最小单元，然后合并
 * arr: 待排序数组
 * left: 左边界
 * right: 右边界
 * temp: 临时数组，用于合并过程
 */
void branch(int arr[], int left, int right, int temp[]) {
    if (left < right) {
        int mid = (left + right) / 2;

        // 向左递归分解
        branch(arr, left, mid, temp);
        // 向右递归分解
        branch(arr, mid + 1, right, temp);

        // 合并左右两部分
        cure(arr, left, mid, right, temp);
    }
}
c
/**
 * 治：合并两个有序子数组
 * arr: 原数组
 * left: 左边起始索引
 * middle: 中间索引（左子数组的结尾）
 * right: 右边结束索引
 * temp: 临时数组，用于暂存排序结果
 */
void cure(int arr[], int left, int middle, int right, int temp[]) {
    int i = left;           // 左子数组的起始索引
    int j = middle + 1;     // 右子数组的起始索引
    int t = 0;              // temp 数组的当前索引

    // 第一步：比较左右两部分元素，较小者放入 temp
    while (i <= middle && j <= right) {
        if (arr[i] < arr[j]) {
            temp[t++] = arr[i++];
        } else {
            temp[t++] = arr[j++];
        }
    }

    // 第二步：处理左子数组剩余元素
    while (i <= middle) {
        temp[t++] = arr[i++];
    }

    // 第三步：处理右子数组剩余元素
    while (j <= right) {
        temp[t++] = arr[j++];
    }

    // 第四步：将 temp 中已排序的元素复制回原数组 arr
    for (int k = 0; k < t; k++) {
        arr[left + k] = temp[k];
    }
}

分配类排序 ​

  • 扑克牌排序
    • 先按牌面大小排序，再按花色排序
    • 先按花色排序，再按牌面大小排序

比较各个排序的时间、空间复杂度 ​

排序方法平均时间复杂度最坏时间复杂度空间复杂度稳定性
简单排序：如冒泡、选择、插入O(n2)O(n^2)O(n2)O(n^2)O(1)O(1)冒泡、插入稳定，选择不稳定
快速排序O(nlogn)O(n log n)O(n2)O(n^2)O(logn)O(log n)不稳定
堆排序O(nlogn)O(n log n)O(nlogn)O(n log n)O(1)O(1)不稳定
归并排序O(nlogn)O(n log n)O(nlogn)O(n log n)O(n)O(n)稳定
基数排序O(d×(n+k))O(d × (n + k))O(d×(n+k))O(d × (n + k))O(k)O(k)稳定

查找 ​

基本概念 ​

  • 查找：根据给定的关键字值，在特定的列表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置
  • 平均查找长度：为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度

基于线性表查找 ​

  • 顺序查找：从后往前遍历查找
    • ASL=n+12ASL = \frac{n+1}{2}
  • 二分法：分为两半，每次查找取中间值比较，随后找左侧或者右侧，重复此过程
    • ASL=n−1nlog⁡2(n+1)−1ASL = \frac{n-1}{n} \log_2(n+1) - 1
c
/**
 * 二分查找
 * @param arr 已排序的数组
 * @param left 左边界索引
 * @param right 右边界索引
 * @param k 要查找的元素
 * @return 如果找到元素则返回其索引，否则返回-1
*/
c
int binarySearch(int arr[], int left, int right, int k) {
    while (left < right) {
        int middle = (left + right) / 2;
        if (k == arr[middle]) {
            return middle;
        }
        if (k > arr[middle]) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    return -1;
}
c
int bSearch(int arr[], int left, int right, int k) {
    if (left > right) {
        return -1;
    } else {
        int middle = (left + right) / 2;
        if (k == arr[middle]) {
            return middle;
        } else if (k > arr[middle]) {
            return bSearch(arr, middle + 1, right, k);
        } else {
            return bSearch(arr, left, middle - 1, k);
        }
    }
}
  • 索引顺序查找法：先匹配索引表，再匹配数据
    • ASL=ns+s2+1ASL = \frac{\frac{n}{s} + s}{2} + 1

基于树查找 ​

二叉排序树 ​

  • 每个节点的左子节点小于父节点，右子节点大于父节点
  • 中序遍历：是升序排序的
  • 最好的情况：ASL≈log2(n+1)−1ASL ≈ log_{2}(n+1) - 1
  • 最坏的情况：ASL=n+12ASL = \frac{n+1}{2}
c
typedef struct TreeNode {
    int data;               // 节点数据
    struct TreeNode* left;  // 左子树指针
    struct TreeNode* right; // 右子树指针
} TreeNode;
c
/**
 * 向二叉排序树中插入节点
 * @param root 树的根节点指针的指针
 * @param data 要插入的数据
 * @return 插入后的根节点指针
 */
TreeNode* insertNode(TreeNode** root, int data) {
    // 如果树为空，则创建根节点
    if (*root == NULL) {
        *root = createNode(data);
        return *root;
    }
    
    // 如果要插入的数据小于当前节点数据，插入到左子树
    if (data < (*root)->data) {
        insertNode(&((*root)->left), data);
    }
    // 如果要插入的数据大于当前节点数据，插入到右子树
    else if (data > (*root)->data) {
        insertNode(&((*root)->right), data);
    }

    return *root;
}
c
TreeNode* deleteNode(TreeNode** root, int data) {
    // 基本情况：树为空
    if (*root == NULL) {
        return NULL;
    }
    
    if (data < (*root)->data) {
        // 如果要删除的数据小于当前节点数据，在左子树中删除
        deleteNode(&((*root)->left), data);
    }else if (data > (*root)->data) {
        // 如果要删除的数据大于当前节点数据，在右子树中删除
        deleteNode(&((*root)->right), data);
    }else {
        // 找到要删除的节点
        // 情况1：节点没有子节点（叶子节点）
        if ((*root)->left == NULL && (*root)->right == NULL) {
            TreeNode* temp = *root;
            *root = NULL;
            free(temp);
        }
        // 情况2：节点只有一个子节点
        else if ((*root)->left == NULL) {
            // 只有右子节点
            TreeNode* temp = *root;
            *root = (*root)->right;
            free(temp);
        } else if ((*root)->right == NULL) { 
            // 只有左子节点
            TreeNode* temp = *root;
            *root = (*root)->left;
            free(temp);
        }
        // 情况3：节点有两个子节点
        else {
            // 找到右子树中的最小节点（中序后继）
            TreeNode* successor = (*root)->right;
            while (successor->left != NULL) {
                successor = successor->left;
            }
            
            // 用后继节点的数据替换当前节点的数据
            (*root)->data = successor->data;
            
            // 删除后继节点
            deleteNode(&((*root)->right), successor->data);
        }
    }
    
    return *root;
}

B树 ​

c
typedef struct BTreeNode {
    int n;                     // 当前节点中关键字的个数
    int *keys;                 // 存储关键字的数组
    struct BTreeNode **childs; // 存储子节点指针的数组
    bool leaf;                 // 是否为叶子节点
} BTreeNode;
c
/**
 * 搜索B树中的关键字
 * @param root B树根节点
 * @param key 要搜索的关键字
 * @return 找到返回true，否则返回false
 */
bool searchKey(BTreeNode* root, int key) {
    if (root == NULL) {
        return false;
    }
    
    int i = 0;
    // 在当前节点中找到第一个不小于key的关键字
    while (i < root->n && key > root->keys[i]) {
        i++;
    }
    
    // 如果找到关键字
    if (i < root->n && key == root->keys[i]) {
        return true;
    }
    
    // 如果是叶子节点且未找到关键字
    if (root->leaf) {
        return false;
    }
    
    // 递归搜索子树
    return searchKey(root->childs[i], key);
}

计算式查找-Hash ​

基本思想：首先在元素的关键字k和元素的存储位置p之间建立一个对应关系H，使得p=H(k)p=H(k) ，H称为散列函数。当查找关键字为k的元素时，再利用散列函数计算出该元素的存储位置p=H(k)p=H(k)，从而达到按关键字直接存取元素的目的。

  • 直接地址法：H(key)=key+CH(key) = key + C
  • 数字分析法：
  • 取模：H(key)=key%mH(key) = key \% m
  • 平方取中：
  • 分段叠加：

处理冲突的方法：

  • 开放定址法：即对产生冲突的key，再次计算新的位置，直到找到一个空闲位置为止。
    • 线性探测再散列
    • 二次探测再散列

后话 ​

🌟 document.querySelector('video').playbackRate = 1.75 用这个方法调整B站视频播放速度

扩充：vscode编写的c语言代码，默认格式化和java语言不同，可能是java和js写多了，看的有一点点难受，在根目录下创建一个.clang-format文件，内容如下：这样再次格式化就和java、js一样了

yaml
BasedOnStyle: LLVM
IndentWidth: 4
TabWidth: 4
UseTab: Never
BreakBeforeBraces: Attach
AllowShortIfStatementsOnASingleLine: false

By Modify.

Copyright © 2023-present Evan You