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

1、-/数据结构实验报告学院自动化学院学号 08016332姓名徐璐峰日期 2017-12-18实验目的1）熟练掌握图的存储方式；2）了解图的特性，学习在实际问题背景下灵活运用图;3）掌握图的两种最短路径算法。实验内容为简化问题，假设南京现有三条地铁线：1号线、2号线和3号线，线路都 是双向的。3条地铁线的站点名分别如下，地铁线交叉的换乘点用T1、T2等表示。请根据3条地铁线的站点和换乘点构造图。 编写程序，任意输入两个站名名 称，输出乘坐地铁最少需要经过的车站数量（含输入的起点和终点，换乘站点只计算一次）。地铁 1 号线（直线）经过车站： A1 A2 A3 T1 A4 A5 A6 A7 A8 T

2、2 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 C18T1、T2实验要求1)用户从键盘输入两个不同的站名，程序输出最少需要经过的车站数量（含输入的起点和终点，换乘站点只计算一次）；2)分别基于迪杰斯特拉算法和弗洛里德算法实现上述地铁换乘问题;

3、3)程序功能模块的划分要适当，多使用流程图来描述算法结构。A1”、“ B7”1需求分析1）输入的形式和输入值的范围。输入的形式需要是地铁站的名称，如“C14”。所输入的的站点名不能是所要求的站点名之外的名称。2）输出的形式。所输出的是基于弗洛里德算法与迪杰斯特拉算法进行的最短路径长度 求解的结果，以及最短路径的车站路径编号，并在输入错误的时候允许重复输入。3）程序所能达到的功能。用户输入车站起点与车站终点之后，通过迪杰斯特拉算法与 弗洛伊德算法，输出从起点到终点的最短路径长度，以及最短路径所经过的车站编号。4）测试数据。在程序运行的开始， 会提示用户输入起点与终点，在用户输入起点与终点之后，程

4、序会输出根据弗洛伊德算法所得到的最短路径所经过的车站数量，及经过的车站路径的编号。之后会再输出根据迪杰斯特拉算法所得的最短路径所经过的车站数量，及所经过的车站路径的编号。如果所输入起点或终点不存在，则会提示“起点/终点输入错误，请确认后重新输入。”之后会继续出现“请输入起点/终点：”之后，用户就可以重新输入原来输入错误的起点或终点车站名。在确认起点与终点都输入正确之后，程序就会输出最短路径与路径编号。在一次程序执行完毕后，支持用户重复输入。2概要设计在程序中之定义了一种抽象数据类型，struct Graph,它包含三个元素，int arrAcc5656;/邻接矩阵int verCount;/点

5、数int arcCount;/边数。并且在程序开始的时候，还定义了长度为56的stri ng型数组，用于存储所有的地铁站点。在程序运行开始的时候，会先调用change_train函数，在change_train函数中，会先对 g.arrAcc5656邻接矩阵进行初始化。之 后调用floyd函数，及printres函数，输出起点到终点的最短路径长度及路径车站编号。之后,会继续调用Dijkstra函数及search Path函数，输出起点到终点的最短路径长度及路径车站编号。3详细设计类视图Craph9 arcCoum airAcca verCount整个程序中所写的函数有：floyd函数，tran

6、sform函数，printres函数，Dijkstra函数,search Path 函数，cha nge_tra in 函数。Floyd函数（图g,邻接矩阵dis,用来存储路径的矩阵path叩）/初始化path矩阵For（row 0 to 总的站点数）For （col 0 to总的站点数）P athrowcol row;For （k 0 to 总的站点数）For （i 0 to 总的站点数）For （j 0 to总的站点数）/存在更近的路径，更新If （disij > disik + diskj） disij - disik + diskj; P athij- p athkj;Trans

7、form函数（字符c）For （i 0 to 站点数）If （存储所有站点的数组si = c）返回i;Printres函数（图Graph*p,经floyd函数转化后的邻接矩阵dis5656,存储路径的矩阵path5656, 起点 start,终点 end）起点数码st = transform（ 起点字符start）;终点数码en = transform（终点字符end）;/将起点与终点转化为存储站点的数组中对应的下标输岀 <<”起点->终点"<< endl;输岀 << "根据弗洛伊德算法得，最少经过的车站数量:"<&

8、lt; dissten + 1 << endl;输岀 << “经过的车站路径编号："；For （i 0 toFor （j 0 toIf （i =站点数）站点数）起点数码st并且j = 终点数码en） /输岀路径stackv int> p athrout; / k- j;do 压栈心 pathik;kA pathrout 的栈（k不等于i）;<<存储站点的数组spathrout的栈顶元素;当输岀弹岀pathrout的栈顶元素； length 栈pathrout 的大小;For （t 0 to le ngth）输岀 << "

9、->"<<弹岀 pathrout输岀 << "->"<<跳岀循环；存储站点的数组spathrout的栈顶元素; 的栈顶元素；用户输入的终点；Dijkstra 函数（总的站点数n,起点v, 一个节点prev,记录图两点间的路径长度 c5656） bool s56;/For当前点到起点的最短路径长度diste nee,记录当前节点的掐判断是否已存入该点到S集合中（i 0 to总的站点数n）diste ncei cvi;si = 0;/初始都未用过该点If （起点到第i个点的距离为1000）第i个点的前一个点为0;否则第i

10、个点的前一个点为起点；/依次将未放入S集合的结点中，取distence最小值的结点，放入结合S中一旦S包含了所有V中顶点，distenee就记录了从源点到所有其他顶点之间的最短路径长度For （i 1 to n）/u v;/找岀当前未使用的点j的distencej最小值For (j 0 to n)if (sj等于 0并且 起点到第j个点的距离（temp）小于1000）U j；tmp diste ncej;/ u保存当前邻接点中距离最小的点的号码su 1; /表示U点已存入S集合中更新 diste neeFor (j 0 to n)If (sj为 0 n ewdist并且点j到点u的距离cuj

11、小于1000）diste nceu + cuj;If (n ewdist < diste ncej)distencej newdist;/ 更新起点到第j个点的最短路径prevj u;/更新第j个点的前一个点search Path函数（用于表示当前点的前一个点的数组p rev,起点v, i nt u）int que56;tot 1;quetot u;tot自增；tmp p revu;当(tmp不等于v)quetot tmp;tot自增； tmp pr evt mp;quetot v;For (i tot to 1)If (i 不等于1)输岀 << squei <<

12、 "->"否则输岀 << squei << endl;换行；Change_train 函数()记录起点到当前点的最短路径 记录当前点的前一个结点 记录路径用于备份的矩阵邻接矩阵定义总的站点的数目+1diste nce56; p rev56;path5656;matrix5656;arrAcc5656;g.verCou nt = 56;/ For (i 0 to 56)diste ncei max;/初始化邻接矩阵For (i 0 to g.verCou nt(56) For ( k 0 to g.verCou nt(56) If (i 与k相同

13、)g.arrAccik = 0;否则g.arrAccik = max;/输入A环线各点连接情况，每个边权重都为1a20 = 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.arrAccaiai + 1g.arrAccai + 1ai/输入B线各点连接情况，每个权重都为1b19 = 16,53,17,18,19,20,50,21,22,23,24,25,26,51,27,28,54,29,30 ;/19For (i 0 to 18)占I八、/g.arrAccbibi + 1g.arrAccbi + 1bi输入C

14、线各点连接情况，每个权重都为1c23 = 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);/23g.arrAcccici + 1g.arrAccci + 1ciFor (i 0 to 56) For (j 0 to 56)arrAccijg.arrAccij;/因为使用完弗洛伊德算法之后，g.arrAcc的返回值已经变化了， 故在此将g.arrAcc中的值都赋值给matrix二维数组中，进行备份For ( i 0 to 56) For ( j

15、 0 to 56)matrixijFor ( i 0 to 56) matrixiiwhile (true) /利用这个死循环来实现用户的重复输入调用 floyd 函数(&g, arrAcc, path);/max;g.arrAccij;定义 judgel = 0, judge2 = 0;输岀 << "请输入起点与终点："输入 >> start >> end;当(judgel = 0 或者 judge2 = 0) For (i 0 to 56) 1;跳岀循环;If (si = start) judgel 否则 judgel 0;I

16、f (judgel = 0) 输岀 << “起点输入错误，请确认后重新输入！" <<换行; 输岀 << "请输入起点："输入 >> start;For (i 0 to 56) 1;跳岀循环;If (si = end) judge2 否则 judge2 0;If (judge2 = 0) 输岀 << “终点输入错误，请确认后重新输入！" <<换行; 输岀 << "请输入终点："输入>> en d;n = tran sform(e nd);v

17、= tra nsform(start);调用 prin tres(&g, arrAcc, p ath, start, en d);使用完弗洛伊德算法之后，g.arrAcc已经变了，所以需要邻接矩阵输岀 << 换行；For (i 0 to 56) /进行重置For (j 0 to 56)matrixij;arrAccij调用 Dijkstra(56, v, diste nee, pr ev, matrix);/最短路径长度换行；输岀 << "根据迪杰斯特拉算法得，最少经过的车站数量 :"<< distencen + 1 <&l

18、t;/路径输岀 << “经过的车站路径编号："；调用 search Path( pr ev, v, n);函数调用关系图和浙餉编入的Mt身曲川魏烤狀丰 -I旳丿品衣力咖以应我攵I腑崔第衷A4调试分析以及对整个设计和实现过程的回顾讨论1）调试过程中遇到的问题及其解决办法，邻接矩阵arrAcc5656的值已经变化了，Dijkstra算法，以及在用户九子那个重复输 在对这个点 就颇费了些功夫，最后不得不先将arrAcc数组储存起来，每与分析；问题一：在进行完floyd算法之后，此时再利用这个矩阵进行接下来的 入，重复调用floyd与Dijkstra函数，都是不能得出正确的结果的

19、。进行调试的时候，次在调用floyd之前，都新建一个 matrix5656数组，将arrAcc5656数组中 的值都复制进来，之后让floyd函数调用matrix数组，而不再调用arrAcc数组。问题二：在借用网上的代码的时候，网上的算法中，无论矩阵还是数组，下标 都是从1开始的，但我自己所建的数组，为了节省内存，都是从 0开始的，所 以在将从1开始的数组以及矩阵转化为从0开始的数组与矩阵的时候，废了很多麻烦。但无论是从0开始，还是从1开始，只是表达数组与矩阵的思想不同， 效果都是一样的。问题三：在设计实现用户的重复输入的过程中，一直找不到如果用户输入错误之后，重新输入时，输入正确之后，结束循

20、环的条件，就一直陷入死循环中。最 后，就设置了 judgel和judge2两个数来记录是否能够在已有的站点中找到所 输入的站点。在依据用户输入的站点对已有的站点数组进行遍历的时候，在数 组中的站点与输入的站点不相同的时候，用0对judge1/judge2进行重复赋值，一旦找到站点数组中的某个站点与用户所输入的站点相同的时候，用1对judge1/judge2进行赋值，并且 break。判断循环的条件就是judge1/judge2=0。问题四：在整个程序中涉及到很多对矩阵进行的操作，包括很多对于矩阵中的 值的修改，在很多情况下，在代码运行错误，以及出现意想不到的结果的时候， 通过输出中间变量矩阵来

21、判断程序那里出现了问题是非常方便的。所以在整个程序编写的过程中，也写了很多的将程序运行过程中生成的矩阵输出的代码， 以便弄清楚代码哪里出现了问题。2)算法的时空分析。空间复杂度：在整个程序运行的过程中，定义的变量有 arrAcc5656,s56,queue5656,dista nce5656, prev5656, path5656,matrix5656,以及三个，大小总共为 64的用于记录站点编号的数组。所以程序的空间复杂度为0(6608).时间复杂度：程序中所有的循环都是以56为单位的。在整个程序运行的过程中，共进行了以56为单位的单重循环 5次，双重循环8次，三重循环1次。所以整个程序的时

22、间复 杂度为 O(200984).5测试结果当输入的车站名满足要求时m祁LT广、厂咛门厂1飞石內e： 5需頤)人起点与輕点：Cfl fill虞饲到fli I根齊_曲洛伊擅聲法得，量屮经过的年詁釵邑：12经过的车封路径堤号：CS->C9->C19->T5->B2->B3->04->B5->T2->A9->ft10->A11想嘉心斯蛰feS法带，显少经过的车站数昌：12经过甘车詁路泾端号：Ce->C9->C1 9->75->B2->B3->B4->B5->T2->A9->f

23、lia->fil 1焉m人起点与英点=65 tl2畝25到<：12根据厲客毋徳审法得=羽4奈过的车诂数註；T经过曲牟詁珞径编号；B5- >B>+->e3->B2->T5->Cl 1 ->C1Z 段据迪我朋特拉算法-寻，7逢过的车詁珞径编号：B5->e4->B3->B2->T5->Cn ->C1Z半;所设计的程序能够实现重复输入，更大程度的满足用户需求。 当输入的车站名不存在时：起点终点均不存在：3S C AWindowsVsystem 3 2c md. exe请输入起点与终点：A2G C20起点输入错诔，

24、请躋认后£新喻入！请输入起点：A3终点输入错课.请确认后S新驸入！请输人终点：511根摇男洛伊德算S；得，最茂经过的$姑数量：8经过的$詁菇e编号：fi8->T2*>B6->B7*>B8->Ba->B10->B11棍据ia杰靳特拉算谍潯，最少经讨的$詁数fi： e经过的车站路径编号；A8- >T2->B6- >B7->E8- >B3->B10->B11请输入起点与终点:o II起点存在，终点不存在:SI C:WindoWysteir32匚nnd exe请谕入起点与终啟fi2 B20浜点输入®

25、惺，请诙认后4W输入！涓输人终点：Ba从口 2到曲根据弗洛伊德算摆得帚少经过的车袖歌呈：13经过的车站路待编号；A2->A3->T1->Ai+->A5->AS->A7->AS->T2->ES->B7->B8->B9根据迪杰斯蔣技算a得，最少经过的年.詁欺量："曾讨的车站跻徉也弓：fi2-?fl3->T1->A*+->A5->A6->A7->AS->T2->B6->BT->BS-?B9请轴入起点q纯点：A4 B67终点瑜入S惺，漕确认兀4新输人！谓输入终点

26、：C5AA 斗至 lC5根据弗洛伊德虫摆得昜少绎过的车站数： 3 竪过的丰站庖径將号：fi斗-门-亡5ffiffi迪杰斯特拉算S得，最少经谊的牟站歎S： 3 纤过的车站路住將弓: AH->T1->C5请输入起点与贸点:终点存在，起点不存在:OB C:Windows5ystem 3 2c rnd pkc请输入起点与终点：fiZO B6起点输入错谍，请确认后重新箍入！ 请输入起点：C11从C11到鶉根据弗洛声德算法得，：a少经过的车詁数量：S环过的车站路胫编弓；C11->T5->B2->B3->B4->B5->T2->Be 根据迴杰斯特拉算袪得

27、，最少经过的车站数量：8经过的李站路径编号：C11 ->T5->B2->B3->B4->B5->T2->Be请输入起点与終点:当用户重复输入错误的时候:请输入起点与缪点：A23 B5 起点输A错谣t请确认后S新输入1 ilWA 起魚J A23起点输入错谋，请确认后重新输入！ 请輪jA起点：A23起点输人错iX. iw确认后車新输人！谴输入起点：BS7起点輸入错谋，请确认后重新输入！ 谙细L头起点：口2根据弗洛伊德篦法得,最少g辽的$鮎数量：ie经过的兰詁路径编号：A2->A3->T1 ->A4->A5->A6->A7

28、->A8->T2->B5 丰据迪杰斯特S鄭去得.最少经过的车詁数量：怕涇过的车站路e编号；A2->A3->T1->A>l->A5->A6->A7->ft8->T2->B5请输入起点与线点:在设计程序的过程中， 考虑了用户输入错误的情况。 在用户输入错误的情况下， 提示用 户是起点，还是终点输入错误， 之后提示用户确认后重新输入。并且支持程序的重复运行，直到用户不再需要查询路径的时候，退出程序。两种算法虽然 网上也有很多有 但将网上的代码改编为自己想要的基于地铁换乘6实验总结本次实验主要就是基于弗洛里德与迪杰斯特拉算法进行最短路径的求解， 原理不同，但总的来说，都是对矩阵进行操作，从而得到自己想要的结果。 关弗洛伊德算法与迪杰斯特拉算法的代码， 的代码还是有很大难度的。首先需要考虑的就是在定义储存所有站点的数组的时候，地铁线路的交叉点应处在数组的什么位置，处于所有站点的末尾与处在站点的中间会是两种不同的处理方法。并且网上的很多代码都是数字作为整个图的节点，但地铁换乘的节点是站点名字，是string类型的量。在将代码从基于数字到基于string也是破费了写功夫。创新之处：1.在初始化邻接矩阵的时候，依据每个站点在总的存储站点的数组里的顺序，定 义了分别表示三条地铁线路的int