数据结构A第三次试验报告

1、实验报告（2014 / 2015学年第二学期）课程名称数据结构A实验名称图的基本运算及飞机换乘次数最少问题实验时间年月日指导单位 计算机学院计算机科学与技术系指导教师学生姓名学院（系）管理学院班级学号专 业信息管理与信息系统实验报告实验名称图的基本运算及飞机换乘次数最少问题指导教师陈雷实验类型设计实验学时2实验时间2一、实验目的和要求(1)图的基本运算 验证教材中关于在邻接矩阵和邻接表两种不冋存储结构上实现图的基本运算的算法。 在邻接矩阵存储结构上实现图的深度和广度优先遍历算法。 设计主函数，测试上述运算。提示：扩充MGraph类，在扩充类上增加 DFS和BFS函数。(2 )飞机最少换乘次数问

2、题设有n个城市，编号为0n-1, m条航线的起点和终点由用户输入提供。寻找一条换乘次数 最少的线路方案。提示：可以使用有向图表示城市间的航线。只要两城市间有航班，则图中这两点间存在一条权 为1的边。可以使用 Dijkstra算法实现。思考：如果是城市公交车的最少换乘问题，将如何解决？假如希望使用类似的算法，则图中的 边如何设置？要求：(1) 掌握在图的邻接矩阵和邻接表存储结构实现图的基本运算的算法。(2) 学习使用图算法解决应用问题的方法。二、实验环境(实验设备)中文五号木体，央文五号 Times new roma n子体，1.25倍行距硬件：微型计算机软件： Windows 操作系统、 Mi

3、crosoft Visual C+6.020三、实验原理及内容1、类和类的层次结构 TQueueabstrat+ virtual void EnQueue( T &x)=0;+ virtual void DeQueue()=0+ virtual bool lsEmpty() const=0+ virtual bool lsFull() const=0+ virtual TFron t()=0SeqQueue -int fron t,rear; -int MaxSize;-T *q;+ SeqQueue()+SeqQueue()+ voidEn Queue( T &x)+ voidDeQueue

4、()+ TFron t()+ boolIsEmpty() const+ boolIsFull() const父类:子类:父类:GraphQueueSeqQueue继承关系子类：LGraph继承关系LGraph#ENode* a+LGraph( int mSize)+LGraph()+ResultCode Insert(int u, int v, T& w) +ResultCode Change(int u,int v,T& w) +ResultCode Remove (int u, int v)+ bool Exist( i nt u, int v)c onst+ int Vertices()

5、+void Output()ExtLGraph+ExtLGraph( int mSize):LGraph(mSize)+void DFS();+void BFS();+void CallI nDegree( int* In Degree);+void TopoSort( int* order);+ int Choose(int *d, bool* s);+void Dijkstra( int v,T* d, int* path);+void BetweenMinPath( int a,int b);-void DFS(int v, bool* visited);-void BFS(int v,

6、 bool* visited);实验报告2、算法及数据结构(1)图的宽度优先遍历所使用的队列结构0123456 7=maxSize-1队列结构示意图(2)图的结构示意(4)图的邻接矩阵表示i234500000001i0100120i00113i0001040i00115ii0000J实验报告4、核心算法代码(1)图的宽度优先遍历，使用邻接矩阵实现void MGraph:BFS()bool* visited = new boo I n;for(i nt i= 0; i n; i+) visitedi = false;for(i nt i= 0; i n; i+)if(!visitedi) BFS

7、(i, visited); delete visited;void MGraph:BFS( int v, bool* visited)SeqQueue q(20);visitedv = true; cout v;q.E nQueue(v);while (!q.lsEmpty()q.Fro nt(v); q.DeQueue(); for(i nt i=0;i n ;i+)当顶点未被访问以及两顶点间存在路径才访问if(!visitedi)&(avi!=INFTY) visitedi= true;couti;q.E nQueue(i);(2)图的深度优先遍历，使用邻接矩阵实现void MGraph:

8、DFS()bool* visited =new bool n;for(i nt i= 0; i n; i+) visitedi =false;for(i nt i= 0; i n; i+)if(!visitedi) DFS(i, visited);delete visited;templatevoid MGraph:DFS(int v, bool* visited)visitedv =true; cout v;for(i nt i=0;i n ;i+)if(!visitedi)&(avi!=INFTY)DFS(i,visited);(3) Djikstra 算法void ExtLGraph:D

9、ijkstra(int v,T* d,int* path)in t i,k,w1;ENode* p=av;if(v n-1)coutOutOfBou nds!e ndl;bool* s=new bool n;for(i=0;iadjVex;di=p-w;pathi=v;p=p-n extArc;p=NULL;sv=true;dv=0;for(i=1;in extArc)w1=p-adjVex;if(!sw1 &dk+p-ww;pathw1=k;(4 )求图的任意两点之间的最短路径算法void ExtLGraph:Betwee nMin Path(i nt a, i nt b)int x=thi

10、s-n;int y=b;if(a x|bx)/对输入数据进行越界判断coutOutofBou nds!Dijkstra(a,d,path);if(pathb=-1)coutThe path is NotPrese nt!e ndl;return;elseint n=0;int* pathmi n=new in t;/申请动态一维数组由于存储路径while(pathy!=-1)pathm inn=pathy;n+;y=pathy;n=n-2;coutthe path is: (=0;n-)倒序输出路径数组，结果为顶点a到b的路径cout pathm inn;cout b)e ndl;coutth

11、e dista nee is:dbe ndl;(5)主函数程序int main (void)int b=10;cout请输入将要建立图的顶点数： b;ExtLGraph lg(b);enum ResultCode status=Failure;int u=0,v=0,w=0,a=0;int* order =new in tb;system(color 70);men u();while (a!=7)cin a;switch(a)case 1:cout请输入始点 u和终点v以及权值 w:endl;while(!(u0|v0|wvw;status=lg .In sert(u,v,w);if(sta

12、tus=Success)coutSuccess!e ndl;else if(status=Duplicate)coutthe path is exist!e ndlPlease in put aga in ! uvw;else if(status=Failure& !(u0|v0|w0)coutI nput Error! uvw;system(pause);system(cls);menu();break;case 2:cout请输入始点u和终点v以及要改变的权值w: uvw;status=lg.Cha nge(u,v,w); if(status=Success)/*coutSuccess!e

13、 ndl;*/ else coutThe path is NotPrese nt!e ndl; system(pause);system(cls);menu();break;case 3:cout请输入要删除的始点u和终点v: uv;status=lg.Remove(u,v);if(status=Success)coutSuccess!e ndl;else coutThe path is NotPrese nt!e ndlRemove Failure!e ndl; system(pause);system(cls);menu();break;case 4:coutBFS :endl;lg.BF

14、S();coutendlDFS :endl;lg.DFS();coute ndl;system(pause);system(cls);menu();break;case 5:coutthe TopoSort is:;lg.TopoSort(order);coute ndl;system(pause);system(cls);menu();break;case 6:cout请输入要查询最短路径的始点u和终点v: uv;lg.Betwee nMin Path(u,v);system(pause);system(cls);menu();break;case 7:printf(n 结束!n);brea

15、k;default:printf(n 请再次输入! n);system(cls);menu();break;coute ndl;system(pause);return 0;5、调试结果截图(以书本 P179图9-17a为例)(1)邻接矩阵数据结构下的图的遍历d:Progr-am FilesMicroseH Visual StudioProjsctMGraphDebuGraphrexe图的邻接矩阵示意0 888188CO018ooOOOOpo898881co180818888i08181OOooooSOOgg31co10(2 )输入路径(图的邻接表存储结构)(3 )图的遍历(4 )最短路径(5 )输入越界实验报告四、实验小结（包括问题和解决方法、心得体会、意见与建议等）（一）实验中遇到的主要问题及解决方法在用邻接矩阵存储结构实现图的广度优先遍历时，出现了输出结果为有序排列，改变图的顶点之间的关系后结果仍然不变， 经调试发现，实现广度优先遍历时使用的队列结构算法有问题。条件约束不当导致访问顶点的邻接点不能入队，从而不能实现广度优先遍历。修改