《数据结构实习报告图》由会员分享，可在线阅读，更多相关《数据结构实习报告图（17页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计实习报告 题 目：图的基本操作学 号：1210522姓 名：何厚华年 级：大二学 院：计算机与控制工程学院专 业：计算机科学与技术完成日期：2014年5月21日授课教师：辛运帏目录1.题目. 22.要求 . . . . . . . . . . . . . . . . . . . . . . . . 23.程序实现 . . . . . . . . . . . . . . . . . . . . . 3 3.1程序运行及编译环境 . . . . . . . . . . . . . . . . 3 3.2程序描述 . . . . . . . . . . . . . . . . . 3
2、 3.3实现功能 . . . . . . . . . . . . . . . . . . 3 3.3.1子功能模块 . . . . . . . . . . . . . . . . . 4 3.3.1.1 子功能模块1 . . . . . . . . . . . . . . . 4 3.3.1.2子功能模块2. . . . . . . . . . . . . . . 5 3.3.1.3子功能模块3. . . . . . . . . . . . . . . 5 3.3.1.4子功能模块4. . . . . . . . . . . . . . 5 3.3.1.5子功能模块5. . . . . . .
3、 . . . . . . . . 5 3.3.2 数据结构. . . . . . . . . . . . . . . . . . . . 6 3.3.2.1 数据结构的操作1 . . . . . . . . . . . . . 7 3.3.2.2 数据结构的操作2 . . . . . . . . . . . . . 7 3.3.2.3 数据结构的操作3 . . . . . . . . . . . 8 3.3.3算法及程序说明. . . . . . . . . . . . . . . . . . 13 3.4运行结果 . . . . . . . . . . . . . . . . . . . 1
4、4 3.5尚未解决的问题 . . . . . . . . . . . . . . . . . . 161. 题目 图的基本操作给定N个顶点、E条边的图G，完成图的相关算法，具体要求如下：1 完成图的创建方法，即从键盘或文件输入图的信息，建立图的邻接表或是邻接矩阵存储结构。2 给出判定图的性质的算法，即能够判定图是否是有向图、无向图、有向无环图、连通图、哈密尔顿图等。3 根据输入的图的性质，实现以下算法（选择其中一两个）：l 如果图是有向无环图，则先实现图的某种遍历算法，在此基础上实现图的拓扑排序算法。l 如果图是连通图，则求出图的最大生成树（不是最小生成树，参考讲授的方法），即得到的生成树权值
5、之和最大。l 如果图是无向图，则以第一个顶点当做源点，求出单源最短路径。l 对于哈密尔顿图，找出其哈密尔顿回路。2.要求：初始输入数据的格式由自己定义，例如，输入文件中保存的初始数据格式有以下两种：格式一3 3 2 15 解释：第一行是图中所含顶点个数m，后面是m行m列数据，对应邻接矩阵。格式二3 41 2 31 3 22 3 13 1 5解释：第一行是图中所含顶点个数m和边数e，后面是e条边的信息，如1 2 3表示顶点1到顶点2有权值为3的边。3. 程序实现 3.1程序运行及编译环境程序是用Visual Studio 2010即VS10.0 编译的。可以在windows系列的操作系统上运行。
6、 3.2程序描述 该程序主要用于实现图的基本操作,包括：建立邻接矩阵存储结构，给出判定图的性质的算法，即能够判定图是否是有向图、无向图、有向无环图、连通图、哈密尔顿图等，然后在此基础上，如果图是连通图，则求出图的最大生成树，如果图是无向图，则以第一个顶点当做源点，求出单源最短路径。其流程如下： A).程序读取输入文件，并生成相应的数据结构a. 用二维数组来声明并存储图，完成初始化的工作b.建立图的邻接矩阵存储c.生成图的一步可达矩阵B).输出相关信息 a.判断图是否是有向图 b.判断图是否是无向图 c.判断图是否是连通图 d.判断图是否是有向无环图 e.判断图是否是哈密顿图C).编码以及译码a
7、.如果图是连通图，则求出图的最大生成树。b.如果图是无向图，则以第一个顶点当做源点，求出单源最短路径。D).完成3.3实现功能建立邻接矩阵存储结构，给出判定图的性质的算法，即能够判定图是否是有向图、无向图、有向无环图、连通图、哈密尔顿图等，然后在此基础上，如果图是连通图，则求出图的最大生成树，如果图是无向图，则以第一个顶点当做源点，求出单源最短路径。3.3.1 子功能模块 子功能按照是否对象的方法分类：数组的处理以及树的处理；3.3.1.1 子功能模块1/*函数原型：int Pow(int x,int base=10);*函数参数：x 表示指数*函数功能：求base的幂次*/int Pow(i
8、nt x,int base=10)if(x=0) return 1;return base*Pow(x-1);3.3.1.2子功能模块2/*函数原型：float Convert2Num(char* str)*函数参数：str 是文件流中的字符串*函数功能：把一个数字字符串转化为一个数字*/float Convert2Num(char* str)float num=0;int i=0,dot=0;if(*str)=I)return INF;while(*(str+i)if(dot!=0) dot+;if(*(str+i)!=.)num=10*num+*(str+i)-0;else dot=1;i
9、+;return dot=0?num:num/Pow(dot-1);3.3.1.3子功能模块3函数功能：Mul矩阵平方放到result矩阵中Void SquareMatrix (int MulMAXNODESMAXNODES,int resultMAXNODESMAXNODES,int n) for(int k=0;kn;k+) for(int l=0;ln;l+) resultkl=0; for(int m=0;mn;m+) if(Mulkm*Mulml!=0) resultkl=1; break; 3.3.2 数据结构/*图这个数据结构的定义，从文件读入，用邻接矩阵存储NodesCount
10、表示结点个数， AdjMatrixMAXNODESMAXNODES是邻接矩阵 ConnectMAXNODESMAXNODES表示一步可达矩阵，其中点到自身为可达*/class Graphint NodesCount;float AdjMatrixMAXNODESMAXNODES;int ConnectMAXNODESMAXNODES;public:Graph(ifstream &fin);/从文件读入图的元素，建立邻接矩阵bool IsUnDirectedGraph();/判断是否是无向图bool IsDirectedGraph();/判断是否是有向图bool IsDirectWithoutLoop();/判断是否是有向无环图bool IsConnected();/判断是否是连通图void Prim(int v);/从节点v开始，用类似prim算法的方法生成最大生成树void floyd();/用floyd算法求任意两个点之间的最短距离int GetNodesCount();/;3.3.2.1 数据结构的操作1/*函数原型：Graph:Graph(ifstream &fin)*
