数据结构第二次试验.地铁换乘.doc

/数据结构实验报告学院自动化学院学号 08016332姓名徐璐峰日期 2017-12-18实验目的1） 熟练掌握图的存储方式；2） 了解图的特性，学习在实际问题背景下灵活运用图;3） 掌握图的两种最短路径算法实验内容为简化问题，假设南京现有三条地铁线：1号线、2号线和3号线，线路都 是双向的3条地铁线的站点名分别如下，地铁线交叉的换乘点用 T1、T2等表示请根据3条地铁线的站点和换乘点构造图 编写程序，任意输入两个站名名 称，输出乘坐地铁最少需要经过的车站数量 （含输入的起点和终点，换乘站点只计算一次）地铁 1 号线（直线）经过车站： A1 A2 A3 T1 A4 A5 A6 A7 A8 T2 A9 A10 A11 A12 T3 A13 A14 A15 T4 A16地铁 2 号线（直线）经过车站： B1 T5 B2 B3 B4 B5 T2 B6 B7 B8 B9 B10 B11 T3 B12 B13 T6 B14 B15地铁 3 号线（环线）经过车站：C1 C2 C3 C4 C5 T1 C6 C7 C8 C9 C10 T5 C11 C12 C13 T6 C14 C15 T4 C16 C17 C18实验要求1）用户从键盘输入两个不同的站名， 程序输出最少需要经过的车站数量（含输入的起点和终点，换乘站点只计算一次）；2） 分别基于迪杰斯特拉算法和弗洛里德算法实现上述地铁换乘问题;3） 程序功能模块的划分要适当，多使用流程图来描述算法结构。

/1需求分析1） 输入的形式和输入值的范围输入的形式需要是地铁站的名称，如“ A1”、“B7”、 “C14”所输入的的站点名不能是所要求的站点名之外的名称2） 输出的形式所输出的是基于弗洛里德算法与迪杰斯特拉算法进行的最短路径长度 求解的结果，以及最短路径的车站路径编号，并在输入错误的时候允许重复输入3） 程序所能达到的功能用户输入车站起点与车站终点之后，通过迪杰斯特拉算法与 弗洛伊德算法，输出从起点到终点的最短路径长度，以及最短路径所经过的车站编号4） 测试数据在程序运行的开始， 会提示用户输入起点与终点， 在用户输入起点与终点之后， 程序会输出根据弗洛伊德算法所得到的最短路径所经过的车站数量， 及经过的车站路径的编号之后会再输出根据迪杰斯特拉算法所得的最短路径所经过的车站数量， 及所经过的车站路径的编号如果所输入起点或终点不存在，则会提示“起点 /终点输入错误，请确认后重新输入之后会继续出现“请输入起点 /终点：”之后，用户就可以重新输入原来输入错误的起点或终点车站名在确认起点与终点都输入正确之后， 程序就会输出最短路径与路径编号在一次程序执行完毕后，支持用户重复输入2概要设计在程序中之定义了一种抽象数据类型， struct Graph，它包含三个元素，int arrAcc[56][56];〃邻接矩阵 int verCount;〃点数int arcCount;〃边数。

并且在程序开始的时候，还定义了长度为56的stri ng型数组，用于存储所有的地铁站点在程序运行开始的时候，会先调用change_train函数，在change_train函数中，会先对 g.arrAcc[56][56]邻接矩阵进行初始化之 后调用floyd函数，及printres函数，输出起点到终点的最短路径长度及路径车站编号 之后，会继续调用Dijkstra函数及searchPath函数，输出起点到终点的最短路径长度及路径车站编号3详细设计类视图Graph結构F字段 —* arcCount・ arrAcca verCount整个程序中所写的函数有： floyd函数，transform函数，printres函数，Dijkstra函数,searchPath 函数，change_train 函数Floyd函数（图g,邻接矩阵dis叩， 用来存储路径的矩阵path叩）//初始化path矩阵For（row 0 to 总的站点数）For （col 0 to 总的站点数）path[row][col] — row;{-/For （k 0 to 总的站点数）For （i 0 to 总的站点数）For （j 0 to 总的站点数）{//存在更近的路径，更新If （dis[i]j > dis[i][k] + dis[k][j]） {dis[i][j] ■ dis[i][k] + dis[k][j]; path[i][j] ■ path[k][j];}}}Transform函数（字符c） {For （i 0 to 站点数）If （存储所有站点的数组s[i] == c）返回i;Printres函数（图Graph*p,经floyd函数转化后的邻接矩阵dis[56][56], 存储路径的矩阵path[56][56], 起点 start,终点 end）{起点数码 st = transform（ 终点数码 en = transform（起点字符start）;终点字符end）;//将起点与终点转化为存储站点的数组中对应的下标输出 <<”起点-> 终点"<< endl;输岀 << "根据弗洛伊德算法得，最少经过的车站数量 :"<< dis[st][en] + 1 << endl;输出 << "经过的车站路径编号："；For （i 0 to 站点数）For （j 0 to 站点数）{If （i == 起点数码st并且j == 终点数码en） //输岀路径{stack< int> pathrout; // 压栈k- j;do {k- path[i][k];kA pathrout 的栈}当（k不等于i）;输岀 << 存储站点的数组s[pathrout的栈顶元素];弹岀pathrout的栈顶元素；length —栈pathrout 的大小;For （t 0 to le ngth）{-/输岀 << "->" << 存储站点的数组s[pathrout的栈顶元素];弹岀pathrout的栈顶元素；}输出 << "->"<< 用户输入的终点；跳岀循环；}}}Dijkstra函数（总的站点数n,起点v,当前点到起点的最短路径长度distenee, 记录当前节点的掐 一个节点prev,记录图两点间的路径长度 c[56][56]）{bool s[56]; // 判断是否已存入该点到S集合中For （ i 0 to 总的站点数n）{diste nce[i] — c[v][i];s[i] = 0; // 初始都未用过该点If （起点到第i个点的距离为1000）第i个点的前一个点为0;否则第i个点的前一个点为起点；}//依次将未放入S集合的结点中，取distence[]最小值的结点，放入结合S中// 一旦S包含了所有V中顶点，distenee就记录了从源点到所有其他顶点之间的最短路径长度For （i 1 to n）{//找岀当前未使用的点j的distence[j] 最小值For （j 0 to n）if （s[j] 等于0 并且 起点到第j个点的距离（temp）小于1000）{u • j; // u 保存当前邻接点中距离最小的点的号码tmp ■ diste nce[j];}s[u] ■ 1; // 表示u点已存入S集合中// 更新 diste neeFor (j 0 to n)If (s[j] 为0 并且 点j到点u的距离c[u][j] 小于1000)n ewdist — diste nce[u] + c[u][j];If (n ewdist < diste nce[j]) {distence[j] ■ newdist;// 更新起点到第j个点的最短路径prev[j] ■ u;//更新第j个点的前一个点{-/}}}}searchPath函数(用于表示当前点的前一个点的数组 prev,起点v, int u){int que[56];tot ■ 1;que[tot] — u;tot自增；tmp ■ prev[u];当(tmp不等于v){que[tot] — tmp;tot自增；tmp ■ prev[tmp];}que[tot] — v;For (i tot to 1)If (i 不等于1)输岀 << s[que[i]] << "->";否则输岀 << s[que[i]] << endl;换行；}change_train 函数(){diste nce[56];记录起点到当前点的最短路径prev[56]; 记录当前点的前一个结点path[56][56];记录路径matrix[56][56]; 用于备份的矩阵arrAcc[56][56];邻接矩阵g.verCou nt = 56;// 定义总的站点的数目+1For (i 0 to 56)diste nce[i] — max;//初始化邻接矩阵For (i 0 to g.verCount(56)) {For ( k 0 to g.verCou nt(56))If (i 与k相同)g.arrAcc[i][k] = 0;否则{-/g.arrAcc[i][k] = max;}}//输入A环线各点连接情况，每个边权重都为 1a[20] = { 0,1,2,49,3,4,5,6,7,50,8,9,10,11,51,12,13,14,52,15 };For (i 0 to 19){g.arrAcc[a[i]][a[i + 1]] ■ 1;g.arrAcc[a[i + 1]][a[i]] ■ 1;}个占I 八、、};//23//输入B线各点连接情况，每个权重都为1b[19] = { 16,53,17,18,19,20,50,21,22,23,24,25,26,51,27,28,54,29,30 };//19For (i 0 to 18){g.arrAcc[b[i]][b[i + 1]] ■ 1;g.arrAcc[b[i + 1]][b[i]] ■ 1;}//输入C线各点连接情况，每个权重都为1c[23] = { 31,32,33,34,35,49,36,37,38,39,40,53,41,42,43,54,44,45,52,46,47,48,31 个点(因为是环线，所以点数加一)For ( i 0 to 22){g.arrAcc[c[i]][c[i + 1]] ■ 1;g.arrAcc[c[i + 1]][c[i]] ■ 1;}For (i 0 to 56) {For (j 0 to 56){arrAcc[i][j] — g.arrAcc[i][j];}}//因为使用完弗洛伊德算法之后，g.arrAcc的返回值已经变化了， //故在此将g.arrAcc中的值都赋值给matrix二维数组中，进行备份For ( i 0 to 56) {For ( j 0 to 56){matrix[i][j] ■ g.arrAcc[i][j];}}For ( i 0 to 56)。