当前位置：文档之家› 数据结构实验报告无向图邻接矩阵存储结构

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

数学与计算机学院课程设计说明书课程名称: 数据结构与算法课程设计课程代码: 6014389题目: 无向图的邻接矩阵存储结构年级/专业/班: 2018级软件4班学生姓名: 吴超学号: 312018*********开始时间: 2018年12月9日完成时间: 2018年12月30日课程设计成绩：学习态度及平时技术水平与实际创新<5）说明书<计算书、图纸、分析总分指导教师签名：年月日数据结构课程设计任务书学院名称：数学与计算机学院课程代码：__6014389______专业：软件工程年级： 2018一、设计题目无向图的邻接矩阵存储结构二、主要内容图是无向带权图，对下列各题，要求写一算法实现。

1）能从键盘上输入各条边和边上的权值；2）构造图的邻接矩阵和顶点集。

3）输出图的各顶点和邻接矩阵4）插入一条边5）删除一条边6）求出各顶点的度7）判断该图是否是连通图，若是，返回1；否则返回0.8）使用深度遍历算法，输出遍历序列。

三、具体要求及应提交的材料用C/C++语言编程实现上述内容，对每个问题写出一个算法实现，并按数学与计算机学院对课程设计说明书规范化要求，写出课程设计说明书，并提交下列材料：1>课程设计说明书打印稿一份2>课程设计说明书电子稿一份；3>源程序电子文档一份。

四、主要技术路线提示用一维数组存放图的顶点信息，二维数组存放各边信息。

五、进度安排按教案计划规定，数据结构课程设计为2周，其进度及时间大致分配如下：[1] 严蔚敏，吴伟民.数据结构.清华大学出版社出版。

[2] 严蔚敏，吴伟民. 数据结构题集(C语言版> .清华大学出版社.2003年5月。

[3]唐策善，李龙澎.数据结构(作C语言描述> .高等教育出版社.2001年9月[4] 朱战立.数据结构(C++语言描述><第二版本）.高等出版社出版.2004年4月[5]胡学钢.数据结构(C语言版> .高等教育出版社.2004年8月指导教师签名日期年月日系主任审核日期年月日目录摘要随着计算机的普及，涉及计算机相关的科目也越来越普遍，其中数据结构是计算机专业重要的专业基础课程与核心课程之一，为适应我国计算机科学技术的发展和应用，学好数据结构非常必要，然而要掌握数据结构的知识非常难，所以对“数据结构”的课程设计比不可少。

本说明书是对“无向图的邻接矩阵存储结构”课程设计的说明。

首先是对需求分析的简要阐述，说明系统要完成的任务和相应的分析，并给出测试数据。

其次是概要设计，说明所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次关系，以及ADT描述。

然后是详细设计，描述实现概要设计中定义的基本功操作和所有数据类型，以及函数的功能及代码实现。

再次是对系统的调试分析说明，以及遇到的问题和解决问题的方法。

然后是用户使用说明书的阐述，然后是测试的数据和结果的分析，最后是对本次课程设计的结论。

关键词：网络化；计算机；对策；图；储存。

引言数据结构是计算机存储、组织数据的方式。

数据结构是指相互之间存在一种或多种特定关系的的集合。

通常情况下，精心选择的数据结构可以带来更高的运行或者存储。

数据结构往往同高效的检索算法和技术有关。

选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。

这种洞见导致了许多种方法和的出现，语言就是其中之一。

此次课程设计根据课堂讲授内容，下发任务书，要求学生完成相应系统，以消化课堂所讲解的内容；通过调试典型例题或习题积累调试C++程序从而获得数据结构的编程经验；通过完成此项课程设计，逐渐培养学生的编程能力、用计算机解决实际问题的能力，并充分理解图的矩阵储存方法。

此次课程设计题目为《无向图的邻接矩阵存储结构》，所利用工具为 Microsoft visual studio 2008.1需求分析随着计算机的普及,信息的存储逐渐和我们的日常生活变得密切起来，而数据的存储方式也多种多样，比如树、链表、数组、图等等。

为了充分体现图的矩阵储存结构的优势与功能，要求本系统应达到以下要求：1.图是无向带权图2.能从键盘上输入各条边和边上的权值；3.构造图的邻接矩阵和顶点集。

4.输出图的各顶点和邻接矩阵5.插入一条边6.删除一条边7.求出各顶点的度8.判断该图是否是连通图，若是，返回1；否则返回0.9.使用深度遍历算法，输出遍历序列。

1.1任务与分析邻接矩阵是表示图形中顶点之间相邻关系的矩阵。

设G=(V,E>是具有n个顶点的图，则G 的邻接矩阵是n阶方阵。

为了实现此算法，用一维数组a[]存放图的顶点信息，二维数组b[][]存放各边信息。

顶点或者边存在，则该数组应有值，通过此来进行建立、插入、删除。

其余方法也将能通过数组的特性来实现。

1.2测试数据1.建立图的矩阵存储结构，第一次建立连通图A1，第二次建立非连通图A2。

如下：图1.1测试数据2.选择输出图3.选择插入节点，插入44.选择插入边，在3,4节点中插入边，权值为555.选择深度优先搜索6.选择判断是否连通7.选择求最小生成树8.选择求各顶点的度9.选择退出，重新运行，此次建立A2的图，再次进行测试。

2 概要设计2.1 ADT描述ADT Glist{{VR}={图的顶点和边}VR={<v,w> | v,w∈V, <v,w>表示顶点v和w间的边；} 基本操作：初始化空图；输入建立图；深度优先遍历图；确定图中的顶点数目；确定图中边的数目；在图中插入一个顶点；在图中插入一条边；删除图中一个顶点删除图中的一条边；求顶点的度；求最小生成树；} ADT Graph。

2.2程序模块结构图2.1：模块结构2.2.1 结构体定义本系统未采用结构体方法，类的定义如下：定义顶点: nodecount，edgecount 边：已经分别存放顶点和边的两个数组： a[MaxNode]和b[MaxNode][MaxNode]。

其余成员函数均以public形式声明。

在邻接矩阵表示的图中，顶点信息用一维数组表示a[]。

在简单情况下可省略，仅以下标值代表顶点序号。

若需要，顶点信息更加丰富。

边<或弧）信息用二维数组表示b[ ][ ]，这也是邻接矩阵。

包含边的权值。

在类中数据成员有4个，重要的是邻接矩阵Edge[ ][ ]、总边数edgecount和顶点数nodecount。

class Graph1{private:int nodecount。

//节点int edgecount。

//边int a[MaxNode]。

//顶点信息组//set<int> a。

int b[MaxNode][MaxNode]。

//权值信息组public:Graph1(int>。

//构造函数int 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(Graph1 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>。

插入一条边删除函数：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{private:int nodecount。