从合并数组到最短路径：我是如何用C语言通关西工大数据结构NOJ实验的

第一次打开西工大NOJ平台的数据结构实验题库时，那些陌生的术语和复杂的算法描述让我感到一阵眩晕。作为一个刚接触数据结构的大二学生，我完全不知道该如何下手完成这些实验。但经过一个学期的摸索和实践，我不仅顺利完成了所有实验，还对数据结构有了更深入的理解。在这篇文章中，我将分享我的学习历程和实战经验，希望能帮助同样面临这些挑战的同学们。

1. 基础篇：从线性表开始

线性表是数据结构中最基础的部分，但也是后续复杂结构的基石。在完成"合并有序数组"这个实验时，我遇到了第一个挑战。

1.1 理解顺序存储结构

顺序表的核心在于连续的内存空间和下标访问。我最初实现的版本是这样的：

typedef struct {
    int elem[MAXSIZE];
    int last = -1;
} SeqList;

这个结构体定义看似简单，但有几个关键点需要注意：

• last指针初始化为-1，表示空表
• 数组下标从0开始，与last的初始值保持一致
• 插入元素时需要先检查空间是否足够

1.2 合并算法的优化

合并两个有序数组的朴素想法是先将它们拼接再排序，但这样时间复杂度会达到O(nlogn)。通过双指针法，可以将复杂度降到O(n)：

void mergeList(SeqList *la, SeqList *lb, SeqList *lc) {
    int ia = 0, ib = 0, ic = 0;
    while (ia <= la->last && ib <= lb->last) {
        lc->elem[ic++] = (la->elem[ia] <= lb->elem[ib]) 
                        ? la->elem[ia++] 
                        : lb->elem[ib++];
    }
    // 处理剩余元素
    while (ia <= la->last) lc->elem[ic++] = la->elem[ia++];
    while (ib <= lb->last) lc->elem[ic++] = lb->elem[ib++];
    lc->last = ic - 1;
}

这个实现有几个值得注意的细节：

1. 使用后缀自增运算符简化代码
2. 条件运算符替代if-else提高可读性
3. 最后需要更新lc的last指针

2. 进阶挑战：非线性结构的实现

当实验进入树和图的部分时，难度明显提升。哈夫曼编码和最短路径算法让我花费了大量时间。

2.1 哈夫曼树的构建

哈夫曼编码实验要求我们实现一个完整的编/译码系统。关键在于如何高效地构建哈夫曼树：

void select(int pos, int *x1, int *x2) {
    int min = INT_MAX;
    for (int i = 1; i <= pos; i++) {
        if (ht[i].weight < min && ht[i].parent == 0) {
            min = ht[i].weight;
            *x1 = i;
        }
    }
    min = INT_MAX;
    for (int i = 1; i <= pos; i++) {
        if (i != *x1 && ht[i].weight < min && ht[i].parent == 0) {
            min = ht[i].weight;
            *x2 = i;
        }
    }
}

构建过程中需要注意：

• 每次选择权重最小的两个节点
• 新节点的权重是子节点权重之和
• 需要维护parent指针来避免重复选择

2.2 编码生成算法

生成编码时，我从叶子节点回溯到根节点，逆向得到编码：

void encode(int n) {
    for (int i = 1; i <= n; i++) {
        hc[i].start = n;
        int c = i, p = ht[c].parent;
        while (p) {
            hc[i].bit[hc[i].start--] = (ht[p].lchild == c) ? 0 : 1;
            c = p;
            p = ht[c].parent;
        }
        hc[i].start++; // 修正start位置
    }
}

这个算法的关键点：

1. 使用start指针记录编码的起始位置
2. 通过parent指针回溯
3. 根据是左孩子还是右孩子决定编码值

3. 图算法实战：最短路径问题

图算法是数据结构中的难点，迪杰斯特拉和弗洛伊德算法各有特点。

3.1 迪杰斯特拉算法的实现

迪杰斯特拉算法适合单源最短路径问题，我的实现分为几个步骤：

1. 初始化距离数组和访问标记

void initDij(Graph *G, Dij *D) {
    for (int i = 0; i < G->Vnum; i++) {
        D->visited[i] = false;
        D->length[i] = G->arc[0][i];
    }
    D->visited[0] = true;
    D->length[0] = 0;
}

2. 主循环：每次选择距离最近的未访问节点

int searchMinLengthV(Graph *G, Dij *D) {
    int min = INT_MAX, r = -1;
    for (int i = 0; i < G->Vnum; i++) {
        if (!D->visited[i] && D->length[i] < min) {
            min = D->length[i];
            r = i;
        }
    }
    if (r != -1) D->visited[r] = true;
    return r;
}

3. 松弛操作：更新邻接节点的距离

void updateArcV(int V0, Graph *G, Dij *D) {
    for (int i = 0; i < G->Vnum; i++) {
        if (!D->visited[i] && G->arc[V0][i] != INF) {
            int new_len = D->length[V0] + G->arc[V0][i];
            if (new_len < D->length[i]) {
                D->length[i] = new_len;
            }
        }
    }
}

3.2 弗洛伊德算法的优势

与迪杰斯特拉不同，弗洛伊德算法可以解决所有节点对的最短路径问题。其核心思想是动态规划：

void floyd(Graph *G) {
    for (int k = 0; k < G->vnum; k++)
        for (int i = 0; i < G->vnum; i++)
            for (int j = 0; j < G->vnum; j++)
                if (G->arc[i][j] > G->arc[i][k] + G->arc[k][j]) {
                    G->arc[i][j] = G->arc[i][k] + G->arc[k][j];
                    G->path[i][j] = k;
                }
}

这个算法的特点：

• 三重循环结构简单直观
• 可以处理负权边(但不能有负权环)
• 空间复杂度O(n²)，适合稠密图

4. 调试技巧与性能优化

在完成这些实验的过程中，我积累了一些宝贵的调试和优化经验。

4.1 常见错误排查

错误类型	表现	解决方法
内存越界	程序崩溃或随机错误	检查数组边界和指针操作
逻辑错误	结果不正确	添加调试打印，分步验证
死循环	程序无响应	检查循环终止条件
内存泄漏	长时间运行内存增长	确保每个malloc都有对应的free

4.2 性能优化技巧

1. 算法选择：根据问题特点选择合适算法，比如稀疏矩阵用十字链表而非二维数组
2. 数据结构优化：使用更高效的数据结构，如优先队列优化迪杰斯特拉算法
3. 缓存友好：尽量顺序访问内存，提高缓存命中率
4. 提前终止：在满足条件时提前退出循环

// 优化后的select函数示例
void select(int pos, int *x1, int *x2) {
    *x1 = *x2 = -1;
    int min1 = INT_MAX, min2 = INT_MAX;
    
    for (int i = 1; i <= pos; i++) {
        if (ht[i].parent == 0) {
            if (ht[i].weight < min1) {
                min2 = min1;
                *x2 = *x1;
                min1 = ht[i].weight;
                *x1 = i;
            } else if (ht[i].weight < min2) {
                min2 = ht[i].weight;
                *x2 = i;
            }
        }
    }
}

这个优化版本只需要一次遍历就能找到两个最小值，时间复杂度从O(2n)降到O(n)。

完成这些数据结构实验后，我最大的收获不是仅仅学会了如何实现这些算法，而是理解了它们背后的设计思想和适用场景。在解决最短路径问题时，我最初总是想直接套用算法，但后来明白更重要的是先分析问题的特点：图是有向还是无向？边权是否为正？需要单源还是所有节点对的结果？这些思考比单纯写代码更有价值。