C 语言手写数据结构与算法：图的遍历与最短路径应用
C 语言手写数据结构与算法：图的遍历与最短路径应用
一、 课程设计目标
《数据结构》是计算机科学中最为核心的基础课程。在现代高级编程语言中，我们通常直接调用标准库（如 C++ STL 的 std::vector 或 Java 的 ArrayList）来处理数据集合。然而，为了深刻理解数据在内存中的物理存储方式和算法的时间/空间复杂度，在期末综合课程设计中，我选择使用纯 C 语言，从零开始实现底层的数据结构和复杂算法。
本次课设的主要目标是：手写链表、栈、队列等基础结构，并重点攻克图（Graph）的存储与遍历算法，最终将其应用到类似“校园导航系统”的具体业务场景中。
二、 基础数据结构的底层实现
在 C 语言中，没有对象的概念，所有的数据结构都需要通过 struct 结构体和指针（Pointer）来构建。
2.1 链表 (Linked List)
我首先实现了单向链表和双向循环链表。
- 内存管理：链表的每一个节点（Node）都需要在运行时通过
malloc()函数向操作系统申请堆内存。 - 指针操作：在实现节点的插入（Insert）和删除（Delete）操作时，必须极其小心地处理指针的断开与重新连接。如果操作顺序错误，就会导致后面的节点丢失（内存泄漏），或者访问到非法的内存地址引发
Segmentation Fault（段错误）。
2.2 栈 (Stack) 与队列 (Queue)
基于已完成的链表（或动态数组），我封装了栈和队列。
- 栈：遵循 LIFO（后进先出）原则，主要用于后续深度优先搜索（DFS）算法中的状态回溯，以及表达式求值等场景。
- 队列：遵循 FIFO（先进先出）原则，主要用于广度优先搜索（BFS）算法中的节点层次遍历。
三、 图论算法的核心攻坚
图是数据结构中最复杂的非线性结构之一。在课设中，我重点研究了图的存储和经典算法。
3.1 图的存储结构
根据图中顶点（Vertex）和边（Edge）的稠密程度，我分别实现了两种存储方式：
- 邻接矩阵 (Adjacency Matrix)：使用一个二维数组
graph[N][N]来表示图。如果顶点 $i$ 和顶点 $j$ 之间有边，则graph[i][j]记录该边的权重；否则记录为无穷大（$\infty$）。这种方式适合存储稠密图，判断两点是否相连的时间复杂度为 $O(1)$，但空间复杂度较高，为 $O(V^2)$。 - 邻接表 (Adjacency List)：使用一个一维数组，数组的每个元素都是一个链表的头指针，链表中存储了与该顶点相邻的所有顶点信息。这种方式极大地节省了稀疏图的存储空间。
3.2 图的遍历 (DFS & BFS)
为了确保能够访问到图中的每一个节点，我编写了图的两种基础遍历算法：
- 深度优先搜索 (DFS)：利用递归或显式栈，沿着一条路径尽可能深地访问节点，直到无法继续为止，然后回溯。
- 广度优先搜索 (BFS)：利用队列，以起始节点为中心，一层一层向外扩展访问。在无权图中，BFS 也是求解最短路径的基础方法。在这两种算法中，都需要维护一个
visited数组，以防止在包含环的图中陷入死循环。
四、 业务落地：Dijkstra 最短路径算法
为了将理论应用于实践，我设计了一个“校园景点导航”的功能。用户输入起点和终点景点，系统需要计算出两点之间的最短步行距离和具体路线。
为此，我完整实现了经典的 Dijkstra 算法：
- 初始化：创建一个距离数组
dist[]，记录起点到所有其他节点的当前已知最短距离。起点的距离设为 0，其余设为无穷大。同时创建一个布尔数组S[]，记录已经找到绝对最短路径的节点集合。 - 迭代寻找：在未加入
S集合的节点中，找到当前dist值最小的节点 $u$，将其加入S集合。 - 松弛操作 (Relaxation)：遍历节点 $u$ 的所有邻接点 $v$。如果通过 $u$ 到达 $v$ 的距离（即
dist[u] + weight(u, v)）小于当前dist[v]的值，则更新dist[v]，并将 $v$ 的前驱节点记录为 $u$（用于最后回溯输出完整路线）。 - 循环：重复步骤 2 和 3，直到所有节点都被加入
S集合。
五、 总结与反思
本次基于 C 语言的数据结构课程设计是一次充满挑战的硬核拉练。
在编写和调试代码的过程中，我经历了无数次的指针越界和内存泄漏报错。但也正是通过不断地使用 IDE 的断点调试功能（如查看局部变量的内存地址和值），我逐渐培养出了严谨的内存管理意识（即 malloc 和 free 必须成对出现）。
手写这些底层数据结构和算法，让我深刻理解了不同数据结构在时间复杂度和空间复杂度上的 trade-off（权衡）。这种对底层原理的通透理解，将为我未来学习数据库索引原理（如 B+ 树）或编写高性能业务代码提供强有力的支撑。