My-Project

Appearance

02331 数据结构 ✒️ ​

概论 ​

什么是数据结构 ​

算法 + 数据结构 = 程序

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

基本概念和术语 ​

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

数据的运算

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

抽象数据类型（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++;
    }
}

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

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

顺序表的定义 ​

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}的地址为Loc[a00]Loc[a_{00}]，每个元素占d个存储单元，求任意元素a的地址，可由如下计算公式得到：

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

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

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

广度优先 ​

图的应用 ​

排序 ​

查找 ​

后话 ​

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

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

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

By Modify.

Copyright © 2023-present Evan You