简介本资源是南京邮电大学《数据结构》课程实验三的完整教学实践材料面向计算机类专业本科生及算法初学者聚焦图论核心知识与实际问题建模能力培养。内容涵盖邻接矩阵与邻接表两种存储结构下的图初始化、边插入/删除/搜索、DFS/BFS遍历等基础运算实现并以“飞机换乘次数最少”为典型应用场景基于有向图建模与Dijkstra算法时间复杂度≤O(n²)完成路径优化求解配套详细C语言源码注释、内存管理说明及可视化界面设计要求。资源为1个352KB的Word文档.doc含标准实验报告模板、算法原理分析、核心代码段含结构体定义、Init/Insert/DFS等函数、测试用例与结果截图格式规范、排版清晰便于直接用于课程作业提交或复习参考。目前已有576人学习下载是理解图抽象结构、掌握经典算法落地的关键实践范例。1. 图的邻接表建模 Dijkstra 变形为什么“飞机换乘次数最少”不能直接套用标准最短路径在南京邮电大学数据结构实验三中“飞机换乘次数最少问题”常被学生误认为是标准的单源最短路径问题直接搬出 Dijkstra 算法、填入航班距离就交差。但真实场景里你买的是机票不是飞行里程——北京→上海→广州→深圳3 次换乘北京→广州直飞0 次换乘。哪怕直飞距离更长换乘次数仍是核心指标。此时边权不再是物理距离或时间而是是否发生换乘的逻辑判别同一航空公司、同一天、连续起降的联程航班不计换乘跨航司、非联程、隔日中转统统算 1 次。这就要求图模型必须承载航班的时间戳、承运方、航班号、起降机场四维元信息而标准邻接矩阵或简单邻接表根本无法表达。实验本质是训练你把现实约束换乘规则精准映射为图结构设计与算法改造能力——不是调库跑通而是定义“边”本身。适合刚学完图的存储结构、正尝试将抽象算法落地到具体业务逻辑的本科生对考研复习王道数据结构中“图的应用”章节也有强对应性。2. 用邻接表构建带航班元信息的有向图为什么不用邻接矩阵2.1 邻接表是唯一可行的存储选择南京邮电大学实验要求处理至少 20 个机场、50 航班的数据集。若强行用邻接矩阵需 20×20400 个单元但实际航班稀疏平均每个机场仅连出 2~3 条航线矩阵填充率不足 15%。更致命的是同一对机场间可能存在多条不同时间、不同航司的航班如南京→北京每天有 CA1501、JD8892、MU2807 三班。邻接矩阵每个 cell 只能存一个值无法承载多航班并存而邻接表每个节点可挂多个FlightNode结构体天然支持一对多关系。这是数据结构选型的第一道分水岭——不是“能用”而是“必须用”。2.2 定义航班节点与邻接表结构C 语言实现// 航班元信息结构体 —— 实验核心数据载体 typedef struct { char flight_no[10]; // 航班号如 CA1501 char airline[10]; // 承运方如 国航 int dep_time; // 起飞时间分钟制08:30 → 510 int arr_time; // 到达时间分钟制 int duration; // 飞行时长分钟 } FlightInfo; // 邻接表的边节点指向下一个航班同时携带本航班信息 typedef struct ArcNode { int adjvex; // 目标机场下标0~n-1 FlightInfo info; // 该航班完整信息 struct ArcNode *nextarc; // 指向下一条从同一机场出发的航班 } ArcNode; // 顶点节点机场信息 出边链表头指针 typedef struct { char airport_name[20]; // 机场名如 NKG ArcNode *firstarc; // 指向第一条出边 } VNode; // 整张图顶点数组 顶点数 边数 typedef struct { VNode vertices[MAX_VERTEX_NUM]; int vexnum; // 机场总数 int arcnum; // 航班总数 } ALGraph;提示dep_time和arr_time必须统一为分钟制整数如 09:45 → 9×6045585避免字符串比较耗时duration可由arr_time - dep_time推导但显式存储可防数据异常符合实验报告“字段完整”要求。2.3 构建图的完整流程从航班列表到邻接表假设输入航班数据格式为NKG,PEK,CA1501,国航,08:30,10:15需完成三步解析机场名哈希映射遍历所有航班提取唯一机场名NKG/PEK等存入vertices[]并建立name → index映射表航班时间标准化用sscanf(line, %*[^,],%*[^,],%*[^,],%*[^,],%d:%d,%d:%d, h1,m1,h2,m2)提取时间转为分钟插入邻接表对每条航班src→dst创建ArcNode填入adjvexdst_index、info全字段头插法挂到vertices[src_index].firstarc。// 示例插入一条 NKG→PEK 的航班 void InsertArc(ALGraph *G, int src_idx, int dst_idx, FlightInfo fi) { ArcNode *p (ArcNode*)malloc(sizeof(ArcNode)); p-adjvex dst_idx; p-info fi; // 结构体整体赋值C11 支持 p-nextarc G-vertices[src_idx].firstarc; G-vertices[src_idx].firstarc p; G-arcnum; }2.3.1 关键验证点检查是否漏建顶点或重复插入实验易错点在于输入文件末尾可能有空行或格式错误行。必须在构建后执行校验遍历vertices[i].firstarc统计每个机场的实际出度对比输入航班数与G-arcnum是否相等打印任意机场如vertices[0]的前两条航班信息确认flight_no和dep_time解析正确。3. 改写 Dijkstra把“距离”换成“换乘次数”并加入时间可行性判断3.1 标准 Dijkstra 失效的根本原因原始 Dijkstra 假设从源点到某点的最短路径其子路径也必是最短的最优子结构。但“换乘次数最少”在加入时间约束后不满足该性质。例如路径 ANKG→PEK08:00→10:00再 PEK→SZX10:30→12:30→ 换乘 1 次路径 BNKG→SHA08:30→10:30再 SHA→SZX11:00→13:00→ 换乘 1 次表面看次数相同但若你 07:50 才到 NKG路径 A 的首班 08:00 航班已不可达而路径 B 的 08:30 航班可赶。此时必须将“能否赶上后续航班”作为状态转移条件而非单纯计数。3.2 状态定义与松弛操作重设计定义dist[i]不再是数字而是结构体typedef struct { int transfers; // 当前到达机场 i 的最小换乘次数 int last_arr_time; // 在机场 i 的最新到达时间用于判断能否衔接下一班 int path_len; // 路径上航班数辅助调试用 } Status; Status dist[MAX_VERTEX_NUM];松弛条件变为双条件判断对当前机场u的每条出边u→v航班f若满足①f.dep_time dist[u].last_arr_time 60预留 60 分钟中转时间②transfers_new dist[u].transfers (u source ? 0 : 1)dist[v].transfers则更新dist[v]。注意首段行程不计换乘u source时加 0后续每跳加 1。这是实验题干隐含规则也是和标准 Dijkstra 最关键的差异点。3.3 改写后的 Dijkstra 主循环C 语言void DijkstraTransfers(ALGraph G, int src, int dest, Status dist[]) { int visited[MAX_VERTEX_NUM] {0}; // 初始化 for (int i 0; i G.vexnum; i) { dist[i].transfers INT_MAX; dist[i].last_arr_time -1; dist[i].path_len 0; } dist[src].transfers 0; dist[src].last_arr_time 0; // 假设可在任意早时间抵达起点 for (int i 0; i G.vexnum; i) { // 选未访问中 transfers 最小的点若相同优先 last_arr_time 更早的 int u -1; for (int j 0; j G.vexnum; j) { if (!visited[j] (u -1 || dist[j].transfers dist[u].transfers || (dist[j].transfers dist[u].transfers dist[j].last_arr_time dist[u].last_arr_time))) { u j; } } if (u -1) break; visited[u] 1; // 遍历 u 的所有出边 ArcNode *p G.vertices[u].firstarc; while (p ! NULL) { int v p-adjvex; FlightInfo f p-info; // 判断能否衔接到达 u 的时间 60 分钟 ≤ 航班起飞时间 if (dist[u].last_arr_time 60 f.dep_time) { int new_trans dist[u].transfers (u src ? 0 : 1); // 严格小于才更新换乘更少优先相同时不更新保持更早到达时间 if (new_trans dist[v].transfers) { dist[v].transfers new_trans; dist[v].last_arr_time f.arr_time; dist[v].path_len dist[u].path_len 1; } } p p-nextarc; } } }3.3.1 参数说明与实验调试技巧参数说明实验常见错误dist[u].last_arr_time 60 f.dep_time强制中转时间 ≥ 60 分钟模拟安检步行忘加 60导致“瞬移式中转”结果换乘数为 0 却无解u src ? 0 : 1起点出发不计换乘符合航空业定义写成u ! src导致起点也加 1全路径换乘数1new_trans dist[v].transfers仅当换乘更少才更新不考虑“相同换乘下时间更早”误用引发无限循环或覆盖更优时间4. 实验数据构造与边界测试如何验证你的 Dijkstra 改写真正可靠4.1 设计三类必测数据集附可直接运行的样例南京邮电大学实验报告要求提供测试用例以下三组覆盖全部关键边界类型数据特征预期输出验证目的基础连通4 机场NKG,PEK,SHA,SZX6 航班存在直飞与一次中转NKG→SZX换乘 1 次NKG→PEK→SZX算法主干逻辑时间阻断NKG→PEK08:00→10:00PEK→SZX10:20→12:20→ 中转仅 20 分钟NKG→SZX无解需提示“无法衔接”时间约束有效性零换乘直飞NKG→SZX 存在航班09:00→11:30NKG→SZX换乘 0 次起点逻辑usrc?0:1正确性样例输入基础连通NKG,PEK,CA1501,国航,08:00,10:00 NKG,SHA,MU2807,东航,08:30,10:30 PEK,SZX,CZ3101,南航,10:30,12:30 SHA,SZX,HU7722,海航,11:00,13:00 NKG,SZX,FM9102,上航,12:00,14:30 PEK,SHA,CA1522,国航,13:00,14:304.2 输出路径还原不只是换乘数还要打印航班序列Dijkstra 只给出最小换乘数但实验要求输出具体路径。需在Status结构中增加前驱记录typedef struct { int transfers; int last_arr_time; int path_len; int parent; // 上一机场下标用于回溯 char last_flight[10]; // 到达本机场所乘航班号 } Status; // 更新时同步记录 if (new_trans dist[v].transfers) { dist[v].transfers new_trans; dist[v].last_arr_time f.arr_time; dist[v].path_len dist[u].path_len 1; dist[v].parent u; strcpy(dist[v].last_flight, f.flight_no); }路径打印函数递归逆序输出void PrintPath(Status dist[], ALGraph G, int src, int dest) { if (dest src) { printf(起点: %s\n, G.vertices[src].airport_name); return; } if (dist[dest].parent -1) { printf(无可行路径\n); return; } PrintPath(dist, G, src, dist[dest].parent); printf(乘坐 %s 从 %s → %s\n, dist[dest].last_flight, G.vertices[dist[dest].parent].airport_name, G.vertices[dest].airport_name); }4.2.1 实验报告关键截图建议控制台输出清晰显示起点 NKG → 终点 SZX换乘次数1及两行航班详情调试断点截图在dist[v].transfers更新处观察u,v,new_trans,f.flight_no的实时值输入文件内容截图证明使用的是符合实验要求的航班数据格式。5. 进阶优化用优先队列加速以及处理“同航司免换乘”的业务扩展5.1 从 O(V²) 到 O((VE) log V)手写最小堆替代线性查找前述 Dijkstra 使用数组遍历找最小transfers时间复杂度 O(V²)。当机场数超 50性能明显下降。南京邮电大学高分实验要求体现算法优化意识。改用二叉最小堆按transfers为主键、last_arr_time为次键排序// 堆元素封装机场下标与状态 typedef struct { int vex; // 机场下标 int transfers; int last_arr_time; } HeapNode; HeapNode heap[MAX_VERTEX_NUM]; int heap_size 0; void push(HeapNode node) { heap[heap_size] node; int i heap_size; while (i 0) { int p (i-1)/2; // transfers 小优先相同时 last_arr_time 大优先更早到达更好衔接 if (heap[i].transfers heap[p].transfers || (heap[i].transfers heap[p].transfers heap[i].last_arr_time heap[p].last_arr_time)) { swap(heap[i], heap[p]); i p; } else break; } } HeapNode pop() { HeapNode root heap[0]; heap[0] heap[--heap_size]; int i 0; while (1) { int l 2*i1, r 2*i2, min_idx i; if (l heap_size (heap[l].transfers heap[min_idx].transfers || (heap[l].transfers heap[min_idx].transfers heap[l].last_arr_time heap[min_idx].last_arr_time))) min_idx l; if (r heap_size (heap[r].transfers heap[min_idx].transfers || (heap[r].transfers heap[min_idx].transfers heap[r].last_arr_time heap[min_idx].last_arr_time))) min_idx r; if (min_idx i) break; swap(heap[i], heap[min_idx]); i min_idx; } return root; }提示last_arr_time在堆中“越大越好”因为到达越早越容易衔接后续航班。这与常规“时间越小越好”相反务必在比较逻辑中反转。5.2 业务扩展“同航司免换乘”规则的图结构适配实际航空业中同一航司的联程票如国航 CA1501CA1202即使中转也计为 0 次换乘。此规则需修改松弛条件// 原条件new_trans dist[u].transfers (u src ? 0 : 1) // 新条件 int new_trans; if (u src) { new_trans 0; } else if (strcmp(f.airline, prev_airline) 0) { // prev_airline 从 dist[u] 中获取 new_trans dist[u].transfers; // 同航司不新增换乘 } else { new_trans dist[u].transfers 1; }实现要点Status结构需新增char last_airline[10]字段初始化dist[src].last_airline 更新dist[v]时同步赋值strcpy(dist[v].last_airline, f.airline)此扩展使图模型真正贴近生产环境也是南京邮电大学课程设计中拉开差距的关键点。5.2.1 验证同航司场景的最小测试用例输入NKG,PEK,CA1501,国航,08:00,10:00 PEK,SZX,CA1202,国航,10:30,12:30 NKG,SZX,MU2807,东航,11:00,13:30预期NKG→SZX 输出换乘 0 次CA1501CA1202而非 1 次MU2807 直飞。此结果直接证明你的业务规则编码正确。本文还有配套的精品资源点击获取
