资源描述：
《最小生成树实验报告材料》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、实用标准文案数据结构课程设计报告题目：最小生成树问题院（系）：计算机工程学院学生姓名:班级：学号:起迄日期:指导教师:2011—2012年度第2学期一、需求分析精彩文档实用标准文案1.问题描述：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。2.基本功能在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。3.输入输出以文本形式输出最小生成树，同时输出它们的权值。通过人机对话方式
2、即用户通过自行选择命令来输入数据和生成相应的数据结果。二、概要设计1.设计思路：因为是最小生成树问题，所以采用了课本上介绍过的克鲁斯卡尔算法和prim算法两种方法来生成最小生成树。根据要求，需采用多种存储结构，所以我选择采用了邻接表和邻接矩阵两种存储结构。2.数据结构设计：图状结构：ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={
3、v,w∈V且P(v,w)，表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息}基本操作：
4、CreateGraph(&G,V,VR)初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。DestroyGraph(&G)初始条件：图G存在。操作结果：销毁图G。LocateVex(G,u)初始条件：图G存在，u和G中顶点有相同特征。操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其它信息。GetVex(G,v)初始条件：图G存在，v是G中某个顶点。精彩文档实用标准文案操作结果：返回v的值。PutVex(&G,v,value)初始条件：图G存在，v是G中某个顶点。操作
5、结果：对v赋值value。FirstAdjVex(G,v)初始条件：图G存在，v是G中某个顶点。操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回“空”。NextAdjVex(G,v,w)初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”。InsertVex(&G,v)初始条件：图G存在，v和图中顶点有相同特征。操作结果：在图G中增添新顶点v。DeleteVex(&G,v)初始条件：图G存在，v是G中某个
6、顶点。操作结果：删除G中顶点v及其相关的弧。InsertArc(&G,v,w)初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中增添弧，若G是无向的，则还增添对称弧。DeleteArc(&G,v,w)初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中删除弧，若G是无向的，则还删除对称弧。DFSTraverse(G,Visit())初始条件：图G存在，Visit是顶点的应用函数。操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅
7、一次。一旦visit()失败，则操作失败。BFSTraverse(G,Visit())初始条件：图G存在，Visit是顶点的应用函数。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。}ADTGraph精彩文档实用标准文案存储结构：邻接矩阵：#defineINFINITYINT_MAX//最大值无穷#defineMAX_VERTEX_NUM20//最大顶点个数typedefenum{UDN}GraphKind;typedefstructAr
8、cCell{VRTypeadj;//VRType是顶点关系类型//对带权图为权值类型InfoTyep*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数GraphKindkind;}MGraph;三、详细设计1.数据类型的定义<1>
9、图类型#defineM20#defineMAX20#definenull0#defineMAX_VERTEX_NUM20//最大顶点个数#defineMAX_NAME3//顶点字符串的最大长度+1#defineMAX_INFO20//相关信息字符串的最大长度+1#defineINFINITYINT_MAX//用整型最大值代替∞typedefintVRType;typedefcharIn
