数据结构图及其应用实验

《数据结构图及其应用实验》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、序号学号姓名成绩指导教师(签名)学期：2010秋季学期任课教师:实验题目:图及其应用小组长:联系电话:电子邮件：完成提交时间：2010年1月1日一、【实验构思(Conceive)](10%)1.基本思路是用无向网表示校区内的各建筑的平面图，图中顶点表示主要建筑，存放建筑的编号、名称、简介等信息，图中的边表示建筑间的道路，存放路径长度等信息。1.将字游图看作一张带权无向图，顶点表示校园的各个建筑，边表示各建筑之间的道路，边上的权值表示距离，为此图选择适当的数据结构。构造一个无向图G并用邻接矩阵来存储。2.利用

2、迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径用二维数组p[i][]来记录，最短路径长度就用一维数组d[订存放；i的范围：0〜20o3.一维数组have[]可用来记录最短路径出现顶点的顺序。根据起点和终点输出最短路径和路径长度。二、【实验设计(Design)](20%)1、深度优先遍历：voiddfs(inti){intj;cout«v[i]«/，“；visitcd[i]=truc;for(j=l;j<=n;j++)if((arcs[i][j]=l)&&(!visited[j]))dfs(j);}2、广

3、度优先遍历：voidbfs(inti){intq[n+l];intf,r,j;f=r=0;cout«v[i]«"visited[i]=true;r++;q[r]=i;while(f

4、ntfC用邻接雉阵表示出校园主要建筑图如下：〃)；for(i=l;i<=n;i++){for(j=l;j<=n;j++)cout«g.arcs[i][j]V“；cout<

5、>〉yn;}yn=l;while(yn-=l){for(i=l;i<=n;i++)visited[i]二false;cout«/z请输入广度优先遍历开始访问的建筑顶点〃；cin>>i;cout<>yn;}}三、【实现描述(Implement)1(30%)1.图的抽象数据类型定义为：ADTGraph{数据对象V:顶点集数据关系R:R二{VR}VR={

6、>

7、v,wgV,表示从v到w的弧}基本操作：CreateGraph(&G,V,VR);//构造图DestroyGraph(&G);//销毁图LocateVex(G,u);//顶点u在图中位置GetVex(G,v);//取顶点v的值PutVex(&G,v,vaIue);//顶点v赋值FirstAdjVex(G,v);//v的第一个邻接点NextAdjVex(G,v,w);//v相对于w的下一个邻接点InsertVex(&G,v);//增添顶点vDeIeteVex(&G,v);//删除顶点v及相关弧I

8、nsertArc(&G,v,w);//增添弧DeIeteArc(&G,v,w);//删除弧DFSTraverse(G,v,Visit0);//深度优先搜索DFSBFSTraverseCG,v,Visit());//广度优先搜索BFS}1.用无向网表示校区内的各建筑的平面图，图中顶点表示主要建筑，存放建筑的编号、名称、简介等信息，图中的边表示建筑间的道路，存放路径长度等信息。将导游图看作一张带权无向图，顶点表示校园的各个建筑，边表示各建筑之间的道路，边上的权值表示距离，为此图选择适当的数据

9、结构。把各种路径都显示给用户，由用户自己选择浏览路线。2.流程图:开冶)四、【测试结果(Testing)](10%)C:UsersYapengGuoDesktopccDebugccexesftT南盘仰M.B■■■■02246811「医-物弊格学"W?----1135791m5^c««mm丿K丿K丿K丿K丿K丿K丿K丿K丿K、yT、7T7T7T7T、yT、7T、7T、yT0000000000000