数据结构核心考点与算法实现指南

实现代码

// 插入操作
bool ListInsert(SqList &L, int i, ElemType e) {
    if(i < 1 || i > L.length + 1) return false;
    for(int j = L.length; j >= i; j--) L.data[j] = L.data[j - 1];
    L.data[i - 1] = e;
    L.length++;
    return true;
}
// 时间复杂度 O(n)

// 删除操作
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;
}
// 时间复杂度 O(n)

// 按值查找
int LocateElem(SqList L, ElemType e) {
    int i;
    for(i = 0; i < L.length; i++)
        if(L.data[i] == e) return i + 1;
    return 0;
}

// 按位查找
int GetElem(SqList L, int i) {
    if(i < 1 || i > L.length) return 0;
    return L.data[i - 1];
}

有序表合并

bool Merge(SqList A, SqList B, SqList &C) {
    if(A.length + B.length > C.MaxSize) return false;
    int i = 0, j = 0, k = 0;
    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++];
    }
    while(i < A.length) C.data[k++] = A.data[i++];
    while(j < B.length) C.data[k++] = B.data[j++];
    C.length = k;
    return true;
}

链表

单链表

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

双链表

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

循环链表

• 循环单链表：L->next = L
• 循环双链表：L->next = L; L->prior = L

栈与队列

栈

• 特性：先进后出 (LIFO)，只能在栈顶操作。
• 顺序栈：

typedef struct {
    ElemType data[MaxSize];
    int top;
} SqStack;

• 链栈：便于共享存储空间，无栈满上溢情况。

队列

• 特性：先进先出 (FIFO)，队头队尾操作。
• 顺序队列：

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

• 循环队列：
  • 队空：Q.front == Q.rear
  • 队满：(Q.rear + 1) % MaxSize == Q.front
  • 长度：(Q.rear + MaxSize - Q.front) % MaxSize
• 链队列：使用链表实现，无溢出限制。

串

• 子串：串中任意个连续的字符组成的子序列。
• 基本操作：赋值、比较、求长、求子串、连接、定位等。

树与二叉树

树的基本概念

• 度：结点拥有的子树数。树的度是树内各结点的度的最大值。
• 深度/高度：树中结点的最大层数。
• 叶子结点：度为 0 的结点。
• 分支结点：度大于 0 的结点。

二叉树

• 性质：
  • 第 k 层至多有 $2^{k-1}$ 个结点。
  • 高度为 h 的二叉树至多有 $2^h - 1$ 个结点。
  • 叶子结点数 $n_0$ 等于度为 2 的结点数 $n_2$ 加 1，即 $n_0 = n_2 + 1$。
  • 完全二叉树高度为 $loor{loor{log_2(n+1)}}$。
• 存储结构：
  • 顺序存储：适用于完全二叉树。
  • 链式存储：含 n 个结点的二叉链表中有 n+1 个空链域。
• 遍历：
  • 先序 (NLR)、中序 (LNR)、后序 (LRN)、层次遍历。
• 特殊二叉树：
  • 满二叉树、完全二叉树、平衡二叉树、二叉排序树 (BST)。
  • 哈夫曼树：带权路径长度 (WPL) 最小的二叉树。

树与森林转换

• 树转二叉树：孩子兄弟表示法（左孩子右兄弟）。
• 森林转二叉树：每棵树转为二叉树，根节点互为兄弟。

图

基本概念

• 顶点度：无向图中关联边的数目；有向图中入度 + 出度。
• 连通图：任意两个顶点都连通。
• 生成树：包含全部顶点的极小连通子图。
• 最小生成树：权值之和最小的生成树（Prim 算法、Kruskal 算法）。
• 最短路径：Dijkstra 算法。
• 拓扑排序：AOV 网中无前驱顶点优先输出。
• 关键路径：AOE 网中从源点到汇点的最长路径。

存储结构

• 邻接矩阵：适合稠密图。
• 邻接表：适合稀疏图，节省空间。

查找

顺序查找

• 平均查找长度 ASL = $(n+1)/2$。

折半查找 (二分查找)

• 仅适用于有序顺序表。
• 时间复杂度 $O(loor{log_2 n})$。

散列表 (Hash)

• 装填因子：$ ext{load factor} = ext{记录数} / ext{表长}$。
• 冲突处理：开放定址法、拉链法。

排序

内部排序分类

• 插入排序：直接插入 (稳定，O(n²))、希尔排序 (不稳定)。
• 交换排序：冒泡 (稳定，O(n²))、快速 (不稳定，O(nlogn))。
• 选择排序：简单选择 (不稳定，O(n²))、堆排序 (不稳定，O(nlogn))。
• 归并排序：二路归并 (稳定，O(nlogn))。
• 基数排序：稳定，O(d(n+r))。

算法比较