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

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

2、类MGraph是从抽象类Graph派生得来，邻接表类LGraph也是从抽象类Graph派生得来。主函数的代码如图所示。三、 详细设计1. 类和类的层次设计程序定义了Graph类，以及邻接矩阵类MGraph和邻接表类LGraph以及循环列表类SeqQueue。邻接矩阵类MGraph继承了Graph的数据成员n和e，重载了Graph的纯虚函数。保护数据成员T* a指向动态生成的二维数组，用以存储邻接矩阵。邻接表类LGraph也继承了Graph的数据成员n和e及重载了Graph的纯虚函数，边结点由类ENode定义，每个结点有三个域adjVex、w和nextArc。邻接表的表头组成为一维数组，a是指向

3、该数组的指针。TSeqQueue-int front, rear;-int maxSize;-BTNode<T> *q;+SeqQueue(int mSize);+SeqQueue()delete q;+bool IsEmpty() constreturn front = rear;+bool IsFull() constreturn (rear + 1) % maxSize = front;+bool Front(BTNode<T> *&x)const;+bool EnQueue(BTNode<T> *x);+bool DeQueue();+voi

4、d Clear()front = rear = 0;（a）循环队列类MGraph#T *a;#T noEdge;#void DFS(int v,bool *visited);#void BFS(int v,bool *visited);+MGraph(int mSize,const T& noedg);+MGraph();+ResultCode Insert(int u,int v,T&w);+ResultCode Remove(int u,int v);+bool Exist(int u,int v)const;+void DFS();+void BFS();TLGraph#

5、ENode<T> *a;+LGraph(int mSize);+LGraph();+ResultCode Insert(int u,int v,T&w);+ResultCode Remove(int u,int v);+bool Exist(int u,int v)const;TGraph#int n,e;+virtual ResultCode Insert(int u,int v,T&w)=0;+virtual ResultCode Remove(int u,int v)=0;+virtual bool Exist(int u,int v)const=0;T（b）

6、模版类Graph， MGraph和LGraph2. 核心算法深度优先搜索用栈来实现：1) 把根节点压入栈中2) 每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱3) 找到所要找的元素时结束程序4) 如果遍历整个树还没有找到，结束程序广度优先搜索使用队列来实现：1) 把根节点放到队列的末尾2) 每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱3) 找到所要找的元素时结束程序4) 如果遍历整个树还没有找到，结束程序DFS()BFS()四、程序代码template <cl

7、ass T>void MGraph<T>:DFS() /深度遍历bool *visited=new booln;for (int i=0;i<n;i+)visitedi=false;for(i=0;i<n;i+)if(!visitedi)DFS(i,visited);deletevisited;template <class T>void MGraph<T>:DFS(int v,bool *visited)visitedv=true;cout<<" "<<v;for(int i=0;i<n;

8、i+)if(avi!=noEdge&&avi!=0&&!visitedi)DFS(i,visited);template <class T>void MGraph<T>:BFS() /广度遍历bool *visited=new booln;for (int i=0;i<n;i+)visitedi=false;for(i=0;i<n;i+)if(!visitedi)BFS(i,visited);deletevisited;template <class T>void MGraph<T>:BFS(int v

9、,bool *visited)SeqQueue<int> q(n);visitedv=true;cout<<" "<<v;q.EnQueue(v);while(!q.IsEmpty()q.Front(v);q.DeQueue(); for(int i=0;i<n;i+) if(avi!=noEdge&&avi!=0&&!visitedi) visitedi=true; cout<<" "<<i; q.EnQueue(i);五、测试和调试1. 测试用例和结果测

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

11、表示城市间的航线。只要两城市间有航班，则图中这两点间存在一条权为1的边。可以使用Dijkstra算法实现）二、 概要设计文件min.cpp中定义了两个类,分别是图数据结构的抽象模板类Graph以及从抽象类Graph派生得来邻接矩阵类MGraph。主函数mian的代码如图所示：三、 详细设计1. 类和类的层次结构程序定义了Graph类，以及邻接矩阵类MGraph。同上邻接矩阵类MGraph也继承了Graph的数据成员n和e，重载了Graph的纯虚函数。保护数据成员T* a指向动态生成的二维数组，用以存储邻接矩阵。MGraph#T *a;#T noEdge;#void DFS(int v,bool

12、 *visited);#void BFS(int v,bool *visited);+MGraph(int mSize,const T& noedg);+MGraph();+ResultCode Insert(int u,int v,T&w);+ResultCode Remove(int u,int v);+bool Exist(int u,int v)const;+void DFS();+void BFS();TGraph#int n,e;+virtual ResultCode Insert(int u,int v,T&w)=0;+virtual ResultCode

13、 Remove(int u,int v)=0;+virtual bool Exist(int u,int v)const=0;T模版类Graph和 MGraph 2. 核心算法定义了类之后，求换乘次数最少主要是通过迪杰斯特拉算法实现。 迪杰斯特拉算法主要通过动态创建数据结构，初始化操作，将源点v加入集合S，使用for循环，按照长度的非递减次序，依次产生n-1条最短路径等步骤实现。核心算法程图如下：Dijkstra ()四、 程序代码template <class T>void MGraph<T>:Dijkstra(int v,T *d,int *path) /迪杰斯特拉

14、算法int i,k,w;if(v<0|v>n-1)throw OutOfBounds;bool *s=new booln;for(i=0;i<n;i+)si=false;di=avi;if(i!=v&&di<INF)pathi=v;elsepathi=-1;sv=true;dv=0;for(i=1;i<n;i+)k=Choose(d,s);sk=true;for(w=0;w<n;w+)if(!sw&&(dk+akw)<dw)dw=dk+akw;pathw=k;五、 测试和调试1. 测试用例和结果1) 输入城市个数以及航线

15、条数2) 分别输入每条航线的起点和终点3) 得到换乘次数最小的路线4) 最后输入N退出2. 结果分析1) 程序能够完全实现题目的要求，通过迪杰斯特拉算法实现了飞机换乘次数最小的路线2) 下一步的目标是使用类似的算法对城市公交车的最少换乘问题进行解决实习小结在本次实验中出现了一些问题在用邻接矩阵存储结构实现图的广度优先遍历时，出现了输出结果为有序排列，改变图的顶点之间的关系后结果仍然不变，修改约束条件后，问题得以解决。在用邻接表存储结构实现Djikstra算法时，出现了指针访问冲突的问题，经调试检查发现是由访问数组越界导致，修改了约束条件后问题得以解决。本次实验主要是要求在邻接表存储结构上实现图

16、的深度优先遍历以及广度优先遍历和使用Djikstra算法求单源最短路径的问题。经过本次实验对图的不同存储结构适用情况有了更进一步认识，通过修改Djikstra算法使其实现在图的邻接表存储结构上求最短路径，进一步加深对该算法的理解。通过这次实验我对图这种应用广泛的数据结构更加熟悉，结合课堂知识，以及老师的帮助，让我学到了更多。 附录：1. 图的基本运算#include<iostream.h>const int INFTY=2147483640;enum ResultCodeUnderflow,Duplicate,Failure,Success,NotPresent;template

17、<class T>class Graph /抽象类public:virtual ResultCode Insert(int u,int v,T&w)=0;virtual ResultCode Remove(int u,int v)=0;virtual bool Exist(int u,int v)const=0;protected:int n,e;template<class T> /循环队列类class SeqQueuepublic:SeqQueue(int mSize);SeqQueue()delete q;bool IsEmpty() constretur

18、n front=rear;bool IsFull() constreturn (rear+1)%maxSize=front;bool Front(T &x)const;bool EnQueue(T x);bool DeQueue();void Clear()front=rear=0;private:int front,rear;int maxSize;T *q;template<class T>SeqQueue<T>:SeqQueue(int mSize) /构造函数maxSize=mSize;q=new TmaxSize;front=rear=0;templa

19、te<class T>bool SeqQueue<T>:Front(T &x)const /取队头元素if(IsEmpty()return false;x=q(front+1)%maxSize;return true;template<class T>bool SeqQueue<T>:EnQueue(T x) /在队尾插入xif(IsFull()cout<<"Full"<<endl;return false;qrear=(rear+1)%maxSize=x;return true;templat

20、e<class T>bool SeqQueue<T>:DeQueue() /删除队头元素if(IsEmpty()cout<<"Underflow"<<endl;return false;front=(front+1)%maxSize;return true;template <class T>class MGraph:public Graph<T> /邻接矩阵类public:MGraph(int mSize,const T& noedg);MGraph();ResultCode Insert(i

21、nt u,int v,T&w); ResultCode Remove(int u,int v);bool Exist(int u,int v)const;void DFS();void BFS();protected:T *a;T noEdge;void DFS(int v,bool *visited);void BFS(int v,bool *visited);template <class T>MGraph<T>:MGraph(int mSize,const T&noedg) /构造函数n=mSize;e=0;noEdge=noedg;a=new T

22、*n;for(int i=0;i<n;i+)ai=new Tn;for(int j=0;j<n;j+)aij=noEdge;aii=0;template <class T>MGraph<T>:MGraph() /析构函数for(int i=0;i<n;i+)delete ai;delete a;template <class T>ResultCode MGraph<T>:Insert(int u,int v,T&w) /插入函数if(u<0|v<0|u>n-1|v>n-1|u=v)return F

23、ailure;if(auv!=noEdge)return Duplicate;auv=w;e+;return Success;template <class T>ResultCode MGraph<T>:Remove(int u,int v) /删除函数if(u<0|v<0|u>n-1|v>n-1|u=v)return Failure;if(auv=noEdge)return NotPresent;auv=noEdge;e-;return Success;template<class T>bool MGraph<T>:Ex

24、ist(int u,int v)const /判断边是否存在if(u<0|v<0|u>n-1|v>n-1|u=v|auv=noEdge)return false;return true;template <class T>void MGraph<T>:DFS() /深度遍历bool *visited=new booln;for (int i=0;i<n;i+)visitedi=false;for(i=0;i<n;i+)if(!visitedi)DFS(i,visited);deletevisited;template <clas

25、s T>void MGraph<T>:DFS(int v,bool *visited)visitedv=true;cout<<" "<<v;for(int i=0;i<n;i+)if(avi!=noEdge&&avi!=0&&!visitedi)DFS(i,visited);template <class T>void MGraph<T>:BFS() /广度遍历bool *visited=new booln;for (int i=0;i<n;i+)visitedi=

26、false;for(i=0;i<n;i+)if(!visitedi)BFS(i,visited);deletevisited;template <class T>void MGraph<T>:BFS(int v,bool *visited)SeqQueue<int> q(n);visitedv=true;cout<<" "<<v;q.EnQueue(v);while(!q.IsEmpty()q.Front(v);q.DeQueue(); for(int i=0;i<n;i+) if(avi!=noEdg

27、e&&avi!=0&&!visitedi) visitedi=true; cout<<" "<<i; q.EnQueue(i);template<class T> /结点类class ENodepublic:ENode() nextArc=NULL;ENode(int vertex,T weight,ENode *next)adjVex=vertex;w=weight;nextArc=next;int adjVex;T w;ENode * nextArc;template <class T>cl

28、ass LGraph:public Graph<T> /邻接表类public:LGraph(int mSize);LGraph();ResultCode Insert(int u,int v,T&w); ResultCode Remove(int u,int v);bool Exist(int u,int v)const;protected:ENode<T> *a;template <class T>LGraph<T>:LGraph(int mSize) /构造函数n=mSize;e=0;a=new ENode<T> *n;f

29、or(int i=0;i<n;i+)ai=NULL;template <class T>LGraph<T>:LGraph() /析构ENode<T> *p,*q;for(int i=0;i<n;i+)p=ai;q=p;while(p)p=p->nextArc;delete q;q=p;delete a;template <class T>bool LGraph<T>:Exist(int u,int v)const /判断边是否存在if(u<0|v<0|u>n-1|v>n-1|u=v)retur

30、n false; ENode<T>*p=au;while(p&&p->adjVex!=v)p=p->nextArc;if(!p)return false;else return true;template <class T>ResultCode LGraph<T>:Insert(int u,int v,T&w) /插入if(u<0|v<0|u>n-1|v>n-1|u=v)return Failure;if(Exist(u,v)return Duplicate;ENode<T>*p=new

31、 ENode<T>(v,w,au);au=p;e+;return Success;template <class T>ResultCode LGraph<T>:Remove(int u,int v) /删除if(u<0|v<0|u>n-1|v>n-1|u=v)return Failure;ENode<T> *p=au,*q;q=NULL;while(p&&p->adjVex!=v)q=p;p=p->nextArc;if(!p)return NotPresent;if(q)q->nextAr

32、c=p->nextArc;elseau=p->nextArc;delete p;e-;return Success;int main() /主函数int n,g;cout<<"请输入元素的个数: "cin>>n;MGraph<int>A(n,INFTY);LGraph<int>B(n);cout<<"请输入边的条数: "cin>>g;int *a=new intg;int *b=new intg;int *w=new intg;for(int i=0;i<g;i+)

33、cout<<"请输入边及权值: "cin>>ai>>bi>>wi;A.Insert(ai,bi,wi);B.Insert(ai,bi,wi);cout<<"该图的深度优先遍历为:"<<endl;A.DFS();cout<<endl;cout<<"该图的广度优先遍历为:"<<endl;A.BFS();cout<<endl;cout<<"请输入要搜索的边: "int c,d;cin>

34、>c>>d;if(A.Exist(c,d)cout<<"邻接矩阵中该边存在!"<<endl;else cout<<"邻接矩阵中该边不存在!"<<endl;if(B.Exist(c,d)cout<<"邻接表中该边存在!"<<endl;else cout<<"邻接表中该边不存在!"<<endl;cout<<"请输入要删除的边: "int e,f;cin>>e>

35、;>f;if(A.Remove(e,f)=Success)cout<<"邻接矩阵中删除该边成功!"<<endl;else if(A.Remove(e,f)=NotPresent)cout<<"邻接矩阵中该边不存在!"<<endl;elsecout<<"输入错误!"<<endl;if(B.Remove(e,f)=Success)cout<<"邻接表中删除该边成功!"<<endl;else if(B.Remove(e,

36、f)=NotPresent)cout<<"邻接表中该边不存在!"<<endl;elsecout<<"邻接表中输入错误!"<<endl;cout<<"删除该边后该图的深度优先遍历为:"<<endl;A.DFS();cout<<endl;cout<<"删除该边后该图的广度优先遍历为:"<<endl;A.BFS();cout<<endl;return 0;2. 飞机换乘次数最少问题#include<

37、;iostream.h>#include<string.h>const int INF=2147483647;enum ResultCodeUnderflow,Duplicate,Failure,Success,NotPresent,OutOfBounds;template <class T>class Graph /抽象类public:virtual ResultCode Insert(int u,int v,T w)=0;virtual ResultCode Remove(int u,int v)=0;virtual bool Exist(int u,int

38、v)const=0;protected:int n,e;template <class T>class MGraph:public Graph<T> /邻接矩阵类public:MGraph(int mSize,const T noedg);MGraph();ResultCode Insert(int u,int v,T w); ResultCode Remove(int u,int v);bool Exist(int u,int v)const;int Choose(int *d,bool *s);void Dijkstra(int v,T *d,int *path);

39、protected:T *a;T noEdge;template <class T>MGraph<T>:MGraph(int mSize,const T noedg)n=mSize;e=0;noEdge=noedg;a=new T*n;for(int i=0;i<n;i+)ai=new Tn;for(int j=0;j<n;j+)aij=noEdge;aii=0;template <class T>MGraph<T>:MGraph()for(int i=0;i<n;i+)delete ai;delete a;template &

40、lt;class T>ResultCode MGraph<T>:Insert(int u,int v,T w)if(u<0|v<0|u>n-1|v>n-1|u=v)return Failure;if(auv!=noEdge)return Duplicate;auv=w;e+;return Success;template <class T>ResultCode MGraph<T>:Remove(int u,int v)if(u<0|v<0|u>n-1|v>n-1|u=v)return Failure;if

41、(auv=noEdge)return NotPresent;auv=noEdge;e-;return Success;template<class T>bool MGraph<T>:Exist(int u,int v)constif(u<0|v<0|u>n-1|v>n-1|u=v|auv=noEdge)return false;return true;template <class T>int MGraph<T>:Choose(int *d,bool *s) /求最小diint i,minpos;T min;min=INF

42、;minpos=-1;for(i=0;i<n;i+)if(di<=min&&!si)min=di;minpos=i;return minpos;template <class T>void MGraph<T>:Dijkstra(int v,T *d,int *path) /迪杰斯特拉算法int i,k,w;if(v<0|v>n-1)throw OutOfBounds;bool *s=new booln;for(i=0;i<n;i+)si=false;di=avi;if(i!=v&&di<INF)pathi=v;elsepathi=-1;sv=true;