数据结构课程设计C++图邻接矩阵-邻接表的建立-课程设计.doc

数据结构课程设计C+图邻接矩阵-邻接表的建立-课程设计数据结构课程设计C+图邻接矩阵-邻接表的建立|数据结构课程设计一.需求分析1.运行环境硬件：计算机486/64M以上操作系统：WIN9x以上/WIN2000/WINXP/WINME相关软件：vistualC+2程序所实现的功能：（1）建立并显示图的邻接表。（2）深度优先遍历，显示遍历结果。（3）对该图进行拓扑排序，显示排序结果。（4）给出某一确定顶点到所有其它顶点的最短路径。3.程序的输入，包含输入的数据格式和说明(1)输入顶点数,及各顶点信息(数据格式为整形)(2)输入边数,及权值(数据格式为整形)4.程序的输出，程序输出的形式(1)输出图的邻接表、深度优先遍历结果、拓扑排序结果。(2)输入某一确定顶点到其它所有顶点的最短路径。5.测试数据二、设计说明1、算法设计的思想建立图类，建立相关成员函数。最后在主函数中实现。具体成员函数的实现请参看源程序。 2、主要的数据结构设计说明图邻接矩阵、邻接表的建立。图的深度优先遍历、拓扑排序、顶点之间的最短路径。3、程序的主要模板templateclassGraph4、程序的主要函数Graph、link()、DFTraverse()、TopologicalOrder()、TopologicalOrder()、GetVertexPos()、ShortestPath三、上机结果及体会1、实际完成的情况说明主要程序参考教材数据结构C+版。2、程序的性能分析可连续建图3、上机过程中出现的问题及其解决方案。编译没有错误，但结果有问题。解决方案：虽然程序的编译通过，只能说明语法上没有问题，结果只所以不正确是因为算法上原因。4、程序中可以改进的地方说明程序中的深度优先遍历，浪费空间较大，可以考虑用循环来做。但这样将付出代码长度度加长的代价。5、程序中可以扩充的功能及设计实现假想实现假想：随用户的输入可以随时动态的显示图的生成。6、收获及体会编写程序即是一件艰苦的工作，又是一件愉快的事情。最大的收获：编程时如果遇到看似简单但又无法解决的问题，很容易灰心丧气。此时切不可烦躁，一定要冷静的思考，认真的分析。要勇敢的面对问题，勇敢的接受问题，勇敢的处理问题，最后最勇敢的解决问题。四、参考文献数据结构（C+版）叶核亚主编机械工业出版社数据结构经典算法实现与习题解答汪杰编著人民邮电出版社数据结构课程设计苏仕华编著机械工业出版社数据结构程序设计题典李春葆编著清华大学出版社数据结构课程与题解（用C/C+描述）胡圣荣编著北京大学出版社程序运行流程图charop/程序控制变量If(op=Y|op=y)if(op=N|op=n)/本程序是邻接矩阵，邻接表的利用，共有4项功能,分别是：/(1)建立并显示图的邻接表。/(2)以非递归方式进行深度优先遍历，显示遍历结果。/(3)对该图进行拓扑排序，显示排序结果。/(4)给出某一确定顶点到所有其它顶点的最短路径。#includeusingnamespacestd;constintMaxVertexes=20;/最大的顶点数constintb=10000;templateclassGraph;structArcNode/定义边结点friendclassGraph;intadjvex;/和边（或弧）相关联的另一个顶点序号intweight;/边（或弧）上的信息ArcNode*nextarc;/指向下一条边结点的指针ArcNode(intv,intw):adjvex(v),weight(w),nextarc(NULL);/构造函数templatestructVertexNode/定义顶点结点friendclassGraph;Typedata;/顶点的信息ArcNode*firstarc;/指向依附该顶点的边链表;templateclassGraphVertexNode*VTable;/顶点表intCurrentNumVertexes;/当前的顶点数intCurrentNumArcs;/当前的边（或弧）数public:intGetVertexPos(constType&v);/取顶点v在数组中的位置Graph(Typev,intnum=MaxVertexes);/构造函数TypeGetValue(intv);/取图中顶点v的值，如果顶点v不存在则返回空intGetweight(intv1,intv2);/取边（或弧）上的权值intGetFirstNeighbor(intv);/取图中顶点v的第一个邻接点的序号。如果不存在返回-1intGetNextNeighbor(intv1,intv2);/取图中下一个邻接点intArcsMaxVertexesMaxVertexes;/用数组记录每个边的信息intInVertex(Type&v);/在图中插入结点intInsertArc(intv1,intv2,intw);/在图中插入依附于v1和v2的边或弧，w是信息intNumberOfVertexes()returnCurrentNumVertexes;/返回当前的顶点数intNumberOfArcs()returnCurrentNumArcs;/返回当前的边（或弧）数int*dist;/最短路径长度数组int*InDegree;/入度数组，记录每个顶点的入度int*path;/最短路径的数组int*s;/最短路径终点数组voidlink();/输出邻接链表voidDFS(constintv,intvisited);/深度优先搜索voidDFTraverse();/深度遍历voidTopologicalOrder();/拓扑排序voidShortestPath(intn,intv);/最短路径;/templateintGraph:GetVertexPos(constType&v)/根据顶点v查找该顶点在邻接表中的位置for(inti=0;iCurrentNumVertexes;i+)if(VTablei.data=v)returni;return-1;templateGraph:Graph(Typev,intnum=MaxVertexes):CurrentNumVertexes(0),CurrentNumArcs(0)Typetail,head;inti=0,e,h,t,w,p=0;while(pMaxVertexes)for(intj=0;jMaxVertexes;j+)Arcspj=b;if(p=j)Arcspj=0;p+;InDegree=newintMaxVertexes;VTable=newVertexNodeMaxVertexes;/创建顶点表for(i=0;inum;i+)/输入各顶点信息InVertex(vi);/在顶点表中插入顶点viInDegreei=0;coute;/输入边的条数coutendl;for(i=0;ie;i+)/逐条输入边cout输入第i+1tailheadw;/输入一条边intj=GetVertexPos(head);while(t=GetVertexPos(tail)=-1)cout输入的顶点(tail)不存在;while(h=GetVertexPos(head)=-1)cout输入的顶点(head)不存在;InsertArc(t,h,w);/插入一条边InDegreej+;/顶点j的入度加1coutendl;templateTypeGraph:GetValue(intv)/取图中顶点v的值，如果顶点v不存在，则返回空if(v=0&vCurrentNumVertexes)returnVTablev.data;returnNULL;templateintGraph:Getweight(intv1,intv2)/取出以顶点v1和v2为两端点的边上的权值if(v1=0&v1=0&v2adjvex=v2)returnp-weight;elsep=p-nextarc;returnNULL;templateintGraph:GetFirstNeighbor(intv)/查找顶点v的第一个邻接顶点的位置if(v=0&vadjvex;return-1;templateintGraph:GetNextNeighbor(intv1,intv2)/查找顶点v1的在v2之后的下一个邻接顶点，如果不存在返回-1if(v1!=-1)ArcNode*p=VTablev1.firstarc;while(p!=NULL)if(p-adjvex=v2&p-nextarc!=NULL)returnp-nextarc-adjvex;/返回下一个邻接顶点在邻接表中的位置elsep=p-nextarc;return-1;/没有查到下一个邻接顶点返回-1templateintGraph:InsertArc(intv1,intv2,intw)/在图中插入弧if(v1=0&v1adjvexnextarc;newnode-nextarc=p-nextarc;p-nextarc=newnode;return1;VTablev1.firstarc=newnode;return1;return-1;templateintGraph:InVertex(Type&v)/在图中插入顶点，插入成功则返回1，否则返回0if(CurrentNumVertexesMaxVertexes-1)/若顶点表未满VTableCurrentNumVertexes.data=v;VTableCurrentNumVertexes.firstarc=NULL;CurrentNumVertexes+;return1;return-1;/以下是实验要求的函数/输出邻接表templatevoidGraph:link()cout输出邻接表:endl;for(inti=0;iCurrentNumVertexes;i+)coutGetValue(i);inta=GetFirstNeighbor(i);if(a!=-1)coutGetValue(a)Getweight(i,a);for(intj=a;j!=-1;j=a)a=GetNextNeighbor(i,j);if(a!=-1)coutGetValue(a)Getweight(i,a);coutendl;/拓扑排序templatevoidGraph:TopologicalOrder()intm=0;/m为输出的顶点数，初始值为0for(inti=0;iCurrentNumVertexes;i+)for(intn=0;nCurrentNumVertexes;n+)if(InDegreen=0)m+;/输出的顶点数加1coutVTablen.dataendl;InDegreen=-1;for(intt=0;t=0&n=0&tCurrentNumVertexes)if(Arcsnt!=0&Arcsnt!=b)InDegreet-;for(inth=0;hCurrentNumVertexes;h+)coutInDegreeh;coutendl;break;if(mCurrentNumVertexes)coutAOV网络中有回路（有向环）！endl;/深度遍历templatevoidGraph:DFS(constintv,intvisited)coutVTablev.data;/访问顶点vvisitedv=1;/顶点v作访问标记intw=GetFirstNeighbor(v);while(w!=-1)/若顶点w存在if(!visitedw)DFS(w,visited);w=GetNextNeighbor(v,w);/重复检测v的所有邻接顶点templatevoidGraph:DFTraverse()inti,n=NumberOfVertexes();/取图的顶点个数int*visited=newintn;/定义访问标记数组visitedfor(i=0;in;i+)visitedi=0;/访问标记数组visited初始化for(i=0;in;i+)/对图中的每一个顶点进行判断if(!visitedi)DFS(i,visited);deletevisited;/释放visited/求最短路径templatevoidGraph:ShortestPath(intn,intv)intmin,u;dist=newintn;s=newintn;path=newintn;for(intj=0;jn;j+)distj=Arcsvj;sj=0;if(j!=v&distjMaxVertexes)pathj=v;elsepathj=-1;sv=1;for(inti=0;i=n-1;i+)min=MaxVertexes;u=v;for(intj=0;jn;j+)if(!sj&distjmin)u=j;min=distj;su=1;for(intw=0;wn;w+)if(!sw&distu+Arcsuwdistw)distw=distu+Arcsuw;pathw=u;if(v!=i&disti!