图邻接矩阵 邻接表的建立c _数据结构课程设计.doc

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