2022年数据结构实验报告无向图邻接矩阵存储结构 .pdf

《2022年数据结构实验报告无向图邻接矩阵存储结构 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构实验报告无向图邻接矩阵存储结构 .pdf（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、个人资料整理仅限学习使用数学与计算机学院课程设计说明书课 程 名 称: 数据结构与算法课程设计课 程 代 码: 6014389 题目: 无向图的邻接矩阵存储结构年级/专业/班: 2018级软件 4班学 生 姓 名: 吴超学号: 312018080611402 开 始 时 间: 2018年 12月 9 日完 成 时 间: 2018年 12月 30日课程设计成绩：学习态度及平时成绩30）技术水平与实际能力20）创新5）说明书 计算书、图纸、分析报告）撰写质量 45）总 分课程设计说明书打印稿一份2课程设计说明书电子稿一份；3源程序电子文档一份。四、主要技术路线提示用一维数组存放图的顶点信息，二维数

2、组存放各边信息。五、进度安排按教案计划规定，数据结构课程设计为2 周，其进度及时间大致分配如下：序号设计内容天数1 分析问题，给出数学模型，选择数据结构2 2 设计算法，给出算法描述1 3 给出源程序清单2 4 编辑、编译、调试源程序2 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 21 页个人资料整理仅限学习使用5 编写课程设计报告3 总计10 六、推荐参考资料1 严蔚敏，吴伟民 . 数据结构 . 清华大学出版社出版。2 严蔚敏，吴伟民 . 数据结构题集 (C 语言版 . 清华大学出版社 .2003 年 5 月。3 唐策善，李龙澎

3、. 数据结构 ( 作 C语言描述 . 高等教育出版社 .2001 年 9 月4 朱战立 . 数据结构 (C+语言描述 . 高等教育出版社 .2004 年 8 月指导教师签名日期年月日系 主 任审核日期年月日目录精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 21 页个人资料整理仅限学习使用摘要随着计算机的普及，涉及计算机相关的科目也越来越普遍，其中数据结构是计算机专业重要的专业基础课程与核心课程之一，为适应我国计算机科学技术的发展和应用，学好数据结构非常必要，然而要掌握数据结构的知识非常难，所以对“数据结构”的课程设计比不可少。本说明书

4、是对“无向图的邻接矩阵存储结构”课程设计的说明。首先是对需求分析的简要阐述，说明系统要完成的任务和相应的分析，并给出测试数据。其次是概要设计，说明所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次关系，以及ADT 描述。然后是详细设计，描述实现概要设计中定义的基本功操作和所有数据类型，以及函数的功能及代码实现。再次是对系统的调试分析说明，以及遇到的问题和解决问题的方法。然后是用户使用说明书的阐述，然后是测试的数据和结果的分析，最后是对本次课程设计的结论。关键词： 网络化；计算机；对策；图；储存。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -

5、第 4 页，共 21 页个人资料整理仅限学习使用引 言数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储。数据结构往往同高效的检索算法和技术有关。选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。这种洞见导致了许多种方法和的出现，语言就是其中之一。此次课程设计根据课堂讲授内容，下发任务书，要求学生完成相应系统，以消化课堂所讲解的内容；通过调试典型例题或习题积累调试C+ 程序从而获得数据结构的编程经验；通过完成此项课程设计，逐渐培养学生的编程能力、用计算机解决实际问题的能力，并充分

6、理解图的矩阵储存方法。此次课程设计题目为无向图的邻接矩阵存储结构，所利用工具为 Microsoft visual studio 2008.1需求分析随着计算机的普及 , 信息的存储逐渐和我们的日常生活变得密切起来，而数据的存储方式也多种多样，比如树、链表、数组、图等等。为了充分体现图的矩阵储存结构的优势与功能，要求本系统应达到以下要求：1.图是无向带权图2.能从键盘上输入各条边和边上的权值；3.构造图的邻接矩阵和顶点集。4.输出图的各顶点和邻接矩阵5.插入一条边6.删除一条边7.求出各顶点的度8.判断该图是否是连通图，若是，返回1；否则返回 0. 9.使用深度遍历算法，输出遍历序列。1.1 任

7、务与分析邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=(V,E是具有 n 个顶点的图，则G的邻接矩阵是 n 阶方阵。为了实现此算法，用一维数组a 存放图的顶点信息，二维数组b存放各边信息。顶点或者边存在，则该数组应有值，通过此来进行建立、插入、删除。其余方法也将能通过数组的特性来实现。1.2 测试数据精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 21 页个人资料整理仅限学习使用1.建立图的矩阵存储结构，第一次建立连通图A1，第二次建立非连通图A2。如下：1231133221234441133图 1.1 测试数据2.选择输出图3.选

8、择插入节点，插入4 4.选择插入边，在 3,4 节点中插入边，权值为55 5.选择深度优先搜索6.选择判断是否连通7.选择求最小生成树8.选择求各顶点的度9.选择退出，重新运行，此次建立A2的图，再次进行测试。2 概要设计2.1 ADT 描述 ADT Glist VR= 图的顶点和边 VR= | v,w V, 表示顶点 v 和 w间的边； 基本操作：初始化空图；输入建立图；深度优先遍历图；确定图中的顶点数目；确定图中边的数目；在图中插入一个顶点；在图中插入一条边；删除图中一个顶点删除图中的一条边；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6

9、页，共 21 页个人资料整理仅限学习使用求顶点的度；求最小生成树； ADT Graph 。2.2 程序模块结构主函数main创建函数菜单边的插入函数顶点的插入函数求顶点的度最小生成树输出函数深度遍历函数判断连通函数图 2.1：模块结构2.2.1 结构体定义本系统未采用结构体方法，类的定义如下：定义顶点 : nodecount ，edgecount 边：已经分别存放顶点和边的两个数组： aMaxNode和bMaxNodeMaxNode 。其余成员函数均以public 形式声明。在邻接矩阵表示的图中，顶点信息用一维数组表示a。在简单情况下可省略，仅以下标值代表顶点序号。若需要，顶点信息更加丰富。边

10、 或弧）信息用二维数组表示b ，这也是邻接矩阵。包含边的权值。在类中数据成员有 4 个，重要的是邻接矩阵Edge 、总边数 edgecount和顶点数 nodecount 。class Graph1 private: int nodecount 。/节点 int edgecount 。/边 int aMaxNode。/顶点信息组 /set a。 int bMaxNodeMaxNode 。/权值信息组public: 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 21 页个人资料整理仅限学习使用 Graph1(int。/构造函数 int

11、getNodeCount(。/当前的节点数 int getEdgeCount( 。/当前的边数 void insertNode(int。/插入一个节点 void isertEdge(int ,int ,int。/插入一条边 void deleteEdge(int,int。/删除一条边 bool isliantong(。/判断是否连通 int getWeight(int,int。/获得某条边的权值 int Depth(int 。/深度遍历准备，用于建立顶点访问数组和记录所访问顶点个数void Depth(int v,int visited,int &n 。/深度遍历void outDu(Grap

12、h1 G。/输出节点个数void PrintOut(Graph1 G 。/输出图void CreatG(int n,int e。/建立图。2.3各功能模块以下将以注释形式为每个函数的功能进行声明：构造函数： Graph1(int 用于初始化图get函数： int getNodeCount(。得到当前的节点数get函数： int getWeight(int,int。获得某条边的权值get函数： int getEdgeCount(。得到当前的边数插入函数： void insertNode(int。插入一个节点插入函数： void isertEdge(int ,int ,int。插入一条边删除函数：

13、 void deleteEdge(int,int。删除一条边判断函数： bool isliantong(。判断是否连通遍历函数 1：int Depth(int 。/深度遍历准备，用于建立顶点访问数组和记录所访问顶点个数遍历函数 2：void Depth(int v,int visited,int &n 。/深度遍历求度函数： void outDu(Graph1 G。输出节点个数输出函数： void PrintOut(Graph1 G 。输出图构建函数： void CreatG(int n,int e。建立图3 详细设计3.1 类的定义class Graph1 精选学习资料 - - - - -

14、- - - - 名师归纳总结 - - - - - - -第 8 页，共 21 页个人资料整理仅限学习使用 private: int nodecount 。/节点 int edgecount 。/边 int aMaxNode。/顶点信息组 /set a。 int bMaxNodeMaxNode 。/权值信息组public: Graph1(int。/构造函数 int getNodeCount(。/当前的节点数 int getEdgeCount( 。/当前的边数 void insertNode(int。/插入一个节点 void isertEdge(int ,int ,int。/插入一条边 void

15、deleteEdge(int,int。/删除一条边 void prim(int。/生成最小树 bool isliantong(。/判断是否连通 int getWeight(int,int。/获得某条边的权值 int Depth(int 。/深度遍历准备，用于建立顶点访问数组和记录所访问顶点个数void Depth(int v,int visited,int &n 。/深度遍历void outDu(Graph1 G。/输出节点个数void PrintOut(Graph1 G 。/输出图void CreatG(int n,int e。/建立图。3.2 初始化初始化邻接矩阵以及有关参数，通过for

16、循环将数组的值都初始化为0，使之成为一个空图。Graph1:Graph1(int s=MaxNode/构造函数 for(int i=0。i for(int j=0。j bij=0 。 nodecount=0 。 for(int k=0。k ak=-1。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 21 页个人资料整理仅限学习使用 3.3 图的构建操作在主函数中要求输入需要构建的图的顶点数和边数，调用构建函数，分别用两个for 语句来构建图 int i,vi,vj,w 。 edgecount=e 。 nodecount=n 。 cout

17、endl 输入顶点的信息 暂设为整型）： 。 for ( i=0。 i coutn i+1ai 。 for ( i=0。 i /输入两个顶点编号和边权值 coutendl 输入边的信息 vi,vj,w ）：vivjw 。 bvi-1vj-1=w 。 bvj-1vi-1=w 。 3.4 输出操作本函数通过传过来的对象G 得到相关数组，通过for 循环来分别输出顶点数组和边的权值数组 int i 。 coutn 输出顶点的信息： endl。 for ( i=0。 i。 i+ coutG.ai 。 coutendln 输出邻接矩阵： 。 for ( i=0。 i。 i+ coutendli+1: 。

18、 for ( int j=0。 j 。j+ coutG.bij 。 cout/ 当前的节点数精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 21 页个人资料整理仅限学习使用 return nodecount 。 int Graph1:getEdgeCount(/ 当前的边数 return edgecount 。 int Graph1:getWeight(int x,int y/获得某条边的权值 return bx-1y-1 。 3.6 插入操作插入顶点：通过将传来的值/插入一个节点 anodecount+=it。 cout当前节点数为

19、： nodecount/插入一条边 bx-1y-1=w 。 by-1x-1=w 。 cout该边插入成功 ! /删除一条边 bx-1y-1=0 。 by-1x-1=0 。 cout边(x,y 已经成功删除 !。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 21 页个人资料整理仅限学习使用 edgecount- 。 3.8 求顶点的度操作通过两个 for循环来查找各顶点，判断其是否有边/输出各点的度 int mMax=0,k,i 。 for(k=0。k。k+ for(i=0。i。i+ if(G.bki!=0 mk+。 cout各点的度

20、： endl。 for(i=0。i。i+ cout顶点i 的度： mi其主要作用是构建访问数组intv ，以及调用核心遍历函数 Depth(int v,int visited,int &n ，其中的 n是用来记录访问的顶点数目，用于判断图的连通性。int Graph1:Depth(int node int n=0。int vMaxNode 。 for(int i=0。i vi=0。 Depth(node,v,n 。 return n 。/n 记录访问节点数，用于判断是否连通精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 21 页个人资

21、料整理仅限学习使用 void Graph1:Depth(int v,int visited,int &n cout v+1 。/访问顶点 v visitedv=1。 /标记顶点 v 已访问n+。/n 记录访问节点数 for (int col=0。 col if (bvcol=0|bvcol=Max continue 。/找 v 一个邻接点 col if (!visitedcol Depth(col, visited,n 。 /调用深度递归遍历 3.10 判断连通操作通过调用遍历函数得到所能访问的顶点数n，然后判断 n与当前顶点数是否相等来确认是否连通。bool Graph1:islianton

22、g(/判断是否连通 int n=0。 n=Depth(0。 cout该图的总节点数为 :nodecount!endl 。 cout其中一个连通分量连通的节点数为:n!/访问到的节点数与顶点数是否相等 return 1 。 else return 0 。 3.11 主函数主函数的主要功能是引导构建新图的邻接矩阵存储结构，并且制作菜单、调用各个相应的功能函数。int main( Graph1 G(10。int x,y,w。int node。cout你好,请问你向图添加几个节点?几条边 ?请依次从键盘输入 !n。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - -

23、-第 13 页，共 21 页个人资料整理仅限学习使用int e。cine。G.CreatG(n,e。cout恭喜你 !你的图已经建立成功 ! 。while(true /system(cls。cout*endl。cout*请选择你要进行的操作 :*endl 。cout*1-输出图 ! *endl 。cout*2-判断图是否连通 ! *endl。cout*3-表示深度优先搜索 ! *endl 。cout*4-表示求各顶点的度 ! *endl 。cout*5-表示插入新节点 !*endl 。cout*6-表示删除边 ! *endl 。cout*7-求边的权值 *endl。cout*8-插入新的边 !

24、 *endl 。cout*0-表示结束操作 ! *endl 。cout*endl。int choice。 coutendl。cout请你做出选择 !choice。switch(choice case 1: G .PrintOut(G。 break 。case 2: if(G.isliantong( cout该图是连通的 !endl。 else cout该图不是连通的 !endl。 break 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 21 页个人资料整理仅限学习使用case 3: int node。 cout请输入你选择的起始

25、节点!node。 cout深度优先搜索结果为 :。 cout。 break 。case 5: cout请输入你要插入的新节点!node。 G .insertNode(node。 coutendl。 break 。case 6: cout请输入你要删除的边 !xy。 G .deleteEdge(x,y。 coutendl。 break 。case 7: cout请输入你要查询的边的两个顶点xy。coutendl。break。case 8: cout请输入你要添加的 e条边以及边上对应的权值!xyw。 G .isertEdge(x,y,w。 break 。case 0: 精选学习资料 - - -

26、- - - - - - 名师归纳总结 - - - - - - -第 15 页，共 21 页个人资料整理仅限学习使用 cout感谢使用！ 。4 调试分析4.1 测试数据测试数据详见图 1 4.2调试问题具体功能方面，在遍历函数中，由于访问节点数组visit 构建问题，无法达到遍历目的，后新增另一遍历功能函数，用于构建visit ，问题才得以解决，而于使用了清屏system(cls和暂停 system(pause 功能，在测试时一度出现暂停次数过多的问题，通过在判断结构中加入break后解决，在判断是否连通功能上，由于判断问题迟迟未能下手，后在遍历函数中加入了一个记录访问节点数的N，从而解决问题。

27、4.3 算法时间复杂度图的创建：时间复杂度为O(n。深度遍历 : 时间复杂度为 O(n。插入顶点和边 : 当插入的顶点和边为x，y 时，若 x=y 时间复杂度为 O(x反之为 O(y。删除顶点和边 : 当删除的顶点和边为x，y 时，若 x=y 时间复杂度为 O(x反之为 O(y。4.4 经验和心得体会书上提供的定义结构体的方法很好，想不COPY 书上的方法，而是改为定义一个结构体，但是重新想想，如果作为一个编程者，并不是一定要全靠自己想方法，如果是有更简便的方法当然好，但是明知道自己的方法更复杂，却还要一条道走到黑，这样太不明智了，我要做的，就是学会如何使用老师的简便方法，并使用于以后的学习中

28、；而在自己编写过程中，虽然经常编译一次性通过，但是在接下来的测试中，基本上每解决一个功能性问题但是却马上接着出现一个新的问题；一次又一次的更改确实严重打击了我的信心和耐心，最后还是不得不承认自己的能力太弱，所以一个简单的函数都解决不了，希望自己在以后的学习中能有质的飞跃！5 用户使用说明本系统是关于图的矩阵存储系统，管理员和游客，要求首先创建一个图之后才能进行后续的操作，并且在输入过程中务必规范输入。6测试结果6.1 创建图精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 21 页个人资料整理仅限学习使用图 6.1 图的创建6.2 插入

29、节点图 6.2 节点的插入6.3 深度优先遍历精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 21 页个人资料整理仅限学习使用图 6.3 深度优先遍历6.4 求各顶点的度图 6.4 定点的度6.5 输出图精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 21 页个人资料整理仅限学习使用图 6.5 图的输出6.6 判断是否连通图 6.6 判断是否连通6.7 求边的权值精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 21 页个人资料整理仅限学习使用图 6.7 边的权值6.8 插入边图 6.8 边的插入6.9 删除边精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 21 页个人资料整理仅限学习使用图 6.9 边的删除结 论本次课程设计“无向图的邻接矩阵存储结构”按照任务书相应的要求成功的完成了任务，由于本课程设计涉及任务明确，采用图的储存结构和算法比较方便处理数据的储存、查询、删除等操作。但图的操作比较难，容易出错并且不易改动。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21 页，共 21 页