数据结构期末复习

期末考试时间: 2025.12.29

往年试卷的特征:

上半学期的内容占 15~40 分.
代码填空占 12~15 分.
手写代码占 0~11 分.

第 2 章线性表

顺序表

单链表

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

单链表的合并

void MergeList_L(LinkList &A, LinkList &B, LinkList &C) {
    p = A->next; q = B->next;
    r = C = A;
    while (p != NULL && q != NULL) {
        if (p->data <= q->data) {
            r = r->next = p; p = p->next;
        } else {
            r = r->next = q; q = q->next;
        }
    }
    r->next = p != NULL ? p : q;
    free(B);
}

单链表的逆置 (无头节点)

void ListReverse_L(LinkList &L) {
    p = L->next; q = L; r = NULL;
    while (p != NULL) {
        r = q; q = p; p = p->next;
        q->next = r;
    }
    L->next = NULL; L = q;
}

第 3 章栈和队列

链队列

typedef struct QNode {
    QElemType data;
    struct QNode *next;
} QNode, *QueuePtr;
typedef struct {
    QueuePtr front, rear;
} LinkQueue;

Status InitQueue(LinkQueue &Q) {
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if (Q.front == NULL) exit(OVERFLOW);
    Q.front->next = NULL;
    return OK;
}

Status EnQueue(LinkQueue &Q, QElemType e) {
    p = (QueuePtr)malloc(sizeof(QNode));
    if (p == NULL) exit(OVERFLOW);
    p->data = e; p->next = NULL;
    Q.rear = Q.rear->next = p;
    return OK;
}

Status DeQueue(LinkQueue &Q, QElemType &e) {
    if (Q.front == Q.rear) return ERROR;
    p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if (Q.rear == p) Q.rear = Q.front;
    free(p);
    return OK;
}

循环队列

typedef struct {
    QElemType *base;
    int front, rear;
} SqQueue;

Status InitQueue(SqQueue &Q) {
    Q.base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
    if (Q.base == NULL) exit(OVERFLOW);
    Q.front = Q.rear = 0;
    return OK;
}

int QueueLength(SqQueue Q) {
    return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}

Status EnQueue(SqQueue &Q, QElemType e) {
    if ((Q.rear + 1) % MAXQSIZE == Q.front) return ERROR;
    Q.base[Q.rear] = e; Q.rear = (Q.rear + 1) % MAXQSIZE;
    return OK;
}

Status DeQueue(SqQueue &Q, QElemType &e) {
    if (Q.front == Q.rear) return ERROR;
    e = Q.base[Q.front]; Q.front = (Q.front + 1) % MAXQSIZE;
    return OK;
}

第 4 章串

KMP 算法

按教材定义,

$next[j]=\begin{cases} 0 & j=1, \\ \pi[j-1]+1, & j>1,\end{cases}$

其中为的 border 长度.

int Index_KMP(SString S, SString T, int pos) {
    i = pos; j = 1;
    while (i <= S[0] && j <= T[0]) {
        if (j == 0 || S[i] == T[j]) {
            i++; j++;
        } else j = next[j];
    }
    return j > T[0] ? (i - T[0]) : 0;
}

void GetNext(SString T, int next[]) {
    i = 1; j = 0;
    next[1] = 0;
    while (i < T[0]) {
        if (j == 0 || T[i] == T[j]) next[++i] = ++j;
        else j = next[j];
    }
}

next 数组的改进: nextval

void GetNextval(SString T, int nextval[]) {
    i = 1; j = 0;
    nextval[1] = 0;
    while (i < T[0]) {
        if (j == 0 || T[i] == T[j]) {
            ++i; ++j;
            nextval[i] = T[i] != T[j] ? j : nextval[j];
        } else j = nextval[j];
    }
}

第 5 章数组和广义表

矩阵的三元组顺序表存储

typedef struct {
    int i, j;
    ElemType e;
} Triple;
typedef struct {
    Triple data[MAXSIZE + 1];
    int mu, nu, tu;
} TSMatrix;

Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) {
    T.mu = M.nu; T.nu = M.mu; T.tu = M.Tu;
    num[1..M.nu] = 0;
    for (t = 1; t <= M.tu; t++) num[M.data[t].j]++;
    cpot[1] = 1;
    for (col = 2; col <= M.nu; col++)
        cpot[col] = cpot[col - 1] + num[col - 1];
    for (t = 1; t <= M.tu; t++) {
        col = M.data[t].j;
        T.data[cpot[col]++] = M.data[t];
    }
    return OK;
}

矩阵的行逻辑链接顺序表存储: 按行优先顺序存储, 维护每一行在数组里的起始位置 . 做矩阵乘法时, 按顺序遍历的每一个非零元, 设其行号为 , 列号为 , 则它和的第行中的元素相乘会对矩阵的乘积 (的第行) 产生贡献. 在目前处理到的的行号为时, 暂存的第行; 处理完的第行后, 把暂存的的这一行中的非零元填入的存储结构中. 在这一过程中要记得记录的数组.

矩阵的十字链表存储

typedef struct OLNode {
    int i, j;
    ElemType e;
    struct OLNode *right, *down;
} OLNode, *OLink;
typedef struct {
    OLink *rhead, *chead;
    int mu, nu, tu;
} CrossList;

第一类广义表

typedef enum { ATOM, LIST } ElemTag;
typedef struct GLNode {
    ElemTag tag;
    union {
        AtomType atom;
        struct {struct GLNode *hp, *tp; } ptr;
    }
} *GList;

第二类广义表

typedef enum { ATOM, LIST } ElemTag;
typedef struct GLNode {
    ElemTag tag;
    union {
        AtomType atom;
        struct GLNode *hp;
    }
    struct GLNode *tp;
} *GList;

第 6 章树和二叉树

二叉树的链式存储结构

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

二叉树的线索化

树的三种存储结构

typedef struct PTNode {
    TElemType data;
    int parent;
} PTNode;
typedef struct {
    PTNode nodes[MAX_TREE_SIZE];
    int r, n;
} PTree;

typedef struct CTNode {
    int child;
    struct CTNode *next;
} *ChildPtr;
typedef struct {
    TElemType data;
    ChildPtr firstchild;
} CTBox;
typedef struct {
    CTBox nodes[MAX_TREE_SIZE];
    int r, n;
} CTree;

typedef struct CSNode {
    ElemType data;
    struct CSNode *firstchild, *nextsibling;
} CSNode, *CSTree;

赫夫曼树: 每次取最小的两个节点.

第 7 章图

可能考手写完整代码的: 邻接表基础操作, DFS, BFS, Dijkstra, Floyd.

数组表示法 (邻接矩阵)

邻接表

typedef struct ArcNode {
    int adjvex;
    struct ArcNode *nextarc;
    InfoType *info;
} ArcNode;
typedef struct {
    VertexType data;
    ArcNode *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM];

十字链表: 其实就是在邻接矩阵的对应位置上画弧结点, 弧结点除弧尾 tailvex 与弧头 headvex 外还要加上纵向链 hlink 和横向链 tlink. 然后顶点结点存储纵向链表和横向链表的头指针 firstin, firstout.
DFS 与 BFS; 对应的生成树 (森林)
Kosaraju 算法求强连通分量: 在反图上按 DFS 序的逆序遍历.
Prim 算法求最小生成树: 每次将与之间代价最小的边加入 . 实现复杂度的方法是: 设置辅助数组 closeedge, 其每个元素都含有 adjvex 和 lowcost 两个域, 在时, closeedge[i-1].lowcost 与 closeedge[i-1].adjvex 分别表示连接中的点与的最小边的代价与这条边连接到的中的点.
Kruskal 算法求最小生成树: 每次取未使用的最小边, 若加入当前的生成树中不构成环则加入.
拓扑排序: 注意用队列还是用栈是无所谓的.
关键路径: 按拓扑序做简单 DP 就能求出值. 麻烦的是求方案. 记求得的以结尾的最长路径为 . 令 , 作反向递推 , 则活动为关键活动的条件是 .

Dijkstra 算法求单源最短路径

void ShortestPath(Graph G, int v0, ShortestPathTable &D) {
    final[] = FALSE; final[v0] = TRUE;
    D[] = G.arcs[v0][]; D[v0] = 0;
    for (i = 1; i < G.vexnum; ++i) {
        min = INFINITY;
        for (w = 0; w < G.vexnum; w++)
            if (!final[w] && D[w] < min) {
                min = D[w]; v = w;
            }
        final[v] = TRUE;
        for (w = 0; w < G.vexnum; w++)
            if (!final[w]) D[w] = min(D[w], min + G.arcs[v][w]);
    }
}

Floyd 算法求全源最短路径: 注意的意义是只经过号顶点的路径的最小值.

第 9 章查找

折半查找 (最坏情形下查找长度 )

int Search_Bin(SSTable ST, KeyType key) {
    low = 1; high = ST.length;
    while (low <= high) {
        mid = (low + high) / 2;
        if (EQ(key, ST.elem[mid].key)) return mid;
        if (LT(key, ST.elem[mid].key)) high = mid - 1;
        else low = mid + 1;
    }
    return 0;
}

斐波那契查找 (平均性能优于折半查找, 最坏性能不如折半查找)

次优查找树: 选择的根节点应使得左右子树的之差的绝对值最小. 确定根节点后, 递归地构建左右子树.
分块查找 (索引顺序查找): . 当取时, 取得最小值 .
BST (删除操作应该不会考)
AVL 树
- 教材中平衡因子的定义是左减右.
- 四种失衡情形及对应的旋转: LL - R, RR - L, LR - LR, RL - RL.
- 旋转的代码记一下, 可能会考默写:
  1
  2
  3
  4
  5
  6
  void R_Rotate(BSTree &p) {
  lc = p->lchild;
  p->lchild = lc->rchild;
  lc->rchild = p;
  p = lc;
  }
- 删除操作不讲.
B 树
- 控制的变量:
  - 每个结点至多度.
  - 结点树时根节点至少度. (推论: 不存在结点数为的 B 树.)
  - 非根非叶子结点至少度.
  - 叶子在同一层.
  - 结点里存储的个数将值域分为个区域, 决定插入的位置.
- 插入:
  - 根据数值找到对应的叶子结点, 在叶子里加数 (注意不是加叶子).
  - 结点里的数的个数超过了, 就将这个结点分裂成两个结点. 这个结点的父结点里需要有一个数来隔开分裂成的两个结点表示的区间, 因此将分裂开的结点的中位数提升到父节点里. (如果分裂开的结点是根结点, 则在上面创建一个新的根结点.) 提升可能会导致父结点的数也超过了, 此时就要重复这个过程, 直到所有结点的度数符合要求.
  - 关于分裂后孩子跟谁的问题, 事实上永远有且只有一种能够维持结点里数的个数与孩子的个数的关系的方案.
- 删除:
  - 如果被删除的数所属结点不是叶子结点, 就把被删除的数换成叶子结点中比它大的最小数, 并试图删除叶子结点中的这个数.
  - 现在要删除叶子结点中的一个数 . 如果中数的个数 , 则可以直接删除.
  - 否则, 中数的个数为 . 我们先删除 . 如果的右 (左) 同胞结点中数的个数 , 则将这些数的最小 (大) 者上移至父结点，并将这个数在父结点中的前驱 (后继) 下移至中. 如果左右同胞结点中数的个数均为 , 则让与右 (左) 同胞结点 (记为 ) 以及父结点中隔开与的数执行分裂过程的反过程 (称为融合). 如果父结点因融合而没有足够的数了, 则认为原本有个数的父结点被删去了数 , 将父结点视为新的 , 将视为新的重复 “从删除 ” 的过程.
- 性能分析: 设一棵阶 B 树深度为 , 含有个关键字. 由于叶子结点的数量 , 有 $h\le\log{\lceil m/2\rceil}\dfrac{n+1}2+2 $因此查找成功时的查找长度$ \le\log{\lceil m/2\rceil}\dfrac{n+1}2+1$.
哈希表
- 冲突处理 (设哈希表长度为 ; 以下所说的 “偏移” 都是模意义下的):
  - 线性探测再散列: 依次尝试在哈希值的基础上偏移 .
  - 二次探测再散列: 依次尝试在哈希值的基础上偏移 .
  - 随机探测再散列: 生成随机数序列作为在哈希值的基础上的偏移.
  - 简单再哈希: 计算另一哈希函数的值.
  - 链地址法: 给哈希表的每一个位置拉一个链表.
- 性能分析:
  - 定义装填因子为表中的记录数与表长之比.
  - 二次探测、随机探测与简单再哈希都满足查找成功时的 ASL 为且查找不成功时的 ASL 为 .

第 10 章排序

直接插入排序与折半插入排序
二路插入排序: 见这里.

表插入排序: 注意重排算法的写法.

// 重排算法
void Arrange(SLinkListType &L) {
    p = L.r[0].next;
    for (i = 1; i < L.length; i++) {
        while (p < i) p = L.r[p].next;
        q = L.r[p].next;
        if (p != i) {
            swap(L.r[p], L.r[i]);
            L.r[i].next = p;
        }
        p = q;
    }
}

希尔排序: 每一轮有一个模数, 要对与每一个剩余类, 给属于这个剩余类的位置构成的子序列排序. 逐渐减少模数.
起泡排序

快速排序 (平均

，最坏

)

int Partition(SqList &L, int low, int high) {
    L.r[0] = L.r[low];
    pivotkey = L.r[low].key;
    while (low < high) {
        while (low < high && L.r[high].key >= pivotkey) --high;
        L.r[low] = L.r[high];
        while (low < high && L.r[low].key <= pivotkey) ++low;
        L.r[high] = L.r[low];
    }
    L.r[low] = L.r[0];
    return low;
}
void QSort(SqList &L, int low, int high) {
    if (low < high) {
        pos = Partition(L, low, high);
        QSort(L, low, pos - 1); QSort(L, pos + 1, high);
    }
}

选择排序
锦标赛排序

堆排序 (建堆比较次数

, 总比较次数

)

typedef SqList HeapType;
void HeapAdjust(HeapType &H, int s, int m) {
    rc = H.r[s];
    for (j = 2 * s; j <= m; j *= 2) {
        if (j < m && LT(H.r[j].key, H.r[j + 1].key)) ++j;
        if (LQ(H.r[j].key, rc.key)) break;
        H.r[s] = H.r[j]; s = j;
    }
    H.r[s] = rc;
}
void HeapSort(HeapType &H) {
    for (i = H.length / 2; i > 0; i--) HeapAdjust(H, i, H.length);
    for (i = H.length; i > 1; i--) {
        swap(H.r[1], H.r[i]);
        HeapAdjust(H, 1, i - 1);
    }
}

归并排序 ()
基数排序 ()
稳定性: 选择排序、堆排序、快速排序是不稳定的, 其他是稳定的.
归并排序最坏情况下的比较次数:

1	2	3	4	5	6	7	8	9	10
0	1	3	5	9	11	14	17	25	27

快速选择算法

// 第 k 小
RcdType QuickSelect(SqList &L, int st, int en, int k) {
    if (st == en) return L.r[st];
    low = st; high = en;
    pivotkey = L.r[st];
    while (low <= high) {
        while (low <= high && L.r[low].key < pivotkey) low++;
        while (low <= high && L.r[high].key > pivotkey) high--;
        if (low <= high) swap(L.r[low++], L.r[high--]);
    }
    if (st + k - 1 <= high) return QuickSelect(L, st, high, k);
    if (st + k - 1 >= low) return QuickSelect(L, low, en, k - (low - st));
    return L.r[high + 1];
}

第 2 章 线性表

第 3 章 栈和队列

第 4 章 串

第 5 章 数组和广义表

第 6 章 树和二叉树

第 7 章 图

第 9 章 查找

第 10 章 排序