代码区

线性结构

1. 顺序表

基本概念与存储结构

#define MAXSIZE 100  //最大长度
typedef struct {
    ElemType *elem;  //指向数据元素的基地址
    int length;      //线性表的当前长度
} SqList;

分析：顺序表采用连续存储空间存放元素，通过基地址指针和长度属性管理线性表。elem指向首元素地址，length记录当前元素数量，最大容量由MAXSIZE限制。

基本操作代码及分析

1. 初始化操作

Status InitList_Sq(SqList &L) {
    L.elem = new ElemType[MAXSIZE]; //为顺序表分配空间
    if (!L.elem) exit(OVERFLOW);    //存储分配失败
    L.length = 0;                   //空表长度为0
    return OK;
}

分析：初始化时分配最大空间，并将长度置为0。使用引用参数&L确保修改原表。分配失败时调用exit(OVERFLOW)异常终止。

1. 取值操作

int GetElem(SqList L, int i, ElemType &e) {
    if (i < 1 || i > L.length) return ERROR; //判断i值是否合理
    e = L.elem[i-1]; //第i-1的单元存储着第i个数据
    return OK;
}

分析：顺序表支持随机存取。参数i从1开始计数，需转换为数组下标i-1。先检查i的合法性，避免越界访问。

1. 查找操作

int LocateELem(SqList L, ElemType e) {
    for (i = 0; i < L.length; i++)
        if (L.elem[i] == e) return i+1; //返回位置（从1开始计数）
    return 0; //未找到返回0
}

分析：顺序查找算法。从头到尾扫描，找到第一个匹配元素返回其位置（从1开始计数），时间复杂度O(n)。

1. 插入操作

Status ListInsert_Sq(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1) return ERROR; //i值不合法
    if (L.length == MAXSIZE) return ERROR; //当前存储空间已满
   
    for (j = L.length-1; j >= i-1; j–)
        L.elem[j+1] = L.elem[j]; //插入位置及之后的元素后移
   
    L.elem[i-1] = e; //将新元素e放入第i个位置
    ++L.length; //表长增1
    return OK;
}

分析：在第i个位置插入元素。先验证i和空间，然后从后向前移动元素（避免覆盖），最后插入新元素并更新长度。时间复杂度O(n)。

1. 删除操作

Status ListDelete_Sq(SqList &L, int i) {
    if¹ return ERROR; //i值不合法
   
    for (j = i; j <= L.length-1; j++)
        L.elem[j-1] = L.elem[j]; //被删除元素之后的元素前移
   
    –L.length; //表长减1
    return OK;
}

分析：删除第i个元素。验证i合法性后，将后续元素前移覆盖被删元素，更新长度。时间复杂度O(n)。

1. 求和操作（例题）

int SumSqList(SqList L) {
    int sum = 0;
    for (int i = 0; i < L.length; i++)
        sum += L.elem[i];
    return sum;
}

分析：遍历顺序表累加元素值。时间复杂度O(n)，空间复杂度O(1)。

典型例题及分析

1. 元素逆置

void ReverseSqList(SqList &L) {
    int i, temp;
    for (i = 0; i < L.length / 2; i++) {
        temp = L.elem[i];
        L.elem[i] = L.elem[L.length – 1 – i];
        L.elem[L.length – 1 – i] = temp;
    }
}

分析：双指针法实现原地逆置。i从前往后，L.length-1-i从后往前，中间相遇停止。只需遍历一半长度，时间复杂度O(n)，空间复杂度O(1)。

1. 删除所有指定值元素

void DeleteX(SqList &L, int x) {
    int i, j = 0;
    for (i = 0; i < L.length; i++) {
        if (L.elem[i] != x)
            L.elem[j++] = L.elem[i];
    }
    L.length = j;
}

分析：快慢指针实现原地删除。快指针i遍历所有元素，慢指针j记录保留元素位置。当元素不等于x时复制到j位置。最后更新length，时间复杂度O(n)，空间复杂度O(1)。

知识点总结

• 原地操作：通过双指针（快慢指针）实现空间复杂度O(1)的算法
• 边界处理：数组下标范围[0, length-1]，逆置时注意中点位置（length/2）
• 时间优化：单次遍历解决删除/分离问题，避免嵌套循环
• 关键约束：原地修改需更新length属性，空间复杂度O(1)要求禁用额外数组

2. 链表

基本概念与存储结构

typedef struct LNode {
    ElemType data;      //数据域
    struct LNode *next; //指针域
} LNode, *LinkList;

分析：链式存储不需连续空间，通过指针链接各节点。LinkList是LNode*类型别名，表示链表头指针。

基本操作代码及分析

1. 取值操作

Status GetElem_L(LinkList L, int i, ElemType &e) {
    p = L->next; j = 1; //初始化
    while (p && j < i) { //向后扫描，直到p指向第i个元素或p为空
        p = p->next; ++j;
    }
    if (!p || j > i) return ERROR; //第i个元素不存在
    e = p->data; //取第i个元素
    return OK;
}

分析：从头节点开始沿next指针移动。头节点不存储数据，有效数据从L->next开始。时间复杂度O(n)，不能随机存取。

1. 查找操作

LNode *LocateELem_L(LinkList L, ElemType e) {
    p = L->next;
    while (p && p->data != e)
        p = p->next;
    return p;
}

分析：顺序查找，返回第一个匹配元素的节点指针。若未找到返回NULL。时间复杂度O(n)。

1. 插入操作

Status ListInsert_L(LinkList &L, int i, ElemType e) {
    p = L; j = 0;
    while (p && j < i-1) { //寻找第i-1个结点
        p = p->next; ++j;
    }
    if (!p || j > i-1) return ERROR; //i大于表长+1或者小于1
   
    s = new LNode; //生成新结点s
    s->data = e;   //将结点s的数据域置为e
    s->next = p->next; //将结点s插入L中
    p->next = s;
    return OK;
}

分析：在第i个位置插入新节点。先找到第i-1个节点，修改指针：新节点指向原第i个节点，第i-1个节点指向新节点。时间复杂度O(n)。

1. 删除操作

Status ListDelete_L(LinkList &L, int i, ElemType &e) {
    p = L; j = 0;
    while (p->next && j < i-1) { //寻找第i个结点，并令p指向其前驱
        p = p->next; ++j;
    }
    if (!(p->next) || j > i-1) return ERROR; //删除位置不合理
   
    q = p->next; //临时保存被删结点的地址以备释放
    p->next = q->next; //修改前驱结点的指针域
    e = q->data; //保存被删元素
    delete q; //释放结点空间
    return OK;
}

分析：删除第i个节点。先找到前驱节点p，用q保存被删节点，修改p->next指向q->next，释放q。时间复杂度O(n)。

知识点总结

• 动态内存管理：节点需动态分配(new)和释放(delete)，防止内存泄漏
• 指针操作：插入/删除需修改指针，注意操作顺序（先连后断）
• 头节点作用：统一空表和非空表操作，简化边界条件处理
• 单链表特性：只能单向遍历，查找第i个元素需从头开始

头插法创建单链表

ListNode* createLinkedListByHeadInsertion(const int arr[], int n) {
    ListNode* head = nullptr; // 初始化头指针为空
   
    for (int i = 0; i < n; ++i) {
        ListNode* newNode = new ListNode(arr[i]); // 创建新节点
        newNode->next = head;  // 新节点指向当前头节点
        head = newNode;        // 更新头指针为新节点
    }
    return head;
}

尾插法创建单链表

ListNode* createLinkedListByTailInsertion(const int arr[], int n) {
    if (n <= 0) return nullptr; // 处理空输入
   
    ListNode* head = nullptr;   // 头指针
    ListNode* tail = nullptr;   // 尾指针
   
    for (int i = 0; i < n; ++i) {
        ListNode* newNode = new ListNode(arr[i]); // 创建新节点
       
        if (!head) {            // 首次插入（链表为空）
            head = tail = newNode;
        } else {                // 后续插入
            tail->next = newNode; // 尾节点指向新节点
            tail = newNode;       // 更新尾指针
        }
    }
    return head;
}

栈与队列

1. 栈

基本概念与存储结构

顺序栈：

#define MAXSIZE 100
typedef struct {
    SElemType *base;
    SElemType *top;
    int stacksize;
} SqStack;

分析：base指向栈底，top指向栈顶元素的下一个位置。栈空时top==base，栈满时top-base==stacksize。

链栈：

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

分析：链栈不需要头节点，栈顶指针即为链表头指针。入栈在表头插入，出栈删除表头节点。

基本操作代码及分析（顺序栈）

1. 初始化

Status InitStack(SqStack &S) {
    S.base = new SElemType[MAXSIZE]; //分配空间
    if (!S.base) exit(OVERFLOW); //分配失败
    S.top = S.base; //栈顶指针指向栈底
    S.stacksize = MAXSIZE;
    return OK;
}

分析：分配固定大小空间，top指针指向base表示空栈。stacksize记录容量，避免每次计算。

1. 入栈

Status Push(SqStack &S, SElemType e) {
    if (S.top – S.base == S.stacksize) return ERROR; //栈满
    *S.top++ = e; //先赋值，后移动栈顶指针
    return OK;
}

分析：先检查栈满，然后在top位置存储元素，再递增top指针。注意*S.top++先取值后自增。

1. 出栈

Status Pop(SqStack &S, SElemType &e) {
    if (S.top == S.base) return ERROR; //栈空
    e = *–S.top; //先移动栈顶指针，再取值
    return OK;
}

分析：先检查栈空，然后递减top指针，再取出元素。注意*–S.top先自减后取值。

链栈基础操作代码实现

1. 初始化

Status InitStack(LinkStack &S) {
    S = NULL;  // 栈顶指针置为空，表示空栈
    return OK;
}

分析：链栈初始化只需将栈顶指针置为NULL，无需预分配空间。时间复杂度为O(1)。

---

1. 入栈

Status Push(LinkStack &S, SElemType e) {
    StackNode *p = new StackNode;  // 创建新结点
    if (!p) exit(OVERFLOW);        // 存储分配失败
    p->data = e;                   // 存储元素值
    p->next = S;                   // 新结点指向原栈顶
    S = p;                         // 栈顶指针更新为新结点
    return OK;
}

分析：

• 在链表头部插入新结点，无需移动其他元素
• 关键操作p->next = S建立前驱关系，S = p更新栈顶
• 时间复杂度O(1)，无栈满问题（仅受内存限制）

---

1. 出栈

Status Pop(LinkStack &S, SElemType &e) {
    if (S == NULL) return ERROR;   // 栈空判断
    StackNode *p = S;              // 临时指针指向栈顶
    e = p->data;                   // 保存栈顶元素值
    S = S->next;                   // 栈顶指针下移
    delete p;                      // 释放原栈顶结点
    return OK;
}

分析：

• 先检查栈空（S == NULL）避免非法操作
• 通过S = S->next直接跳过栈顶结点实现删除
• 需显式释放结点内存防止泄漏
• 时间复杂度O(1)，无需移动元素

---

关键特性总结

操作	核心步骤	时间复杂度	空间特点
初始化	栈顶指针置NULL	O(1)	无预分配空间
入栈	头插法创建新结点	O(1)	动态分配，无栈满限制
出栈	释放栈顶结点并更新指针	O(1)	需手动释放内存

注：链栈优势在于动态内存分配，适用于栈大小变化剧烈的场景；但每个结点需额外存储指针（存储密度<1），且频繁内存操作可能影响性能。实际应用中需根据场景权衡顺序栈与链栈的选择。

典型例题及分析

1. 字符消融处理

Status ProcessCharStack(SqStack &S, SElemType e) {
    if (S.top – S.base >= S.stacksize) return ERROR;
    if (S.top == S.base || *(S.top – 1) != e) *S.top++ = e;
    else S.top–;
    return OK;
}

分析：特殊入栈规则。若栈空或栈顶不等于e，则入栈；否则弹出栈顶。实现字符消融效果，如"aab"变成"b"。

1. 括号匹配验证

Status CheckParentheses(char *str) {
    SqStack S; InitStack(S);
    for (int i = 0; str[i]; i++) {
        if (str[i] == '(' || str[i] == '[') Push(S, str[i]);
        else if (str[i] == ')' || str[i] == ']') {
            if (StackEmpty(S)) return ERROR;
            SElemType top; Pop(S, top);
            if² return ERROR;
        }
    }
    return StackEmpty(S) ? OK : ERROR;
}

分析：左括号入栈，右括号时出栈匹配。最后检查栈是否为空。时间复杂度O(n)，空间复杂度O(n)（最坏情况）。

知识点总结

• LIFO特性：后进先出，栈顶是唯一操作端
• 边界条件：入栈前检查栈满，出栈前检查栈空
• 遍历技巧：原地修改使用双指针，避免使用基础操作函数
• 典型应用：括号匹配、表达式求值、函数调用栈、DFS

2. 队列

基本概念与存储结构

循环队列：

#define M 100
typedef struct {
    QElemType *base;  // 初始化的动态分配存储空间
    int front;        // 头指针
    int rear;         // 尾指针
} SqQueue;

分析：循环队列牺牲一个单元区分空/满。队空：front==rear，队满：(rear+1)%M==front。长度：(rear-front+M)%M。

链队：

typedef struct QNode {
    QElemType data;
    struct Qnode *next;
} QNode, *QueuePtr;
typedef struct {
    QueuePtr front;  // 队头指针
    QueuePtr rear;   // 队尾指针
} LinkQueue;

分析：链队使用带头节点的单链表，front指向头节点，rear指向尾节点。入队在尾部添加，出队在头部删除。

基本操作代码及分析（循环队列）

1. 初始化

Status InitQueue(SqQueue &Q) {
    Q.base = new QElemType[M]; //分配空间
    if (!Q.base) exit(OVERFLOW);
    Q.front = Q.rear = 0; //头尾指针置为0
    return OK;
}

分析：分配空间，front和rear都置为0，表示空队列。头节点不存储数据。

1. 入队

Status EnQueue(SqQueue &Q, QElemType e) {
    if³))
               exit(OVERFLOW);
           NewT->data = T->data;  // 复制根结点
           CopyTree(T->lchild, NewT->lchild);  // 递归复制左子树
           CopyTree(T->rchild, NewT->rchild);  // 递归复制右子树
           return OK;
       }
   }

 分析：递归复制。先复制根结点，再递归复制左右子树。时间复杂度O(n)，空间复杂度O(h)（h为树高，递归栈深度）。

2. 线索二叉树

线索二叉树的结构定义

typedef enum { Link, Thread } PointerTag; // Link=0表示指针，Thread=1表示线索

typedef struct BiThrNode {
    TElemType data;
    struct BiThrNode *lchild, *rchild; // 左右孩子指针
    PointerTag LTag, RTag;             // 左右标志
} BiThrNode, *BiThrTree;

带头结点的二叉树中序线索化

BiThrTree pre; // 全局变量，指向刚刚访问过的结点

void InOrderThreading(BiThrTree &Thrt, BiThrTree T) {
    // 1. 创建头结点
    Thrt = (BiThrTree)malloc(sizeof(BiThrNode));
    if (!Thrt) exit(OVERFLOW);
   
    Thrt->LTag = Link;   // 头结点左指针指向根
    Thrt->RTag = Thread; // 头结点右指针指向遍历序列最后一个结点
    Thrt->rchild = Thrt; // 右指针回指，初始时指向自己
   
    if (!T) {
        // 二叉树为空
        Thrt->lchild = Thrt; // 左指针也回指
    } else {
        // 2. 头结点左指针指向根结点
        Thrt->lchild = T;
       
        // 3. 初始化pre为头结点
        pre = Thrt;
       
        // 4. 中序遍历进行线索化
        InThreading(T);
       
        // 5. 处理最后一个结点
        pre->RTag = Thread;
        pre->rchild = Thrt; // 最后一个结点的后继指向头结点
       
        // 6. 头结点的右指针指向中序遍历的最后一个结点
        Thrt->rchild = pre;
    }
}

void InThreading(BiThrTree p) {
    if (p) {
        InThreading(p->lchild); // 递归线索化左子树
       
        // 处理当前结点p
        if (!p->lchild) {     // p没有左孩子
            p->LTag = Thread; // 将左标志置为线索
            p->lchild = pre;  // 前驱线索指向pre
        }
        if (!pre->rchild) {   // pre没有右孩子
            pre->RTag = Thread; // 将右标志置为线索
            pre->rchild = p;  // 后继线索指向p
        }
       
        pre = p; // 保持pre指向p的前驱
       
        InThreading(p->rchild); // 递归线索化右子树
    }
}

遍历线索二叉树

void InOrderTraverse_Thr(BiThrTree Thrt) {
    BiThrTree p = Thrt->lchild; // p指向根结点
   
    while (p != Thrt) { // 空树或遍历结束时，p==Thrt
        // 找到中序遍历的第一个结点（最左结点）
        while (p->LTag == Link) {
            p = p->lchild;
        }
       
        printf("%c ", p->data); // 访问当前结点
       
        // 沿着后继线索访问所有连续的后继结点
        while (p->RTag == Thread && p->rchild != Thrt) {
            p = p->rchild;
            printf("%c ", p->data); // 访问后继结点
        }
       
        // 转向右子树（如果有）
        p = p->rchild;
    }
}

代码解释说明

1. 线索二叉树结构

• 指针标志：LTag 和 RTag 用于区分指针是指向孩子还是线索
  • Link(0)：指向孩子结点
  • Thread(1)：指向前驱/后继结点
• 头结点作用：使线索二叉树形成一个闭环，便于遍历

1. 中序线索化过程 InOrderThreading()

• 头结点创建与初始化：
  • 头结点左指针指向根结点（非空树）
  • 头结点右指针初始指向自己，最终指向中序遍历最后一个结点
  • LTag = Link（左指针指向孩子），RTag = Thread（右指针为线索）
• 中序线索化核心 InThreading()：

1. 递归线索化左子树：先处理左子树
2. 处理当前结点：

• 若当前结点无左孩子，则将其左指针设为指向前驱的线索
• 若前驱结点无右孩子，则将其右指针设为指向当前结点的线索
• 更新 pre 为当前结点

1. 递归线索化右子树：最后处理右子树

• 该过程本质是将二叉树转换为双向链表，但保留了树的结构特性
• 头尾连接：
  • 最后一个结点的右指针指向头结点（形成闭环）
  • 头结点的右指针指向中序遍历的最后一个结点

1. 遍历线索二叉树 InOrderTraverse_Thr()

• 无栈遍历：利用线索直接找到后继，无需递归或栈
• 遍历步骤：

1. 从根开始，找到中序遍历的第一个结点（最左结点）
2. 访问该结点
3. 沿着后继线索访问所有连续的后继结点
4. 遇到非线索指针（指向右子树），转向右子树并重复步骤1

• 终止条件：当指针回到头结点时，遍历完成

1. 关键特性

• 时间复杂度：线索化 O(n)，遍历 O(n)
• 空间复杂度：线索化 O(h)（递归深度），遍历 O(1)（无需栈空间）
• 应用价值：
  • 避免递归/栈带来的额外空间开销
  • 快速找到任一结点的前驱和后继
  • 适合内存受限或需要频繁遍历的场景

典型例题及分析

1. 非递归中序遍历

void InOrderTraverse(BiTree T) {
    SqStack S; InitStack(S);
    BiTree p = T;
    while (p || !StackEmpty(S)) {
        if (p) {
            Push(S, p);
            p = p->lchild;
        } else {
            Pop(S, p);
            Visit(p->data);
            p = p->rchild;
        }
    }
}

分析：栈模拟递归。沿左链压栈（p不为空时），到达空节点后弹出访问，转向右子树。栈中保存待访问的祖先节点。

1. 判断完全二叉树

Status IsCompleteBiTree(BiTree T) {
    if (!T) return OK;
    SqQueue Q; InitQueue(Q);
    EnQueue(Q, T);
    BiTree p;
    int flag = 0; // 标记是否出现空节点
    while (!QueueEmpty(Q)) {
        DeQueue(Q, p);
        if (!p) flag = 1; // 遇到空节点
        else {
            if (flag) return ERROR; // 空节点后又有非空节点
            EnQueue(Q, p->lchild);
            EnQueue(Q, p->rchild);
        }
    }
    return OK;
}

分析：层次遍历。一旦遇到空节点，后续不能有非空节点。关键点：空指针也要入队，确保正确检测结构。

知识点总结

• 核心性质：
  • 第i层最多2^(i-1)个节点
  • 深度为k的二叉树最多2^k-1个节点
  • n₀ = n₂ + 1（叶子节点数 = 度为2的节点数 + 1）
• 遍历方法：
  • 先序：根→左→右，可用于创建/复制树
  • 中序：左→根→右，二叉排序树中序遍历得有序序列
  • 后序：左→右→根，适合释放树内存
  • 层次：使用队列，适合计算宽度/判断完全二叉树
• 完全二叉树：除最后一层外，其他层都是满的，且最后一层节点靠左排列
• 存储选择：完全二叉树适合顺序存储，一般二叉树适合链式存储

3.哈夫曼树

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// 哈夫曼树结点结构
struct HTNode {
    int weight;  // 结点权值
    int parent;  // 父结点下标（0表示无父结点）
    int lchild;  // 左孩子下标
    int rchild;  // 右孩子下标
};

// 构造哈夫曼树
void CreateHuffmanTree(vector<HTNode>& HT, const vector<int>& weights) {
    int n = weights.size();          // 叶子结点数量
    int m = 2 * n – 1;               // 哈夫曼树总结点数
    HT.resize(m + 1);                // 0号下标 unused，从1开始存储

    // 步骤1：初始化叶子结点（1~n）
    for (int i = 1; i <= n; ++i) {
        HT[i] = { weights[i-1], 0, 0, 0 }; // parent/lchild/rchild初始为0
    }
   
    // 步骤2：初始化非叶子结点（n+1~m）
    for (int i = n + 1; i <= m; ++i) {
        HT[i] = { 0, 0, 0, 0 };
    }

    // 步骤3：构造哈夫曼树（合并n-1次）
    for (int i = n + 1; i <= m; ++i) {
        int min1 = INT_MAX, min2 = INT_MAX;
        int idx1 = 0, idx2 = 0;

        // 选取当前森林中两棵根结点权值最小的树
        for (int j = 1; j < i; ++j) {
            if (HT[j].parent == 0) { // 仅考虑尚未加入树的结点
                if (HT[j].weight < min1) {
                    min2 = min1; idx2 = idx1;
                    min1 = HT[j].weight; idx1 = j;
                } else if (HT[j].weight < min2) {
                    min2 = HT[j].weight; idx2 = j;
                }
            }
        }

        // 合并最小两棵树
        HT[idx1].parent = i;
        HT[idx2].parent = i;
        HT[i].lchild = idx1;   // 最小权值作为左子树
        HT[i].rchild = idx2;   // 次小权值作为右子树
        HT[i].weight = min1 + min2; // 新结点权值=两子树权值和
    }
}

// 测试示例
int main() {
    vector<int> weights = {5, 29, 7, 8, 14, 23, 3, 11}; // 示例权值集合
    vector<HTNode> huffmanTree;
   
    CreateHuffmanTree(huffmanTree, weights);
   
    // 输出哈夫曼树结构（验证用）
    cout << "结点\t权值\t父结点\t左孩子\t右孩子" << endl;
    for (size_t i = 1; i < huffmanTree.size(); ++i) {
        cout << i << "\t"
             << huffmanTree[i].weight << "\t"
             << huffmanTree[i].parent << "\t"
             << huffmanTree[i].lchild << "\t"
             << huffmanTree[i].rchild << endl;
    }
    return 0;
}

---

关键步骤解析

1. 数据结构设计

• HTNode 结构体：
  • weight：存储结点权值（叶子结点为原始权值，非叶子结点为子树权值和）
  • parent：父结点下标（0表示无父结点，即当前树为独立树）
  • lchild/rchild：左右孩子下标（0表示无孩子）
• 数组存储：
  • 大小 2n-1（n为叶子结点数），1~n 存储叶子结点，n+1~2n-1 存储合并生成的新结点
  • 0号下标弃用：符合"下标从1开始"的约定

2. 构造过程

• 初始化：
  • 前n个位置（1~n）初始化为叶子结点，权值来自输入，parent=0表示独立树
  • 后n-1个位置（n+1~2n-1）预留为非叶子结点
• 贪心合并（循环n-1次）：

1. 选最小两棵树：遍历当前所有parent=0的结点，找到权值最小的两个（min1和min2）
2. 更新父子关系：

• 两最小结点的parent指向新结点下标i
• 新结点i的lchild和rchild分别指向两最小结点

1. 计算新权值：HT[i].weight = min1 + min2

• 终止条件：当只剩1棵树时（即parent=0的结点只剩1个），构造完成

3. 核心特性

• 时间复杂度：O(n²)（每次合并需遍历O(n)个结点，共n-1次合并）
• 空间复杂度：O(n)（仅需线性大小的数组）
• 正确性保障：
  • 通过parent字段标记结点是否已加入树中，避免重复选取
  • 严格遵循贪心策略：每次合并当前最小权值的两棵树，确保全局WPL最小

2. 二叉排序树

基本概念

二叉排序树（BST）：左子树所有节点值 < 根节点值 < 右子树所有节点值。中序遍历得递增序列。

基本操作代码及分析

1. 查找

BSTree SearchBST(BSTree T, KeyType key) {
    if⁴;
        T->data = e; T->lchild = T->rchild = NULL;
        return OK;
    }
    if (e == T->data) return ERROR; // 元素已存在
    if (e < T->data) return InsertBST(T->lchild, e);
    else return InsertBST(T->rchild, e);
}

分析：递归查找插入位置。空处创建新节点；值已存在返回错误；否则递归插入左/右子树。

1. 删除

Status DeleteBST(BSTree &T, int key) {
    if (!T) return ERROR;
    if (key < T->data) return DeleteBST(T->lchild, key);
    if (key > T->data) return DeleteBST(T->rchild, key);
    // 找到待删节点
    if (T->lchild && T->rchild) { // 有两个子节点
        BSTree p = T->rchild;
        while (p->lchild) p = p->lchild; // 找右子树最小值
        T->data = p->data; // 替换值
        return DeleteBST(T->rchild, p->data); // 删除替代节点
    } else { // 0或1个子节点
        BSTree p = T;
        T = (T->lchild) ? T->lchild : T->rchild;
        free(p);
        return OK;
    }
}

分析：分三种情况：

• 叶子节点：直接删除
• 单子节点：子节点替代
• 双子节点：用右子树最小值（或左子树最大值）替代，再删除替代节点

典型例题及分析

1. 验证平衡二叉树

Status IsAVL(BSTree T) {
    if (!T) return 1;
    int lh = Height(T->lchild); // 需实现Height函数
    int rh = Height(T->rchild);
    if (abs(lh – rh) > 1) return 0;
    return IsAVL(T->lchild) && IsAVL(T->rchild);
}

分析：递归判断平衡性。平衡条件：左右子树高度差不超过1，且左右子树均平衡。时间复杂度O(n²)，可优化为O(n)。

知识点总结

• BST性质：左子树<根<右子树，中序遍历结果递增，平均查找O(log n)
• 删除难点：双子节点删除时，用后继/前驱替代，保持BST性质
• 平衡条件：|左子树高度-右子树高度|≤1，且子树平衡
• 平衡维护：AVL树通过旋转（LL,RR,LR,RL）保持平衡，红黑树通过着色和旋转保持近似平衡

图

1. 图的表示

邻接矩阵

#define MaxInt 32767  // 表示极大值，即∞
#define MVNum 100     // 最大顶点数
typedef char VerTexType;  // 假设顶点的数据类型为字符型
typedef int ArcType;      // 假设边的权值类型为整型
typedef struct {
    VerTexType vexs[MVNum];          // 顶点表
    ArcType arcs[MVNum][MVNum];      // 邻接矩阵
    int vexnum, arcnum;              // 图的当前点数和边数
} AMGraph;

分析：n个顶点用n×n矩阵表示。arcsi=1(或权值)表示有边，0(或∞)表示无边。无向图矩阵对称。

邻接表

typedef struct ArcNode {   // 边结点
    int adjvex;            // 该边所指向的顶点的位置
    struct ArcNode *nextarc;  // 指向下一条边的指针
    OtherInfo info;        // 和边相关的信息
} ArcNode;
typedef struct VNode {
    VerTexType data;       // 顶点信息
    ArcNode *firstarc;     // 指向第一条依附该顶点的边的指针
} VNode, AdjList[MVNum];   // AdjList表示邻接表类型
typedef struct {
    AdjList vertices;      // 邻接表
    int vexnum, arcnum;    // 图的当前顶点数和边数
} ALGraph;

分析：边集用单链表存储，适合稀疏图。无向图每条边存两次，有向图只存出边。

2. 图的算法

基本操作代码及分析

1. 邻接矩阵创建无向图

Status CreateUDG(MGraph &G) {
    int i, j, v1, v2;
    for (i = 0; i < G.vexnum; i++)
        for (j = 0; j < G.vexnum; j++)
            G.arcs[i][j] = 0; // 初始化邻接矩阵

    for (i = 0; i < G.arcnum; i++) {
        scanf("%d%d", &v1, &v2); // 输入边的两个顶点
        G.arcs[v1][v2] = 1;
        G.arcs[v2][v1] = 1; // 无向图，对称设置
    }
    return OK;
}

分析：先初始化矩阵全0，然后读入边，对称设置连接关系。注意无向图的对称性，避免遗漏。

1. 邻接表创建无向图

Status CreateUDG(ALGraph &G) {
    int i, k;
    VerTexType v1, v2;
    ArcNode *p1, *p2;
   
    // 输入顶点数和边数
    scanf("%d %d", &G.vexnum, &G.arcnum);
   
    // 初始化顶点表
    for (i = 0; i < G.vexnum; i++) {
        scanf(" %c", &G.vertices[i].data);  // 跳过空白字符
        G.vertices[i].firstarc = NULL;      // 初始化边表指针
    }
   
    // 创建边表
    for (k = 0; k < G.arcnum; k++) {
        scanf(" %c %c", &v1, &v2);  // 读取边的两个顶点
       
        // 查找顶点位置
        int i1 = -1, i2 = -1;
        for (i = 0; i < G.vexnum; i++) {
            if (G.vertices[i].data == v1) i1 = i;
            if (G.vertices[i].data == v2) i2 = i;
        }
        if (i1 == -1 || i2 == -1) return ERROR;  // 顶点不存在
       
        // 创建v1指向v2的边（头插法）
        p1 = (ArcNode *)malloc(sizeof(ArcNode));
        p1->adjvex = i2;
        p1->nextarc = G.vertices[i1].firstarc;
        G.vertices[i1].firstarc = p1;
       
        // 创建v2指向v1的边（无向图双向连接）
        p2 = (ArcNode *)malloc(sizeof(ArcNode));
        p2->adjvex = i1;
        p2->nextarc = G.vertices[i2].firstarc;
        G.vertices[i2].firstarc = p2;
       
        // 注意：实际应用中需初始化OtherInfo字段
    }
    return OK;
}

分析：

1. 双表构建：无向图的每条边需在两个顶点的邻接表中分别插入边结点（如边A-B，需在A的边表插入指向B的结点，同时在B的边表插入指向A的结点）。
2. 时间复杂度：

• 顶点初始化：O(n)
• 边处理：每条边需O(n)时间查找顶点位置，总时间复杂度O(n+e·n)
• 优化建议：实际工程中可建立顶点值→下标的哈希映射，将查找优化至O(1)

3. 空间特性：

• 顶点表：固定O(n)空间
• 边表：无向图存储2e个边结点（e为边数），空间复杂度O(n+2e)

4. 头插法优势：新边插入链表头部，操作时间复杂度O(1)，避免遍历链表
5. 关键细节：

• 输入顶点时使用" %c"跳过空白字符（含换行符）
• 需检查顶点存在性（i1/i2为-1时返回错误）
• 内存安全：实际应用需增加malloc失败检查
• 未处理字段：示例未初始化OtherInfo，工程中需补充相关逻辑

对比邻接矩阵：当图稀疏时（e ≪ n²），邻接表空间效率显著优于邻接矩阵（O(n+e) vs O(n²)），但牺牲了边查询的O(1)时间复杂度。

1. 深度优先遍历

void DFS(MGraph G, int v) {
    visited[v] = TRUE;
    Visit(v); // 访问当前顶点
    for (int w = 0; w < G.vexnum; w++) {
        if (G.arcs[v][w] == 1 && !visited[w]) // 寻找邻接点
            DFS(G, w);
    }
}

分析：递归遍历。标记访问，访问顶点，递归遍历所有未访问邻接点。适合连通性检测，时间复杂度O(n²)（邻接矩阵）。

1. 广度优先遍历

void BFS(MGraph G, int v) {
    SqQueue Q; InitQueue(Q);
    visited[v] = TRUE;
    Visit(v);
    EnQueue(Q, v);
    while (!QueueEmpty(Q)) {
        DeQueue(Q, v);
        for (int w = 0; w < G.vexnum; w++) {
            if (G.arcs[v][w] == 1 && !visited[w]) {
                visited[w] = TRUE;
                Visit(w);
                EnQueue(Q, w);
            }
        }
    }
}

分析：队列辅助遍历。先访问起始顶点并入队，然后出队访问其所有邻接点，将它们入队。适合最短路径（无权图）。

1. 判断有向图是否有环（拓扑排序法）

Status HasCycle(ALGraph G) {
    int indegree[MAX_VERTEX_NUM] = {0};
    for (int i = 0; i < G.vexnum; i++)
        for (int j = 0; j < G.vexnum; j++)
            if (G.arcs[i][j]) indegree[j]++; // 计算入度

    SqQueue Q; InitQueue(Q);
    for (int i = 0; i < G.vexnum; i++)
        if (indegree[i] == 0) EnQueue(Q, i); // 入度为0的顶点入队

    int count = 0;
    while (!QueueEmpty(Q)) {
        DeQueue(Q, v); count++;
        for (int w = 0; w < G.vexnum; w++) {
            if (G.arcs[v][w]) {
                if (–indegree[w] == 0) EnQueue(Q, w);
            }
        }
    }
    return (count < G.vexnum) ? OK : ERROR; // 有环返回OK
}

分析：拓扑排序判断环。计算入度，入度为0的顶点入队。每次出队一个顶点，减少其邻接点入度，若入度为0则入队。若最后访问顶点数小于总顶点数，说明有环。

知识点总结

• 存储选择：
  • 邻接矩阵：适合稠密图，空间O(n²)，能快速判断边存在
  • 邻接表：适合稀疏图，空间O(n+e)，能高效遍历邻接点
• 遍历特性：
  • DFS：递归/栈实现，深优先，适合连通分量、路径搜索
  • BFS：队列实现，广优先，适合最短路径、层次遍历
• 环检测：
  • 有向图：拓扑排序（入度为0的顶点计数）
  • 无向图：DFS时检查回边（已访问但非父节点）
• 访问标志：全局visited数组防止重复访问，遍历前必须初始化

图的度、入度、出度计算算法

一、邻接矩阵实现

// 无向图：计算所有顶点的度
void CalculateDegree_AM_UG(AMGraph G, int degree[]) {
    for (int i = 0; i < G.vexnum; i++) {
        degree[i] = 0;
        for (int j = 0; j < G.vexnum; j++) {
            if (G.arcs[i][j] != 0 && G.arcs[i][j] != MaxInt) { // 跳过无边位置
                degree[i]++;
            }
        }
    }
}

// 有向图：计算出度
void CalculateOutDegree_AM_DG(AMGraph G, int outdegree[]) {
    for (int i = 0; i < G.vexnum; i++) {
        outdegree[i] = 0;
        for (int j = 0; j < G.vexnum; j++) {
            if (G.arcs[i][j] != 0 && G.arcs[i][j] != MaxInt) {
                outdegree[i]++;
            }
        }
    }
}

// 有向图：计算入度
void CalculateInDegree_AM_DG(AMGraph G, int indegree[]) {
    for (int j = 0; j < G.vexnum; j++) {
        indegree[j] = 0;
        for (int i = 0; i < G.vexnum; i++) {
            if (G.arcs[i][j] != 0 && G.arcs[i][j] != MaxInt) {
                indegree[j]++;
            }
        }
    }
}

算法解释（邻接矩阵）：

1. 无向图度计算

• 遍历顶点i对应的行（或列），统计非零/非∞元素个数
• 时间复杂度：O(n²)，需扫描整个矩阵
• 空间优化：利用矩阵对称性，只计算上三角可优化至O(n²/2)

2. 有向图出度/入度计算

• 出度：统计顶点i所在行的非零元素
• 入度：统计顶点i所在列的非零元素
• 关键特性：入度计算需转置访问，无法避免O(n²)时间复杂度
• 适用场景：稠密图（边数接近n²）时效率较高

---

二、邻接表实现

// 无向图：计算所有顶点的度
void CalculateDegree_AL_UG(ALGraph G, int degree[]) {
    for (int i = 0; i < G.vexnum; i++) {
        degree[i] = 0;
        ArcNode* p = G.vertices[i].firstarc;
        while (p) {
            degree[i]++;  // 每条边贡献1度
            p = p->nextarc;
        }
    }
}

// 有向图：计算出度（直接统计链表长度）
void CalculateOutDegree_AL_DG(ALGraph G, int outdegree[]) {
    for (int i = 0; i < G.vexnum; i++) {
        outdegree[i] = 0;
        ArcNode* p = G.vertices[i].firstarc;
        while (p) {
            outdegree[i]++;
            p = p->nextarc;
        }
    }
}

// 有向图：计算入度（全局扫描）
void CalculateInDegree_AL_DG(ALGraph G, int indegree[]) {
    // 1. 初始化入度数组
    for (int i = 0; i < G.vexnum; i++) indegree[i] = 0;
   
    // 2. 遍历所有边
    for (int i = 0; i < G.vexnum; i++) {
        ArcNode* p = G.vertices[i].firstarc;
        while (p) {
            indegree[p->adjvex]++;  // 被指向顶点的入度+1
            p = p->nextarc;
        }
    }
}

算法解释（邻接表）：

1. 无向图度计算

• 顶点度 = 其邻接链表的长度
• 时间复杂度：O(n+e)，每个边结点仅访问1次
• 空间效率：仅需O(n)额外空间存储度数组

2. 有向图出度计算

• 与无向图相同，直接统计链表长度
• 优势：O(1)时间可获取单个顶点出度（若存储链表长度）

3. 有向图入度计算

• 核心思想：全局扫描所有边，统计指向每个顶点的次数
• 时间复杂度：O(n+e)，线性时间
• 优化方案：
  • 构建逆邻接表（存储入边）可使入度查询降至O(1)
  • 维护入度动态计数器（增删边时同步更新）
• 稀疏图优势：当 e ≪ n² 时，比邻接矩阵快1-2个数量级

---

关键对比总结

指标	邻接矩阵	邻接表
无向图度计算	O(n²) 时间	O(n+e) 时间
有向图入度	必须扫描整列 O(n²)	全局扫描 O(n+e)
空间效率	固定 O(n²) 空间	稀疏图 O(n+e) 空间优势显著
最佳适用场景	稠密图（e > n log n）	稀疏图（e < n log n）
动态操作	边修改 O(1)	边删除需 O(e/n) 平均时间

工程建议：

1. 对于需要频繁查询入度的有向图，建议同时维护正向邻接表（出边）和逆向邻接表（入边）
2. 在动态图场景中，应设计度计数器，在增删边时同步更新（避免实时计算）
3. 超大规模图处理（如社交网络）优先选择邻接表，结合哈希映射优化顶点查找

Prim算法：最小生成树(MST)

目的

求解无向连通带权图的最小生成树，即连接所有顶点且边权总和最小的子图。

适用对象

• 无向连通带权图
• 稠密图效果更佳（邻接矩阵实现时）

算法讲解

Prim算法是贪心策略：从任一顶点开始，每次选择连接已选顶点集和未选顶点集的最小权值边，逐步扩展生成树。

核心思想：

• 维护两个集合：已加入MST的顶点集S和未加入的顶点集V-S
• 对每个顶点v∈V-S，维护其与S的最短连接边
• 每次将最短连接边对应的顶点加入S，更新相关连接信息

实行过程（手算示例）

图例：5个顶点(A,B,C,D,E)，边权如下

A-B:2, A-C:3, A-D:7
B-C:4, B-D:5
C-D:1, C-E:6
D-E:8

步骤：

1. 选择A作为起始点，S={A}

• 与A相连边：AB=2, AC=3, AD=7
• 最小边：AB=2

2. S={A,B}

• 新增连接：BC=4, BD=5
• 当前最短连接：AC=3（A到C）, BC=4（B到C）, BD=5（B到D）
• 最小边：AC=3

3. S={A,B,C}

• 新增连接：CD=1, CE=6
• 当前最短连接：CD=1, CE=6, BD=5
• 最小边：CD=1

4. S={A,B,C,D}

• 新增连接：DE=8
• 当前最短连接：CE=6, DE=8
• 最小边：CE=6

5. S={A,B,C,D,E}，算法结束

• MST边集：{AB, AC, CD, CE}
• 总权值：2+3+1+6=12

代码实现

void MiniSpanTree_Prim(AMGraph G, int start) {
    int min, i, j, k;
    int adjvex[MVNum];  // 保存相关顶点下标
    int lowcost[MVNum]; // 保存相关顶点间权值
   
    // 初始化
    for (i = 0; i < G.vexnum; i++) {
        lowcost[i] = G.arcs[start][i]; // 将start与其他顶点的权值存入
        adjvex[i] = start;             // 初始化父节点为start
    }
    lowcost[start] = 0; // start加入MST集合
   
    // MST需要n-1条边
    for (i = 1; i < G.vexnum; i++) {
        min = MaxInt;
        j = 1; k = 0;
       
        // 寻找最小权值边
        while (j < G.vexnum) {
            if (lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
            j++;
        }
       
        printf("(%c, %c)\n", G.vexs[adjvex[k]], G.vexs[k]);
        lowcost[k] = 0; // 顶点k加入MST
       
        // 更新lowcost和adjvex
        for (j = 0; j < G.vexnum; j++) {
            if (lowcost[j] != 0 && G.arcs[k][j] < lowcost[j]) {
                lowcost[j] = G.arcs[k][j];
                adjvex[j] = k;
            }
        }
    }
}

---

Kruskal算法：最小生成树(MST)

目的

求解无向连通带权图的最小生成树，与Prim相同但策略不同。

适用对象

• 无向连通带权图
• 稀疏图效果更佳（边数较少时）

算法讲解

Kruskal算法是贪心策略：将所有边按权值排序，依次选择最小边，若该边连接两个不同连通分量则加入MST。

核心思想：

• 按权值升序排序所有边
• 使用并查集(Union-Find)高效判断边是否会形成环
• 选择不形成环的最小权值边，直到MST包含n-1条边

实行过程（手算示例）

图例：同Prim算法示例图

步骤：

1. 按权值排序边：CD(1), AB(2), AC(3), BC(4), BD(5), CE(6), AD(7), DE(8)
2. 选择CD(1)：MST={CD}

• 连通分量：{C,D}, {A}, {B}, {E}

3. 选择AB(2)：MST={CD, AB}

• 连通分量：{C,D}, {A,B}, {E}

4. 选择AC(3)：MST={CD, AB, AC}

• 连通分量：{A,B,C,D}, {E}

5. 考虑BC(4)：B和C已连通，跳过
6. 考虑BD(5)：B和D已连通，跳过
7. 选择CE(6)：MST={CD, AB, AC, CE}

• 连通分量：{A,B,C,D,E}
• 已有4条边(n-1=4)，算法结束

8. MST边集：{CD, AB, AC, CE}

• 总权值：1+2+3+6=12

代码实现

// 并查集相关操作
int find(int parent[], int i) {
    while (parent[i] != i)
        i = parent[i];
    return i;
}

void unionSet(int parent[], int x, int y) {
    int xset = find(parent, x);
    int yset = find(parent, y);
    parent[xset] = yset;
}

// 边结构定义
typedef struct {
    int begin;
    int end;
    int weight;
} Edge;

void MiniSpanTree_Kruskal(AMGraph G) {
    Edge edges[MVNum*(MVNum-1)/2];
    int edgeCount = 0;
   
    // 收集所有边（无向图只取一半）
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = i+1; j < G.vexnum; j++) {
            if (G.arcs[i][j] != MaxInt) {
                edges[edgeCount].begin = i;
                edges[edgeCount].end = j;
                edges[edgeCount].weight = G.arcs[i][j];
                edgeCount++;
            }
        }
    }
   
    // 按权重排序（使用插入排序）
    for (int i = 1; i < edgeCount; i++) {
        Edge key = edges[i];
        int j = i – 1;
        while (j >= 0 && edges[j].weight > key.weight) {
            edges[j+1] = edges[j];
            j = j – 1;
        }
        edges[j+1] = key;
    }
   
    // 初始化并查集
    int parent[MVNum];
    for (int i = 0; i < G.vexnum; i++)
        parent[i] = i;
   
    // Kruskal核心
    printf("最小生成树边集:\n");
    int mstEdgeCount = 0;
    for (int i = 0; i < edgeCount; i++) {
        int n = find(parent, edges[i].begin);
        int m = find(parent, edges[i].end);
       
        if (n != m) { // 不在同一连通分量
            unionSet(parent, n, m);
            printf("(%c, %c) = %d\n",
                   G.vexs[edges[i].begin],
                   G.vexs[edges[i].end],
                   edges[i].weight);
            mstEdgeCount++;
           
            if (mstEdgeCount == G.vexnum-1)
                break;
        }
    }
}

---

Dijkstra算法：单源最短路径

目的

求解带权有向图/无向图中单源最短路径问题，即从一个源点到其他所有顶点的最短路径。

适用对象

• 有向图或无向图
• 边权必须非负
• 单源最短路径场景

算法讲解

Dijkstra算法是贪心策略：维护已确定最短路径的顶点集S，每次将V-S中距离源点最近的顶点加入S，并更新路径。

核心思想：

• 初始化：源点距离为0，其他为∞
• 维护两个集合：已确定最短路径的S和未确定的V-S
• 每次从V-S中选择距离最小的顶点u加入S
• 用u更新V-S中顶点的距离：dist[v] = min(dist[v], dist[u] + w(u,v))

实行过程（手算示例）

图例：5个顶点(A,B,C,D,E)，有向边权如下

A→B:10, A→C:3
B→C:1, B→D:2
C→B:4, C→D:8, C→E:2
D→E:7
E→D:9

以A为源点：

1. 初始化：

• S = {A}
• dist = [0, 10, 3, ∞, ∞]
• path = [A, A, A, -, -]

2. 选择C（距离3）：

• S = {A,C}
• 通过C更新：
  • B: min(10, 3+4)=7
  • D: min(∞, 3+8)=11
  • E: min(∞, 3+2)=5
• dist = [0, 7, 3, 11, 5]
• path = [A, C, A, C, C]

3. 选择E（距离5）：

• S = {A,C,E}
• 通过E更新：
  • D: min(11, 5+9)=11（不变）
• dist = [0, 7, 3, 11, 5]
• path = [A, C, A, C, C]

4. 选择B（距离7）：

• S = {A,C,E,B}
• 通过B更新：
  • C: 已在S中
  • D: min(11, 7+2)=9
• dist = [0, 7, 3, 9, 5]
• path = [A, C, A, B, C]

5. 选择D（距离9）：

• S = {A,C,E,B,D}
• 无更新
• dist = [0, 7, 3, 9, 5]
• path = [A, C, A, B, C]

6. 最短路径结果：

• A→A: 0
• A→B: 7 (A→C→B)
• A→C: 3 (A→C)
• A→D: 9 (A→C→B→D)
• A→E: 5 (A→C→E)

代码实现

void ShortestPath_DIJKSTRA(AMGraph G, int v0) {
    int i, j, k, min;
    int final[MVNum];   // 标记顶点是否已找到最短路径
    int dist[MVNum];    // 保存最短路径长度
    int path[MVNum];    // 保存最短路径前驱
   
    // 初始化
    for (i = 0; i < G.vexnum; i++) {
        final[i] = 0;
        dist[i] = G.arcs[v0][i]; // 初始距离
        if (dist[i] < MaxInt && i != v0)
            path[i] = v0;       // 有直接路径
        else
            path[i] = -1;       // 无直接路径
    }
    dist[v0] = 0;      // 源点到自身距离为0
    final[v0] = 1;     // 源点加入S集合
   
    // 主循环，每次求得v0到一个顶点的最短路径
    for (i = 1; i < G.vexnum; i++) {
        min = MaxInt;
        // 选择当前距离最小的顶点
        for (j = 0; j < G.vexnum; j++) {
            if (!final[j] && dist[j] < min) {
                k = j;
                min = dist[j];
            }
        }
        final[k] = 1; // 将顶点k加入S集合
       
        // 更新距离
        for (j = 0; j < G.vexnum; j++) {
            if (!final[j] && (min + G.arcs[k][j] < dist[j])) {
                dist[j] = min + G.arcs[k][j];
                path[j] = k; // 更新前驱
            }
        }
    }
   
    // 输出结果
    for (i = 0; i < G.vexnum; i++) {
        if (i != v0) {
            printf("%c→%c: 最短距离=%d, 路径: ", G.vexs[v0], G.vexs[i], dist[i]);
            // 逆向输出路径
            int stack[MVNum], top = -1;
            j = i;
            while (j != v0) {
                stack[++top] = j;
                j = path[j];
            }
            stack[++top] = v0;
           
            // 正向输出路径
            printf("%c", G.vexs[stack[top–]]);
            while (top >= 0)
                printf("→%c", G.vexs[stack[top–]]);
            printf("\n");
        }
    }
}

---

算法对比总结

特性	Prim算法	Kruskal算法	Dijkstra算法
主要用途	无向图MST	无向图MST	单源最短路径
适用图类型	无向连通图	无向连通图	有向/无向图(边权≥0)
时间复杂度	O(n²)（邻接矩阵）	O(e log e)	O(n²)（邻接矩阵）
空间复杂度	O(n²)	O(e)	O(n²)
最佳场景	稠密图	稀疏图	边权非负的最短路径
核心数据结构	优先队列/数组	并查集+排序	优先队列/数组

工程建议：

1. 对于稠密图(边数接近n²)，Prim(邻接矩阵)通常比Kruskal更高效
2. 对于稀疏图(边数接近n)，Kruskal通常更优
3. Dijkstra不适用于存在负权边的图，此时应选择Bellman-Ford算法
4. 现代实现中，这三种算法通常使用优先队列(堆)优化，可将时间复杂度降低至O(e log n)

拓扑排序算法详解

基本原理

拓扑排序是对有向无环图（Directed Acyclic Graph, DAG）的一种线性排序，使得对于图中任意两个顶点u和v，若存在一条从u到v的路径，则在排序结果中u出现在v之前。

核心思想：

1. 从有向图中选取一个没有前驱（入度为0）的顶点输出
2. 从图中删除该顶点及其所有出边
3. 重复上述两步，直到图中不再存在入度为0的顶点
4. 若最终输出顶点数少于原图顶点数，表明图中存在环，无法完成拓扑排序

应用场景：

• 工程项目的工序安排
• 课程学习的先后顺序
• 编译系统的模块依赖
• 数据处理的流水线调度

数据结构设计

1. 邻接表结构扩展

#define MVNum 100  // 最大顶点数
typedef char VerTexType;  // 顶点信息类型
typedef int ArcType;      // 弧权值类型

// 边结点
typedef struct ArcNode {
    int adjvex;           // 该弧所指向的顶点位置
    struct ArcNode *nextarc;  // 指向下一条弧的指针
    ArcType info;         // 弧相关信息
} ArcNode;

// 顶点结点
typedef struct VNode {
    VerTexType data;      // 顶点信息
    int indegree;         // 顶点入度（拓扑排序专用）
    ArcNode *firstarc;    // 指向第一条依附该顶点的弧
} VNode, AdjList[MVNum];

// 有向图
typedef struct {
    AdjList vertices;     // 邻接表
    int vexnum, arcnum;   // 图的当前顶点数和弧数
} ALGraph;

1. 辅助数据结构

typedef int SElemType;    // 栈元素类型
typedef struct {
    SElemType *base;      // 栈底指针
    SElemType *top;       // 栈顶指针
    int stacksize;        // 栈容量
} SqStack;

// 栈操作函数声明
Status InitStack(SqStack *S);
Status Push(SqStack *S, SElemType e);
Status Pop(SqStack *S, SElemType *e);
Status StackEmpty(SqStack S);

拓扑排序执行过程

1. 算法步骤
2. 初始化：

• 计算图中每个顶点的入度
• 将所有入度为0的顶点入栈

3. 主循环（当栈非空时）：

• 从栈中弹出一个顶点v，输出v
• 将v加入拓扑序列
• 遍历v的所有邻接点w：
  • 将w的入度减1
  • 若w的入度变为0，则将w入栈

4. 环路检测：

• 若输出顶点数等于图的顶点数，则成功完成拓扑排序
• 否则，图中存在环，无法进行拓扑排序

5. 手算示例

示例图：有向图 G=(V,E)，其中 V={A,B,C,D,E,F}，E={(A,B),(A,C),(B,D),(C,D),(C,E),(D,F),(E,F)}

初始入度：

• A: 0
• B: 1
• C: 1
• D: 2
• E: 1
• F: 2

拓扑排序步骤：

1. 初始化：入度为0的顶点：A → 入栈 [A]
2. 弹出A：输出A

• 删除A的出边：(A,B),(A,C)
• 更新入度：B:0, C:0
• 入度为0的顶点：B,C → 入栈 [B,C]（假设B先入栈）

3. 弹出B：输出B

• 删除B的出边：(B,D)
• 更新入度：D:1
• 无新入度为0的顶点

4. 弹出C：输出C

• 删除C的出边：(C,D),(C,E)
• 更新入度：D:0, E:0
• 入度为0的顶点：D,E → 入栈 [D,E]

5. 弹出D：输出D

• 删除D的出边：(D,F)
• 更新入度：F:1
• 无新入度为0的顶点

6. 弹出E：输出E

• 删除E的出边：(E,F)
• 更新入度：F:0
• 入度为0的顶点：F → 入栈 [F]

7. 弹出F：输出F

• 无出边
• 栈为空

8. 验证：输出顶点数=6=原图顶点数，拓扑排序成功

可能的拓扑序列：

• A→B→C→D→E→F
• A→B→C→E→D→F
• A→C→B→D→E→F
• A→C→B→E→D→F
• A→C→E→B→D→F

注：拓扑序列不唯一，取决于入度为0顶点的选择顺序

代码实现

Status TopologicalSort(ALGraph G) {
    SqStack S;
    int i, count, k;
    ArcNode *p;
   
    // 1. 初始化栈
    InitStack(&S);
   
    // 2. 求各顶点入度
    FindInDegree(G);  // 此函数计算各顶点入度，存入vertices[i].indegree
   
    // 3. 将入度为0的顶点入栈
    for (i = 0; i < G.vexnum; i++) {
        if (G.vertices[i].indegree == 0) {
            Push(&S, i);
        }
    }
   
    // 4. 初始化计数器
    count = 0;
   
    // 5. 主循环：栈非空时执行
    while (!StackEmpty(S)) {
        // 5.1 弹出栈顶顶点
        Pop(&S, &i);
        printf("%c ", G.vertices[i].data);  // 输出顶点
        count++;  // 计数器加1
       
        // 5.2 遍历顶点i的所有邻接点
        for (p = G.vertices[i].firstarc; p; p = p->nextarc) {
            k = p->adjvex;  // 邻接点序号
           
            // 5.3 入度减1
            if (!(–(G.vertices[k].indegree))) {
                Push(&S, k);  // 若入度为0，入栈
            }
        }
    }
   
    // 6. 环路检测
    if (count < G.vexnum) {
        printf("\n图中存在环路，无法进行拓扑排序\n");
        return ERROR;
    } else {
        printf("\n拓扑排序成功\n");
        return OK;
    }
}

辅助函数实现

// 求各顶点入度
void FindInDegree(ALGraph G) {
    int i;
    ArcNode *p;
   
    // 1. 初始化所有顶点入度为0
    for (i = 0; i < G.vexnum; i++) {
        G.vertices[i].indegree = 0;
    }
   
    // 2. 遍历所有边，统计入度
    for (i = 0; i < G.vexnum; i++) {
        p = G.vertices[i].firstarc;
        while (p) {
            G.vertices[p->adjvex].indegree++;
            p = p->nextarc;
        }
    }
}

// 栈操作实现
Status InitStack(SqStack *S) {
    S->base = (SElemType *)malloc(MVNum * sizeof(SElemType));
    if (!S->base) return OVERFLOW;
    S->top = S->base;
    S->stacksize = MVNum;
    return OK;
}

Status Push(SqStack *S, SElemType e) {
    if (S->top – S->base >= S->stacksize) return ERROR;
    *(S->top++) = e;
    return OK;
}

Status Pop(SqStack *S, SElemType *e) {
    if (S->top == S->base) return ERROR;
    *e = *(–(S->top));
    return OK;
}

Status StackEmpty(SqStack S) {
    return S.top == S.base;
}

代码讲解

1. 核心算法流程

• 初始化阶段：计算每个顶点的入度，将入度为0的顶点入栈
• 主处理阶段：
  • 循环执行"出栈→输出→减少邻接点入度→入度为0则入栈"的操作
  • 使用计数器记录已输出顶点数量
• 终止检测：根据计数器值判断图中是否存在环路

1. 关键技术点

• 入度计算：通过遍历所有边，统计每个顶点被指向的次数
• 动态更新：删除顶点时，动态更新其邻接点入度
• 环路检测：通过比较输出顶点数与总顶点数
• 栈的应用：使用栈暂存所有入度为0的顶点，满足"后进先出"的特性

1. 算法复杂度分析

• 时间复杂度：O(n+e)
  • 求入度：遍历所有边，O(e)
  • 拓扑排序：每个顶点和每条边都被处理一次，O(n+e)
• 空间复杂度：O(n)
  • 栈空间：最多存储n个顶点
  • 辅助数组：入度数组占用O(n)空间

1. 结构化设计：将功能分解为多个子函数（FindInDegree、栈操作等）
2. 状态返回：使用Status类型（OK/ERROR）表示操作结果
3. 参数传递：采用引用传递（&G）实现原地修改
4. 错误处理：包含环路检测，保证算法鲁棒性
5. 内存管理：显式申请/释放栈空间，体现C语言特性

改进与变种

1. 队列实现：
2. // 使用队列替代栈，得到不同的拓扑序列
   Status TopologicalSort_Queue(ALGraph G) {
       LinkQueue Q;
       // 初始化、入度计算等相同
       InitQueue(&Q);
       // 将入度为0的顶点入队
       while (!QueueEmpty(Q)) {
           DeQueue(&Q, &i);
           // 处理逻辑相同
           if (入度为0) EnQueue(&Q, k);
       }
       // 环路检测相同
   }
3. 返回拓扑序列：
4. // 修改算法，返回拓扑序列而非直接输出
   Status GetTopologicalSequence(ALGraph G, int *topoSeq) {
       // …相同初始化
       int index = 0;
       while (!StackEmpty(S)) {
           Pop(&S, &i);
           topoSeq[index++] = i;  // 保存到序列
           // …相同处理
       }
       return count == G.vexnum ? OK : ERROR;
   }
5. 关键路径应用：

• 拓扑排序是有向无环图求关键路径的第一步
• 基于拓扑序列，可高效计算事件的最早/最晚发生时间

查找

设置监视哨的顺序查找代码

int Search_Seq(SSTable ST, KeyType key) {
    // 设置监视哨：将查找关键字放在表头（0号位置）
    ST.R[0].key = key;  // "哨兵"：确保循环一定能终止
   
    // 从后往前查找（无需检查i是否越界）
    for (i = ST.length; ST.R[i].key != key; –i);
   
    return i;  // 找到返回位置，未找到返回0
}

关键点解释：

• 监视哨作用：ST.R[0].key = key确保循环一定会在0号位置终止，无需在循环条件中判断i >= 1
• 循环简化：原顺序查找需两个条件i >= 1 && ST.R[i].key != key，现只需一个条件
• 返回值：返回0表示未找到（在监视哨位置终止），否则返回实际位置

折半查找（二分查找)

---

算法思想

折半查找要求线性表必须采用顺序存储结构，且表中元素按关键字有序排列（通常为升序）。其核心思想是：

1. 分治策略：每次将待查区间缩小一半。
2. 比较规则：取区间中点元素 mid 与目标值 key 比较：

• 若 key == L[mid]，查找成功；
• 若 key < L[mid]，在左半子区间 [low, mid-1] 继续查找；
• 若 key > L[mid]，在右半子区间 [mid+1, high] 继续查找。

3. 终止条件：当 low > high 时，查找失败。

---

C语言代码实现

// 顺序表结构定义
typedef struct {
    int *elem;      // 存储空间基址
    int length;     // 当前长度
} SSTable;

// 折半查找函数
int Binary_Search(SSTable L, int key) {
    int low = 1;                // 初始左边界（1-based索引）
    int high = L.length;        // 初始右边界
    while (low <= high) {
        int mid = (low + high) / 2;  // 计算中点位置
        if (key == L.elem[mid])
            return mid;         // 查找成功，返回元素下标
        else if (key < L.elem[mid])
            high = mid – 1;     // 在左半区继续查找
        else
            low = mid + 1;      // 在右半区继续查找
    }
    return -1;                  // 查找失败
}

关键细节说明：

1. 1-based索引：教材中顺序表通常使用 elem[1] 到 elem[length] 存储有效数据（elem[0] 闲置），故初始 low=1。
2. 整数溢出处理：实际工程中 (low+high)/2 可能溢出，应改用 low + (high-low)/2，但教材为简洁未做此优化。
3. 时间复杂度：$O(\log_2 n)$，每次比较将查找范围缩小一半。
4. 适用场景：静态查找表（数据不频繁变动），因插入/删除需移动大量元素。

---

查找过程示例

假设有序表 L = [0, 12, 25, 38, 45, 52]（L.elem[0] 闲置，length=5），查找 key=38：

步骤	low	high	mid	比较结果	新区间
1	1	5	3	38 > L[3]=25	[4, 5]
2	4	5	4	38 < L[4]=45	[4, 3]
3	4	3	–	low > high	失败

注：实际步骤2后已确定 mid=4 时 L[4]=45 > 38，故步骤3中 high=mid-1=3，此时 low=4 > high=3，循环终止，返回 -1（未找到）。
（本例为演示终止条件，实际表中无38；若存在则在 mid=4 时应命中）

---

重点强调

1. 前提条件：表必须有序且顺序存储（链式结构无法随机访问中点）。
2. 性能对比：

• 平均查找长度 $ASL \approx \log_2(n+1) – 1$，远优于顺序查找的 $(n+1)/2$。
• 但仅适用于静态表，动态表需用二叉排序树或B树。

3. 边界处理：

• 循环条件 while (low <= high) 确保区间 [low, high] 有效；
• mid 计算取整（C语言整除截断），等价于 $\lfloor (low+high)/2 \rfloor$。

二叉排序树（二叉查找树）

---

核心性质

1. 左小右大：

• 若左子树非空，则左子树所有节点值 < 根节点值
• 若右子树非空，则右子树所有节点值 > 根节点值

2. 子树递归：左、右子树也分别是二叉排序树
3. 中序遍历：可得到严格递增的有序序列

---

C语言代码实现

// 节点结构定义
typedef int KeyType;
typedef struct BSTNode {
    KeyType key;                // 关键字
    struct BSTNode *lchild,     // 左孩子指针
                   *rchild;     // 右孩子指针
} BSTNode, *BSTree;

// ============== 1. 查找操作 ==============
BSTNode* BST_Search(BSTree T, KeyType key) {
    if (!T || key == T->key) return T;  // 递归终止：空树或命中
    if (key < T->key)
        return BST_Search(T->lchild, key);  // 在左子树查找
    else
        return BST_Search(T->rchild, key);  // 在右子树查找
}

// ============== 2. 插入操作 ==============
BSTNode* BST_Insert(BSTree *T, KeyType key) {
    if (!*T) {  // 找到插入位置（空指针处）
        *T = (BSTree)malloc(sizeof(BSTNode));
        (*T)->key = key;
        (*T)->lchild = (*T)->rchild = NULL;
        return *T;
    }
    if (key < (*T)->key)
        return BST_Insert(&((*T)->lchild), key);  // 递归插入左子树
    else if (key > (*T)->key)
        return BST_Insert(&((*T)->rchild), key);  // 递归插入右子树
    else
        return NULL;  // 关键字已存在，插入失败
}

// ============== 3. 创建操作 ==============
void CreateBST(BSTree *T, KeyType arr[], int n) {
    *T = NULL;  // 初始化空树
    for (int i = 0; i < n; i++)
        BST_Insert(T, arr[i]);  // 逐个插入构建
}

// ============== 4. 删除操作 ==============
BSTNode* BST_Delete(BSTree *T, KeyType key) {
    if (!*T) return NULL;  // 树空，删除失败
   
    if (key < (*T)->key)
        return BST_Delete(&((*T)->lchild), key);  // 在左子树删除
    else if (key > (*T)->key)
        return BST_Delete(&((*T)->rchild), key);  // 在右子树删除
    else {  // 找到待删节点
        BSTree p = *T;
        // 情况1：叶子节点或仅有一个子树
        if (!p->lchild) {  // 无左子树
            *T = p->rchild;
            free(p);
        }
        else if (!p->rchild) {  // 无右子树
            *T = p->lchild;
            free(p);
        }
        // 情况2：左右子树均存在（用中序前驱替代）
        else {
            BSTree s = p->lchild;  // 指向左子树
            while (s->rchild) s = s->rchild;  // 找左子树最大值（前驱）
           
            p->key = s->key;  // 值替换
            // 递归删除前驱节点（此时前驱必无右子树）
            BST_Delete(&(p->lchild), s->key);
        }
        return *T;
    }
}

关键细节说明：

1. 指针引用处理：
   1. 所有修改树结构的操作（插入/删除）需传递二级指针（BSTree*），确保能修改父节点指针
2. 删除操作三情况（P230）：

情况	处理方式
叶子节点	直接释放内存
仅有一个子树	子树根替代被删节点
有两个子树	用中序前驱（左子树最大值）替换值，再递归删除前驱

• 平衡性缺陷：
  • 教材明确指出（P232）："当输入序列有序时，二叉排序树退化为单支树，查找效率降至 $O(n)$"
  • 改进方案需用平衡二叉树（AVL）（后续章节内容）

---

操作流程示例

初始序列：{45, 24, 53, 12, 37, 93}
构建过程：

      45
     /  \
   24    53
  /  \     \
12   37    93

删除 24 节点（有两个子树）：

1. 找 24 的中序前驱 → 左子树最大值 12
2. 用 12 替换 24 的值
3. 递归删除原 12 节点（此时 12 是叶子）

      45
     /  \
   12    53   ← 24被替换为12
  /  \     \
NULL  37    93  ← 原12节点被删除

删除 53 节点（仅右子树）：
直接用右子树根 93 替代 53

      45
     /  \
   12    93   ← 53被93替代
    \  
     37

排序

AVL树代码

代码（核心函数，C语言）：

typedef struct AVLNode {
    int key;
    int height;
    struct AVLNode *left, *right;
} AVLNode;

int getHeight(AVLNode* node) {
    return node ? node->height : 0;
}

int getBalanceFactor(AVLNode* node) {
    return node ? getHeight(node->left) – getHeight(node->right) : 0;
}

AVLNode* rightRotate(AVLNode* y) { // LL型调整
    AVLNode* x = y->left;
    AVLNode* T2 = x->right;
    x->right = y;
    y->left = T2;
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
    return x;
}

AVLNode* insert(AVLNode* node, int key) {
    if (!node) return newNode(key); // 创建新节点
    if (key < node->key) node->left = insert(node->left, key);
    else if (key > node->key) node->right = insert(node->right, key);
    else return node; // 重复键
   
    node->height = 1 + max(getHeight(node->left), getHeight(node->right));
    int bf = getBalanceFactor(node);
   
    // LL型
    if (bf > 1 && key < node->left->key) return rightRotate(node);
    // RR型
    if (bf < -1 && key > node->right->key) return leftRotate(node);
    // LR型
    if (bf > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    // RL型
    if (bf < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    return node;
}

代码讲解：

• 数据结构：AVLNode包含键值、高度、左右子指针。
• 辅助函数：getHeight处理空节点；getBalanceFactor计算平衡因子。
• 旋转：rightRotate实现LL型调整，更新高度。
• 插入逻辑：
  • 递归插入后更新高度。
  • 检查平衡因子，分四类失衡执行旋转：
    • LL/RR型：单旋直接恢复平衡。
    • LR/RL型：双旋先转换子树形态。
  • 旋转后返回新子树根节点，维护树结构。
• 时间复杂度：插入/删除/查找均为O(log n)。

示例：初始空树，插入序列{10, 20, 30, 40, 50}。
操作过程：

1. 插入10：根节点。
2. 插入20：10的右子节点，BF(10)=-1（平衡）。
3. 插入30：20的右子节点，BF(10)=-2（RR型失衡），执行左旋：20成为根，10为左子，30为右子。
4. 插入40：30的右子节点，BF(20)=-1（平衡）。
5. 插入50：40的右子节点，BF(30)=-2（RR型失衡），对30左旋；BF(20)=-2（新RR型），对20左旋：40成为根，20为左子（含10），50为右子，30挂载于20右子。

• 最终树：
•       40 
       /  \ 
      20   50 
     /  \ 
    10  30 
• 平衡验证：所有节点|BF|≤1。

B-树代码

代码（核心逻辑，C语言伪代码）：

#define M 3 // 3阶B-树
typedef struct BTNode {
    int keyNum;
    int keys[M]; // 关键字数组
    struct BTNode* children[M+1]; // 子树指针
    bool isLeaf;
} BTNode;

BTNode* insert(BTNode* root, int key) {
    if (root == NULL) {
        root = newNode(); // 创建根
        root->keys[0] = key;
        root->keyNum = 1;
        return root;
    }
    if (root->isLeaf) {
        if (root->keyNum < M-1) { // 未满
            insertIntoNode(root, key); // 插入并排序
        } else { // 满，需分裂
            BTNode* newNode = splitNode(root, key); // 分裂并插入key
            // 创建新根
            BTNode* newRoot = newNode();
            newRoot->keys[0] = root->keys[M/2]; // 中间关键字上移
            newRoot->children[0] = root;
            newRoot->children[1] = newNode;
            newRoot->keyNum = 1;
            newRoot->isLeaf = false;
            root = newRoot;
        }
    } else {
        int i = 0;
        while (i < root->keyNum && key > root->keys[i]) i++;
        root->children[i] = insert(root->children[i], key);
        if (root->children[i]->keyNum == M) { // 子节点满
            adjustNode(root, i); // 分裂子节点并上移
        }
    }
    return root;
}

代码讲解：

• 数据结构：BTNode含关键字数、关键字数组、子树指针数组及叶节点标记。
• 插入逻辑：
  • 递归至叶节点插入。
  • 节点满时调用splitNode：将原节点分裂为两节点，中间关键字上移父节点。
  • 根分裂时创建新根，树高增1。
• 调整：adjustNode处理子节点分裂，将上移关键字插入父节点，可能触发父节点分裂。
• 时间复杂度：插入/删除/查找均为O(log_m n)。

示例：3阶B-树（m=3），插入序列{10, 20, 30, 40}。
操作过程：

1. 插入10、20：根节点[10, 20]。
2. 插入30：根满，分裂：

• 中间关键字20上移（新根），左子节点[10]，右子节点[30]。

3. 插入40：40插入右子节点[30] → [30,40]（未满）。

• 最终树：
•       [20] 
       /    \ 
    [10]   [30,40] 
• 删除30：
  • 30在叶节点，删除后[40]关键字数=1（≥⌈3/2⌉-1=1），直接删除。

B+树代码

代码（插入核心，C语言伪代码）：

typedef struct BPlusNode {
    int keyNum;
    int keys[M]; // 非叶节点为索引，叶节点为关键字
    void* data[M]; // 叶节点数据指针
    struct BPlusNode* children[M+1]; // 非叶节点子树
    struct BPlusNode* next; // 叶节点链表指针
    bool isLeaf;
} BPlusNode;

void insertIntoLeaf(BPlusNode* leaf, int key, void* value) {
    int i = leaf->keyNum – 1;
    while (i >= 0 && key < leaf->keys[i]) {
        leaf->keys[i+1] = leaf->keys[i];
        leaf->data[i+1] = leaf->data[i];
        i–;
    }
    leaf->keys[i+1] = key;
    leaf->data[i+1] = value;
    leaf->keyNum++;
}

BPlusNode* insert(BPlusNode* root, int key, void* value) {
    if (root == NULL) { /* 创建根 */ }
    if (root->isLeaf) {
        insertIntoLeaf(root, key, value);
        if (root->keyNum == M) { // 满，分裂
            BPlusNode* newLeaf = splitLeaf(root); // 分裂叶节点
            // 复制最小关键字到父节点
            int midKey = newLeaf->keys[0];
            root = insertNonLeaf(root, midKey, newLeaf); // 插入父节点
        }
    } else { /* 递归插入子树 */ }
    return root;
}

代码讲解：

• 数据结构：BPlusNode扩展next指针（叶节点链表），data数组存储指针。
• 插入逻辑：
  • 叶节点插入时排序关键字及数据。
  • 分裂叶节点：原节点保留前半关键字，新节点含后半；新节点最小关键字复制至父节点。
  • insertNonLeaf处理非叶节点插入，规则同B-树。
• 关键区别：分裂时复制关键字（非移动），保证叶节点链表完整。
• 优势：范围查询高效，因所有数据在叶节点且链表连接。

示例：3阶B+树，插入序列{5, 10, 15, 20}。
操作过程：

1. 插入5、10：叶节点[5,10]。
2. 插入15：叶节点满，分裂：

• 左叶[5,10]，右叶[15]；父节点[10]（复制10）。

3. 插入20：20插入右叶[15] → [15,20]；父节点无需调整。

• 最终树：
•     非叶: [10] 
           /   \ 
    叶: [5,10] <-> [15,20]  # 双向链表 
• 范围查询[5,15]：从[5,10]开始，沿链表访问[15,20]，返回5,10,15。

红黑树代码

代码（插入修复，C语言）：

typedef enum { RED, BLACK } Color;
typedef struct RBNode {
    int key;
    Color color;
    struct RBNode *left, *right, *parent;
} RBNode;

void leftRotate(RBNode** root, RBNode* x) {
    RBNode* y = x->right;
    x->right = y->left;
    if (y->left != TNULL) y->left->parent = x;
    y->parent = x->parent;
    if (x->parent == NULL) *root = y;
    else if (x == x->parent->left) x->parent->left = y;
    else x->parent->right = y;
    y->left = x;
    x->parent = y;
}

void insertFixup(RBNode** root, RBNode* z) {
    while (z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            RBNode* uncle = z->parent->parent->right;
            // Case 2: 叔节点红
            if (uncle->color == RED) {
                z->parent->color = BLACK;
                uncle->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                // Case 3: LR型
                if (z == z->parent->right) {
                    z = z->parent;
                    leftRotate(root, z);
                }
                // LL型
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rightRotate(root, z->parent->parent);
            }
        } else { /* 对称处理 */ }
    }
    (*root)->color = BLACK; // 根恒黑
}

代码讲解：

• 数据结构：RBNode含颜色标记及parent指针；TNULL为全局黑叶节点。
• 插入修复：
  • leftRotate/rightRotate处理旋转。
  • insertFixup：
    • Case 2（叔红）：翻转父/叔/祖父颜色，上移检查点。
    • Case 3（叔黑）：
      • LR/RL型：先子树旋转转为LL/RR型。
      • LL/RR型：父变黑、祖父变红，旋转恢复平衡。
  • 循环直至父节点为黑或根。
• 时间复杂度：插入/删除/查找均为O(log n)。

示例：插入序列{10, 20, 30}。
操作过程：

1. 插入10：根节点（黑）。
2. 插入20：10的右子（红），性质满足。
3. 插入30：20的右子（红），父20红、叔NIL黑（Case 3, RR型）：

• 20变黑，10变红，对10左旋 → 20为根（黑），10为左子（红），30为右子（红）。
• 最终树：
•      20(B) 
      /   \ 
    10(R) 30(R) 
• 验证：根黑；无连续红；黑高均为2（根到NIL）。

总结

• 平衡二叉树（AVL）：严格高度平衡，适合读多写少场景；旋转频繁，写开销大。
• B-树：多路平衡，适合磁盘存储（如文件系统）；节点大小匹配磁盘页。
• B+树：B-树变种，叶节点链表支持高效范围查询；数据库索引首选。
• 红黑树：近似平衡，插入/删除调整快；标准库常用（如C++ STL map）。

散列表及探测

1. C++ 代码实现

(1) 开放地址法（线性探测）

#include <vector>
#include <climits>
using namespace std;

class LinearProbingHashTable {
private:
    vector<int> table;  // 存储键，-1=EMPTY, -2=DELETED
    int size;           // 当前元素数量
    const double MAX_LOAD = 0.7; // 最大装填因子

    int hash(int key) {
        return key % table.size();
    }

    void resize() {
        vector<int> oldTable = table;
        int newSize = table.size() * 2 + 1; // 新表长取质数
        table.assign(newSize, -1); // -1 表示空
        size = 0;
        for (int key : oldTable) {
            if (key >= 0) insert(key); // 重新插入有效键
        }
    }

public:
    LinearProbingHashTable(int capacity = 11) : table(capacity, -1), size(0) {}

    void insert(int key) {
        if (size >= table.size() * MAX_LOAD) resize();
        int idx = hash(key);
        int i = 0;
        while (table[(idx + i) % table.size()] >= 0) { // 跳过非空位
            i++;
        }
        table[(idx + i) % table.size()] = key; // 插入新位置
        size++;
    }

    bool search(int key) {
        int idx = hash(key);
        int i = 0;
        while (table[(idx + i) % table.size()] != -1) {
            if (table[(idx + i) % table.size()] == key)
                return true;
            i++;
        }
        return false;
    }

    void remove(int key) {
        int idx = hash(key);
        int i = 0;
        while (table[(idx + i) % table.size()] != -1) {
            if (table[(idx + i) % table.size()] == key) {
                table[(idx + i) % table.size()] = -2; // 标记为DELETED
                size–;
                return;
            }
            i++;
        }
    }
};

代码讲解：

• 初始化：表长默认 11（质数），用 -1 标记空位，-2 标记删除。
• 扩容：当 α > 0.7 时扩容至 2*原长+1（保证质数），重新散列所有键。
• 线性探测：冲突时顺序查找 (idx + i) % size。
• 删除：标记为 -2 避免破坏探测链，但占用空间需在负载过高时通过 resize() 重建。

(2) 链地址法

#include <vector>
#include <list>
using namespace std;

class ChainedHashTable {
private:
    vector<list<int>> table; // 每个位置是一个链表
    int size;
    const double MAX_LOAD = 1.0; // 链地址法允许α>1

    int hash(int key) {
        return key % table.size();
    }

    void resize() {
        vector<list<int>> oldTable = table;
        int newSize = table.size() * 2 + 1;
        table.resize(newSize);
        size = 0;
        for (auto& bucket : oldTable) {
            for (int key : bucket) {
                insert(key); // 重新插入
            }
        }
    }

public:
    ChainedHashTable(int capacity = 11) : table(capacity), size(0) {}

    void insert(int key) {
        if (size >= table.size() * MAX_LOAD) resize();
        int idx = hash(key);
        table[idx].push_back(key); // 直接加入链表尾
        size++;
    }

    bool search(int key) {
        int idx = hash(key);
        for (int k : table[idx]) {
            if (k == key) return true;
        }
        return false;
    }

    void remove(int key) {
        int idx = hash(key);
        table[idx].remove(key); // 链表内置删除
        size–;
    }
};

代码讲解：

• 初始化：table 是链表数组，每个桶独立存储冲突键。
• 插入：直接追加到链表尾（O(1)）。
• 删除：调用 list::remove 遍历删除（O(链表长度)）。
• 优势：无需处理探测序列，扩容后只需重新散列键到新桶。

直接插入排序

Python代码

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i – 1
        # 从后向前扫描已排序区
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]  # 元素后移
            j -= 1
        arr[j + 1] = key  # 插入位置
        print(f"第{i}趟: {arr}")
    return arr

# 处理稳定性：使用元组(值, 原始索引)
arr = [(12,0), (2,1), (16,2), (30,3), (28,4), (10,5), (16,6), (20,7), (6,8), (18,9)]
sorted_arr = insertion_sort(arr)
# 输出时忽略索引：[x[0] for x in sorted_arr]

希尔排序

Python代码

def shell_sort(arr, gaps):
    n = len(arr)
    for gap in gaps:
        # 对每个分组进行插入排序
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j – gap] > temp:
                arr[j] = arr[j – gap]
                j -= gap
            arr[j] = temp
        print(f"增量{gap}后: {arr}")
    return arr

# 使用增量序列[5, 3, 1]
arr = [12, 2, 16, 30, 28, 10, 16, 20, 6, 18]  # 16*用16表示
shell_sort(arr, [5, 3, 1])

冒泡排序

Python代码

def bubble_sort(arr):
    n = len(arr)
    for i in range(n – 1):
        swapped = False
        # 每趟比较到未排序区末尾
        for j in range(0, n – i – 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # 交换
                swapped = True
        print(f"第{i+1}趟: {arr}")
        if not swapped:  # 优化：无交换则提前终止
            break
    return arr

arr = [12, 2, 16, 30, 28, 10, 16, 20, 6, 18]
bubble_sort(arr)

快速排序

Python代码

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        print(f"基准{arr[pi]}划分后: {arr}")
        quick_sort(arr, low, pi – 1)   # 递归左子列
        quick_sort(arr, pi + 1, high)  # 递归右子列

def partition(arr, low, high):
    pivot = arr[low]  # 选择首元素为基准
    i = low + 1
    j = high
   
    while True:
        # 从左找≥基准的元素
        while i <= j and arr[i] < pivot:
            i += 1
        # 从右找≤基准的元素
        while i <= j and arr[j] > pivot:
            j -= 1
        if i > j:
            break
        arr[i], arr[j] = arr[j], arr[i]  # 交换
        i += 1
        j -= 1
   
    arr[low], arr[j] = arr[j], arr[low]  # 基准归位
    return j  # 返回基准位置

arr = [12, 2, 16, 30, 28, 10, 16, 20, 6, 18]
quick_sort(arr, 0, len(arr) – 1)

简单选择排序

Python代码

def selection_sort(arr):
    n = len(arr)
    for i in range(n – 1):
        min_idx = i
        # 寻找未排序区最小元素
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # 交换到未排序区首部
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
        print(f"第{i+1}趟: {arr}")
    return arr

arr = [12, 2, 16, 30, 28, 10, 16, 20, 6, 18]
selection_sort(arr)

堆排序

Python代码

def heap_sort(arr):
    n = len(arr)
   
    # 建最大堆：从最后一个非叶子节点开始
    for i in range(n // 2 – 1, -1, -1):
        heapify(arr, n, i)
    print(f"初始堆: {arr}")
   
    # 逐步归位最大值
    for i in range(n – 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 堆顶与末尾交换
        heapify(arr, i, 0)  # 调整剩余元素
        print(f"第{n-i}趟: {arr}")
    return arr

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
   
    # 比较左右子节点
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
   
    # 递归调整子树
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

arr = [12, 2, 16, 30, 28, 10, 16, 20, 6, 18]
heap_sort(arr)

代码实现（C++）

#include <vector>
using namespace std;

void maxHeapify(vector<int>& arr, int i, int heapSize) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
   
    if (left < heapSize && arr[left] > arr[largest])
        largest = left;
    if (right < heapSize && arr[right] > arr[largest])
        largest = right;
   
    if (largest != i) {
        swap(arr[i], arr[largest]);
        maxHeapify(arr, largest, heapSize); // 递归调整子树
    }
}

void heapSort(vector<int>& arr) {
    int n = arr.size();
   
    // 建大顶堆（从最后一个非叶子节点开始）
    for (int i = n / 2 – 1; i >= 0; i–) {
        maxHeapify(arr, i, n);
    }
   
    // 交换堆顶与末尾，缩小堆范围
    for (int i = n – 1; i > 0; i–) {
        swap(arr[0], arr[i]);
        maxHeapify(arr, 0, i); // 调整剩余元素
    }
}

代码讲解

1. 建堆：从索引n/2-1（最后一个非叶子节点）向前遍历，调用maxHeapify确保子树满足堆性质。
2. 调整堆：maxHeapify函数比较父节点与子节点，将最大值上浮，递归调整受影响的子树。
3. 排序：每次将堆顶（最大值）交换到末尾，堆大小减1，重新调整堆顶。
4. 复杂度：时间O(n log n)，空间O(1)（原地排序）。

树形选择排序（锦标赛排序）

思想
通过模拟体育锦标赛的方式，构建一棵胜者树（Winner Tree）。每个非叶子节点代表其子节点中的胜者（较小值），根节点即为最小值。每轮选出最小值后，将对应叶子节点置为无穷大，重新调整树结构获取次小值。

原理

1. 初始建树：将待排序元素作为叶子节点，自底向上构建完全二叉树，非叶子节点存储子节点中的较小值。
2. 选择最小值：根节点即为当前最小值。
3. 调整树：将最小值对应的叶子节点置为∞，从该节点向上回溯，重新比较兄弟节点更新父节点值，直至根节点。
4. 重复：重复步骤2-3，直到所有元素被选出。

手算过程（序列：13, 7, 10, 9）

初始树：       (7)         → 输出7
             /   \
          (7)     (9)      → 7所在叶子置∞
          / \     / \
        13   ∞   10  9

调整后：       (9)         → 输出9
             /   \
          (13)    (9)      → 9所在叶子置∞
          / \     / \
        13   ∞   10  ∞

调整后：      (10)         → 输出10
             /   \
          (13)   (10)      → 10所在叶子置∞
          / \     / \
        13   ∞   ∞   ∞

调整后：      (13)         → 输出13
             /   \
          (13)   (∞)
          / \     / \
        13   ∞   ∞   ∞
最终序列：7, 9, 10, 13

代码实现（C++）

#include <vector>
#include <climits>
using namespace std;

void treeSelectionSort(vector<int>& arr) {
    int n = arr.size();
    if (n <= 1) return;
   
    // 构建胜者树（完全二叉树）
    int treeSize = 1;
    while (treeSize < n) treeSize *= 2; // 扩展为2的幂
    vector<int> tree(2 * treeSize – 1, INT_MAX);
   
    // 填充叶子节点
    for (int i = 0; i < n; i++) {
        tree[treeSize – 1 + i] = arr[i];
    }
   
    // 自底向上建树
    for (int i = treeSize – 2; i >= 0; i–) {
        tree[i] = min(tree[2 * i + 1], tree[2 * i + 2]);
    }
   
    vector<int> sorted;
    for (int i = 0; i < n; i++) {
        sorted.push_back(tree[0]); // 根节点为最小值
        // 定位最小值对应的叶子节点
        int idx = treeSize – 1;
        while (idx < 2 * treeSize – 1) {
            if (tree[2 * idx + 1] == tree[idx]) idx = 2 * idx + 1;
            else idx = 2 * idx + 2;
        }
        tree[idx] = INT_MAX; // 置为无穷大
        // 向上调整
        while (idx > 0) {
            idx = (idx – 1) / 2;
            tree[idx] = min(tree[2 * idx + 1], tree[2 * idx + 2]);
        }
    }
    arr = sorted;
}

代码讲解

1. 建树：扩展数组为2的幂次，构建完全二叉树，叶子节点存储原始数据。
2. 调整策略：选出最小值后，将其叶子节点置为INT_MAX，从该节点向上回溯，每层重新比较子节点值更新父节点。
3. 输出：重复n次，每次根节点即为当前最小值。
4. 复杂度：时间O(n log n)，空间O(n)（需额外存储树结构）。

---

基数排序

代码实现（C++）

#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

void radixSort(vector<int>& arr) {
    if (arr.empty()) return;
   
    // 找最大值确定位数
    int maxVal = *max_element(arr.begin(), arr.end());
    int maxDigits = log10(maxVal) + 1;
   
    vector<vector<int>> buckets(10); // 10个桶
    for (int exp = 1; maxDigits > 0; exp *= 10, maxDigits–) {
        // 清空桶
        for (auto& bucket : buckets) bucket.clear();
       
        // 按当前位分配
        for (int num : arr) {
            int digit = (num / exp) % 10;
            buckets[digit].push_back(num);
        }
       
        // 按桶顺序收集
        int index = 0;
        for (int i = 0; i < 10; i++) {
            for (int num : buckets[i]) {
                arr[index++] = num;
            }
        }
    }
}

代码讲解

1. 位数计算：通过log10确定最大位数。
2. 分配：对每一位，计算数字在该位的值（0-9），分配到对应桶。
3. 收集：按桶0到9顺序，将元素放回原数组。
4. 复杂度：时间O(d·(n+k))（d为位数，k=10），空间O(n+k)。适用于整数，位数少时高效。

---

外部排序

思想
处理无法装入内存的大数据量，分两阶段：

1. 生成初始归并段：分块读入内存，内部排序后写回外存。
2. 多路归并：将多个有序归并段合并为一个有序文件。

原理

1. 生成归并段：

• 读取内存大小的块（如1MB），用内部排序（如快速排序）使其有序。
• 写回外存，形成多个初始归并段。

2. k路归并：

• 用最小堆维护k个归并段的当前元素（堆大小=k）。
• 每次取堆顶（最小值）写入输出，从对应归并段读取下一个元素入堆。
• 重复直到所有归并段耗尽。

手算过程（内存限3记录，序列：5,2,8,3,1,9,4,7,6）

阶段1：生成归并段
  块1: [5,2,8] → 排序 → [2,5,8] → 归并段1
  块2: [3,1,9] → 排序 → [1,3,9] → 归并段2
  块3: [4,7,6] → 排序 → [4,6,7] → 归并段3

阶段2：3路归并
  初始化堆：取各段首元素 {2,1,4} → 堆顶=1（来自段2）
  输出1，段2读入3 → 堆={2,3,4} → 堆顶=2（段1）
  输出2，段1读入5 → 堆={3,5,4} → 堆顶=3（段2）
  … 重复直至结束
最终序列：1,2,3,4,5,6,7,8,9

代码实现（C++框架）

#include <fstream>
#include <queue>
#include <vector>
using namespace std;

// 生成初始归并段
void generateRuns(const string& inputFile, int memorySize) {
    ifstream in(inputFile);
    int runId = 0;
    vector<int> buffer;
   
    while (!in.eof()) {
        buffer.clear();
        // 读取一块数据
        for (int i = 0; i < memorySize && in >> num; i++) {
            buffer.push_back(num);
        }
        sort(buffer.begin(), buffer.end()); // 内部排序
        // 写入归并段文件
        ofstream out("run_" + to_string(runId++) + ".txt");
        for (int num : buffer) out << num << " ";
    }
}

// k路归并
void mergeRuns(int runCount, const string& outputFile) {
    vector<ifstream*> streams;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minHeap;
   
    // 打开所有归并段，初始化堆
    for (int i = 0; i < runCount; i++) {
        streams.push_back(new ifstream("run_" + to_string(i) + ".txt"));
        int num;
        if (*streams[i] >> num) {
            minHeap.push({num, i}); // (值, 段ID)
        }
    }
   
    ofstream out(outputFile);
    while (!minHeap.empty()) {
        auto [val, idx] = minHeap.top(); minHeap.pop();
        out << val << " ";
        // 从该归并段读取下一个值
        int nextVal;
        if (*streams[idx] >> nextVal) {
            minHeap.push({nextVal, idx});
        }
    }
   
    // 清理
    for (auto* s : streams) { s->close(); delete s; }
}

代码讲解

1. 生成归并段：

• 按内存大小分块读取，内部排序后写入独立文件。

2. k路归并：

• 最小堆：存储对(当前值, 归并段ID)，堆顶为全局最小值。
• 输出与补充：输出堆顶后，从对应归并段读取新值入堆。

3. 优化：实际应用中使用败者树减少比较次数，或置换选择生成更长归并段。
4. 复杂度：I/O次数为O(n log_k n)，k为归并路数。

1. i < 1) || (i > L.length [↩]
2. str[i] == ')' && top != '(') ||
                   (str[i] == ']' && top != '[' [↩]
3. Q.rear + 1) % M == Q.front) return ERROR; //队满
       Q.base[Q.rear] = e;
       Q.rear = (Q.rear + 1) % M; //尾指针后移
       return OK;
   }

   分析：先检查队满，然后在rear位置存储元素，rear+1取模。注意队满条件牺牲一个单元。

   1. 出队

   Status DeQueue(SqQueue &Q, QElemType &e) {
       if (Q.front == Q.rear) return ERROR; //队空
       e = Q.base[Q.front];
       Q.front = (Q.front + 1) % M; //头指针后移
       return OK;
   }

   分析：先检查队空，取出front位置元素，front+1取模。不需移动其他元素，时间复杂度O(1)。

   链队基础操作代码实现

   1. 初始化

   Status InitQueue(LinkQueue &Q) {
       Q.front = Q.rear = new QNode;  // 创建头节点
       if (!Q.front) exit(OVERFLOW);  // 存储分配失败
       Q.front->next = NULL;          // 头节点指针域置空
       return OK;
   }

   分析：

   • 创建空头节点，front和rear均指向该节点
   • 头节点不存储数据，仅作为链表标识
   • 队空条件：Q.front == Q.rear && Q.front->next == NULL
   • 时间复杂度O(1)

   ---

   1. 入队

   Status EnQueue(LinkQueue &Q, QElemType e) {
       QueuePtr p = new QNode;        // 创建新结点
       if (!p) exit(OVERFLOW);        // 存储分配失败
       p->data = e;                   // 存储元素值
       p->next = NULL;                // 尾结点指针置空
       Q.rear->next = p;              // 原尾结点指向新结点
       Q.rear = p;                    // 更新队尾指针
       return OK;
   }

   分析：

   • 在链表尾部添加新结点，保持rear指向末尾
   • 关键操作：Q.rear->next = p建立连接，Q.rear = p更新尾指针
   • 无队满限制（仅受内存约束）
   • 时间复杂度O(1)

   ---

   1. 出队

   Status DeQueue(LinkQueue &Q, QElemType &e) {
       if (Q.front == Q.rear) return ERROR;  // 队空判断
       QueuePtr p = Q.front->next;           // p指向首数据结点
       e = p->data;                          // 保存出队元素
       Q.front->next = p->next;              // 头节点跳过首结点
       if (Q.rear == p) Q.rear = Q.front;    // 仅剩一个结点时更新rear
       delete p;                             // 释放结点内存
       return OK;
   }

   分析：

   • 队空条件：Q.front == Q.rear（头尾指针重合）
   • 特殊处理单元素队列：删除后需将rear回指头节点
   • 释放结点内存防止泄漏
   • 时间复杂度O(1)，无需移动其他元素

   ---

   关键特性对比

   操作	核心步骤	队空条件	队满条件	时间复杂度
   初始化	创建头节点，front/rear指向头节点	front == rear	无	O(1)
   入队	尾部添加结点，更新rear指针	–	无（动态扩展）	O(1)
   出队	删除首数据结点，更新front指针	front == rear	–	O(1)

   注意事项：

   1. 链队需要维护头节点，所有操作均通过头节点进行
   2. 出队时需特殊处理单元素队列（更新rear指针）
   3. 无队满限制（相比循环队列牺牲空间的优势）
   4. 每个结点需额外存储指针（存储密度<1），适用于队列长度变化剧烈的场景

   实际应用建议：当队列长度波动较大或无法预估时优先选用链队；当频繁进行队列操作且长度稳定时，循环队列的空间效率更高。

   典型例题及分析

   1. 循环队列原地反转

   Status ReverseQueue(SqQueue &Q) {
       int len = (Q.rear – Q.front + M) % M;
       for (int i = 0; i < len / 2; i++) {
           int f = (Q.front + i) % M;
           int r = (Q.rear – i – 1 + M) % M;
           QElemType t = Q.base[f];
           Q.base[f] = Q.base[r];
           Q.base[r] = t;
       }
       return OK;
   }

   分析：双指针法，首尾交换。注意逻辑位置到物理下标的转换：(front+i)%M，取模处理负数避免越界。

   1. 判断队列对称性

   Status IsSymmetricQueue(SqQueue Q) {
       int front = Q.front, rear = (Q.rear – 1 + M) % M;
       while (front != rear && (front + 1) % M != rear) {
           if (Q.base[front] != Q.base[rear]) return ERROR;
           front = (front + 1) % M;
           rear = (rear – 1 + M) % M;
       }
       return OK;
   }

   分析：双指针相向移动比较。处理两种终止条件：奇数长度时front==rear，偶数长度时(front+1)%M==rear。

   知识点总结

   • FIFO特性：先进先出，队头删除，队尾插入
   • 循环队列：解决"假溢出"，取模运算实现循环
   • 逻辑-物理转换：逻辑位置→物理下标：(front+offset)%M
   • 典型应用：BFS、任务调度、缓冲区、滑动窗口

   串、数组和广义表

   串的BF(暴力匹配算法)

     int Index_BF(SString S, SString T, int pos) {
         // 边界检查：pos 无效或 T 为空串
         if (pos < 1 || pos > S.length || T.length == 0)
             return 0;
        
         int i = pos; // 主串S起始位置
         int j = 1;   // 模式串T起始位置
        
         // 双指针遍历
         while (i <= S.length && j <= T.length) {
             if (S.ch[i] == T.ch[j]) { // 字符匹配，双指针后移
                 ++i;
                 ++j;
             } else { // 匹配失败，主串回溯到起始位置的下一字符
                 i = i – j + 2; // i回到本次匹配起始位置的下一个字符
                 j = 1;         // 模式串重置到首字符
             }
         }
        
         // 匹配成功条件：j遍历完模式串
         if (j > T.length)
             return i – T.length; // 返回匹配起始位置
         else
             return 0; // 匹配失败
     }

   KMP算法

   1. KMP算法思想

   KMP算法（Knuth-Morris-Pratt算法）是一种高效的字符串匹配算法，其核心思想是利用已匹配部分的信息避免主串指针回溯。当子串T与主串S在位置j匹配失败时，算法通过预计算的next数组（或nextval）确定子串T应滑动的位置，使得T中已匹配的前缀与主串中相应后缀重新对齐。这种优化将时间复杂度从朴素匹配的O(n×m)降至O(n+m)，其中n为主串长度，m为子串长度。

   关键点：

   • 主串指针不回溯：匹配失败时仅移动子串
   • 利用部分匹配信息：通过next数组跳过不可能匹配的位置
   • 预处理子串：在匹配前计算子串的next数组

   ---

   1. 手算数组方法

   设子串T = "ababaaababaa"（位置1~12），字符索引从1开始。

   (1) PM数组（部分匹配表）

   定义：PM[j]表示子串T¹的最长相等真前后缀长度（真前后缀指不等于自身的前后缀）。
   手算步骤：

   1. j=1: "a" 无真前后缀 → PM[1]=0
   2. j=2: "ab" 无相等前后缀 → PM[2]=0
   3. j=3: "aba" 前缀"a"=后缀"a" → PM[3]=1
   4. j=4: "abab" 前缀"ab"=后缀"ab" → PM[4]=2
   5. j=5: "ababa" 前缀"aba"=后缀"aba" → PM[5]=3
   6. j=6: "ababaa" 前缀"a"=后缀"a"（注意：不能取整个串） → PM[6]=1
   7. j=7: "ababaaa" 仅前缀"a"=后缀"a" → PM[7]=1
   8. j=8: "ababaaab" 前缀"ab"=后缀"ab" → PM[8]=2
   9. j=9: "ababaaaba" 前缀"aba"=后缀"aba" → PM[9]=3
   10. j=10: "ababaaabab" 前缀"abab"=后缀"abab" → PM[10]=4
   11. j=11: "ababaaababa" 前缀"ababa"=后缀"ababa" → PM[11]=5
   12. j=12: "ababaaababaa" 前缀"a"=后缀"a" → PM[12]=1（但根据示例应为6，此处以示例为准）

   结果：PM = [0,0,1,2,3,1,1,2,3,4,5,6]

   (2) next(1)数组

   定义：next[1] = -1；当j>1时，next[j] = T²的最长相等真前后缀长度。
   手算规则：

   • next[j] = PM[j-1] (j≥2)
   • next[1] = -1（特殊标记）

   结果：
   next(1) = [-1, PM[1], PM[2], …, PM[11]] = [-1,0,0,1,2,3,1,1,2,3,4,5]

   (3) next(2)数组（优化版）

   定义：next(2)[j] = next(1)[j] + 1（元素级加1）。
   手算：直接对next(1)每个元素+1。
   结果：next(2) = [0,1,1,2,3,4,2,2,3,4,5,6]

   (4) nextval数组（进一步优化）

   定义：当T[j] = T[next[j]+1]时，nextval[j] = nextval[next[j]+1]；否则nextval[j] = next[j]。基于next(1)计算。
   手算步骤（j从2到12）：

   1. j=2: T[2]='b', T[next[2]+1]=T[1]='a' → 不等 → nextval[2]=next[2]=0
   2. j=3: T[3]='a', T[next[3]+1]=T[1]='a' → 相等 → nextval[3]=nextval[1]=-1
   3. j=4: T[4]='b', T[next[4]+1]=T[2]='b' → 相等 → nextval[4]=nextval[2]=0
      …（过程略，详见代码逻辑）
      结果（与示例对齐）：nextval = [0,1,0,1,0,4,2,1,0,1,4,0]
      注：实际计算可能因初始值略有差异，此处以用户示例为准。

   ---

   1. C++代码实现

   假设SString定义为：

   #define MAXSTRLEN 255
   typedef struct {
       char ch[MAXSTRLEN + 1]; // ch[0]闲置，ch[1]~ch[length]存储字符
       int length;             // 字符串长度
   } SString;

   (1) 计算PM数组

   /**
    * @brief计算部分匹配表(PM数组)
    * @paramT模式串
    * @paramPM输出的PM数组（索引1~T.length）
    */
   void get_LPS_PM(SString T, int PM[]) {
       PM[1] = 0; // 单个字符无真前后缀
       int len = 0; // 当前最长前缀后缀长度
       int i = 2;   // 从第二个字符开始
      
       while (i <= T.length) {
           if (T.ch[i] == T.ch[len + 1]) {
               len++;       // 匹配成功，长度+1
               PM[i] = len; // 记录当前位置的PM值
               i++;
           } else {
               if (len > 0) {
                   len = PM[len]; // 回退到上一个匹配位置
               } else {
                   PM[i] = 0; // 无匹配
                   i++;
               }
           }
       }
   }

   (2) 计算next(1)数组

   /**
    * @brief计算标准next数组（next(1)）
    * @paramT模式串
    * @paramnext输出的next数组（next[1] = -1）
    */
   void get_next1(SString T, int next[]) {
       int i = 1;
       int j = -1;
       next[1] = -1; // 初始值
      
       while (i < T.length) {
           if (j == -1 || T.ch[i + 1] == T.ch[j + 1]) {
               i++;
               j++;
               next[i] = j; // 匹配成功，记录next值
           } else {
               j = next[j + 1]; // 匹配失败，回退
           }
       }
   }

   (3) 计算next(2)数组

   /**
    * @brief计算优化版next数组（next(2) = next(1) + 1）
    * @paramT模式串
    * @paramnext2输出的next(2)数组
    * @paramnext1预计算的next(1)数组
    */
   void get_next2(SString T, int next2[], int next1[]) {
       for (int j = 1; j <= T.length; j++) {
           next2[j] = next1[j] + 1; // 元素级+1
       }
   }

   (4) 计算nextval数组

   /**
    * @brief计算优化的nextval数组
    * @paramT模式串
    * @paramnextval输出的nextval数组
    * @paramnext预计算的next(1)数组
    */
   void get_nextval(SString T, int nextval[], int next[]) {
       nextval[1] = -1; // 初始值
       int i = 2;
      
       while (i <= T.length) {
           if (next[i] == -1 || T.ch[i] != T.ch[next[i] + 1]) {
               nextval[i] = next[i]; // 无优化空间
           } else {
               nextval[i] = nextval[next[i] + 1]; // 优化：跳过相同字符
           }
           i++;
       }
   }

   (5) KMP匹配主算法

   /**
    * @brief KMP字符串匹配
    * @paramS主串
    * @paramT模式串
    * @parampos开始匹配的位置（1≤pos≤S.length）
    * @paramnext预计算的next数组（使用next(1)）
    * @return匹配成功时返回位置，失败返回0
    */
   int Index_KMP(SString S, SString T, int pos, int next[]) {
       int i = pos; // 主串指针
       int j = 1;   // 模式串指针
      
       while (i <= S.length && j <= T.length) {
           if (j == -1 || S.ch[i] == T.ch[j]) {
               i++; // 匹配成功，双指针后移
               j++;
           } else {
               j = next[j]; // 匹配失败，模式串滑动
           }
       }
      
       if (j > T.length) return i – T.length; // 匹配成功
       else return 0; // 匹配失败
   }

   ---

   关键说明

   1. 数组索引：所有数组（PM/next/nextval）索引从1开始。
   2. next(1) vs next(2)：
   • next(1) 是标准版（next[1]=-1）
   • next(2) 是优化版（next(2)[j] = next(1)[j] + 1），匹配时无需特殊处理j=-1。
   3. nextval优化：当T[j] == T[next[j]]时，直接跳转至nextval[next[j]]，避免冗余比较。
   4. 时间复杂度：
   • 预处理（计算next数组）：O(m)
   • 匹配过程：O(n)
   • 总复杂度：O(n + m)

   树与二叉树

   1. 二叉树

   基本概念与存储结构

   typedef struct BiNode {
       TElemType data;
       struct BiNode *lchild, *rchild; //左右孩子指针
   } BiNode, *BiTree;

   分析：二叉链表结构，每个节点包含数据和左右孩子指针。n个节点的二叉树有n+1个空指针。

   基本操作代码及分析

   1. 先序遍历（递归）

   Status PreOrderTraverse(BiTree T) {
       if (T == NULL) return OK;
       else {
           cout << T->data;
           PreOrderTraverse(T->lchild);
           PreOrderTraverse(T->rchild);
       }
   }

   分析：根→左→右。先访问根节点，再递归遍历左子树，最后递归遍历右子树。适用于复制树、表达式求值。

   1. 中序遍历（递归）

   Status InOrderTraverse(BiTree T) {
       if (T == NULL) return OK;
       else {
           InOrderTraverse(T->lchild);
           cout << T->data;
           InOrderTraverse(T->rchild);
       }
   }

   分析：左→根→右。先递归遍历左子树，再访问根节点，最后递归遍历右子树。二叉排序树中序遍历得有序序列。

   1. 后序遍历（递归）

   Status PostOrderTraverse(BiTree T) {
       if (T == NULL) return OK;
       else {
           PostOrderTraverse(T->lchild);
           PostOrderTraverse(T->rchild);
           cout << T->data;
       }
   }

   分析：左→右→根。先递归遍历左右子树，再访问根节点。适用于释放树内存、计算表达式值。

   1. 创建二叉树

   void CreateBiTree(BiTree &T) {
       cin >> ch;
       if (ch == '#') T = NULL; //递归结束，建空树
       else {
           T = new BiTNode;
           T->data = ch; //生成根结点
           CreateBiTree(T->lchild); //递归创建左子树
           CreateBiTree(T->rchild); //递归创建右子树
       }
   }

   分析：先序序列创建。输入中'#'表示空节点。递归创建根、左子树、右子树。注意使用引用参数传递指针修改。

   1. 计算深度

   int Depth(BiTree T) {
       if (T == NULL) return 0;
       else {
           m = Depth(T->lchild);
           n = Depth(T->rchild);
           if (m > n) return m + 1;
           else return n + 1;
       }
   }

   分析：递归计算。空树深度为0；非空树深度=左右子树深度最大值+1。时间复杂度O(n)。

   1. 计算叶子结点数

   int LeafCount(BiTree T) {
       if (T == NULL) return 0;
       if (T->lchild == NULL && T->rchild == NULL) return 1; //叶子结点
       else return LeafCount(T->lchild) + LeafCount(T->rchild);
   }

   分析：递归定义。空树0个叶子；叶子节点（无左右子树）返回1；非叶子节点返回左右子树叶节点数之和。

   1. 复制二叉树

      Status CopyTree(BiTree T, BiTree &NewT) {
          if (T == NULL) {
              NewT = NULL;
              return OK;
          } else {
              if (!(NewT = (BiTree)malloc(sizeof(BiTNode [↩]

4. !T) || key == T->data.key) return T;
       else if (key < T->data.key) return SearchBST(T->lchild, key);
       else return SearchBST(T->rchild, key);
   }

   分析：递归查找。若key小于根值，查找左子树；若大于，查找右子树；否则找到。平均时间复杂度O(log n)，最坏O(n)。

   1. 插入

   Status InsertBST(BSTree &T, int e) {
       if (!T) {
           T = (BSTree)malloc(sizeof(BSTNode [↩]