伪代码版本 · C++

与 C 版内容一致，改用 C++ 语法书写（引用传参、bool 等），适合习惯用 C++ 作答的同学。

文件一览

序号	内容	文件
01	线性表	01_线性表.cpp
02	栈和队列	02_栈和队列.cpp
03	树与层序遍历	03_树与层序遍历.cpp
04	排序算法	04_排序算法.cpp
05	串与查找	05_串与查找.cpp
06	图的核心算法	06_图的核心算法.cpp

01 线性表

#include <iostream>
using namespace std;

/* =========================================
 * 408 统考数据结构核心代码 - 线性表 (C++ 伪代码及引用风格)
 * =========================================
 * 说明：408 官方教材（如王道、严蔚敏版）极爱使用 C++ 的引用 `&` 传参，
 * 这也是统考卷上最主流的写法，免去了冗余繁杂的指针二级解引。
 * 建议在考研试卷上使用本写法规避由于星号和地址符混乱丢分。
 */

#define MaxSize 50
typedef int ElemType;

// 1. 顺序表结构体定义
typedef struct {
    ElemType data[MaxSize];
    int length;
} SqList;

// 2. 单链表结构体定义
typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

/* -----------------------------------------
 * 【1】顺序表核心操作
 * ----------------------------------------- */

// 【重点】使用了 `&` 直接操作实体对象本身，无需使用指针箭头 `->`
void InitList(SqList &L) {
    L.length = 0;
}

// 顺序表插入
bool ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1) return false; // 判断 i 的范围是否有效
    if (L.length >= MaxSize) return false;       // 存满了不能插
    
    for (int j = L.length; j >= i; j--) {
        L.data[j] = L.data[j - 1];               // 将第 i 个元素及之后的元素后移
    }
    L.data[i - 1] = e;                           // 在位置 i 放上 e
    L.length++;
    return true;
}

// 顺序表删除
// 引用传入 e 直接带回结果
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--;
    return true;
}

/* -----------------------------------------
 * 【2】单链表核心操作
 * ----------------------------------------- */

// 头插法建立单链表（C++ `new` 关键字操作更清爽）
LinkList List_HeadInsert(LinkList &L) {
    LNode *s;
    int x;
    L = new LNode;       // 用 new 代替繁杂的 malloc
    L->next = NULL;
    
    cin >> x;
    while (x != 9999) { // 9999 为结束标志
        s = new LNode;
        s->data = x;
        
        // 核心两步
        s->next = L->next; 
        L->next = s;
        
        cin >> x;
    }
    return L;
}

// 找寻指定位置的结点
LNode* GetElem(LinkList L, int i) {
    if (i < 0) return NULL;
    if (i == 0) return L; // 返回头结点
    
    int j = 1;
    LNode *p = L->next;   // 从第一号存真实元素的结点起步
    
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p; // 到达第 i 个或者到底为空
}

// 逆置单链表（常考重点大题子操作！）
// 使用指针直接“原地逆置”法
void ReverseList(LinkList &L) {
    if (L->next == NULL || L->next->next == NULL) return; 
    
    LNode *p = L->next;       // 工作指针
    LNode *r = p->next;       // 防止断链丢掉后面的队伍
    L->next = NULL;           // 先将头结点摘下
    
    while (p != NULL) {
        r = p->next;          // 保留后路
        p->next = L->next;    // 进行头插
        L->next = p;
        p = r;                // 回到后路继续冲
    }
}

02 栈和队列

#include <iostream>
using namespace std;

/* =========================================
 * 408 统考数据结构核心代码 - 栈与队列 (C++ 引用风格)
 * ========================================= */

#define MaxSize 50
typedef int ElemType;

// 1. 顺序栈定义
typedef struct {
    ElemType data[MaxSize];
    int top; // 栈顶指针，初始为 -1
} SqStack;

// 2. 循环队列定义
typedef struct {
    ElemType data[MaxSize];
    int front, rear; // front 队头，rear 队尾
} SqQueue;


/* -----------------------------------------
 * 【1】顺序栈核心操作
 * ----------------------------------------- */

// 初始化
void InitStack(SqStack &S) {
    S.top = -1; // 纯面向对象引用，没有箭头 ->
}

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

// 进栈法
bool Push(SqStack &S, ElemType x) {
    if (S.top == MaxSize - 1) return false; // 栈满报错
    
    S.top = S.top + 1; // 先加指针
    S.data[S.top] = x; // 再入元素
    return true;
}

// 出栈法
// 传引用 &x，直接带回出栈的值
bool Pop(SqStack &S, ElemType &x) {
    if (S.top == -1) return false; // 栈空报错
    
    x = S.data[S.top]; // 先取元素
    S.top = S.top - 1; // 再减指针
    return true;
}


/* -----------------------------------------
 * 【2】循环队列核心操作 (牺牲一个单元法)
 * ----------------------------------------- */

// 初始化队列
void InitQueue(SqQueue &Q) {
    Q.front = Q.rear = 0;
}

// 判空 (首尾相遇)
bool QueueEmpty(SqQueue Q) {
    return Q.front == Q.rear;
}

// 入队
bool EnQueue(SqQueue &Q, ElemType x) {
    // 【考点】判断队满条件：尾指针的下一个位置是头指针时，就是满了
    if ((Q.rear + 1) % MaxSize == Q.front) return false;
    
    Q.data[Q.rear] = x; // 放入队列
    Q.rear = (Q.rear + 1) % MaxSize; // 队尾指针加一取模
    return true;
}

// 出队
bool DeQueue(SqQueue &Q, ElemType &x) {
    if (Q.front == Q.rear) return false; // 队空报错
    
    x = Q.data[Q.front]; // 先取出当前队头元素
    Q.front = (Q.front + 1) % MaxSize; // 队头指针加一取模
    return true;
}

03 树与层序遍历

#include <iostream>
#include <stack>
#include <queue>
using namespace std;

/* =========================================
 * 408 统考数据结构核心代码 - 树与遍历 (C++ 风格)
 * 利用了 C++ 内置的 <stack> 与 <queue> STL
 * 在考场中如果题目没有明文禁止，使用 STL 能极大的缩减非递归书写的复杂度！
 * ========================================= */

typedef int ElemType;

// 二叉树链式存储定义
typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

/* -----------------------------------------
 * 【1】递归遍历系列
 * ----------------------------------------- */

void visit(BiTNode *p) {
    cout << p->data << " ";
}

// 先序遍历 (NLR)
void PreOrder(BiTree T) {
    if (T != NULL) {
        visit(T);               // 访问根结点
        PreOrder(T->lchild);    // 遍历左子树
        PreOrder(T->rchild);    // 遍历右子树
    }
}

// 中序遍历 (LNR)
void InOrder(BiTree T) {
    if (T != NULL) {
        InOrder(T->lchild);     
        visit(T);               
        InOrder(T->rchild);     
    }
}

/* -----------------------------------------
 * 【2】借助 C++ STL stack 的非递归中序遍历
 * （在 408 算法真题中极其管用）
 * ----------------------------------------- */
void InOrderNonRecursive(BiTree T) {
    stack<BiTNode*> S;
    BiTree p = T;
    
    while (p != NULL || !S.empty()) {
        if (p != NULL) {
            S.push(p);       // 左路一条道走到黑入栈
            p = p->lchild;
        } else {
            p = S.top();     // 获取栈顶
            S.pop();         // 弹出栈顶
            visit(p);        // 访问它
            p = p->rchild;   // 开辟新航线
        }
    }
}

/* -----------------------------------------
 * 【3】借助 C++ STL queue 的层序遍历 (BFS)
 * ----------------------------------------- */
void LevelOrder(BiTree T) {
    queue<BiTNode*> Q;
    BiTree p;
    
    if(T != NULL) {
        Q.push(T); // 根节点入队
    }
    
    while(!Q.empty()) {
        p = Q.front(); // 取队头
        Q.pop();       // 出队
        visit(p);
        
        if (p->lchild != NULL) {
            Q.push(p->lchild);
        }
        if (p->rchild != NULL) {
            Q.push(p->rchild);
        }
    }
}

/* -----------------------------------------
 * 【4】求二叉树深度 (常考应用小操作)
 * ----------------------------------------- */
int TreeDepth(BiTree T) {
    if (T == NULL) return 0;
    
    int ldepth = TreeDepth(T->lchild);
    int rdepth = TreeDepth(T->rchild);
    
    // 树的高度 = 左右子树最大的加自己本身(1)
    return (ldepth > rdepth ? ldepth : rdepth) + 1;
}

// 5. 判别是否是平衡二叉树 (AVL 树)
// C++ 可以直接使用 & 引用回传深度信息，使得代码比 C 纯指针更加清晰直白
bool isBalanced(BiTree T, int &depth) {
    if (T == NULL) {
        depth = 0;
        return true; 
    }
    
    int ldepth, rdepth;
    // 分别检查左、右孩子是否平衡，同时获取它们的深度
    if (isBalanced(T->lchild, ldepth) && isBalanced(T->rchild, rdepth)) {
        int diff = ldepth - rdepth;
        if (diff >= -1 && diff <= 1) {
            depth = (ldepth > rdepth ? ldepth : rdepth) + 1; 
            return true; 
        }
    }
    return false; // 不平衡
}

/* -----------------------------------------
 * 【5】并查集 (Union-Find) 极高频考点
 * ----------------------------------------- */

#define SIZE 100
int UFSets[SIZE]; 

// 初始化
void Initial(int S[]) {
    for (int i = 0; i < SIZE; i++) S[i] = -1; 
}

// 并查集 Find：附带路径压缩
int Find(int S[], int x) {
    int root = x;
    while (S[root] >= 0) root = S[root]; // 寻根
    
    // 路径压缩：将这一路上的所有人都直接挂在最大的老祖宗名下
    int curr = x, temp;
    while (curr != root) {
        temp = S[curr]; 
        S[curr] = root; 
        curr = temp;
    }
    return root; 
}

// 并查集 Union：小集合合并到大集合
void Union(int S[], int Root1, int Root2) {
    if (Root1 == Root2) return; 
    
    // 我们约定 S[] 当它是根时，存入的是该集合拥有的结点总数（取负）
    if (S[Root2] < S[Root1]) { // Root2 人数更多 (负的更大)
        S[Root2] += S[Root1];  // 人口吸收
        S[Root1] = Root2;      // Root1 的爹变成 Root2
    } else {
        S[Root1] += S[Root2];
        S[Root2] = Root1;
    }
}

04 排序算法

#include <iostream>
using namespace std;

/* =========================================
 * 408 统考数据结构核心代码 - 排序算法 (C++ 风格)
 * ========================================= */

// C++ 中可以直接使用 std::swap，无需自己写指针交换方法
// 也可以写引用的 swap 如下:
void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

/* -----------------------------------------
 * 【1】快速排序 (划区王牌)
 * ----------------------------------------- */

// 快速排序的划分思想，C++伪码中更喜欢使用引用传递与直接赋值
int Partition(int A[], int low, int high) {
    int 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(int A[], int low, int high) {
    if (low < high) {
        int pivotpos = Partition(A, low, high); 
        QuickSort(A, low, pivotpos - 1);        
        QuickSort(A, pivotpos + 1, high);       
    }
}


/* -----------------------------------------
 * 【2】起泡排序
 * ----------------------------------------- */
void BubbleSort(int A[], int n) {
    bool flag; // C++ 具有内置的 bool 数据类型，不需要用 1/0 代替
    for (int i = 0; i < n - 1; i++) {
        flag = false; 
        for (int j = n - 1; j > i; j--) { 
            if (A[j - 1] > A[j]) {
                swap(A[j - 1], A[j]); // 若使用自定义 swap，可以直接传参数
                flag = true;
            }
        }
        if (!flag) return; // 提前下班
    }
}

/* -----------------------------------------
 * 【3】堆排序 (极重要：大顶堆构建)
 * ----------------------------------------- */

// 将以 k 为根的子树调整为大顶堆 (向下调整)
void HeadAdjust(int A[], int k, int len) {
    A[0] = A[k]; // A[0] 暂存根结点 (假设数组 0 为空缺/暂存位)
    
    // i 初始为左孩子
    for (int i = 2 * k; i <= len; i *= 2) {
        // 如果右孩子更大，就把 i 指向右孩子
        if (i < len && A[i] < A[i + 1]) {
            i++; 
        }
        // 反之，要是根居然比最大的孩子还大，那就已经是个大顶堆了
        if (A[0] >= A[i]) {
            break;
        } else {
            A[k] = A[i]; // 大的给到双亲
            k = i;       // 继续往下挖
        }
    }
    A[k] = A[0]; // 将筛选结点放到最终应该在的位置
}

// 建立大顶堆
void BuildMaxHeap(int A[], int len) {
    // 从最后一个非叶子结点开始反复往下调整
    for (int i = len / 2; i > 0; i--) {
        HeadAdjust(A, i, len);
    }
}

// 整体堆排序
void HeapSort(int A[], int len) {
    BuildMaxHeap(A, len);       // 1. 初始化堆
    for (int i = len; i > 1; i--) {
        swap(A[i], A[1]);       // 2. 将堆顶（天枢最大值）摘下来放到队尾
        HeadAdjust(A, 1, i - 1);// 3. 剥削被摘走的范围内的剩余元素重新建堆
    }
}

/* -----------------------------------------
 * 【4】归并排序 (Merge Sort) 
 * 【极度重要】辅以全局或临时的辅助数组 B
 * ----------------------------------------- */
int B[100]; // 外部开辟辅助数组防止每次归并时发生反复分配的时间开销

void Merge(int A[], int low, int mid, int high) {
    int i, j, k;
    for (k = low; k <= high; ++k) B[k] = A[k]; // 复制
    
    // 双指针法在两个有序序列中抽取较小者放入原数组
    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; ++k) {
        if (B[i] <= B[j]) A[k] = B[i++]; 
        else A[k] = B[j++];
    }
    
    while (i <= mid)  A[k++] = B[i++];
    while (j <= high) A[k++] = B[j++];
}

void MergeSort(int 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】基于 QuickSort 的特殊分离应用
 * 把所有的奇数移向数组前端，全部偶数移向末尾，要求时间 O(N) 一趟！
 * ----------------------------------------- */

void MoveOddEven(int A[], int len) {
    int low = 0, high = len - 1;
    while(low < high) {
        // 后方找到第一个可以前移的奇数
        while(low < high && A[high] % 2 == 0) high--;
        // 前方找到第一个可以后移的偶数
        while(low < high && A[low] % 2 != 0) low++;
        
        if (low < high) {
            swap(A[low], A[high]); // 被抓到则交换
        }
    }
}

05 串与查找

#include <iostream>
using namespace std;

/* =========================================
 * 408 统考数据结构核心代码 - 串与查找 (C++ 伪代码)
 * ========================================= */

// 定义传统的考试专用 SString
typedef struct {
    char ch[100]; 
    int length;
} SString;

/* -----------------------------------------
 * 【1】字符串匹配：KMP 算法核心
 * 注意：由于 C++ 可以使用引用，我们可以用 `&`
 * ----------------------------------------- */

// 1. 推导 next 数组的灵魂逻辑
void get_next(SString T, int next[]) {
    int i = 1, j = 0;
    next[1] = 0; // 王道定义第一位就是 0
    
    while (i < T.length) {
        if (j == 0 || T.ch[i] == T.ch[j]) {
            ++i; ++j;
            next[i] = j; 
        } else {
            j = next[j]; // 发生失配，神级跳跃
        }
    }
}

// 2. 推导加强版容错 nextval 数组 (防坑利器)
void get_nextval(SString T, int nextval[]) {
    int i = 1, j = 0;
    nextval[1] = 0;
    
    while (i < T.length) {
        if (j == 0 || T.ch[i] == T.ch[j]) {
            ++i; ++j;
            // 如果新匹配上的那个字符，居然和旧的失配字符是同一个字！
            // 那么既然刚刚都失配了，你再让他拿同样的字去配也是必然失配！
            // 故直接跨过它，继承它的 next 归宿。
            if (T.ch[i] != T.ch[j]) {
                nextval[i] = j;
            } else {
                nextval[i] = nextval[j]; 
            }
        } else {
            j = nextval[j];
        }
    }
}

// 3. KMP 主干匹配计算
int Index_KMP(SString S, SString T, int next[]) {
    int i = 1, j = 1; 
    
    while (i <= S.length && j <= T.length) {
        if(j == 0 || S.ch[i] == T.ch[j]) {
            ++i; ++j; 
        } else {
            j = next[j]; 
        }
    }
    
    if (j > T.length) return i - T.length; // 返回子串在主串中的起始下标
    else return 0;
}

/* -----------------------------------------
 * 【2】折半查找 (Binary Search)
 * ----------------------------------------- */

// 折半查找：找得到就返回数组下标对应的人，找不到滚回 -1
int Binary_Search(int A[], int len, int key) {
    int low = 0, high = len - 1, mid;
    
    while (low <= high) {
        mid = (low + high) / 2;
        
        if (A[mid] == key) return mid;  
        else if (A[mid] > key) high = mid - 1; 
        else low = mid + 1;  
    }
    
    return -1; 
}

06 图的核心算法

#include <iostream>
#include <queue>
using namespace std;

/* =========================================
 * 408 统考数据结构核心代码 - 图的核心算法 (C++ 伪代码)
 * =========================================
 * C++ 可以直接使用 `#include <queue>`，在考卷上手撸 BFS
 * 在代码上会远远简洁于手写数组和队列指针的 C 版本。
 */

#define MaxVertexNum 100

// 边/弧结点
typedef struct ArcNode {
    int adjvex;               // 指向那个顶点
    struct ArcNode *nextarc;  // 指向下一条弧
    // int info;              // 如果有网，带权值
} ArcNode;

// 顶点表
typedef struct VNode {
    int data;                 
    ArcNode *firstarc;        
} VNode, AdjList[MaxVertexNum];

//图的邻接表体系
typedef struct {
    AdjList vertices;         
    int vexnum, arcnum;       
} ALGraph;

/* -----------------------------------------
 * 【1】BFS 与 DFS 的基本框架
 * ----------------------------------------- */
bool visited[MaxVertexNum];

void visit(int v) {
    cout << "V: " << v << endl; // 虚拟访问
}

// ------ 深度优先 DFS ------
void DFS(ALGraph G, int v) {
    visit(v);              
    visited[v] = true;        
    
    ArcNode *p = G.vertices[v].firstarc; 
    while (p != NULL) {
        int w = p->adjvex;
        if (!visited[w]) { 
            DFS(G, w);     
        }
        p = p->nextarc;    
    }
}

void DFSTraverse(ALGraph G) {
    for (int i = 0; i < G.vexnum; i++) visited[i] = false; 
    
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i]) DFS(G, i);
    }
}

// ------ 广度优先 BFS (直接使用 STL) ------
void BFS(ALGraph G, int v) {
    queue<int> Q; // STL 使此处的逻辑无比好写！
    visit(v);
    visited[v] = true;
    Q.push(v); 
    
    while (!Q.empty()) {
        int target = Q.front();
        Q.pop();
        
        ArcNode *p = G.vertices[target].firstarc;
        while (p != NULL) {
            int w = p->adjvex;
            if (!visited[w]) { 
                visit(w);      
                visited[w] = true;
                Q.push(w);    
            }
            p = p->nextarc;
        }
    }
}

void BFSTraverse(ALGraph G) {
    for (int i = 0; i < G.vexnum; i++) visited[i] = false; 
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i]) BFS(G, i);
    }
}

/* -----------------------------------------
 * 【2】Dijkstra 最短路径 (伪代码框架)
 * ----------------------------------------- */
#define INF 999999
int dist[MaxVertexNum];
int path[MaxVertexNum];
bool isFinal[MaxVertexNum];

// 传二维数组的语法在 408 经常这样书写
void Dijkstra(int curr_vex, int vexnum, int Edge[][MaxVertexNum]) {
    // 1. 初始化
    for (int i = 0; i < vexnum; i++) {
        dist[i] = Edge[curr_vex][i];
        isFinal[i] = false;     
        if (dist[i] < INF) path[i] = curr_vex;
        else path[i] = -1;
    }
    
    isFinal[curr_vex] = true; 
    dist[curr_vex] = 0;
    
    // 2. 依次寻找最短接入点
    for (int i = 0; i < vexnum - 1; i++) {
        int min = INF;
        int min_id = -1;
        
        for (int j = 0; j < vexnum; j++) {
            if (!isFinal[j] && dist[j] < min) {
                min = dist[j];
                min_id = j;
            }
        }
        
        if(min_id == -1) break; 
        isFinal[min_id] = true; 
        
        // （2）借助新接入点拉踩其余未接入点的值
        for (int j = 0; j < vexnum; j++) {
            if (!isFinal[j] && dist[min_id] + Edge[min_id][j] < dist[j]) {
                dist[j] = dist[min_id] + Edge[min_id][j];
                path[j] = min_id; 
            }
        }
    }
}