数据结构课程设计 图的遍历.docVIP

数据结构课程设计 图遍历的演示 题5.3 图遍历的演示 实习报告 题目:试设计一个程序,演示在连通和非连通的无向图上访问全部结点的操作 班级：04计算机科学与技术1班 姓名：胡海洪 学号：3104006429 完成日期：06年7月一、需求分析 1、以邻接多重表为存储结构； 2、实现连通和非连通的无向图的深度优先和广度优先遍历； 3、要求利用栈实现无向图的深度优先遍历； 4、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和生成树的边集； 5、用凹入表打印生成树； 6、求出从一个结点到另外一个结点，但不经过另外一个指定结点的所有简单路径； 6、本程序用C++语言编写，在TURBO C++ 3.0环境下通过。 二、概要设计 1、设定图的抽象数据类型: ADT Graph{ 数据对象V:V是具有相同特性的数据元素的集合,称为点集. 数据关系R: R={VR} VR={(v,w)|v,w属于V,(v,w)表示v和w之间存在的路径} 基本操作P: CreatGraph(G,V,VR) 初始条件:V是图的顶点集,VR是图中弧的集合. 操作结果:按V和VR是定义构造图G. DestroyGraph(G) 初始条件:图G存在 操作结果:销毁图G LocateVex(G,u) 初始条件: 图G存在,u和G中顶点有相同的特征 操作结果:若图G中存在顶点u,则返回该顶点在图中的位置;否则返回其他信息 GetVex(G,v) 初始条件: 图G存在,v是G中顶点 操作结果:返回v的值 FirstAjvex(G,v) 初始条件: 图G存在,v是G中顶点 操作结果:返回v的第一个邻接顶点,若顶在图中没有邻接顶点,则返回为空 NextAjvex(G,v,w) 初始条件: 图G存在,v是G中顶点,w是v的邻接顶点 操作结果:返回v的下一个邻接顶点,若w是v的最后一个邻接顶点,则返回空 DeleteVexx(G,v) 初始条件: 图G存在,v是G中顶点 操作结果:删除顶点v已经其相关的弧 DFSTraverse(G,visit()) 初始条件: 图G存在,visit的顶点的应用函数 操作结果: 对图进行深度优先遍历,在遍历过程中对每个结点调用visit函数一次,一旦visit失败,则操作失败 BFSTraverse(G,visit()) 初始条件: 图G存在,visit的顶点的应用函数 操作结果:对图进行广度优先遍历,在遍历过程中对每个结点调用visit函数一次,一旦visit失败,则操作失败 }ADT Graph 2、设定栈的抽象数据类型： ADT Stack{ 数据对象：D={ai | ai∈CharSet，i=1，2，……，n，n≥0} 数据关系：R1={ai-1,ai | ai-1,ai∈D,i=2，……，n} 基本操作： InitStack(S) 操作结果：构造一个空栈S。 DestroyStack(S) 初始条件：栈S已存在。 操作结果：栈S被销毁。 Push(S,e); 初始条件：栈S已存在。 操作结果：在栈S的栈顶插入新的栈顶元素e。 Pop(S,e); 初始条件：栈S已存在。 操作结果：删除S的栈顶元素，并以e返回其值。 StackEmpty(S) 初始条件：栈S已存在。 操作结果：若S为空栈，则返回TRUE，否则返回FALSE。 }ADT Stack 3、设定队列的抽象数据类型： ADT Queue{ 数据对象:D={ai|ai属于Elemset,i=1,2….,n,n=0} 数据关系:R1={ai-1,ai|ai-1,ai属于D,i=1,2,…,n} 约定ai为端为队列头,an为队列尾 基本操作: InitQueue(Q) 操作结果:构造一个空队列Q DestryoQueue(Q) 初始条件：队列Q已存在。 操作结果：队列Q被销毁，不再存在。 EnQueue(Q,e) 初始条件:队列Q已经存在 操作结果:插入元素e为Q的新的队尾元素 DeQueue(Q,E) 初始条件:Q为非空队列 操作结果:删除Q的队尾元素,并用e返回其值 QueueEmpty(Q) 初始条件:队列已经存在 操作结果:若队列为空,则返回TRUE,否则返回FLASE }ADT Queue 4、本程序包含九个模块： 主程序模块 void main () { 手动构造一个图； 从文件导入一个图； 显示图的信息； 进行深度优先遍历图； 进行广度优先遍历图； 保存图到一个文件； 寻找路径； 销毁一个图； }； 手动构造一个图-自己输入图的顶点和边生成一个图； 从文件导入一个图； 显示图的信息-打印图的所有顶点和边； 进行深度优先遍历图-打出遍历的结点序列和边集； 进行广度优先遍历图-打出