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

从合并数组到最短路径我是如何用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; }这个实现有几个值得注意的细节使用后缀自增运算符简化代码条件运算符替代if-else提高可读性最后需要更新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位置 } }这个算法的关键点使用start指针记录编码的起始位置通过parent指针回溯根据是左孩子还是右孩子决定编码值3. 图算法实战最短路径问题图算法是数据结构中的难点迪杰斯特拉和弗洛伊德算法各有特点。3.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; }主循环每次选择距离最近的未访问节点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; }松弛操作更新邻接节点的距离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都有对应的free4.2 性能优化技巧算法选择根据问题特点选择合适算法比如稀疏矩阵用十字链表而非二维数组数据结构优化使用更高效的数据结构如优先队列优化迪杰斯特拉算法缓存友好尽量顺序访问内存提高缓存命中率提前终止在满足条件时提前退出循环// 优化后的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)。完成这些数据结构实验后我最大的收获不是仅仅学会了如何实现这些算法而是理解了它们背后的设计思想和适用场景。在解决最短路径问题时我最初总是想直接套用算法但后来明白更重要的是先分析问题的特点图是有向还是无向边权是否为正需要单源还是所有节点对的结果这些思考比单纯写代码更有价值。