南邮数据结构上机实验三图的基本运算及飞机换乘次数最少问题

1、和3瑯唸/毀实验报告（2015/2016学年第二学期）课程名称数据结构A实验名称图的基本运算及飞机换乘次数最少问题实验时间2016年5月19日指导单位科学与技术系指导教师骆健学生姓名班级学号学生姓名班级学号学院（系）管理学院专业信息管理与信息系统(b)(b)模版类Graph,MGraph和LGraph实习题名：图的基本运算班级姓名学号日期2016.05.19一、问题描述验证教材中关于在邻接矩阵和邻接表两种不同的储存结构上实现图的基本运算的算法（见程序9.1程序9.8），在邻接矩阵存储结构上实现图的深度和广度优先遍历算法，设计主函数，测试上述运算。二、概要设计文件graph.cpp中在该文件中定

2、义图数据结构的抽象模板类Graph。邻接矩阵类MGraph是从抽象类Graph派生得来，邻接表类LGraph也是从抽象类Graph派生得来。主函数的代码如图所示。drfBff羽s-drfBff羽s-PA君%qT-riMKFl.h/-liT-2Lffl闕;.?-g：出制*3；：EE/帖|JjlUD諏E幻*EV：广-巴7.34/：弓口卄：萼科曲氏血矗E：:三、详细设计类和类的层次设计程序定义了Graph类，以及邻接矩阵类MGraph和邻接表类LGraph以及循环列表类SeqQueue。邻接矩阵类MGraph继承了Graph的数据成员n和e，重载了Graph的纯虚函数。保护数据成员T*a指向动态生成

3、的二维数组，用以存储邻接矩阵。邻接表类LGraph也继承了Graph的数据成员n和e及重载了Graph的纯虚函数，边结点由类ENode定义，每个结点有三个域adjVex、w和nextArc。邻接表的表头组成为一维数组，a是指向该数组的指针。TSeqQueue-intfront,rear;-intmaxSize;-BTNode*q;+SeqQueue(intmSize);+SeqQueue()deleteq;+boolIsEmpty()constreturnfront=rear;+boolIsFull()constreturn(rear+1)%maxSize=front;+boolFront(B

4、TNode*&x)const;+boolEnQueue(BTNode*x);+boolDeQueue();+voidClear()front=rear=0;(a)循环队列类TGraph#intn,e;+virtualResultCodeInsert(intu,intv,T&w)=0;+virtualResultCodeRemove(intu,intv)=0;+virtualboolExist(intu,intv)const=0;TTMGraphLGraph#T*a;#TnoEdge;#voidDFS(intv,bool*visited);#voidBFS(intv,bool*visited);

5、#ENode*a;+LGraph(intmSize);+LGraph();+ResultCodeInsert(intu,intv,T&w);+ResultCodeRemove(intu,intv);+boolExist(intu,intv)const;+MGraph(intmSize,constT&noedg);+MGraph();+ResultCodeInsert(intu,intv,T&w);+ResultCodeRemove(intu,intv);+boolExist(intu,intv)const;+voidDFS();+voidBFS();核心算法深度优先搜索用栈来实现：1）把根节点

6、压入栈中2）每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱3）找到所要找的元素时结束程序4）如果遍历整个树还没有找到，结束程序广度优先搜索使用队列来实现：1）把根节点放到队列的末尾2）每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱3）找到所要找的元素时结束程序4）如果遍历整个树还没有找到，结束程序DFS()四、程序代码templatevclassTvoidMGraphvT:DFS()深度遍历bool*visited=newbooln;for(inti=0;ivn;i+

7、)visitedi=false;for(i=0;in;i+)if(!visitedi)DFS(i,visited);deletevisited;templatevoidMGraph:DFS(intv,bool*visited)visitedv=true;coutvvv;for(inti=0;ivoidMGraphvT:BFS()广度遍历bool*visited=newbooln;for(inti=0;ivn;i+)visitedi=false;for(i=0;in;i+)if(!visitedi)BFS(i,visited);deletevisited;templatevoidMGraph:B

8、FS(intv,bool*visited)SeqQueuevintq(n);visitedv=true;coutvvv;q.EnQueue(v);while(!q.IsEmpty()q.Front(v);q.DeQueue();for(inti=0;in;i+)if(avi!=noEdge&avi!=0&!visitedi)visitedi=true;coutvvebugl.ee!输入边以及权值2)214-5输入边以及权值2)214-5&1?243-r5Ri13-cLk-rLTKftttfi“：J:“-.;厂.-.1.1.1.1-l-l-111!-llimlxlxlI-lrhjbIIc1:1宀

9、I.n+Jrrw-s3）得到图的深度遍历以及广度遍历4）输入要搜索的边，得到搜索结果5）输入要删除的边，得到新的遍历2.结果分析1）程序能够正确的实现关于在邻接矩阵和邻接表两种不同的储存结构上实现图的基本运算的算法，在邻接矩阵存储结构上实现图的深度和广度优先遍历算法2）由测试结果来看，若在输出数据时以图的形式输出，更简单直观，程序还有待改进。实习题名：飞机最少换乘问题班级姓名学号日期2016.05.19一、问题描述设有n个城市，编号为0n1,m条航线的起点和终点由用户输入提供。寻找一条换乘次数最少的线路方案。（提示：可以使用有向图表示城市间的航线。只要两城市间有航班，则图中这两点间存在一条权为

10、1的边。可以使用Dijkstra算法实现）二、概要设计文件min.cpp中定义了两个类，分别是图数据结构的抽象模板类Graph以及从抽象类Graph派生得来邻接矩阵类MGraph。主函数mian的代码如图所示：三、详细设计类和类的层次结构程序定义了Graph类，以及邻接矩阵类MGraph。同上邻接矩阵类MGraph也继承了Graph的数据成员n和e,重载了Graph的纯虚函数。保护数据成员T*a指向动态生成的二维数组，用以存储邻接矩阵。TGraph#intn,e;+virtualResultCodeInsert(intu,intv,T&w)=0;+virtualResultCodeRemove

11、(intu,intv)=0;+virtualboolExist(intu,intv)const=0;TMGraph#T*a;#TnoEdge;#voidDFS(intv,bool*visited);#voidBFS(intv,bool*visited);_+MGraph(intmSize,constT&noedg);+MGraph();+ResultCodeInsert(intu,intv,T&w);+ResultCodeRemove(intu,intv);+boolExist(intu,intv)const;+voidDFS();+voidBFS();模版类Graph和MGraph2.核心算

12、法定义了类之后，求换乘次数最少主要是通过迪杰斯特拉算法实现。迪杰斯特拉算法主要通过动态创建数据结构，初始化操作，将源点v加入集合S,使用for循环，按照长度的非递减次序，依次产生n-1条最短路径等步骤实现。核心算法程图如下：Dijkstra()四、程序代码迪杰斯特拉算法templatevclassT迪杰斯特拉算法voidMGraphvT:Dijkstra(intv,T*d,int*path)inti,k,w;if(vvOllvn-l)throwOutOfBounds;bool*s=newbooln;for(i=0;ivn;i+)si=false;di=avi;if(i!=v&divINF)pa

13、thi=v;elsepathi=-1;sv=true;dv=0;for(i=1;in;i+)k=Choose(d,s);sk=true;for(w=0;wconstintINFTY=2147483640;enumResultCodeUnderflow,Duplicate,Failure,Success,NotPresent;templateclassGraph抽象类public:virtualResultCodeInsert(intu,intv,T&w)=0;virtualResultCodeRemove(intu,intv)=0;virtualboolExist(intu,intv)cons

14、t=0;protected:intn,e;templatevclassT循环队列类classSeqQueuepublic:SeqQueue(intmSize);SeqQueue()deleteq;boolIsEmpty()constreturnfront=rear;boolIsFull()constreturn(rear+1)%maxSize=front;boolFront(T&x)const;boolEnQueue(Tx);boolDeQueue();voidClear()front=rear=0;private:intfront,rear;intmaxSize;T*q;templatevc

15、lassTSeqQueue:SeqQueue(intmSize)构造函数maxSize=mSize;q=newTmaxSize;front=rear=0;templatevclassTboolSeqQueuevT:Front(T&x)const取队头元素if(IsEmpty()returnfalse;x=q(front+l)%maxSize;returntrue;templatevclassTboolSeqQueuevT:EnQueue(Tx)在队尾插入xif(IsFull()coutvvFullvvendl;returnfalse;qrear=(rear+1)%maxSize=x;retur

16、ntrue;templatevclassTboolSeqQueuevT:DeQueue()删除队头元素if(IsEmpty()coutvvUnderflowvvendl;returnfalse;front=(front+1)%maxSize;returntrue;templatevclassTclassMGraph:publicGraphvT邻接矩阵类public:MGraph(intmSize,constT&noedg);MGraph();ResultCodeInsert(intu,intv,T&w);ResultCodeRemove(intu,intv);boolExist(intu,in

17、tv)const;voidDFS();voidBFS();protected:T*a;TnoEdge;voidDFS(intv,bool*visited);voidBFS(intv,bool*visited);templatevclassTMGraphvT:MGraph(intmSize,constT&noedg)n=mSize;e=0;noEdge=noedg;a=newT*n;for(inti=0;ivn;i+)ai=newTn;for(intj=0;jvn;j+)aij=noEdge;aii=0;templateMGraph:MGraph()析构函数for(inti=0;in;i+)de

18、leteai;deletea;templateResultCodeMGraph:Insert(intu,intv,T&w)if(uvOllvvOllun-lllvn-lllu=v)returnFailure;if(auv!=noEdge)returnDuplicate;auv=w;e+;returnSuccess;templateResultCodeMGraph:Remove(intu,intv)if(uv0llvv0llun-1llvn-1llu=v)returnFailure;if(auv=noEdge)returnNotPresent;auv=noEdge;e-;returnSucces

19、s;构造函数插入函数删除函数templatevclassTboolMGraphvT:Exist(intu,intv)const判断边是否存在if(uvOllvvOllun-lllvn-lllu=vllauv=noEdge)returnfalse;returntrue;templatevoidMGraphvT:DFS()深度遍历bool*visited=newbooln;for(inti=0;ivn;i+)visitedi=false;for(i=0;in;i+)if(!visitedi)DFS(i,visited);deletevisited;templatevoidMGraph:DFS(in

20、tv,bool*visited)visitedv=true;coutvvv;for(inti=0;in;i+)if(avi!=noEdge&avi!=0&!visitedi)DFS(i,visited);templatevoidMGraph:BFS()广度遍历bool*visited=newbooln;for(inti=0;in;i+)visitedi=false;for(i=0;in;i+)if(!visitedi)BFS(i,visited);deletevisited;templatevoidMGraph:BFS(intv,bool*visited)SeqQueuevintq(n);vi

21、sitedv=true;coutvvvvv;q.EnQueue(v);while(!q.IsEmpty()q.Front(v);q.DeQueue();for(inti=0;ivn;i+)if(avi!=noEdge&avi!=0&!visitedi)visitedi=true;coutvv/结点类classENodepublic:ENode()nextArc=NULL;ENode(intvertex,Tweight,ENode*next)adjVex=vertex;w=weight;nextArc=next;intadjVex;Tw;ENode*nextArc;templatevclassT

22、classLGraph:publicGraphvT邻接表类public:LGraph(intmSize);LGraph();ResultCodeInsert(intu,intv,T&w);ResultCodeRemove(intu,intv);boolExist(intu,intv)const;protected:ENodevT*a;templatevclassTLGraphvT:LGraph(intmSize)构造函数n=mSize;e=0;a=newENodevT*n;for(inti=O;ivn;i+)ai=NULL;templatevclassTLGraphvT:LGraph()析构E

23、NodevT*p,*q;for(inti=0;inextArc;deleteq;q=p;deletea;templateboolLGraph:Exist(intu,intv)const判断边是否存在if(uvOllvvOllun-lllvn-lllu=v)returnfalse;ENode*p=au;while(p&p-adjVex!=v)p=p-nextArc;if(!p)returnfalse;elsereturntrue;templateResultCodeLGraph:Insert(intu,intv,T&w)插入if(uv0llvv0llun-1llvn-1llu=v)returnF

24、ailure;if(Exist(u,v)returnDuplicate;ENode*p=newENode(v,w,au);au=p;e+;returnSuccess;删除templatevclassT删除ResultCodeLGraphvT:Remove(intu,intv)if(uvOllvvOllun-lllvn-lllu=v)returnFailure;ENodevT*p=au,*q;q=NULL;while(p&p-adjVex!=v)q=p;p=p-nextArc;if(!p)returnNotPresent;if(q)q-nextArc=p-nextArc;elseau=p-nex

25、tArc;deletep;e-;returnSuccess;intmain()主函数intn,g;coutvv请输入元素的个数:;cinn;MGraphvintA(n,INFTY);LGraphB(n);coutvv请输入边的条数:;cing;int*a=newintg;int*b=newintg;int*w=newintg;for(inti=0;ivg;i+)coutvv请输入边及权值:;cinaibiwi;Insert(ai,bi,wi);Insert(ai,bi,wi);coutvv该图的深度优先遍历为:vvendl;A.DFS();coutvvendl;coutvv该图的广度优先遍历为

26、:vvendl;A.BFS();coutvvendl;coutvv请输入要搜索的边:;intc,d;cincd;if(A.Exist(c,d)coutvv邻接矩阵中该边存在!vvendl;elsecoutvv邻接矩阵中该边不存在!vvendl;if(B.Exist(c,d)coutvv邻接表中该边存在!vvendl;elsecoutvv邻接表中该边不存在!vvendl;coutvv请输入要删除的边:;inte,f;cinef;if(A.Remove(e,f)=Success)coutvv邻接矩阵中删除该边成功!vvendl;elseif(A.Remove(e,f)=NotPresent)cou

27、tvv邻接矩阵中该边不存在!vvendl;elsecoutvv输入错误!vvendl;if(B.Remove(e,f)=Success)coutvv邻接表中删除该边成功!vvendl;elseif(B.Remove(e,f)=NotPresent)coutvv邻接表中该边不存在!vvendl;elsecoutvv邻接表中输入错误!vvendl;coutvv删除该边后该图的深度优先遍历为:vvendl;A.DFS();coutvvendl;coutvv删除该边后该图的广度优先遍历为:vvendl;A.BFS();coutvvendl;return0;2.飞机换乘次数最少问题#includevio

28、stream.h#includevstring.hconstintINF=2147483647;enumResultCodeUnderflow,Duplicate,Failure,Success,NotPresent,OutOfBounds;templateclassGraph抽象类public:virtualResultCodeInsert(intu,intv,Tw)=0;virtualResultCodeRemove(intu,intv)=0;virtualboolExist(intu,intv)const=0;protected:intn,e;templateclassMGraph:pu

29、blicGraphvT邻接矩阵类public:MGraph(intmSize,constTnoedg);MGraph();ResultCodeInsert(intu,intv,Tw);ResultCodeRemove(intu,intv);boolExist(intu,intv)const;intChoose(int*d,bool*s);voidDijkstra(intv,T*d,int*path);protected:T*a;TnoEdge;templateMGraph:MGraph(intmSize,constTnoedg)n=mSize;e=0;noEdge=noedg;a=newT*n

30、;for(inti=0;ivn;i+)ai=newTn;for(intj=0;jn;j+)aij=noEdge;aii=0;templateMGraph:MGraph()for(inti=O;ivn;i+)deleteai;deletea;templatevclassTResultCodeMGraphvT:Insert(intu,intv,Tw)if(uvOllvvOllun-lllvn-lllu=v)returnFailure;if(auv!=noEdge)returnDuplicate;auv=w;e+;returnSuccess;templateResultCodeMGraph:Remove(intu,intv)if(uv0llvv0llun-1llvn-1llu=v)returnFailure;if(auv=noEdge)returnNotPresent;auv=noEdge;e-;returnSuccess;templatevclassTboolMGraphvT:Exist(intu,intv)constif(uv0llvv0llun-1llvn-1llu=vllauv=