数据结构实验七

实验报告（2014/2015学年第一学期）课程名称数据结构——使用C++语言描述实验名称图的基本运算及飞机换乘次数最少问题实验时间2014年12月3日指导单位计算机科学与技术系指导教师学生姓名班级学号学院(系)专业实验报告2实验名称图的基本运算及飞机换乘次数最少问题指导教师实验类型上机实验学时4实验时间2014年12月3日一、实验目的和要求1.验证在邻接矩阵和邻接表实现图的基本运算的算法；在邻接矩阵存储结构上实现图的深度和宽度优先遍历算法。2.设有n个城市，编号为0～n−1，m条航线的起点和终点由用户输入提供。寻找一条换乘次数最少的线路方案。提示：可以使用有向图表示城市间的航线。只要两城市间有航班，则图中这两点间存在一条权为1的边。可以使用Dijkstra算法实现。思考：如果是城市公交车的最少换乘问题，将如何解决？假如希望使用类似的算法，则图中的边如何设置？二、实验环境(实验设备)Vs2013win8.1实验原理及内容:实验一：1）掌握在图的邻接矩阵和邻接表存储结构实现图的基本运算的算法2）学习使用图算法解决应用问题的方法邻接矩阵的遍历与邻接表的遍历类似，都是通过递归来实现。以下是代码：voidExtMGraphT::DFS(){bool*visited=newbool[n];for(inti=0;in;i++)visited[i]=false;for(i=0;in;i++){if(!visited[i]){DFS(i,visited);coutendl;}}3delete[]visited;}templateclassTvoidExtMGraphT::DFS(intv,bool*visited){visited[v]=true;coutv;for(intu=0;un;u++)if(a[v][u]!=noEdge&&!visited[u])DFS(u,visited);}templateclassTvoidExtMGraphT::BFS(){bool*visited=newbool[n];for(inti=0;in;i++)visited[i]=false;for(inti=0;in;i++){if(!visited[i]){BFS(i,visited);}}delete[]visited;}templateclassTvoidExtMGraphT::BFS(intv,bool*visited){SeqQueueintq(Vertices());visited[v]=true;coutv;q.EnQueue(v);while(!q.IsEmpty()){q.Front(v);q.DeQueue();for(inti=0;in;i++)if(!visited[i]&&a[v][i]!=noEdge)4{visited[i]=true;couti;q.EnQueue(i);}}}在主函数中只要添加该代码：#include”extMGraph.h”voidmain(){intweight=3;intnoEdge=1000;intk=1;intl=2;ExtMGraphintextMGraph2(8,noEdge);extMGraph2.Insert(1,2,k);extMGraph2.Insert(1,4,k);extMGraph2.Insert(2,3,k);extMGraph2.Insert(4,3,k);extMGraph2.Insert(4,5,k);extMGraph2.Insert(3,6,k);extMGraph2.Insert(5,7,k);extMGraph2.Insert(6,7,k);extMGraph2.DFS();extMGraph2.BFS();}实验二：飞机的换乘问题。具体实现代码:Graph.h:#includeiostreamusingnamespacestd;enumResultCode{Underflow,Overflow,Success,Duplicate,NotPresent};voidshowResultCode(ResultCoderesult){intr=(int)result;switch(result){case0:coutResultCode:Underflowendl;break;case1:coutResultCode:Overflowendl;break;case2:coutResultCode:Successendl;break;case3:coutResultCode:Duplicateendl;break;case4:coutResultCode:NotPresentendl;break;default:coutExceptionoccured:unknownresultcodeendl;5}}templateclassTclassGraph{public:virtualResultCodeInsert(intu,intv,T&w)=0;virtualResultCodeRemove(intu,intv)=0;virtualboolExist(intu,intv)const=0;virtualintVerticles()const{returnn;}protected:intn,e;//e为边数};MGraph.h:#includeGraph.htemplateclassTclassMGraph:publicGraphT{public:MGraph(intmSize,constT&noedg);~MGraph();ResultCodeInsert(intu,intv,T&w);ResultCodeRemove(intu,intv);boolExist(intu,intv)const;protected:T**a;TnoEdge;};templateclassTMGraphT::MGraph(intmSize,constT&noedg){n=mSize;e=0;noEdge=noedg;a=newT*[n];for(inti=0;in;i++){a[i]=newT[n];for(intj=0;jn;j++){a[i][j]=noEdge;}a[i][i]=0;}}templateclassTMGraphT::~MGraph(){for(inti=0;in;i++)delete[]a[i];6delete[]a;}templateclassTboolMGraphT::Exist(intu,intv)const{if(u0||v0||un-1||vn-1||u==v||a[u][v]==noEdge)returnfalse;returntrue;}templateclassTResultCodeMGraphT::Insert(intu,intv,T&w){if(u0||v0||un-1||u==v)returnOverflow;if(a[u][v]!=noEdge)returnDuplicate;a[u][v]=w;e++;returnSuccess;}templateclassTResultCodeMGraphT::Remove(intu,intv){if(u0||v0||un-1||u==v)returnOverflow;if(a[u][v]==noEdge)returnNotPresent;a[u][v]=noEdge;e--;returnSuccess;}extMGraph.h:#includeMGraph.h#includeSeqQueue.h#defineINFTY10000templateclassTclassExtMGraph:publicMGraphT{public:ExtMGraph(intmSize,constT&noedg):MGraphT(mSize,noedg){}voidDFS();voidBFS();intChoose(int*d,bool*s);voidDijkstra(intv,T*d,int*path);voidShowDijkstra(intv,intflag);voidFloyd(T**d,int**path);intVertices(){returnn;}private:voidDFS(intv,bool*visited);voidBFS(intv,bool*visited);};7templateclassTvoidExtMGraphT::DFS(){bool*visited=newbool[n];for(inti=0;in;i++)visited[i]=false;for(i=0;in;i++){if(!visited[i]){DFS(i,visited);coutendl;}}delete[]visited;}templateclassTvoidExtMGraphT::DFS(intv,bool*visited){visited[v]=true;coutv;for(intu=0;un;u++)if(a[v][u]!=noEdge&&!visited[u])DFS(u,visited);}templateclassTvoidExtMGraphT::BFS(){bool*visited=newbool[n];for(inti=0;in;i++)visited[i]=false;for(inti=0;in;i++){if(!visited[i]){BFS(i,visited);}}delete[]visited;8}templateclassTvoidExtMGraphT::BFS(intv,bool*visited){SeqQueueintq(Vertices());visited[v]=true;coutv;q.EnQueue(v);while(!q.IsEmpty()){q.Front(v);q.DeQueue();for(inti=0;in;i++)if(!visited[i]&&a[v][i]!=noEdge){visited[i]=true;couti;q.EnQueue(i);}}}templateclassTintExtMGraphT::Choose(int*d,bool*s){inti,minpos;Tmin;min=INFTY;minpos=-1;for(i=0;in;i++)if(d[i]min&&!s[i]){min=d[i];minpos=i;}returnminpos;}templateclassTvoidExtMGraphT::Dijkstra(intv,T*d,int*path){inti,k,w;if(v0||vn-1)9{coutoutofbounds!endl;return;}bool*s=newbool[n];for(i=0;in;i++){s[i]=false;d[i]=a[v][i];if(i!=v&&d[i]INFTY)path[i]=v;elsepath[i]=-1;}s[v]=true;d[v]=0;for(i=0;in-1;i++){k=Choose(d,s);s[k]=true;for(w=0;wn;w++)if(!s[w]&&d[k]+a[k][w]d[w]){d[w]=d[k]+a[k][w];path[w]=k;}}}templateclassTvoidExtMGraphT::ShowDijkstra(intv,intflag){T*d=newT[n];int*path=newint[n];inttemp;Dijks