数据结构课程设计-图的邻接矩阵

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

1、无向图的邻接矩阵存储结构数据结构课程设计报告设计题目：图的邻接矩阵存储结构院系计算机学院年级x级学生xxxx学号xxxxxxxxxx指导教师xxxxxxxxx起止时间10-6/10-102013年10月10日20/20无向图的邻接矩阵存储结构目录1需求分析42概要设计42.1ADT描述42.2程序模块结构52.3　各功能模块63　详细设计73.1类的定义73.2初始化83.3图的构建操作83.4输出操作93.5get操作93.6插入操作103.7删除操作103.8求顶点的度操作113.9深度遍历作……………………………………………………………………………...113.10判断连通操

2、作123.11主函数134调试分析164.1调试问题164.2算法时间复杂度165　用户手册165.1主界面165.2创建图175.3插入节点175.4深度优先遍历175.5求各顶点的度185.6输出图185.7判断是否连通195.8求边的权值195.9插入边195.10删除边20结论20参考文献……………………………………………………………………………………………………………………………………..2020/20无向图的邻接矩阵存储结构摘要随着计算机的普及，涉及计算机相关的科目也越来越普遍，其中数据结构是计算机专业重要的专业基础课程与核心课程之一，为适应我国计算机科学技术的发展和应

3、用，学好数据结构非常必要，然而要掌握数据结构的知识非常难，所以对“数据结构”的课程设计比不可少。本说明书是对“无向图的邻接矩阵存储结构”课程设计的说明。首先是对需求分析的简要阐述，说明系统要完成的任务和相应的分析，并给出测试数据。其次是概要设计，说明所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次关系，以及ADT描述。然后是详细设计，描述实现概要设计中定义的基本功操作和所有数据类型，以及函数的功能及代码实现。再次是对系统的调试分析说明，以及遇到的问题和解决问题的方法。然后是用户使用说明书的阐述，然后是测试的数据和结果的分析，最后是对本次课程设计的结论。关键词：网络化；计

4、算机；对策；图；储存。20/20无向图的邻接矩阵存储结构1需求分析随着计算机的普及,信息的存储逐渐和我们的日常生活变得密切起来，而数据的存储方式也多种多样，比如树、链表、数组、图等等。为了充分体现图的矩阵储存结构的优势与功能，要求本系统应达到以下要求：1.图是无向带权图2.能从键盘上输入各条边和边上的权值；3.构造图的邻接矩阵和顶点集。4.输出图的各顶点和邻接矩阵5.插入一条边6.删除一条边7.求出各顶点的度8.判断该图是否是连通图，若是，返回1；否则返回0.9.使用深度遍历算法，输出遍历序列。2概要设计2.1ADT描述ADTGlist{{VR}={图的顶点和边}VR={

5、

6、v,w∈V,表示顶点v和w间的边；}基本操作：初始化空图；输入建立图；深度优先遍历图；确定图中的顶点数目；确定图中边的数目；在图中插入一个顶点；20/20无向图的邻接矩阵存储结构在图中插入一条边；删除图中一个顶点删除图中的一条边；求顶点的度；求最小生成树；}ADTGraph;2.2程序模块结构图2.1：模块结构2.2.1　结构体定义本系统未采用结构体方法，类的定义如下：定义顶点:nodecount，edgecount边：已经分别存放顶点和边的两个数组：a[MaxNode]和b[MaxNode][MaxNode];其余成员函数均以public形式声明。在邻接矩阵表示的图中

7、，顶点信息用一维数组表示a[]。在简单情况下可省略，仅以下标值代表顶点序号。若需要，顶点信息更加丰富。边（或弧）信息用二维数组表示b[][20/20无向图的邻接矩阵存储结构]，这也是邻接矩阵。包含边的权值。在类中数据成员有4个，重要的是邻接矩阵Edge[][]、总边数edgecount和顶点数nodecount。classGraph1{private:intnodecount;//节点intedgecount;//边inta[MaxNode];//顶点信息组//seta;intb[MaxNode][MaxNode];//权值信息组public:Graph1(int);//

8、构造函数intgetNodeCount();//当前的节点数intgetEdgeCount();//当前的边数voidinsertNode(int);//插入一个节点voidisertEdge(int,int,int);//插入一条边voiddeleteEdge(int,int);//删除一条边boolisliantong();//判断是否连通intgetWeight(int,int);//获得某条边的权值intDepth(int);//深度遍历准备，用于建立顶点访问