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

数据结构 课程设计报告 设计题目： 图的邻接矩阵存储结构 年 级 x 级 学 生 xxxx 学 号 xxxxxxxxxx 指导教师 xxxxxxxxx 起止时间 10-6/10-10 2013年10月10日 目 录 1 需求分析 4 2 概要设计 4 2.1 ADT描述 4 2.2程序模块结构 5 2.3　各功能模块 6 3　详细设计 7 3.1类的定义 7 3.2 初始化 8 3.3 图的构建操作 8 3.4 输出操作 9 3.5 get操作 9 3.6 插入操作 10 3.7 删除操作 10 3.8 求顶点的度操作 11 3.9 深度遍历作……………………………………………………………………………...113.10 判断连通操作 12 3.11 主函数 13 4 调试分析 16 4.1调试问题 16 4.2 算法时间复杂度 16 5　用户手册 16 5.1主界面 16 5.2 创建图 17 5.3插入节点 17 5.4 深度优先遍历 17 5.5 求各顶点的度 18 5.6 输出图 18 5.7 判断是否连通 19 5.8 求边的权值 19 5.9 插入边 19 5.10 删除边 20 结 论 20 参考文献……………………………………………………………………………………………………………………………………..20 1 需求分析 随着计算机的普及,信息的存储逐渐和我们的日常生活变得密切起来，而数据的存储方式也多种多样，比如树、链表、数组、图等等。 为了充分体现图的矩阵储存结构的优势与功能，要求本系统应达到以下要求： 图是无向带权图 能从键盘上输入各条边和边上的权值； 构造图的邻接矩阵和顶点集。 输出图的各顶点和邻接矩阵 插入一条边 删除一条边 求出各顶点的度 判断该图是否是连通图，若是，返回1；否则返回0. 使用深度遍历算法，输出遍历序列。 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];//顶点信息组 //setint 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); //建立图 };构造函数Graph1(int) 用于初始化图 get函数：int getNodeCount();