数据结构图及其应用实验.doc

实验难度： A B C 序号学号姓名成绩指导教师 （签名）学期: 2010秋季学期 任课教师: 实验题目: 图及其应用 小 组 长: 联系电话: 电子邮件: 完成提交时间：2010年1月1 日一、【实验构思（Conceive）】(10%) 1.基本思路是用无向网表示校区内的各建筑的平面图，图中顶点表示主要建筑，存放建筑的编号、名称、简介等信息，图中的边表示建筑间的道路，存放路径长度等信息。 2.将导游图看作一张带权无向图，顶点表示校园的各个建筑，边表示各建筑之间的道路，边上的权值表示距离，为此图选择适当的数据结构。 构造一个无向图G并用邻接矩阵来存储。 3.利用迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径用二维数组pi来记 录，最短路径长度就用一维数组di存放；i的范围：020。 4.一维数组have可用来记录最短路径出现顶点的顺序。根据起点和终点输出最短路径和路径长度。 二、【实验设计(Design)】(20%) 1、深度优先遍历： void dfs(int i) int j; coutvi ; visitedi=true; for(j=1;j=n;j+) if(arcsij=1)&(!visitedj) dfs(j);2、广度优先遍历： void bfs(int i) int qn+1; int f,r,j; f=r=0; coutvi ; visitedi=true; r+;qr=i; while(fr) f+;i=qf; for(j=1;j=n;j+) if(arcsij=1)&(!visitedj) coutvj ; visitedj=true; r+;qr=j; 3、主函数：void main() int i,j;graph g; int yn=1; g.creatadj();printf(用邻接矩阵表示出校园主要建筑图如下：n); for(i=1;i=n;i+) for(j=1;j=n;j+) coutg.arcsij ; coutendl; while(yn=1) for(i=1;i=n;i+) visitedi=false; couti; coutendl; cout从i输出的深度优先遍历序列为aendl; g.dfs(i)； coutendlyn; yn=1; while(yn=1) for(i=1;i=n;i+) visitedi=false; couti; coutendl; cout从i输出的广度优先遍历序列为aendl; g.bfs(i); coutendlyn; 三、【实现描述（Implement）】(30%)1图的抽象数据类型定义为：ADT Graph 数据对象V：顶点集数据关系R：R=VR VR=|v,wV,表示从v到w的弧基本操作：CreateGraph(&G,V,VR); /构造图DestroyGraph(&G); /销毁图LocateVex(G,u); /顶点u在图中位置GetVex(G,v)；/取顶点v的值PutVex(&G,v,value); /顶点v赋值FirstAdjVex(G,v); /v的第一个邻接点NextAdjVex(G,v,w); /v相对于w的下一个邻接点InsertVex(&G,v); /增添顶点vDeleteVex(&G,v); /删除顶点v及相关弧InsertArc(&G,v,w); /增添弧DeleteArc(&G,v,w); /删除弧DFSTraverse(G,v,Visit(); /深度优先搜索DFSBFSTraverse(G,v,Visit(); /广度优先搜索BFS2.用无向网表示校区内的各建筑的平面图，图中顶点表示主要建筑，存放建筑的编号、名称、简介等信息，图中的边表示建筑间的道路，存放路径长度等信息。 将导游图看作一张带权无向图，顶点表示校园的各个建筑，边表示各建筑之间的道路，边上的权值表示距离，为此图选择适当的数据结构。把各种路径都显示给用户，由用户自己选择浏览路线。 3.流程图：四、【测试结果（Testing）】(10%)根据所给出的导游图输入顶点信息1-12共12个顶点，然后根据所给出的学校重要建筑信息输入边信息：第一条边至第15条边的邻接顶点分别为：1,2， 1，3， 2，3， 2，5； ，3，4，4，7，5，6， 6，7，5，9，6，9，7，8， 8，10， 10，11， 10，12， 9，12。显示遍历结果：输入深度优先遍历开始访问的顶点 2显示结果：2 1 3 4 7 6 5 9 12 10 8 11输入深度优先遍历开始访问的顶点 5显示结果：5 2 1 3 4 7 6 9 12 10 8 11输入广度优先遍历开始访问的顶点 4显示结果：4 3 7 1 2 6 8 5 9 10 12 11五、【实验总结】(10%) 本次实验使用无向网表示校区内的各建筑的平面图，使用邻接矩阵来存储，通过先关遍历算法函数对图进行遍历。这使我学习到了图的基本存储方式和相关算法。通过这将导游图看作一张带权无向图，顶点表示校园的各个建筑，边表示各建筑之间的道路，为此图选择适当的数据结构。另外，使用抽象数据类型将算法分成模块形式，不仅降低了程序的复杂程度，同时也增强了程序的可读性，使对程序的分析难度降低。调试时应自底向上，先调试底层模块，再调试上层模块。最后，整个程序进行联合调试。在实验过程中我遇到了很多小困难，比如对错误的分析等。但是在实验中通过查找资料，询问同学，我又复习和学习了很多东西。同时我也深刻认识到，书本上的知识只有通过自己实践才能记得牢学得透。六、【项目运作描述（Operate）】(10%) 本次实验设计的主要是根据校园内的主要道路建筑示意图，对导游图上的各个节点分别进行深度和广度遍历，同时显示遍历结果。建筑物用数字表示，可以根据提示说明知道建筑物的名字，如1表示西一门。本项目操作简便，显示清晰易懂。七、【代码】(10%)#includeusing namespace std;const int n=12;const int e=15;#define elemtype int bool visitedn+1;class graphpublic: elemtype vn+1; int arcsn+1n+1;void creatadj()int i,j,k;cout *校园图*endl;cout以下是学校的重要建筑endl;cout *endl;cout * 1东门 2.南二门 *endl;cout * 3.校医院 4.力行楼 *endl;cout * 5.南一门 6.知味堂 *endl;cout * 7.格物楼 8.仰止楼 *endl;cout * 9.风雨操场 10.中邦楼 *endl;cout * 11.文汇楼 12.西门 *endl;cout *endl;cout下面是景点与景点之间的距离和介绍:n;cout1. 东门 -2. 南二门 距离为：500米endl;cout2. 南二门 -3. 校医院 距离为：400米endl;cout1. 东门 -3. 校医院 距离为：300米endl;cout3. 校医院 -4. 力行楼 距离为：400米endl;cout3. 校医院 -4. 力行楼 距离为：400米endl;cout4. 力行楼 -7. 格物楼 距离为：400米endl;cout2. 南二门 -5. 南一门 距离为：200米endl;cout5. 南一门 -6. 知味堂 距离为：100米endl;cout6. 知味堂 -7. 格物楼 距离为：150米endl;cout6. 知味堂 -9. 风雨操场 距离为：200米endl;cout5. 南一门 -9. 风雨操场 距离为：400米endl;cout7. 格物楼 -8. 仰止楼 距离为：500米endl;cout8. 仰止楼 -10.中邦楼 距离为：400米endl;cout10.中邦楼 -11.文汇楼 距离为：200米endl;cout10.中邦楼 -12.西门 距离为：200米endl;cout9. 风雨操场-12.西门 距离为：600米endl;/校园图 cout请输入n个顶点信息endl; for(k=1;kvk; for(i=1;i=n;i+) for(j=1;j=n;j+) arcsij=0; for(k=1;k=e;k+) cout请输入第k条边，共eij; coutendl; arcsij=1; arcsji=1; void dfs(int i) int j; coutvi ; visitedi=true; for(j=1;j=n;j+) if(arcsij=1)&(!visitedj) dfs(j); void bfs(int i) int qn+1; int f,r,j; f=r=0; coutvi ; visitedi=true; r+;qr=i; while(fr) f+;i=qf; for(j=1;j=n;j+) if(arcsij=1)&(!visitedj) coutvj ; visitedj=true; r+;qr=j; ;void main() int i,j;graph g; int yn=1; g.creatadj();printf(用邻接矩阵表示出校园主要建筑图如下：n); for(i=1;i=n;i+) for(j=1;j=n;j+) coutg.arcsij ; coutendl; while(yn=1) fo