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

《图邻接矩阵 邻接表的建立c++_数据结构课程设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图邻接矩阵邻接表的建立c++_数据结构课程设计一.需求分析1.运行环境硬件：计算机486/64M以上操作系统：WIN9x以上/WIN2000/WINXP/WINME相关软件：vistualC++2．程序所实现的功能：（1）建立并显示图的邻接表。（2）深度优先遍历，显示遍历结果。（3）对该图进行拓扑排序，显示排序结果。（4）给出某一确定顶点到所有其它顶点的最短路径。3.程序的输入，包含输入的数据格式和说明(1)输入顶点数,及各顶点信息(数据格式为整形)(2)输入边数,及权值(数据格式为整形)4.程序的输出，程序输出的形式(1)输出图的邻接表、

2、深度优先遍历结果、拓扑排序结果。(2)输入某一确定顶点到其它所有顶点的最短路径。5.测试数据二、设计说明1、算法设计的思想建立图类，建立相关成员函数。最后在主函数中实现。具体成员函数的实现请参看源程序。　　2、主要的数据结构设计说明图邻接矩阵、邻接表的建立。图的深度优先遍历、拓扑排序、顶点之间的最短路径。3、程序的主要模板templateclassGraph4、程序的主要函数Graph、link()、DFTraverse()、TopologicalOrder()、TopologicalOrder()、GetVertex

3、Pos()、ShortestPath三、上机结果及体会1、实际完成的情况说明主要程序参考教材《数据结构——C++版》。2、程序的性能分析可连续建图3、上机过程中出现的问题及其解决方案。编译没有错误，但结果有问题。解决方案：虽然程序的编译通过，只能说明语法上没有问题，结果只所以不正确是因为算法上原因。4、程序中可以改进的地方说明程序中的深度优先遍历，浪费空间较大，可以考虑用循环来做。但这样将付出代码长度度加长的代价。5、程序中可以扩充的功能及设计实现假想实现假想：随用户的输入可以随时动态的显示图的生成。6、收获及体会编写程序即是一件艰苦的工作

4、，又是一件愉快的事情。最大的收获：编程时如果遇到看似简单但又无法解决的问题，很容易灰心丧气。此时切不可烦躁，一定要冷静的思考，认真的分析。要勇敢的面对问题，勇敢的接受问题，勇敢的处理问题，最后最勇敢的解决问题。四、参考文献数据结构（C++版）叶核亚主编机械工业出版社数据结构经典算法实现与习题解答汪杰编著人民邮电出版社数据结构课程设计苏仕华编著机械工业出版社数据结构程序设计题典李春葆编著清华大学出版社数据结构课程与题解（用C/C++描述）胡圣荣编著北京大学出版社[程序运行流程图]charop//程序控制变量If(op=='Y'

5、

6、op=='y

7、')if(op=='N'

8、

9、op=='n')//本程序是邻接矩阵，邻接表的利用，共有4项功能,分别是：//(1)建立并显示图的邻接表。//(2)以非递归方式进行深度优先遍历，显示遍历结果。//(3)对该图进行拓扑排序，显示排序结果。//(4)给出某一确定顶点到所有其它顶点的最短路径。#includeusingnamespacestd;constintMaxVertexes=20;//最大的顶点数constintb=10000;templateclassGraph;structArcNode{//定义

10、边结点friendclassGraph;intadjvex;//和边（或弧）相关联的另一个顶点序号intweight;//边（或弧）上的信息ArcNode*nextarc;//指向下一条边结点的指针ArcNode(intv,intw):adjvex(v),weight(w),nextarc(NULL){}};//构造函数templatestructVertexNode{//定义顶点结点friendclassGraph;Typedata;//顶点的信息ArcNode*first

11、arc;//指向依附该顶点的边链表};templateclassGraph{VertexNode*VTable;//顶点表intCurrentNumVertexes;//当前的顶点数intCurrentNumArcs;//当前的边（或弧）数public:intGetVertexPos(constType&v);//取顶点v在数组中的位置Graph(Typev[],intnum=MaxVertexes);//构造函数TypeGetValue(intv);//取图中顶点v的值，如果顶点v不存在则返回空intGe

12、tweight(intv1,intv2);//取边（或弧）上的权值intGetFirstNeighbor(intv);//取图中顶点v的第一个邻接点的序号。如果不存在返回-1in