实习报告
题目：编制一个演示图种遍历输出输出的题目：编制一个演示图构建和2种遍历输出的操作的程序班级：计算机（信息安全）姓名：学号：完成日期：班级：计算机（信息安全）姓名：学号：完成日期：2009514
一．需求分析
1本演示程序中，元素限定为char型。2演示程序以用户和计算机的对话方式执行，即在计算机终端显示“提示信息“后，由用户在键盘上输入符合演示程序中规则的图的边数，结点数；相应的先序和按层遍历会显示其后。3程序执行命令包括：1）根据用户给出的图字符串进行对临接表的先序构建2）输出构建的临接表4测试数据用户输入：abcde结果：DLRabcdeLDRcbdaeLRDcdbeaCe
gabecd用户输入：abcde结果：DLRabcdeLDRbdcaeLRDdcbeaCe
gabecd
二．概要设计
为实现上述程序功能，需要三个抽象数据类型：队列和图1．图的抽象数据类型定义为：ADTGraph数据对象V：顶点集：数据关系R：RVR：VRvwvw∈Vvw表示从v到w的弧的弧∈表示从基本操作操作：基本操作：CreateGraphGVVR构造图构造图DestroyGraphG销毁图销毁图LocateVexGu顶点u在图中位置顶点GetVexGv；取顶点v的值；取顶点PutVexGvvalue顶点v赋值顶点FirstAdjVexGvv的第一个邻接点NextAdjVexGvwv相对于w的下一个邻接点I
sertVexGv增添顶点v增添顶点增添DeleteVexGv删除顶点v及相关弧删除顶点I
sertArcGvw增添弧增添弧vw增添弧DeleteArcGvw删除弧删除弧vw删除弧DFSTraverseGvVisit深度优先搜索DFS深度优先搜索BFSTraverseGvVisit广度优先搜索BFS广度优先搜索
f2本程序包含四个模块：1）主程序模块：mai
初始化一个空队列；（利用CreateQueueQ函数）进入用户输入图顶点数和边数阶段；进入用户输入图的边信息阶段；根据用户输入的图的边信息进行对邻接表的构建（利用CreateGraphG这个函数）输出邻接表两种遍历输出构建的邻接表（利用DFSqiBFSG这2个函数）2图单元模块实现图抽象数据类型。3邻接表2种遍历单元模块（包含队列单元模块）4图节点结构单元模块定义图的节点结构。各模块是之间关系如下：主程序模块图单元模块邻接表2种遍历单元模块图节点结构单元模块
三．详细设计
1元素类型（此程序固定为char）结点类型typedefstructi
tbasei
ttopi
tle
gthQueue队列结点typedefstructarcNodei
tlocatestructarcNode
extarcNode边结点typedefstructVNodechardataarcNodefirstarcVNodeV20顶点结点
ftypedefsr