学校-数据结构

数据结构网课代码整理

注：以下代码基于 C 语言实现，通用数据类型 ElemType 统一定义为 int。

一、线性表

1. 顺序表

1.1 顺序表结构体定义（静态+动态）

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 通用数据类型定义
typedef int ElemType;

// 1. 静态顺序表
#define MaxSize 50 // 静态顺序表最大长度
typedef struct {
    ElemType data[MaxSize]; // 存储元素的数组
    int length;             // 当前顺序表长度
} SqList;

// 2. 动态顺序表
#define InitSize 50 // 动态顺序表初始长度
typedef struct {
    ElemType *data; // 指向动态分配数组的指针
    int MaxSize;    // 数组最大容量
    int length;     // 当前顺序表长度
} SeqList;

1.2 顺序表核心操作

// 1. 静态顺序表初始化
void InitSqList(SqList &L) {
    L.length = 0; // 初始长度为0
}

// 2. 动态顺序表初始化（分配内存）
bool InitSeqList(SeqList &L) {
    L.data = (ElemType *)malloc(sizeof(ElemType) * InitSize);
    if (L.data == NULL) return false; // 内存分配失败
    L.MaxSize = InitSize;
    L.length = 0;
    return true;
}

// 3. 顺序表插入操作（在第i个位置插入元素e，1<=i<=L.length+1）
bool ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1) return false; // 位置不合法
    if (L.length >= MaxSize) return false;       // 顺序表已满
    
    // 从后往前移动元素，腾出位置
    for (int j = L.length; j >= i; j--) {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e; // 插入元素（数组下标从0开始）
    L.length++;        // 长度+1
    return true;
}

// 4. 顺序表删除操作（删除第i个位置元素，用e返回删除值，1<=i<=L.length）
bool ListDelete(SqList &L, int i, ElemType &e) {
    if (i < 1 || i > L.length) return false; // 位置不合法
    
    e = L.data[i - 1]; // 保存删除元素
    // 从前往后移动元素，覆盖删除位置
    for (int j = i; j < L.length; j++) {
        L.data[j - 1] = L.data[j];
    }
    L.length--; // 长度-1
    return true;
}

// 5. 顺序表按位查找（返回第i个位置元素，1<=i<=L.length）
ElemType GetElem(SqList L, int i) {
    if (i < 1 || i > L.length) {
        printf("位置不合法\n");
        exit(1); // 实际应用中可返回特殊值，此处简化处理
    }
    return L.data[i - 1];
}

// 6. 顺序表按值查找（返回第一个值为e的元素位序，找不到返回0）
int LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i + 1; // 位序从1开始
        }
    }
    return 0; // 查找失败
}

// 7. 合并两个有序顺序表A、B为有序顺序表C
bool MergeSqList(SqList A, SqList B, SqList &C) {
    if (A.length + B.length > MaxSize) return false; // C容量不足
    
    int i = 0, j = 0, k = 0;
    // 按顺序取A、B中较小元素存入C
    while (i < A.length && j < B.length) {
        if (A.data[i] <= B.data[j]) {
            C.data[k++] = A.data[i++];
        } else {
            C.data[k++] = B.data[j++];
        }
    }
    // 处理A中剩余元素
    while (i < A.length) {
        C.data[k++] = A.data[i++];
    }
    // 处理B中剩余元素
    while (j < B.length) {
        C.data[k++] = B.data[j++];
    }
    C.length = k; // 设置C的长度
    return true;
}

2. 链表

2.1 单链表结构体定义

// 单链表结点结构
typedef struct LNode {
    ElemType data;       // 数据域
    struct LNode *next;  // 指针域（指向后继结点）
} LNode, *LinkList;

2.2 单链表核心操作

// 1. 单链表初始化（带头结点）
bool InitLinkList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode)); // 创建头结点
    if (L == NULL) return false;        // 内存分配失败
    L->next = NULL;                     // 头结点后继为NULL（空表）
    return true;
}

// 2. 单链表按序号查找（返回第i个结点的指针，1<=i，找不到返回NULL）
LNode *GetElemLinkList(LinkList L, int i) {
    if (i < 0) return NULL; // i=0返回头结点
    LNode *p = L;
    int j = 0;
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p; // j==i时返回目标结点，否则返回NULL
}

// 3. 单链表按值查找（返回第一个值为e的结点指针，找不到返回NULL）
LNode *LocateElemLinkList(LinkList L, ElemType e) {
    LNode *p = L->next; // 从首元结点开始查找
    while (p != NULL && p->data != e) {
        p = p->next;
    }
    return p; // 找到返回结点，否则返回NULL
}

// 4. 单链表插入（在第i个位置插入值为e的结点，1<=i<=表长+1）
bool ListInsertLinkList(LinkList &L, int i, ElemType e) {
    LNode *p = GetElemLinkList(L, i - 1); // 找到前驱结点（第i-1个）
    if (p == NULL) return false;          // 前驱结点不存在（i不合法）
    
    // 创建新结点
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) return false;
    s->data = e;
    
    // 插入逻辑：s的后继 = p的后继；p的后继 = s
    s->next = p->next;
    p->next = s;
    return true;
}

// 5. 单链表删除（删除第i个位置结点，用e返回删除值，1<=i<=表长）
bool ListDeleteLinkList(LinkList &L, int i, ElemType &e) {
    LNode *p = GetElemLinkList(L, i - 1); // 找到前驱结点（第i-1个）
    if (p == NULL || p->next == NULL) return false; // 前驱不存在或无待删结点
    
    LNode *q = p->next; // q指向待删除结点
    e = q->data;        // 保存删除值
    p->next = q->next;  // 前驱指向待删结点的后继
    free(q);            // 释放待删结点内存
    return true;
}

2.3 双链表

// 双链表结点结构
typedef struct DNode {
    ElemType data;         // 数据域
    struct DNode *prior;   // 前驱指针
    struct DNode *next;    // 后继指针
} DNode, *DLinkList;

// 双链表初始化（带头结点）
bool InitDLinkList(DLinkList &L) {
    L = (DNode *)malloc(sizeof(DNode));
    if (L == NULL) return false;
    L->prior = NULL; // 头结点前驱为NULL
    L->next = NULL;  // 头结点后继为NULL
    return true;
}

// 双链表插入（在p结点之后插入s结点）
bool DLinkListInsertAfter(DNode *p, DNode *s) {
    if (p == NULL || s == NULL) return false;
    
    s->next = p->next;
    if (p->next != NULL) { // 若p有后继，需修改后继的前驱
        p->next->prior = s;
    }
    s->prior = p;
    p->next = s;
    return true;
}

// 双链表删除（删除p结点的后继结点q）
bool DLinkListDeleteNext(DNode *p) {
    if (p == NULL || p->next == NULL) return false;
    
    DNode *q = p->next;
    p->next = q->next;
    if (q->next != NULL) { // 若q有后继，需修改后继的前驱
        q->next->prior = p;
    }
    free(q);
    return true;
}

2.4 循环单链表（带头结点）

// 循环单链表初始化
bool InitCircLinkList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode));
    if (L == NULL) return false;
    L->next = L; // 头结点后继指向自身（空表）
    return true;
}

// 循环单链表判空（头结点后继是否指向自身）
bool CircLinkListEmpty(LinkList L) {
    return L->next == L;
}

二、栈和队列

1. 栈

1.1 顺序栈

// 顺序栈结构体
#define StackMaxSize 50
typedef struct {
    ElemType data[StackMaxSize]; // 存储栈元素
    int top;                     // 栈顶指针（初始为-1）
} SqStack;

// 1. 顺序栈初始化
void InitSqStack(SqStack &S) {
    S.top = -1; // 栈空标志
}

// 2. 判栈空
bool StackEmpty(SqStack S) {
    return S.top == -1;
}

// 3. 进栈（压栈）
bool Push(SqStack &S, ElemType x) {
    if (S.top == StackMaxSize - 1) return false; // 栈满
    S.data[++S.top] = x; // 栈顶指针先加1，再存元素
    return true;
}

// 4. 出栈（弹栈）
bool Pop(SqStack &S, ElemType &x) {
    if (StackEmpty(S)) return false; // 栈空
    x = S.data[S.top--]; // 先取栈顶元素，再减指针
    return true;
}

// 5. 读栈顶元素
bool GetTop(SqStack S, ElemType &x) {
    if (StackEmpty(S)) return false; // 栈空
    x = S.data[S.top]; // 仅读取，不修改指针
    return true;
}

1.2 链栈

// 链栈结构体（不带头结点，栈顶指针即头指针）
typedef struct LinkNode {
    ElemType data;       // 数据域
    struct LinkNode *next; // 指针域
} LinkNode, *LiStack;

// 1. 链栈初始化（空栈）
void InitLiStack(LiStack &S) {
    S = NULL; // 栈顶指针为NULL
}

// 2. 判栈空
bool LiStackEmpty(LiStack S) {
    return S == NULL;
}

// 3. 进栈
bool LiStackPush(LiStack &S, ElemType x) {
    // 创建新结点（栈顶插入）
    LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode));
    if (p == NULL) return false;
    p->data = x;
    p->next = S; // 新结点后继指向原栈顶
    S = p;       // 栈顶指针指向新结点
    return true;
}

// 4. 出栈
bool LiStackPop(LiStack &S, ElemType &x) {
    if (LiStackEmpty(S)) return false; // 栈空
    LinkNode *p = S;       // p指向栈顶结点
    x = p->data;           // 保存栈顶值
    S = S->next;           // 栈顶指针下移
    free(p);               // 释放原栈顶结点
    return true;
}

2. 队列

2.1 循环队列（顺序存储）

// 循环队列结构体
#define QueueMaxSize 50
typedef struct {
    ElemType data[QueueMaxSize]; // 存储队列元素
    int front;                   // 队头指针（指向队头元素）
    int rear;                    // 队尾指针（指向队尾元素下一个位置）
} SqQueue;

// 1. 循环队列初始化（front=rear=0）
void InitSqQueue(SqQueue &Q) {
    Q.front = Q.rear = 0;
}

// 2. 判队空（front==rear）
bool QueueEmpty(SqQueue Q) {
    return Q.front == Q.rear;
}

// 3. 判队满（(rear+1)%QueueMaxSize == front）
bool QueueFull(SqQueue Q) {
    return (Q.rear + 1) % QueueMaxSize == Q.front;
}

// 4. 入队
bool EnQueue(SqQueue &Q, ElemType x) {
    if (QueueFull(Q)) return false; // 队满
    Q.data[Q.rear] = x;             // 存入队尾
    Q.rear = (Q.rear + 1) % QueueMaxSize; // 队尾指针后移（循环）
    return true;
}

// 5. 出队
bool DeQueue(SqQueue &Q, ElemType &x) {
    if (QueueEmpty(Q)) return false; // 队空
    x = Q.data[Q.front];            // 取出队头
    Q.front = (Q.front + 1) % QueueMaxSize; // 队头指针后移（循环）
    return true;
}

// 6. 读队头元素
bool GetHead(SqQueue Q, ElemType &x) {
    if (QueueEmpty(Q)) return false; // 队空
    x = Q.data[Q.front];
    return true;
}

// 7. 计算队列元素个数
int QueueLength(SqQueue Q) {
    return (Q.rear - Q.front + QueueMaxSize) % QueueMaxSize;
}

2.2 链队列

// 链队列结构体（带头结点，front指向头结点，rear指向队尾结点）
typedef struct LinkNode { // 队列结点
    ElemType data;
    struct LinkNode *next;
} LinkNode;

typedef struct { // 队列头、尾指针
    LinkNode *front, *rear;
} LinkQueue;

// 1. 链队列初始化
void InitLinkQueue(LinkQueue &Q) {
    // 创建头结点
    Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
    if (Q.front == NULL) exit(1);
    Q.front->next = NULL; // 头结点后继为NULL
}

// 2. 判队空
bool LinkQueueEmpty(LinkQueue Q) {
    return Q.front == Q.rear;
}

// 3. 入队
bool EnLinkQueue(LinkQueue &Q, ElemType x) {
    // 创建新结点
    LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode));
    if (p == NULL) return false;
    p->data = x;
    p->next = NULL;
    
    Q.rear->next = p; // 队尾结点指向新结点
    Q.rear = p;       // 队尾指针更新为新结点
    return true;
}

// 4. 出队
bool DeLinkQueue(LinkQueue &Q, ElemType &x) {
    if (LinkQueueEmpty(Q)) return false; // 队空
    
    LinkNode *p = Q.front->next; // p指向队头元素结点
    x = p->data;                 // 保存队头值
    Q.front->next = p->next;     // 头结点指向队头下一个
    
    // 若队头是最后一个元素，队尾指针需指向头结点
    if (Q.rear == p) {
        Q.rear = Q.front;
    }
    free(p); // 释放队头结点
    return true;
}

三、树和二叉树

1. 二叉树结构体（二叉链表）

// 二叉树结点结构
typedef struct BiTNode {
    ElemType data;                 // 数据域
    struct BiTNode *lchild, *rchild; // 左、右孩子指针
} BiTNode, *BiTree;

2. 二叉树遍历（递归实现）

// 1. 先序遍历（根 -> 左 -> 右）
void PreOrder(BiTree T) {
    if (T != NULL) {
        printf("%d ", T->data);    // 访问根结点
        PreOrder(T->lchild);       // 递归遍历左子树
        PreOrder(T->rchild);       // 递归遍历右子树
    }
}

// 2. 中序遍历（左 -> 根 -> 右）
void InOrder(BiTree T) {
    if (T != NULL) {
        InOrder(T->lchild);        // 递归遍历左子树
        printf("%d ", T->data);    // 访问根结点
        InOrder(T->rchild);        // 递归遍历右子树
    }
}

// 3. 后序遍历（左 -> 右 -> 根）
void PostOrder(BiTree T) {
    if (T != NULL) {
        PostOrder(T->lchild);      // 递归遍历左子树
        PostOrder(T->rchild);      // 递归遍历右子树
        printf("%d ", T->data);    // 访问根结点
    }
}

// 4. 层次遍历（借助队列）
void LevelOrder(BiTree T) {
    LinkQueue Q;
    InitLinkQueue(Q);              // 初始化辅助队列
    
    if (T != NULL) {
        EnLinkQueue(Q, T->data);   // 根结点入队（注：实际应存结点指针，此处简化）
        Q.front->next->data = T->data; // 修正：队列存储结点指针，此处补全逻辑
        BiTNode *p = T;
        EnLinkQueue(Q, p->data);   // 实际代码应存储p指针，此处简化为数据
    }
    
    while (!LinkQueueEmpty(Q)) {
        BiTNode *p;                // 实际应出队结点指针，此处简化
        ElemType x;
        DeLinkQueue(Q, x);         // 出队（简化为数据）
        printf("%d ", x);          // 访问结点
        
        // 左孩子入队
        if (p->lchild != NULL) {
            EnLinkQueue(Q, p->lchild->data);
        }
        // 右孩子入队
        if (p->rchild != NULL) {
            EnLinkQueue(Q, p->rchild->data);
        }
    }
}

3. 二叉排序树

// 1. 二叉排序树插入（递归）
bool BST_Insert(BiTree &T, ElemType key) {
    if (T == NULL) { // 空树，创建新结点
        T = (BiTNode *)malloc(sizeof(BiTNode));
        T->data = key;
        T->lchild = T->rchild = NULL;
        return true;
    } else if (key == T->data) {
        return false; // 关键字已存在，插入失败
    } else if (key < T->data) {
        return BST_Insert(T->lchild, key); // 插入左子树
    } else {
        return BST_Insert(T->rchild, key); // 插入右子树
    }
}

// 2. 二叉排序树构造（从数组创建）
void CreateBST(BiTree &T, ElemType key[], int n) {
    T = NULL; // 初始为空树
    for (int i = 0; i < n; i++) {
        BST_Insert(T, key[i]); // 逐个插入关键字
    }
}

// 3. 二叉排序树查找（递归）
BiTNode *BST_Search(BiTree T, ElemType key) {
    if (T == NULL || T->data == key) {
        return T; // 空树或找到目标结点
    } else if (key < T->data) {
        return BST_Search(T->lchild, key); // 左子树查找
    } else {
        return BST_Search(T->rchild, key); // 右子树查找
    }
}

4. 哈夫曼树（构造与编码）

// 哈夫曼树结点结构
typedef struct {
    ElemType weight; // 结点权重
    int parent, lchild, rchild; // 父结点、左/右孩子下标
} HTNode, *HuffmanTree;

// 哈夫曼编码表（每个字符的编码）
typedef char **HuffmanCode;

// 1. 选择权值最小的两个结点（s1 < s2）
void Select(HuffmanTree HT, int n, int &s1, int &s2) {
    int min1 = INT_MAX, min2 = INT_MAX;
    s1 = s2 = 0;
    for (int i = 1; i <= n; i++) {
        if (HT[i].parent == 0) { // 未被选作子结点
            if (HT[i].weight < min1) {
                min2 = min1;
                s2 = s1;
                min1 = HT[i].weight;
                s1 = i;
            } else if (HT[i].weight < min2) {
                min2 = HT[i].weight;
                s2 = i;
            }
        }
    }
}

// 2. 构造哈夫曼树
void CreateHuffmanTree(HuffmanTree &HT, int n) {
    if (n <= 1) return;
    int m = 2 * n - 1; // 哈夫曼树总结点数
    HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); // 下标从1开始
    
    // 初始化前n个结点（叶子结点）
    for (int i = 1; i <= n; i++) {
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
        printf("输入第%d个叶子结点的权重：", i);
        scanf("%d", &HT[i].weight);
    }
    
    // 初始化后m-n个结点（非叶子结点）
    for (int i = n + 1; i <= m; i++) {
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
        HT[i].weight = 0;
    }
    
    // 构建哈夫曼树
    for (int i = n + 1; i <= m; i++) {
        int s1, s2;
        Select(HT, i - 1, s1, s2); // 选两个最小权重结点
        HT[s1].parent = i;
        HT[s2].parent = i;
        HT[i].lchild = s1; // 左孩子权重更小
        HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
}

// 3. 生成哈夫曼编码（从叶子到根逆向求）
void CreateHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n) {
    HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); // 下标从1开始
    char *cd = (char *)malloc(n * sizeof(char)); // 临时存储编码（最长n-1位）
    cd[n - 1] = '\0'; // 编码结束符
    
    for (int i = 1; i <= n; i++) {
        int start = n - 1; // 从编码末尾开始填
        int c = i;
        int f = HT[i].parent; // 父结点下标
        while (f != 0) { // 直到根结点（parent=0）
            start--;
            if (HT[f].lchild == c) {
                cd[start] = '0'; // 左孩子为0
            } else {
                cd[start] = '1'; // 右孩子为1
            }
            c = f;
            f = HT[f].parent;
        }
        // 分配内存并保存编码
        HC[i] = (char *)malloc((n - start) * sizeof(char));
        strcpy(HC[i], &cd[start]);
    }
    free(cd); // 释放临时空间
}

四、图

1. 图的存储结构

1.1 邻接矩阵（无向图/有向图/带权图）

#define MaxVertexNum 100 // 最大顶点数
#define INF 32767        // 表示无穷大（无边）

// 邻接矩阵结构体
typedef struct {
    char Vex[MaxVertexNum];          // 顶点表（存储顶点信息，如字符）
    int Edge[MaxVertexNum][MaxVertexNum]; // 邻接矩阵（边的权重）
    int vexnum, arcnum;              // 顶点数和边数
} MGraph;

// 1. 初始化邻接矩阵（无向图）
void InitMGraph(MGraph &G, int n) {
    G.vexnum = n;
    G.arcnum = 0;
    
    // 初始化顶点表（简化：顶点编号0~n-1，此处用字符'A'~'Z'）
    for (int i = 0; i < G.vexnum; i++) {
        G.Vex[i] = 'A' + i;
    }
    
    // 初始化邻接矩阵（无边为INF，自环为0）
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = 0; j < G.vexnum; j++) {
            G.Edge[i][j] = (i == j) ? 0 : INF;
        }
    }
}

// 2. 添加无向边（v1、v2为顶点下标，w为权重）
void AddUndirEdge(MGraph &G, int v1, int v2, int w) {
    G.Edge[v1][v2] = w;
    G.Edge[v2][v1] = w; // 无向图对称
    G.arcnum++;
}

// 3. 添加有向边（v1为弧尾，v2为弧头，w为权重）
void AddDirEdge(MGraph &G, int v1, int v2, int w) {
    G.Edge[v1][v2] = w;
    G.arcnum++;
}

1.2 邻接表（无向图/有向图）

// 邻接表边结点结构
typedef struct ArcNode {
    int adjvex;                 // 邻接点下标
    int weight;                 // 边的权重（可选）
    struct ArcNode *nextarc;    // 下一条边的指针
} ArcNode;

// 邻接表顶点结构
typedef struct VNode {
    char data;                  // 顶点信息
    ArcNode *firstarc;          // 指向第一条边的指针
} VNode, AdjList[MaxVertexNum];

// 邻接表图结构
typedef struct {
    AdjList vertices;           // 顶点数组
    int vexnum, arcnum;         // 顶点数和边数
} ALGraph;

// 1. 初始化邻接表
void InitALGraph(ALGraph &G, int n) {
    G.vexnum = n;
    G.arcnum = 0;
    
    // 初始化顶点（顶点编号0~n-1，字符'A'~'Z'）
    for (int i = 0; i < G.vexnum; i++) {
        G.vertices[i].data = 'A' + i;
        G.vertices[i].firstarc = NULL; // 初始无邻接边
    }
}

// 2. 添加无向边（v1、v2为顶点下标，w为权重）
void AddUndirArc(ALGraph &G, int v1, int v2, int w) {
    // 创建v1指向v2的边结点
    ArcNode *p1 = (ArcNode *)malloc(sizeof(ArcNode));
    p1->adjvex = v2;
    p1->weight = w;
    p1->nextarc = G.vertices[v1].firstarc;
    G.vertices[v1].firstarc = p1;
    
    // 创建v2指向v1的边结点（无向图对称）
    ArcNode *p2 = (ArcNode *)malloc(sizeof(ArcNode));
    p2->adjvex = v1;
    p2->weight = w;
    p2->nextarc = G.vertices[v2].firstarc;
    G.vertices[v2].firstarc = p2;
    
    G.arcnum++;
}

// 3. 添加有向边（v1为弧尾，v2为弧头，w为权重）
void AddDirArc(ALGraph &G, int v1, int v2, int w) {
    ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
    p->adjvex = v2;
    p->weight = w;
    p->nextarc = G.vertices[v1].firstarc;
    G.vertices[v1].firstarc = p;
    
    G.arcnum++;
}

2. 图的遍历（DFS+BFS）

// 全局变量：访问标记数组（0未访问，1已访问）
bool visited[MaxVertexNum];

// 1. 邻接矩阵深度优先遍历（DFS）
void DFS_MGraph(MGraph G, int v) {
    printf("%c ", G.Vex[v]); // 访问当前顶点
    visited[v] = true;       // 标记为已访问
    
    // 遍历所有邻接点
    for (int w = 0; w < G.vexnum; w++) {
        // 存在边且未访问
        if (G.Edge[v][w] != INF && G.Edge[v][w] != 0 && !visited[w]) {
            DFS_MGraph(G, w); // 递归访问
        }
    }
}

// 2. 邻接表深度优先遍历（DFS）
void DFS_ALGraph(ALGraph G, int v) {
    printf("%c ", G.vertices[v].data); // 访问当前顶点
    visited[v] = true;                 // 标记为已访问
    
    ArcNode *p = G.vertices[v].firstarc; // 指向第一条边
    while (p != NULL) {
        int w = p->adjvex;
        if (!visited[w]) {
            DFS_ALGraph(G, w); // 递归访问邻接点
        }
        p = p->nextarc; // 访问下一条边
    }
}

// 3. 邻接矩阵广度优先遍历（BFS，借助队列）
void BFS_MGraph(MGraph G, int v) {
    SqQueue Q;
    InitSqQueue(Q);          // 初始化队列
    
    printf("%c ", G.Vex[v]); // 访问当前顶点
    visited[v] = true;       // 标记为已访问
    EnQueue(Q, v);           // 顶点下标入队
    
    while (!QueueEmpty(Q)) {
        int u;
        DeQueue(Q, u);       // 出队顶点u
        
        // 遍历u的所有邻接点
        for (int w = 0; w < G.vexnum; w++) {
            if (G.Edge[u][w] != INF && G.Edge[u][w] != 0 && !visited[w]) {
                printf("%c ", G.Vex[w]); // 访问w
                visited[w] = true;       // 标记
                EnQueue(Q, w);           // w入队
            }
        }
    }
}

// 4. 邻接表广度优先遍历（BFS）
void BFS_ALGraph(ALGraph G, int v) {
    SqQueue Q;
    InitSqQueue(Q);                  // 初始化队列
    
    printf("%c ", G.vertices[v].data); // 访问当前顶点
    visited[v] = true;                 // 标记为已访问
    EnQueue(Q, v);                     // 顶点下标入队
    
    while (!QueueEmpty(Q)) {
        int u;
        DeQueue(Q, u);                 // 出队顶点u
        
        ArcNode *p = G.vertices[u].firstarc; // 指向u的第一条边
        while (p != NULL) {
            int w = p->adjvex;
            if (!visited[w]) {
                printf("%c ", G.vertices[w].data); // 访问w
                visited[w] = true;                 // 标记
                EnQueue(Q, w);                     // w入队
            }
            p = p->nextarc; // 下一条边
        }
    }
}

// 图的全遍历（处理非连通图）
void TraverseGraph(ALGraph G) {
    // 初始化访问标记
    for (int i = 0; i < G.vexnum; i++) {
        visited[i] = false;
    }
    // 遍历所有顶点，未访问则开始DFS/BFS
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            DFS_ALGraph(G, i); // 或BFS_ALGraph(G, i)
        }
    }
}

3. 最小生成树（Prim算法+Kruskal算法）

3.1 Prim算法（邻接矩阵，从顶点出发）

// Prim算法求最小生成树（无向带权图，从v0开始）
void Prim(MGraph G, int v0) {
    int lowcost[MaxVertexNum]; // 记录顶点到生成树的最小权重
    int adjvex[MaxVertexNum];  // 记录最小权重边的邻接点
    int sum = 0;               // 最小生成树总权重
    
    // 初始化：v0加入生成树
    for (int i = 0; i < G.vexnum; i++) {
        lowcost[i] = G.Edge[v0][i]; // v0到各顶点的权重
        adjvex[i] = v0;             // 初始邻接点均为v0
    }
    lowcost[v0] = 0; // 标记v0已加入生成树
    
    // 选择剩余n-1个顶点
    for (int i = 1; i < G.vexnum; i++) {
        int min = INF;
        int k = -1;
        // 找lowcost中最小的顶点k（未加入生成树）
        for (int j = 0; j < G.vexnum; j++) {
            if (lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }
        
        // 输出边（adjvex[k], k）及权重
        printf("边(%c, %c) 权重：%d\n", G.Vex[adjvex[k]], G.Vex[k], min);
        sum += min;
        lowcost[k] = 0; // 标记k已加入生成树
        
        // 更新lowcost：k加入后，其他顶点到生成树的最小权重
        for (int j = 0; j < G.vexnum; j++) {
            if (lowcost[j] != 0 && G.Edge[k][j] < lowcost[j]) {
                lowcost[j] = G.Edge[k][j];
                adjvex[j] = k;
            }
        }
    }
    printf("最小生成树总权重：%d\n", sum);
}

3.2 Kruskal算法（按边选，需并查集）

// 边的结构体（用于Kruskal算法）
typedef struct {
    int v1, v2; // 边的两个顶点下标
    int weight; // 边的权重
} Edge;

// 并查集查找（找顶点u的根，路径压缩）
int Find(int parent[], int u) {
    if (parent[u] != u) {
        parent[u] = Find(parent, parent[u]); // 路径压缩
    }
    return parent[u];
}

// 并查集合并（合并u和v的集合）
void Union(int parent[], int u, int v) {
    int rootU = Find(parent, u);
    int rootV = Find(parent, v);
    if (rootU != rootV) {
        parent[rootV] = rootU; // v的根指向u的根
    }
}

// Kruskal算法求最小生成树（按边权重排序，选无环的最小边）
void Kruskal(MGraph G) {
    Edge edges[MaxVertexNum * MaxVertexNum]; // 存储所有边
    int edgeCnt = 0;
    int sum = 0; // 最小生成树总权重
    
    // 1. 从邻接矩阵提取所有无向边（避免重复，v1 < v2）
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = i + 1; j < G.vexnum; j++) {
            if (G.Edge[i][j] != INF && G.Edge[i][j] != 0) {
                edges[edgeCnt].v1 = i;
                edges[edgeCnt].v2 = j;
                edges[edgeCnt].weight = G.Edge[i][j];
                edgeCnt++;
            }
        }
    }
    
    // 2. 按边权重从小到大排序（冒泡排序简化，实际用快速排序）
    for (int i = 0; i < edgeCnt - 1; i++) {
        for (int j = 0; j < edgeCnt - i - 1; j++) {
            if (edges[j].weight > edges[j + 1].weight) {
                Edge temp = edges[j];
                edges[j] = edges[j + 1];
                edges[j + 1] = temp;
            }
        }
    }
    
    // 3. 初始化并查集（parent[i] = i）
    int parent[MaxVertexNum];
    for (int i = 0; i < G.vexnum; i++) {
        parent[i] = i;
    }
    
    // 4. 选边构建最小生成树
    for (int i = 0; i < edgeCnt; i++) {
        int u = edges[i].v1;
        int v = edges[i].v2;
        int rootU = Find(parent, u);
        int rootV = Find(parent, v);
        
        if (rootU != rootV) { // 无环，选这条边
            printf("边(%c, %c) 权重：%d\n", G.Vex[u], G.Vex[v], edges[i].weight);
            sum += edges[i].weight;
            Union(parent, u, v); // 合并两个集合
        }
    }
    printf("最小生成树总权重：%d\n", sum);
}

4. 最短路径（Dijkstra算法）

// Dijkstra算法（邻接矩阵，求v0到所有顶点的最短路径）
void Dijkstra(MGraph G, int v0) {
    int dist[MaxVertexNum];  // dist[i]：v0到i的最短路径长度
    bool visited[MaxVertexNum]; // 标记顶点是否已确定最短路径
    int path[MaxVertexNum];  // path[i]：v0到i的最短路径中i的前驱
    
    // 1. 初始化
    for (int i = 0; i < G.vexnum; i++) {
        dist[i] = G.Edge[v0][i];       // 初始为v0到i的直接边权重
        visited[i] = false;            // 均未确定
        path[i] = (dist[i] != INF) ? v0 : -1; // 有直接边则前驱为v0，否则-1
    }
    dist[v0] = 0;         // v0到自身路径长度为0
    visited[v0] = true;   // 标记v0已确定
    
    // 2. 确定剩余n-1个顶点的最短路径
    for (int i = 1; i < G.vexnum; i++) {
        // 找dist中最小的未确定顶点u
        int min = INF;
        int u = -1;
        for (int j = 0; j < G.vexnum; j++) {
            if (!visited[j] && dist[j] < min) {
                min = dist[j];
                u = j;
            }
        }
        if (u == -1) break; // 无可达顶点，退出
        visited[u] = true;  // 标记u已确定
        
        // 更新u的邻接点的dist
        for (int w = 0; w < G.vexnum; w++) {
            // 未确定、有边、v0->u->w比v0->w短
            if (!visited[w] && G.Edge[u][w] != INF && dist[u] + G.Edge[u][w] < dist[w]) {
                dist[w] = dist[u] + G.Edge[u][w];
                path[w] = u; // 更新前驱为u
            }
        }
    }
    
    // 3. 输出结果（v0到各顶点的最短路径和长度）
    for (int i = 0; i < G.vexnum; i++) {
        if (dist[i] == INF) {
            printf("%c到%c：无路径\n", G.Vex[v0], G.Vex[i]);
        } else {
            printf("%c到%c：路径长度=%d，路径：", G.Vex[v0], G.Vex[i], dist[i]);
            // 回溯路径（从i到v0）
            int temp[MaxVertexNum], cnt = 0;
            for (int j = i; j != -1; j = path[j]) {
                temp[cnt++] = j;
            }
            // 反向输出路径
            for (int j = cnt - 1; j >= 0; j--) {
                printf("%c%s", G.Vex[temp[j]], (j == 0) ? "\n" : "->");
            }
        }
    }
}

5. 拓扑排序（AOV网，邻接表）

// 拓扑排序（邻接表，返回拓扑序列，成功返回true）
bool TopologicalSort(ALGraph G, int topo[]) {
    int inDegree[MaxVertexNum] = {0}; // 顶点入度数组
    SqQueue Q;
    InitSqQueue(Q);
    int count = 0; // 记录已输出的顶点数
    
    // 1. 计算所有顶点的入度
    for (int i = 0; i < G.vexnum; i++) {
        ArcNode *p = G.vertices[i].firstarc;
        while (p != NULL) {
            int w = p->adjvex;
            inDegree[w]++;
            p = p->nextarc;
        }
    }
    
    // 2. 入度为0的顶点入队
    for (int i = 0; i < G.vexnum; i++) {
        if (inDegree[i] == 0) {
            EnQueue(Q, i);
        }
    }
    
    // 3. 拓扑排序
    while (!QueueEmpty(Q)) {
        int u;
        DeQueue(Q, u);         // 出队入度为0的顶点u
        topo[count++] = u;     // 加入拓扑序列
        
        // 删除u的所有出边（邻接点入度-1）
        ArcNode *p = G.vertices[u].firstarc;
        while (p != NULL) {
            int w = p->adjvex;
            inDegree[w]--;
            if (inDegree[w] == 0) { // 入度为0则入队
                EnQueue(Q, w);
            }
            p = p->nextarc;
        }
    }
    
    // 若输出顶点数等于总顶点数，无环；否则有环
    return count == G.vexnum;
}

五、查找

1. 顺序查找（带哨兵）

// 顺序查找表结构体
typedef struct {
    ElemType *elem;  // 数据元素数组（0号为哨兵）
    int TableLen;    // 表长度（elem[1..TableLen]存储数据）
} SSTable;

// 顺序查找（带哨兵，查找关键字key，返回位序，失败返回0）
int Search_Seq(SSTable ST, ElemType key) {
    ST.elem[0] = key; // 哨兵：避免循环中判断越界
    int i = ST.TableLen;
    while (ST.elem[i] != key) {
        i--;
    }
    return i; // i=0则失败，否则为位序
}

2. 折半查找（二分查找，有序顺序表）

// 折半查找（有序顺序表L，查找key，返回下标，失败返回-1）
int Binary_Search(SSTable L, ElemType key) {
    int low = 1, high = L.TableLen; // 表元素从1开始
    while (low <= high) {
        int mid = (low + high) / 2; // 中间位置
        if (L.elem[mid] == key) {
            return mid; // 找到，返回下标
        } else if (L.elem[mid] > key) {
            high = mid - 1; // 左半区查找
        } else {
            low = mid + 1; // 右半区查找
        }
    }
    return -1; // 查找失败
}

3. 散列表（哈希表）

3.1 线性探测法解决冲突

#define HashTableSize 13 // 散列表长度（取质数）
#define NULL_KEY -32767  // 空关键字标记

// 散列表结构体
typedef struct {
    ElemType *elem;  // 散列表数组
    int count;       // 当前元素个数
} HashTable;

// 1. 初始化散列表
bool InitHashTable(HashTable &HT) {
    HT.count = 0;
    HT.elem = (ElemType *)malloc(HashTableSize * sizeof(ElemType));
    if (HT.elem == NULL) return false;
    
    // 初始化为空关键字
    for (int i = 0; i < HashTableSize; i++) {
        HT.elem[i] = NULL_KEY;
    }
    return true;
}

// 2. 散列函数（除留余数法）
int Hash(ElemType key) {
    return key % HashTableSize;
}

// 3. 线性探测插入（插入key，成功返回true，失败返回false）
bool InsertHash_Linear(HashTable &HT, ElemType key) {
    if (HT.count >= HashTableSize) return false; // 表满
    
    int addr = Hash(key); // 初始散列地址
    // 线性探测（冲突则addr=(addr+1)%HashTableSize）
    while (HT.elem[addr] != NULL_KEY) {
        addr = (addr + 1) % HashTableSize;
    }
    HT.elem[addr] = key; // 插入关键字
    HT.count++;
    return true;
}

// 4. 线性探测查找（查找key，成功返回地址，失败返回-1）
int SearchHash_Linear(HashTable HT, ElemType key) {
    int addr = Hash(key);
    // 线性探测（空关键字或找到则退出）
    while (HT.elem[addr] != NULL_KEY && HT.elem[addr] != key) {
        addr = (addr + 1) % HashTableSize;
    }
    if (HT.elem[addr] == key) {
        return addr; // 找到，返回地址
    } else {
        return -1; // 失败
    }
}

3.2 拉链法解决冲突

// 拉链法散列表结点结构
typedef struct HashNode {
    ElemType key;              // 关键字
    struct HashNode *next;     // 下一个结点指针
} HashNode;

typedef struct {
    HashNode *head[HashTableSize]; // 表头数组（每个元素是链表头指针）
    int count;                     // 当前元素个数
} HashTable_Link;

// 1. 初始化拉链法散列表
void InitHashTable_Link(HashTable_Link &HT) {
    HT.count = 0;
    for (int i = 0; i < HashTableSize; i++) {
        HT.head[i] = NULL; // 表头初始为NULL
    }
}

// 2. 拉链法插入（插入key）
bool InsertHash_Link(HashTable_Link &HT, ElemType key) {
    int addr = Hash(key); // 计算散列地址
    
    // 创建新结点
    HashNode *p = (HashNode *)malloc(sizeof(HashNode));
    if (p == NULL) return false;
    p->key = key;
    p->next = NULL;
    
    // 插入到对应链表的头部（简化）
    if (HT.head[addr] == NULL) {
        HT.head[addr] = p;
    } else {
        p->next = HT.head[addr];
        HT.head[addr] = p;
    }
    HT.count++;
    return true;
}

// 3. 拉链法查找（查找key，成功返回结点指针，失败返回NULL）
HashNode *SearchHash_Link(HashTable_Link HT, ElemType key) {
    int addr = Hash(key);
    HashNode *p = HT.head[addr];
    
    // 遍历对应链表
    while (p != NULL && p->key != key) {
        p = p->next;
    }
    return p; // 找到返回结点，否则返回NULL
}

六、排序

1. 插入排序

1.1 直接插入排序

// 直接插入排序（数组A，长度n，A[0]为哨兵）
void InsertSort(ElemType A[], int n) {
    int i, j;
    for (i = 2; i <= n; i++) { // 从第2个元素开始插入（A[1]已有序）
        if (A[i] < A[i - 1]) { // 当前元素小于前驱，需插入
            A[0] = A[i];       // 哨兵：保存当前元素
            // 从后往前查找插入位置
            for (j = i - 1; A[0] < A[j]; j--) {
                A[j + 1] = A[j]; // 元素后移
            }
            A[j + 1] = A[0]; // 插入到正确位置
        }
    }
}

1.2 希尔排序（增量序列d=5,3,1）

// 希尔排序（数组A，长度n）
void ShellSort(ElemType A[], int n) {
    int i, j, d;
    // 增量序列：d=5,3,1（可根据需求调整）
    for (d = 5; d >= 1; d--) {
        // 对每个增量d，进行直接插入排序
        for (i = d + 1; i <= n; i++) {
            if (A[i] < A[i - d]) { // 当前元素小于前驱
                A[0] = A[i];       // 哨兵
                // 查找插入位置
                for (j = i - d; j > 0 && A[0] < A[j]; j -= d) {
                    A[j + d] = A[j]; // 元素后移d位
                }
                A[j + d] = A[0]; // 插入
            }
        }
    }
}

2. 交换排序

2.1 冒泡排序

// 冒泡排序（数组A，长度n，从小到大）
void BubbleSort(ElemType A[], int n) {
    for (int i = 0; i < n - 1; i++) { // 最多n-1趟
        bool flag = false; // 标记本趟是否发生交换
        // 从后往前比较，将最小元素"冒泡"到前面
        for (int j = n - 1; j > i; j--) {
            if (A[j - 1] > A[j]) {
                // 交换A[j-1]和A[j]
                ElemType temp = A[j - 1];
                A[j - 1] = A[j];
                A[j] = temp;
                flag = true; // 发生交换
            }
        }
        if (!flag) break; // 本趟无交换，说明已有序，提前退出
    }
}

2.2 快速排序（递归）

// 一趟快速排序（以A[low]为枢轴，返回枢轴最终位置）
int Partition(ElemType A[], int low, int high) {
    ElemType pivot = A[low]; // 枢轴元素
    while (low < high) {
        // 从右往左找小于枢轴的元素
        while (low < high && A[high] >= pivot) {
            high--;
        }
        A[low] = A[high]; // 移到左半区
        
        // 从左往右找大于枢轴的元素
        while (low < high && A[low] <= pivot) {
            low++;
        }
        A[high] = A[low]; // 移到右半区
    }
    A[low] = pivot; // 枢轴放到最终位置
    return low;     // 返回枢轴位置
}

// 快速排序（递归）
void QuickSort(ElemType A[], int low, int high) {
    if (low < high) {
        int pivotPos = Partition(A, low, high); // 一趟排序，获枢轴位置
        QuickSort(A, low, pivotPos - 1);        // 递归左子表
        QuickSort(A, pivotPos + 1, high);       // 递归右子表
    }
}

3. 选择排序

3.1 简单选择排序

// 简单选择排序（数组A，长度n，从小到大）
void SelectSort(ElemType A[], int n) {
    for (int i = 0; i < n - 1; i++) { // 选n-1次（最后一个元素自动有序）
        int min = i; // 记录最小元素下标
        // 找i~n-1中最小元素
        for (int j = i + 1; j < n; j++) {
            if (A[j] < A[min]) {
                min = j;
            }
        }
        // 交换A[i]和A[min]
        if (min != i) {
            ElemType temp = A[i];
            A[i] = A[min];
            A[min] = temp;
        }
    }
}

3.2 堆排序

// 调整大根堆（i为待调整结点，n为堆的大小）
void HeadAdjust(ElemType A[], int i, int n) {
    ElemType temp = A[i]; // 保存待调整结点
    // j为i的左孩子
    for (int j = 2 * i + 1; j < n; j = 2 * j + 1) {
        // 选左、右孩子中较大的一个
        if (j + 1 < n && A[j] < A[j + 1]) {
            j++;
        }
        // 若待调整结点大于孩子，无需调整
        if (temp >= A[j]) {
            break;
        }
        // 孩子上移
        A[i] = A[j];
        i = j; // i指向孩子位置，继续向下调整
    }
    A[i] = temp; // 待调整结点放到最终位置
}

// 构建大根堆
void BuildMaxHeap(ElemType A[], int n) {
    // 从最后一个非叶子结点（n/2-1）开始调整
    for (int i = n / 2 - 1; i >= 0; i--) {
        HeadAdjust(A, i, n);
    }
}

// 堆排序（数组A，长度n，从小到大）
void HeapSort(ElemType A[], int n) {
    BuildMaxHeap(A, n); // 构建初始大根堆
    
    // n-1次交换+调整
    for (int i = n - 1; i > 0; i--) {
        // 交换堆顶（最大元素）和堆尾
        ElemType temp = A[0];
        A[0] = A[i];
        A[i] = temp;
        
        // 调整剩余i个元素为大根堆
        HeadAdjust(A, 0, i);
    }
}

4. 归并排序（二路归并，递归）

// 合并两个有序子表（A[low..mid]和A[mid+1..high]合并为有序表）
void Merge(ElemType A[], int low, int mid, int high) {
    ElemType *B = (ElemType *)malloc((high - low + 1) * sizeof(ElemType)); // 临时数组
    int i = low, j = mid + 1, k = 0;
    
    // 按顺序合并
    while (i <= mid && j <= high) {
        if (A[i] <= A[j]) {
            B[k++] = A[i++];
        } else {
            B[k++] = A[j++];
        }
    }
    
    // 处理剩余元素
    while (i <= mid) {
        B[k++] = A[i++];
    }
    while (j <= high) {
        B[k++] = A[j++];
    }
    
    // 复制回原数组
    for (k = 0, i = low; i <= high; k++, i++) {
        A[i] = B[k];
    }
    free(B); // 释放临时空间
}

// 二路归并排序（递归）
void MergeSort(ElemType A[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2; // 分中点
        MergeSort(A, low, mid);     // 递归左子表
        MergeSort(A, mid + 1, high); // 递归右子表
        Merge(A, low, mid, high);   // 合并
    }
}

5. 基数排序（链式，按位排序）

// 基数排序结点结构
typedef struct RadixNode {
    ElemType key;                // 关键字（假设为整数）
    struct RadixNode *next;      // 下一个结点指针
} RadixNode, *RadixList;

// 基数排序（链式，按个位、十位、百位...排序，maxBit为最大关键字的位数）
void RadixSort(RadixList &L, int maxBit) {
    // 初始化10个队列（0~9）
    RadixList queue[10], tail[10];
    for (int i = 0; i < 10; i++) {
        queue[i] = (RadixNode *)malloc(sizeof(RadixNode));
        queue[i]->next = NULL;
        tail[i] = queue[i];
    }
    
    RadixNode *p = L->next; // L为头结点，p指向首元结点
    for (int bit = 1; bit <= maxBit; bit++) { // 按位排序（从低位到高位）
        // 1. 将结点按当前位的值入队
        while (p != NULL) {
            // 取当前位的值（bit=1取个位，bit=2取十位...）
            int digit = (p->key / (int)pow(10, bit - 1)) % 10;
            // 入队
            tail[digit]->next = p;
            tail[digit] = p;
            p = p->next;
        }
        
        // 2. 从队列0~9依次出队，重新链接
        p = L; // p指向头结点，准备链接
        for (int i = 0; i < 10; i++) {
            if (queue[i]->next != NULL) {
                p->next = queue[i]->next;
                p = tail[i]; // p移到当前链尾
                tail[i]->next = NULL; // 队列清空
            }
        }
        p->next = NULL; // 链表收尾
        p = L->next;    // p指向新链表首元结点，准备下一轮
    }
    
    // 释放队列头结点
    for (int i = 0; i < 10; i++) {
        free(queue[i]);
    }
}

七、串（String）

1. 串的定长顺序存储结构

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

// 串的定长顺序存储（最大长度为255）
#define MaxStrLen 255
typedef struct {
    char ch[MaxStrLen + 1]; // 存储串（ch[0] unused，从ch[1]开始存字符）
    int length;             // 串的实际长度
} SString;

2. 串的核心操作实现

// 1. 串复制：将串S复制到串T
bool StrCopy(SString &T, SString S) {
    if (S.length > MaxStrLen) return false; // S长度超过最大限制
    // 复制字符（从ch[1]到ch[S.length]）
    for (int i = 1; i <= S.length; i++) {
        T.ch[i] = S.ch[i];
    }
    T.length = S.length; // 同步长度
    return true;
}

// 2. 判空操作：若S为空串，返回true
bool StrEmpty(SString S) {
    return S.length == 0;
}

// 3. 串比较：S>T返回1，S=T返回0，S<T返回-1
int StrCompare(SString S, SString T) {
    // 逐字符比较（直到其中一个串结束或字符不同）
    for (int i = 1; i <= S.length && i <= T.length; i++) {
        if (S.ch[i] != T.ch[i]) {
            return S.ch[i] - T.ch[i]; // 字符ASCII差值
        }
    }
    // 长度不同时，长串更大
    return S.length - T.length;
}

// 4. 求串长：返回串S的实际长度
int StrLength(SString S) {
    return S.length;
}

// 5. 求子串：从S的第pos个字符开始，取len个字符存入Sub
// 注：pos从1开始，需满足1<=pos<=S.length且0<=len<=S.length-pos+1
bool SubString(SString &Sub, SString S, int pos, int len) {
    // 检查参数合法性
    if (pos < 1 || pos > S.length || len < 0 || len > S.length - pos + 1) {
        return false;
    }
    // 复制子串
    for (int i = 1; i <= len; i++) {
        Sub.ch[i] = S.ch[pos + i - 1];
    }
    Sub.length = len;
    return true;
}

// 6. 串联接：将S1和S2连接成新串T（S1在前，S2在后）
bool Concat(SString &T, SString S1, SString S2) {
    // 总长度超过最大限制，连接失败
    if (S1.length + S2.length > MaxStrLen) {
        // 若需部分连接，可修改为仅复制S1全量+S2部分，此处按完整连接实现
        return false;
    }
    // 复制S1到T
    for (int i = 1; i <= S1.length; i++) {
        T.ch[i] = S1.ch[i];
    }
    // 复制S2到T的后续位置
    for (int i = 1; i <= S2.length; i++) {
        T.ch[S1.length + i] = S2.ch[i];
    }
    T.length = S1.length + S2.length;
    return true;
}

// 7. 模式匹配（简单BF算法）：找T在S中首次出现的位置，失败返回0
int Index(SString S, SString T) {
    int i = 1; // 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; // S回溯到上次匹配起始位置的下一个
            j = 1;         // T重置到第一个字符
        }
    }
    // 若T遍历完，返回首次匹配的起始位置（i-T.length）
    return j > T.length ? (i - T.length) : 0;
}

八、矩阵压缩存储

1. 对称矩阵（下三角压缩存储）

// 对称矩阵压缩存储（下三角+主对角线，存于一维数组）
#define MaxMatrixSize 100 // 原矩阵最大阶数
typedef struct {
    int *data; // 压缩存储数组，大小为n(n+1)/2
    int n;     // 原矩阵阶数
} SymmetricMatrix;

// 初始化对称矩阵（阶数为n）
bool InitSymmetricMatrix(SymmetricMatrix &M, int n) {
    if (n < 1 || n > MaxMatrixSize) return false;
    M.n = n;
    // 计算压缩数组大小：n(n+1)/2
    int size = n * (n + 1) / 2;
    M.data = (int *)malloc(size * sizeof(int));
    return M.data != NULL;
}

// 取值：获取原矩阵A[i][j]的值（i,j从1开始）
int GetSymmetricValue(SymmetricMatrix M, int i, int j) {
    if (i < 1 || i > M.n || j < 1 || j > M.n) {
        printf("矩阵下标越界\n");
        exit(1);
    }
    // 对称矩阵：A[i][j] = A[j][i]，统一存于下三角（i>=j）
    if (i < j) {
        int temp = i; i = j; j = temp; // 交换i,j，确保i>=j
    }
    // 压缩地址公式：k = i(i-1)/2 + j - 1（数组从0开始）
    int k = i * (i - 1) / 2 + j - 1;
    return M.data[k];
}

// 赋值：给原矩阵A[i][j]赋值为val（自动同步对称位置）
bool SetSymmetricValue(SymmetricMatrix &M, int i, int j, int val) {
    if (i < 1 || i > M.n || j < 1 || j > M.n) return false;
    // 处理对称位置，仅在下三角存储
    if (i >= j) {
        int k = i * (i - 1) / 2 + j - 1;
        M.data[k] = val;
    } else {
        int k = j * (j - 1) / 2 + i - 1;
        M.data[k] = val;
    }
    return true;
}

2. 下三角矩阵（压缩存储）

// 下三角矩阵压缩存储（下三角存值，上三角存常量c）
typedef struct {
    int *data; // 压缩数组，大小为n(n+1)/2 + 1（最后一位存常量c）
    int n;     // 原矩阵阶数
    int c;     // 上三角常量（通常为0）
} LowerTriMatrix;

// 初始化下三角矩阵
bool InitLowerTriMatrix(LowerTriMatrix &M, int n, int c) {
    if (n < 1 || n > MaxMatrixSize) return false;
    M.n = n;
    M.c = c;
    int size = n * (n + 1) / 2 + 1; // 下三角n(n+1)/2 + 常量1位
    M.data = (int *)malloc(size * sizeof(int));
    return M.data != NULL;
}

// 取值：获取A[i][j]的值（i,j从1开始）
int GetLowerTriValue(LowerTriMatrix M, int i, int j) {
    if (i < 1 || i > M.n || j < 1 || j > M.n) {
        printf("矩阵下标越界\n");
        exit(1);
    }
    if (i >= j) {
        // 下三角：地址k = i(i-1)/2 + j -1
        int k = i * (i - 1) / 2 + j - 1;
        return M.data[k];
    } else {
        // 上三角：返回常量c
        return M.c;
    }
}

3. 稀疏矩阵（三元组顺序存储）

// 稀疏矩阵三元组（行标、列标、值）
#define MaxTripleNum 1000 // 最大非零元素个数
typedef struct {
    int i, j; // 非零元素的行标、列标（从1开始）
    int e;    // 非零元素的值
} Triple;

// 稀疏矩阵的三元组存储结构
typedef struct {
    Triple data[MaxTripleNum + 1]; // 三元组数组（data[0] unused）
    int mu, nu, tu;                // 矩阵行数、列数、非零元素个数
} TSMatrix;

// 稀疏矩阵转置（普通算法：按列序遍历原矩阵）
bool TransposeTSMatrix(TSMatrix M, TSMatrix &T) {
    T.mu = M.nu; // T的行数 = M的列数
    T.nu = M.mu; // T的列数 = M的行数
    T.tu = M.tu; // 非零元素个数不变
    if (T.tu == 0) return true; // 空矩阵无需转置

    int col, p, q = 1; // q：T的三元组下标
    // 按原矩阵的列序（col从1到M.nu）遍历
    for (col = 1; col <= M.nu; col++) {
        // 遍历原矩阵所有三元组，找列标=col的元素
        for (p = 1; p <= M.tu; p++) {
            if (M.data[p].j == col) {
                // 转置后：行标=原列标，列标=原行标
                T.data[q].i = M.data[p].j;
                T.data[q].j = M.data[p].i;
                T.data[q].e = M.data[p].e;
                q++;
            }
        }
    }
    return true;
}

// 稀疏矩阵快速转置（借助辅助数组，时间复杂度O(mu+tu)）
bool FastTransposeTSMatrix(TSMatrix M, TSMatrix &T) {
    T.mu = M.nu;
    T.nu = M.mu;
    T.tu = M.tu;
    if (T.tu == 0) return true;

    // 辅助数组1：num[col] = 原矩阵第col列的非零元素个数
    int *num = (int *)calloc(M.nu + 1, sizeof(int));
    // 辅助数组2：cpot[col] = 原矩阵第col列第一个非零元素在T中的位置
    int *cpot = (int *)malloc((M.nu + 1) * sizeof(int));
    if (num == NULL || cpot == NULL) return false;

    // 步骤1：统计每列非零元素个数
    for (int p = 1; p <= M.tu; p++) {
        int col = M.data[p].j;
        num[col]++;
    }

    // 步骤2：计算每列第一个非零元素在T中的起始位置
    cpot[1] = 1;
    for (int col = 2; col <= M.nu; col++) {
        cpot[col] = cpot[col - 1] + num[col - 1];
    }

    // 步骤3：按原矩阵顺序遍历，直接放入T的对应位置
    for (int p = 1; p <= M.tu; p++) {
        int col = M.data[p].j;
        int q = cpot[col]; // T中的目标位置
        // 转置赋值
        T.data[q].i = M.data[p].j;
        T.data[q].j = M.data[p].i;
        T.data[q].e = M.data[p].e;
        cpot[col]++; // 该列下一个元素位置+1
    }

    free(num);
    free(cpot);
    return true;
}

九、图的关键路径（AOE网）

1. AOE网的邻接表存储

// AOE网边结点（含权值：活动持续时间）
typedef struct ArcNode {
    int adjvex;         // 邻接点（事件编号，从1开始）
    int weight;         // 活动持续时间
    struct ArcNode *nextarc; // 下一条边
} ArcNode;

// AOE网顶点结点（事件）
typedef struct VNode {
    int inDegree;       // 事件的入度（用于拓扑排序）
    ArcNode *firstarc;  // 指向第一条出边
} VNode;

// AOE网结构
typedef struct {
    VNode vertices[MaxVertexNum + 1]; // 顶点数组（从1开始编号）
    int vexnum, arcnum;               // 事件数、活动数
} AOEGraph;

2. 关键路径算法实现

#include <stdlib.h>
#include <limits.h>

// 1. 拓扑排序（附带计算事件最早发生时间ve）
// 返回：拓扑序列数组，ve数组；成功返回true，失败（有环）返回false
bool TopologicalSort_AOE(AOEGraph G, int topo[], int ve[]) {
    int queue[MaxVertexNum], front = 0, rear = 0;
    int count = 0; // 统计输出的事件数

    // 初始化：ve[事件] = 0（源点事件最早发生时间为0）
    for (int i = 1; i <= G.vexnum; i++) {
        ve[i] = 0;
        // 入度为0的事件入队（源点）
        if (G.vertices[i].inDegree == 0) {
            queue[rear++] = i;
        }
    }

    while (front < rear) {
        int u = queue[front++]; // 出队事件u
        topo[++count] = u;      // 加入拓扑序列

        // 遍历u的所有出边（活动u->v）
        ArcNode *p = G.vertices[u].firstarc;
        while (p != NULL) {
            int v = p->adjvex;
            G.vertices[v].inDegree--; // v的入度-1

            // 更新事件v的最早发生时间：ve[v] = max(ve[v], ve[u] + 活动持续时间)
            if (ve[v] < ve[u] + p->weight) {
                ve[v] = ve[u] + p->weight;
            }

            // 入度为0时入队
            if (G.vertices[v].inDegree == 0) {
                queue[rear++] = v;
            }
            p = p->nextarc;
        }
    }

    // 若输出事件数≠总事件数，说明有环
    return count == G.vexnum;
}

// 2. 计算事件最迟发生时间vl、活动最早e/最迟l开始时间，找出关键活动
void CriticalPath(AOEGraph G) {
    int *topo = (int *)malloc((G.vexnum + 1) * sizeof(int)); // 拓扑序列
    int *ve = (int *)malloc((G.vexnum + 1) * sizeof(int));   // 事件最早发生时间
    int *vl = (int *)malloc((G.vexnum + 1) * sizeof(int));   // 事件最迟发生时间

    // 步骤1：拓扑排序并计算ve
    if (!TopologicalSort_AOE(G, topo, ve)) {
        printf("AOE网存在环，无关键路径\n");
        free(topo); free(ve); free(vl);
        return;
    }

    // 步骤2：初始化vl（汇点事件最迟=最早，按逆拓扑序计算）
    for (int i = 1; i <= G.vexnum; i++) {
        vl[i] = ve[G.vexnum]; // 汇点：ve[vexnum]（假设最后一个事件是汇点）
    }

    // 逆拓扑序遍历，计算vl
    for (int i = G.vexnum; i >= 1; i--) {
        int u = topo[i]; // 取当前事件u
        ArcNode *p = G.vertices[u].firstarc;
        while (p != NULL) {
            int v = p->adjvex;
            // 事件u的最迟 = min(事件v的最迟 - 活动u->v的持续时间, 当前vl[u])
            if (vl[u] > vl[v] - p->weight) {
                vl[u] = vl[v] - p->weight;
            }
            p = p->nextarc;
        }
    }

    // 步骤3：遍历所有活动，计算e、l、d=l-e，d=0为关键活动
    printf("关键活动（u->v，持续时间，e，l，d）：\n");
    for (int u = 1; u <= G.vexnum; u++) {
        ArcNode *p = G.vertices[u].firstarc;
        while (p != NULL) {
            int v = p->adjvex;
            int weight = p->weight;
            int e = ve[u];                  // 活动最早开始时间 = 事件u的最早
            int l = vl[v] - weight;         // 活动最迟开始时间 = 事件v的最迟 - 持续时间
            int d = l - e;                  // 时间余量

            // 输出所有活动，标记关键活动（d=0）
            if (d == 0) {
                printf("关键活动：%d->%d，持续时间：%d，e=%d，l=%d，d=%d\n", 
                       u, v, weight, e, l, d);
            } else {
                printf("非关键活动：%d->%d，持续时间：%d，e=%d，l=%d，d=%d\n", 
                       u, v, weight, e, l, d);
            }
            p = p->nextarc;
        }
    }

    free(topo);
    free(ve);
    free(vl);
}

十、树与森林的转换

1. 树的孩子兄弟表示法

// 树的孩子兄弟表示法（便于转换为二叉树）
typedef struct CSNode {
    ElemType data;          // 结点数据
    struct CSNode *firstChild; // 指向第一个孩子
    struct CSNode *nextSibling; // 指向右兄弟
} CSNode, *CSTree;

2. 树转换为二叉树

// 树转二叉树：递归处理每个结点的孩子与兄弟关系
void TreeToBiTree(CSTree T, BiTree &BT) {
    if (T == NULL) {
        BT = NULL;
        return;
    }

    // 1. 创建二叉树根结点（树的根结点作为二叉树的根）
    BT = (BiTNode *)malloc(sizeof(BiTNode));
    BT->data = T->data;
    BT->rchild = NULL; // 树的根无兄弟，二叉树右孩子初始为NULL

    // 2. 递归处理第一个孩子（作为二叉树的左孩子）
    TreeToBiTree(T->firstChild, BT->lchild);

    // 3. 递归处理兄弟（第一个孩子的兄弟作为二叉树的右孩子）
    CSNode *sibling = T->firstChild != NULL ? T->firstChild->nextSibling : NULL;
    BiTNode *p = BT->lchild; // p指向左孩子（第一个孩子对应的二叉树结点）
    while (sibling != NULL) {
        BiTNode *q = (BiTNode *)malloc(sizeof(BiTNode));
        q->data = sibling->data;
        q->rchild = NULL;

        // 兄弟的孩子作为q的左孩子
        TreeToBiTree(sibling->firstChild, q->lchild);

        // 将q作为p的右孩子（兄弟关系转为右孩子）
        p->rchild = q;
        p = q;

        // 处理下一个兄弟
        sibling = sibling->nextSibling;
    }
}

3. 森林转换为二叉树

// 森林转二叉树：先将每棵树转二叉树，再将各二叉树的根作为兄弟链入
void ForestToBiTree(CSTree forest[], int treeNum, BiTree &BT) {
    if (treeNum == 0) {
        BT = NULL;
        return;
    }

    // 1. 第一棵树转为二叉树，作为最终二叉树的根
    TreeToBiTree(forest[0], BT);

    // 2. 后续每棵树转为二叉树后，作为前一棵二叉树的右孩子（兄弟关系）
    BiTNode *p = BT;
    for (int i = 1; i < treeNum; i++) {
        BiTree temp;
        TreeToBiTree(forest[i], temp);
        p->rchild = temp; // 前一棵的右孩子 = 当前树的二叉树
        p = temp;         // 移动到当前树的二叉树根
    }
}

十一、排序算法补充（基数排序）

// 基数排序（链式存储，按个位→十位→百位...排序）
#define Radix 10 // 基数（0-9）
typedef struct RadixNode {
    int key;                // 关键字（假设为整数）
    struct RadixNode *next; // 下一个结点
} RadixNode, *RadixList;

// 初始化基数排序链表（头结点）
void InitRadixList(RadixList &L) {
    L = (RadixNode *)malloc(sizeof(RadixNode));
    L->next = NULL;
}

// 插入结点到链表尾部
void InsertRadixNode(RadixList &L, int key) {
    RadixNode *newNode = (RadixNode *)malloc(sizeof(RadixNode));
    newNode->key = key;
    newNode->next = NULL;

    RadixNode *p = L;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = newNode;
}

// 获取关键字的第d位数字（d=1：个位，d=2：十位...）
int GetDigit(int key, int d) {
    for (int i = 1; i < d; i++) {
        key /= 10;
    }
    return key % 10;
}

// 基数排序（L为待排序链表，maxDigit为关键字最大位数）
void RadixSort(RadixList &L, int maxDigit) {
    // 初始化10个桶（0-9），每个桶含头、尾指针
    RadixList bucket[Radix], bucketTail[Radix];
    for (int i = 0; i < Radix; i++) {
        InitRadixList(bucket[i]);
        bucketTail[i] = bucket[i]; // 尾指针初始指向头结点
    }

    RadixNode *p = L->next; // 指向待排序链表的首元结点
    for (int d = 1; d <= maxDigit; d++) { // 按位排序（从低位到高位）
        // 1. 将结点按第d位数字入对应桶
        while (p != NULL) {
            int digit = GetDigit(p->key, d);
            // 入桶（尾插法，保持顺序）
            bucketTail[digit]->next = p;
            bucketTail[digit] = p;
            // 移动p到下一个结点
            RadixNode *temp = p;
            p = p->next;
            temp->next = NULL; // 断开原链表连接
        }

        // 2. 将10个桶的结点按顺序链接回原链表
        p = L; // p指向原链表头结点，准备链接
        for (int i = 0; i < Radix; i++) {
            if (bucket[i]->next != NULL) {
                p->next = bucket[i]->next;
                p = bucketTail[i]; // 移动到当前桶的尾结点
                bucket[i]->next = NULL; // 清空桶，准备下一轮
                bucketTail[i] = bucket[i]; // 重置桶尾指针
            }
        }
        p->next = NULL; // 链表收尾
        p = L->next;    // p指向新链表首元结点，准备下一轮排序
    }

    // 释放桶的头结点
    for (int i = 0; i < Radix; i++) {
        free(bucket[i]);
    }
}