数据结构考研全攻略
408 全考点 · 图解 + 手算 + 代码

int x = 1;
while (x < n)
    x = x * 2;      // 基本语句：每次翻倍，执行 ⌈log₂n⌉ 次 → O(log₂n)

int sum = 0;
for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++)   // 内层执行 n-i+1 次
        sum++;                      // 共 n+(n-1)+…+1 = n(n+1)/2 → O(n²)

#define MaxSize 50
typedef struct {
    int data[MaxSize];   // 连续存储区
    int length;          // 当前元素个数
} SqList;

bool ListInsert(SqList &L, int i, int 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;                              // 位序 i → 下标 i-1
    L.length++;
    return true;
}

bool ListDelete(SqList &L, int i, int &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;
}

typedef struct LNode {
    int data;              // 数据域
    struct LNode *next;    // 指针域：指向后继结点
} LNode, *LinkList;        // LNode* 强调「结点」，LinkList 强调「整个链表」

// 头插法建表：读入的顺序与链表顺序【相反】
LinkList CreateByHead(int a[], int n) {
    LinkList L = new LNode;      // 头结点
    L->next = NULL;
    for (int i = 0; i < n; i++) {
        LNode *s = new LNode;
        s->data = a[i];
        s->next = L->next;       // 新结点插到头结点之后
        L->next = s;
    }
    return L;
}

// 尾插法建表：顺序一致，需要一个尾指针 r
LinkList CreateByTail(int a[], int n) {
    LinkList L = new LNode;
    LNode *r = L;                // r 永远指向尾结点
    for (int i = 0; i < n; i++) {
        LNode *s = new LNode;
        s->data = a[i]; r->next = s; r = s;
    }
    r->next = NULL;
    return L;
}

// 删除 p 的后继结点
void DeleteAfter(LNode *p) {
    LNode *q = p->next;
    p->next = q->next;
    delete q;
}

typedef struct DNode {
    int data;
    struct DNode *prior, *next;
} DNode, *DLinkList;

// 在 p 之后插入 s —— 四句口诀：先接新，再改旧
s->next = p->next;
s->prior = p;
p->next->prior = s;    // 注意：必须在 p->next = s 之前做
p->next = s;

#define MaxSize 50
typedef struct {
    int data[MaxSize];
    int top;                       // 栈顶指针
} SqStack;

void InitStack(SqStack &S) { S.top = -1; }
bool StackEmpty(SqStack S)  { return S.top == -1; }

bool Push(SqStack &S, int x) {
    if (S.top == MaxSize - 1) return false;   // 栈满
    S.data[++S.top] = x;                      // 先移指针再存
    return true;
}

bool Pop(SqStack &S, int &x) {
    if (S.top == -1) return false;            // 栈空
    x = S.data[S.top--];                      // 先取再移
    return true;
}

typedef struct {
    int data[MaxSize];
    int front, rear;
} SqQueue;

bool EnQueue(SqQueue &Q, int 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, int &x) {
    if (Q.rear == Q.front) return false;                    // 队空
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;
    return true;
}

bool bracketCheck(char str[], int len) {
    SqStack S; InitStack(S);
    for (int i = 0; i < len; i++) {
        char c = str[i];
        if (c == '(' || c == '[' || c == '{') {
            Push(S, c);                       // 左括号进栈
        } else if (c == ')' || c == ']' || c == '}') {
            if (StackEmpty(S)) return false;  // 右括号多了
            char t; Pop(S, t);
            if ((c == ')' && t != '(') ||
                (c == ']' && t != '[') ||
                (c == '}' && t != '{')) return false;
        }
    }
    return StackEmpty(S);                     // 栈空 → 全部匹配；不空 → 左括号多了
}

void get_next(char T[], int next[], int m) {
    int i = 1, j = 0;
    next[1] = 0;
    while (i < m) {
        if (j == 0 || T[i] == T[j]) {   // 字符相等（或从头开始）
            ++i; ++j;
            next[i] = j;                // next[i+1] 由 next[i] 推出
        } else {
            j = next[j];                // 失配：j 退到 next[j]
        }
    }
}

int KMP(char S[], char T[], int n, int m, int next[]) {
    int i = 1, j = 1;
    while (i <= n && j <= m) {
        if (j == 0 || S[i] == T[j]) {   // 匹配成功或 j 归零：双指针一起走
            ++i; ++j;
        } else {
            j = next[j];                // 失配：i 不动，j 回退
        }
    }
    if (j > m) return i - m;            // 匹配成功，返回起始位序
    return 0;                           // 失败
}

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void PreOrder(BiTree T) {          // 先序
    if (T != NULL) {
        visit(T);                  // 根
        PreOrder(T->lchild);       // 左
        PreOrder(T->rchild);       // 右
    }
}
void InOrder(BiTree T) {           // 中序：visit 移到中间
    if (T != NULL) {
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}
void PostOrder(BiTree T) {         // 后序：visit 移到最后
    if (T != NULL) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}

// 层序遍历：借助队列（C++ STL，见上一册第 15 章）
void LevelOrder(BiTree T) {
    queue<BiTree> Q;
    if (T != NULL) Q.push(T);
    while (!Q.empty()) {
        BiTree p = Q.front(); Q.pop();
        visit(p);                          // 出队即访问
        if (p->lchild) Q.push(p->lchild);  // 先左后右依次入队
        if (p->rchild) Q.push(p->rchild);
    }
}

typedef struct ThreadNode {
    int data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;    // 0 = 指向孩子；1 = 指向前驱/后继的线索
} ThreadNode, *ThreadTree;

int fa[N];
void init() { for (int i = 0; i < N; i++) fa[i] = i; }   // 各自为营

int find(int x) {                       // 一直向上找根
    return fa[x] == x ? x : find(fa[x]);
}

void merge(int x, int y) {              // 一棵树挂到另一棵下
    fa[find(x)] = find(y);
}

#define MaxVertexNum 100
// 邻接矩阵：判断有没有边 O(1)
int G[MaxVertexNum][MaxVertexNum];   // 0/1 或权值 INFINITY 表示不邻接

// 邻接表：边表用链串起来
typedef struct ArcNode {             // 边表结点
    int adjvex;                      // 邻接点下标
    struct ArcNode *next;
} ArcNode;
typedef struct VNode {               // 顶点表结点
    int data;
    ArcNode *first;
} VNode, AdjList[MaxVertexNum];

bool visited[MaxVertexNum];

// 广度优先：类似树的层序，靠「队列」
void BFS(AdjList G, int v) {
    queue<int> Q;
    visited[v] = true;
    cout << v << " ";
    Q.push(v);
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (int w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w))
            if (!visited[w]) {
                visited[w] = true;
                cout << w << " ";
                Q.push(w);
            }
    }
}

// 深度优先：类似树的先序，靠「递归」（本质是栈）
void DFS(AdjList G, int v) {
    visited[v] = true;
    cout << v << " ";
    for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
        if (!visited[w]) DFS(G, w);
}

// Prim：「一棵树长大」——每次挑【树内 → 树外】的最短边，加入新点
// 适合稠密图，O(n²)，与边数无关
void Prim(int G[][N], int n) {
    int lowCost[N];            // 树外各点到树的最短距离
    bool inTree[N] = {false};
    for (int i = 1; i < n; i++) lowCost[i] = G[0][i];
    inTree[0] = true;
    for (int k = 1; k < n; k++) {
        int minV = -1;
        for (int j = 0; j < n; j++)                     // 扩展点循环 n-1 轮
            if (!inTree[j] && (minV == -1 || lowCost[j] < lowCost[minV]))
                minV = j;
        inTree[minV] = true;
        for (int j = 0; j < n; j++)                     // 用新点更新距离
            if (!inTree[j] && G[minV][j] < lowCost[j])
                lowCost[j] = G[minV][j];
    }
}

// Kruskal：「森林变森林」——边按权从小到大试，不成环就要
// 适合稀疏图 O(e log e)，判环用并查集
sort(edges, edges + e);                  // 按 权值 从小到大排序
int cnt = 0;                             // 已选边数，选满 n-1 条结束
for (int i = 0; i < e && cnt < n - 1; i++) {
    if (find(u) != find(v)) {            // 两端不在同一集合 → 不成环
        merge(u, v);                     // （并查集见第 5 章）
        cnt++;
    }
}

for (int k = 0; k < n; k++)        // 中间点 k 必须在最外层！
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (D[i][k] + D[k][j] < D[i][j])
                D[i][j] = D[i][k] + D[k][j];
// 时间 O(n³)，空间 O(n²)；允许负权边，但不允许负权回路

int BinarySearch(int a[], int n, int key) {   // 长度 n，下标 0..n-1
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if      (a[mid] == key) return mid;
        else if (a[mid] >  key) high = mid - 1;
        else                    low  = mid + 1;
    }
    return -1;
}

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 p = Partition(a, low, high);
        QuickSort(a, low, p - 1);    // 递归左右两段
        QuickSort(a, p + 1, high);
    }
}

void SiftDown(int a[], int k, int n) {      // a[k] 下沉，堆规模 n
    a[0] = a[k];                            // 暂存
    for (int i = 2 * k; i <= n; i *= 2) {   // 沿较大的孩子下沉
        if (i < n && a[i] < a[i + 1]) i++;
        if (a[0] >= a[i]) break;
        a[k] = a[i];                        // 孩子上移
        k = i;
    }
    a[k] = a[0];                            // 放到最终位置
}

void HeapSort(int a[], int n) {
    for (int i = n / 2; i >= 1; i--)        // ① 建堆：从最后分支结点倒序
        SiftDown(a, i, n);
    for (int i = n; i > 1; i--) {
        swap(a[1], a[i]);                   // ② 堆顶换到末尾
        SiftDown(a, 1, i - 1);              // ③ 规模减一后重新下沉
    }
}

int Majority(int A[], int n) {
    // 第 1 趟：候选抵消
    int candidate = A[0], count = 1;
    for (int i = 1; i < n; i++) {
        if (A[i] == candidate) count++;
        else if (count > 0)    count--;
        else { candidate = A[i]; count = 1; }   // 票数清零，换候选人
    }
    // 第 2 趟：验证（候选可能不存在，必须数一遍！）
    count = 0;
    for (int i = 0; i < n; i++)
        if (A[i] == candidate) count++;
    if (count > n / 2) return candidate;
    return -1;
}

void Rearrange(LinkList L) {
    // ① 快慢指针：slow 到中点，fast 扫尾
    LNode *slow = L, *fast = L;
    while (fast->next != NULL) {
        slow = slow->next;
        fast = fast->next;
        if (fast->next != NULL) fast = fast->next;
    }
    // ② 断链：p1 = 前半, p2 = 后半
    LNode *p2 = slow->next;
    slow->next = NULL;
    // ③ 后半段原地逆置（头插法）
    LNode *p = p2, *q;
    p2 = NULL;
    while (p != NULL) {
        q = p->next;
        p->next = p2;
        p2 = p;
        p = q;
    }
    // ④ 交替归并：p1 取一个、p2 插一个
    LNode *p1 = L->next, *t = L;
    while (p1 != NULL && p2 != NULL) {
        LNode *n1 = p1->next, *n2 = p2->next;
        t->next = p1; t = p1; p1 = n1;
        t->next = p2; t = p2; p2 = n2;
    }
    t->next = (p1 != NULL) ? p1 : p2;   // 接上剩余结点
}