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

无向图的邻接矩阵存储结构数据结构课程设计报告设计题目： 图的邻接矩阵存储结构院 系 计算机学院 年 级 x 级 学 生 xxxx 学 号 xxxxxxxxxx 指导教师 xxxxxxxxx 起止时间 10-6/10-10 2013年10月10日目 录 1 需求分析42 概要设计42.1 ADT描述42.2程序模块结构52.3各功能模块63详细设计73.1类的定义73.2 初始化83.3 图的构建操作83.4 输出操作93.5 get操作93.6 插入操作103.7 删除操作103.8 求顶点的度操作113.9 深度遍历作.113.10 判断连通操作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参考文献.20摘 要 随着计算机的普及，涉及计算机相关的科目也越来越普遍，其中数据结构是计算机专业重要的专业基础课程与核心课程之一，为适应我国计算机科学技术的发展和应用，学好数据结构非常必要，然而要掌握数据结构的知识非常难，所以对“数据结构”的课程设计比不可少。本说明书是对“无向图的邻接矩阵存储结构”课程设计的说明。首先是对需求分析的简要阐述，说明系统要完成的任务和相应的分析，并给出测试数据。其次是概要设计，说明所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次关系，以及ADT描述。然后是详细设计，描述实现概要设计中定义的基本功操作和所有数据类型，以及函数的功能及代码实现。再次是对系统的调试分析说明，以及遇到的问题和解决问题的方法。然后是用户使用说明书的阐述，然后是测试的数据和结果的分析，最后是对本次课程设计的结论。关键词：网络化；计算机；对策；图；储存。 1 需求分析 随着计算机的普及,信息的存储逐渐和我们的日常生活变得密切起来，而数据的存储方式也多种多样，比如树、链表、数组、图等等。为了充分体现图的矩阵储存结构的优势与功能，要求本系统应达到以下要求：1. 图是无向带权图2. 能从键盘上输入各条边和边上的权值；3. 构造图的邻接矩阵和顶点集。4. 输出图的各顶点和邻接矩阵5. 插入一条边6. 删除一条边7. 求出各顶点的度8. 判断该图是否是连通图，若是，返回1；否则返回0.9. 使用深度遍历算法，输出遍历序列。2 概要设计 2.1 ADT描述 ADT Glist VR=图的顶点和边VR= | v,wV, 表示顶点v和w间的边；基本操作：初始化空图；输入建立图；深度优先遍历图；确定图中的顶点数目；确定图中边的数目；在图中插入一个顶点；在图中插入一条边；删除图中一个顶点删除图中的一条边；求顶点的度；求最小生成树； ADT Graph;2.2程序模块结构 图2.1：模块结构2.2.1结构体定义本系统未采用结构体方法，类的定义如下：定义顶点: nodecount，edgecount 边：已经分别存放顶点和边的两个数组： aMaxNode和 bMaxNodeMaxNode;其余成员函数均以public形式声明。在邻接矩阵表示的图中，顶点信息用一维数组表示a。在简单情况下可省略，仅以下标值代表顶点序号。若需要，顶点信息更加丰富。边（或弧）信息用二维数组表示b ，这也是邻接矩阵。包含边的权值。在类中数据成员有4个，重要的是邻接矩阵Edge 、总边数edgecount和顶点数nodecount。class Graph1 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 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;/节点 int edgecount;/边 int aMaxNode;/顶点信息组 /set a; int bMaxNodeMaxNode;/权值信息组public: Graph1(int);/构造函数 int getNodeCount();/当前的节点数 int getEdgeCount();/当前的边数 void insertNode(int);/插入一个节点 void isertEdge(int ,int ,int);/插入一条边 void 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循环将数组的值都初始化为0，使之成为一个空图。Graph1:Graph1(int s=MaxNode)/构造函数 for(int i=0;i=s-1;i+) for(int j=0;j=s-1;j+) bij=0; nodecount=0; for(int k=0;k=s-1;k+) ak=-1; 3.3 图的构建操作在主函数中要求输入需要构建的图的顶点数和边数，调用构建函数，分别用两个for语句来构建图（即输入顶点的值和边的权值），此处要求输入有一定的顺序，不能随意输入。void Graph1:CreatG(int n,int e) int i,vi,vj,w; edgecount=e; nodecount=n; coutendl 输入顶点的信息（暂设为整型）： ; for ( i=0; inodecount; i+ ) coutn i+1ai; for ( i=0; iedgecount; i+ ) /输入两个顶点编号和边权值 coutendl 输入边的信息（vi,vj,w）：vivjw; bvi-1vj-1=w; bvj-1vi-1=w; 3.4 输出操作本函数通过传过来的对象G得到相关数组，通过for循环来分别输出顶点数组和边的权值数组（邻接矩阵）。void Graph1:PrintOut(Graph1 G) int i; coutn 输出顶点的信息：endl; for ( i=0; iG.getNodeCount(); i+ ) coutG.ai ; coutendln 输出邻接矩阵： ; for ( i=0; iG.getNodeCount(); i+ ) coutendli+1: ; for ( int j=0; jG.getNodeCount() ;j+ ) coutG.bij ; coutendl; 3.5 get操作用于得到图的顶点数、边数、权值int Graph1:getNodeCount()/当前的节点数 return nodecount; int Graph1:getEdgeCount()/当前的边数 return edgecount; int Graph1:getWeight(int x,int y)/获得某条边的权值 return bx-1y-1;3.6 插入操作插入顶点：通过将传来的值（顶点值）赋到一个当前顶点数下一个的数组元素中实现插入功能，此时顶点树加1。插入边：原理与插入顶点相同，通过传过来的两个顶点信息与权值进行相应赋值，不过此时应该注意表示同一条边的两个数组都该赋值。 void Graph1:insertNode(int it)/插入一个节点 anodecount+=it; cout当前节点数为：nodecountendl; void Graph1:isertEdge(int x,int y,int w)/插入一条边 bx-1y-1=w; by-1x-1=w; cout该边插入成功! endl; edgecount+; 3.7 删除操作将相应的数组值赋为0从而达到删除目的。 void Graph1:deleteEdge(int x ,int y)/删除一条边 bx-1y-1=0; by-1x-1=0; cout边(x,y)已经成功删除!; edgecount-; 3.8 求顶点的度操作通过两个for循环来查找各顶点，判断其是否有边（权值），有边的话又有几条边，每找到一条边则度数加一，记录到存放顶点的度数的数组M中，搜索完成后输出各顶点的度。void Graph1:outDu(Graph1 G)/输出各点的度 int mMax=0,k,i; for(k=0;kG.getNodeCount();k+) for(i=0;iG.getNodeCount();i+) if(G.bki!=0) mk+; cout各点的度：endl; for(i=0;iG.getNodeCount();i+) cout顶点i的度：miendl; 3.9 深度遍历操作图的深度优先遍历DFS算法是沿着某初始顶点出发的一条路径，尽可能深入地前进，即每次在访问完当前顶点后，首先访问当前顶点的一个未被访问过的邻接顶点，然后去访问这个邻接点的一个未被访问过的邻接点，这是一个递归算法。其中第一个遍历函数Depth(int node)其主要作用是构建访问数组int v，以及调用核心遍历函数Depth(int v,int visited,int &n)，其中的n是用来记录访问的顶点数目，用于判断图的连通性。int Graph1:Depth(int node) int n=0;int vMaxNode; for(int i=0;i=nodecount-1;i+) vi=0; Depth(node,v,n); return n;/n记录访问节点数，用于判断是否连通 void Graph1:Depth(int v,int visited,int &n) cout v+1 ;/访问顶点v visitedv=1; /标记顶点v已访问n+;/n记录访问节点数 for (int col=0; colnodecount; col+) if (bvcol=0|bvcol=Max) continue; /找v一个邻接点col if (!visitedcol) Depth(col, visited,n); /调用深度递归遍历 3.10 判断连通操作通过调用遍历函数得到所能访问的顶点数n，然后判断n与当前顶点数是否相等来确认是否连通。bool Graph1:isliantong()/判断是否连通 int n=0; n=Depth(0); cout该图的总节点数为:nodecount!endl; cout其中一个连通分量连通的节点数为:n!endl; if(n=nodecount)/访问到的节点数与顶点数是否相等 return 1; else return 0; 3.11 主函数主函数的主要功能是引导构建新图的邻接矩阵存储结构，并且制作菜单、调用各个相应的功能函数。int main()system(cls);system(color 1f);system(mode con: cols=78 lines=35);cout n;cout 必做题：无向图的邻接矩阵存储结构 n;cout 姓名：xxxx n;cout 学号：xxxxxxxxx n;cout n;coutn;Graph1 G(10);int x,y,w;int node; cout你好,请依次输入图的节点数n和边数e:ne;G.CreatG(n,e);cout恭喜你!你的图已经建立成功!endl;system(pause);while(true)coutendl;coutn;cout 欢迎进入图的邻接矩阵存储结构演示系统 n;cout - n;cout 请选择您要的操作： n;cout 1.输出图 2.判断图是否连通 n;cout 3.深度优先搜索 4.求各顶点的度 n;cout 5.插入新节点 6.删除边 n;cout 7.求边的权值 8.插入新的边 n;cout 0.退出系统 n;coutn;int choice;coutendl;cout请你做出选择!choice;switch(choice)case 1: G.PrintOut(G);break;case 2:if(G.isliantong()cout该图是连通的!endl;elsecout该图不是连通的!endl;break;case 3:int node;cout请输入你选择的起始节点!node;cout深度优先搜索结果为:endl;G.Depth(node-1);coutendl;break;case 4: G.outDu(G);break;case 5:cout请输入你要插入的新节点!node;G.insertNode(node);coutendl;