搜索
1（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度：B□序号学号姓名成绩指导教师（签名）学期：2010秋季学期任课教师:实验题目:图及其应用小组长:联系电话:电子邮件:完成提交时间：2010年12月27日云南大学软件学院数据结构实验报告2一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）本次实验的主要目的在于熟悉图这种数据结构的表示和应用，学会运用图对实际问题进行建模和设计，以便在实际问题背景下灵活运用图和抽象数据类型的基本操作。具体要求如下：根据云南大学呈贡校区主要道路建筑示意图，测量出主要建筑（教学楼、办公楼、食堂、学生宿舍、运动场、乘车点等）之间的距离。以图为工具，建立模型，用户（师生）通过终端可询问：从某一建筑到另一建筑的最短路径，用户从校园某处（由用户选定）进入，选取一条最佳路线，使用户可以不重复地浏览各建筑，最后回到出口（出口就在入口旁边）。基本思路：用无向网表示校区内的各建筑的平面图，图中顶点表示主要建筑，存放建筑的编号、名称、简介等信息，图中的边表示建筑间的道路，存放路径长度等信息。将导游图看作一张带权无向图，顶点表示校园的各个建筑，边表示各建筑之间的道路，边上的权值表示距离，为此图选择适当的数据结构。把各种路径都显示给用户，由用户自己选择浏览路线。首先用指针数组存储景点信息，即图中顶点和边的信息。景点数据信息由程序指定存储，然后采用迪杰斯特拉算法求出最短路径，即从人口出发，顺着某一条边开始循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合置，求得一条通路。最后调用子函数将路径结果和景点信息打印出来。算法思想：首先构造一个无向图G并用邻接矩阵来存储，建立一个指针数组将图的信息存储起来。然后利用迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径用二维数组p[v][w]来记录，最短路径长度就用一维数组D[w]存放。即从人口出发，顺着某一条边开始循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合置，求得一条通路。根据起点和终点输出最短路径和路径长度，最后调用子函数将路径结果打印出来。对于用户查询的景点信息，通过指针直接访问该图中的顶点，并将该顶点中存储的信息显示出来。二、【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系）抽象数据类型：typedefstructArcCell{intadj;//相邻接的景点之间的距离}ArcCell;//定义边的类型typedefstructVertexType{intnumber;//景点编号char*sight;//景点名称char*info;//景点描述}VertexType;//定义顶点的类型3typedefstruct{VertexTypevex[NUM];//图中的顶点，即为景点ArcCellarc[NUM][NUM];//图中的边，即为景点间的距离intvexnum,arcnum;//顶点数，边数}MGraph;//定义图的类型voidmain()//主函数,主要就是调用图的建立函数和路径求解函数等charMenu()//主菜单函数，为用户提供人性化的选择，然后调用相应的函数voidCreate(intv,inta)//创建图函数，构造一个无向图G并用邻接矩阵来存储，建立一个指针数组将图的信息存储起来，包括景点的序号、名称和介绍voidList()//景点列表函数，利用for循环将顶点的信息即景点的序号和名称全部打印出来voidPath(intnum)//迪杰斯特拉算法最短路径函数num为入口点的编号，利用循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合，求得一条最短的路径voidOutput(intsight1,intsight2)//输出函数，输出景点的名称和sight1到sight2的最短路径长度，存放在D[]数组中voidHaMiTonian(intm)//哈密尔顿图的遍历，递归遍历图中的各个顶点，求最短路径voiddisplay()//显示哈密尔顿图的遍历的结果，打印出最短路径函数的调用关系：三、【实现描述（Implement）】(30%)（本部分应包括：抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。）函数设计：voidmain()//主函数{intv0,v1;inti,num;4charflag;Create(NUM,11);do{flag=Menu();switch(flag){case'1':system(cls);//执行系统命令，清楚先前屏幕显示的内容List();//输出景点列表printf(\n\n\t请选择起点景点（0～26）：);scanf(%d,&v0);printf(\t请选择终点景点（0～26）：);scanf(%d,&v1);Path(v0);//计算两个景点之间的最短路径Output(v0,v1);//输出结果printf(\n\n\t请按任意键继续...\n);getchar();//利用getchar()函数让程序运行到上一行时，等待按下下一个键才返回getchar();break;case'2':system(cls);List();//输出景点列表printf(\n\n\t请输入您要查找的景点编号：);scanf(%d,&num);for(i=0;iNUM;i++){if(num==G.vex[i].number){printf(\n\n\t您要查找景点信息如下:);printf(\n\n\t%s:,G.vex[i].sight);printf(\t%s\n\n,G.vex[i].info);printf(\n\t按任意键返回...);getchar();getchar();break;}}if(i==NUM){printf(\n\n\t没有找到！);printf(\n\n\t按任意键返回...);getchar();getchar();}break;}}while(flag!='0');}5charMenu()//主菜单{charc;intflag;do{flag=1;system(cls);List();//输出景点列表printf(\n\t\t\t┏━━━━━━━━━━━━━━━┑\n);printf(\t\t\t┃┃\n);printf(\t\t\t┃1、查询景点路径┃\n);printf(\t\t\t┃2、查询景点信息┃\n);printf(\t\t\t┃0、退出┃\n);printf(\t\t\t┃┃\n);printf(\t\t\t┗━━━━━━━━━━━━━━━┛\n);printf(\t请输入您的选择：);scanf(%c,&c);if(c=='1'||c=='2'||c=='0')flag=0;}while(flag);returnc;}voidCreate(intv,inta)//创建图函数{inti,j;G.vexnum=v;//初始化结构中的景点数和边数G.arcnum=a;for(i=0;iG.vexnum;++i)G.vex[i].number=i;//初始化每一个景点的编号//初始化没一个景点名及其景点描述G.vex[0].sight=云大西二门;G.vex[0].info=云南大学西二门是目前云南大学主要的进出口;G.vex[1].sight=百家道;G.vex[1].info=正对西二门的一条大道，直接通向校园各个地方;G.vex[2].sight=文典广场;G.vex[2].info=学校举行重大活动的广场，另外还在这里举行升国旗仪式;G.vex[3].sight=云大会堂;G.vex[3].info=这里是学校举行重要典礼和仪式的室内场所以及学生活动中心;G.vex[4].sight=中山邦翰楼;G.vex[4].info=教学楼，一楼设有学生事务中心，是学生处和教务处的办公所在地;G.vex[5].sight=仰止楼;6G.vex[5].info=云南大学图书馆;G.vex[6].sight=桦苑;G.vex[6].info=研究生宿舍生活区;G.vex[7].sight=楠苑;G.vex[7].info=经济学院、信息学院、体育学院、商旅学院、城建学院、数统学院和中加合作项目等学院的学生宿舍生活区;G.vex[8].sight=格物楼;G.vex[8].info=综合教学楼和自习室，一般是理工科学院的学生上公共课和自习;G.vex[9].sight=楠苑体育场;G.vex[9].info=学生上体育课和进行体育锻炼的地方，目前设有篮球场、网球场、排球场和田径场;G.vex[10].sight=知味堂;G.vex[10].info=学生餐厅，设有二个一般食堂、一个风味食堂和一个清真食堂;G.vex[11].sight=楠苑超市;G.vex[11].info=云南大学后勤教育超市之一，为学生提供各种生活学习用品;G.vex[12].sight=综合服务楼;G.vex[12].info=综合服务中心，一楼设有超市、药店、眼镜店、饰品店、农行ATM机和茶室，三楼是学校学生会、自律委、社联等各校级的办公室;G.vex[13].sight=楸苑;G.vex[13].info=软件学院、物科学院、化工学院、生科学院和资环学院等学院的学生宿舍生活区;G.vex[14].sight=力行楼;G.vex[14].info=公共教学楼，一楼设有公共机房;G.vex[15].sight=软件楼;G.vex[15].info=软件学院行政办公楼和实验楼;G.vex[16].sight=校医院;G.vex[16].info=学生医疗场所;G.vex[17].sight=明远楼;G.vex[17].info=教学楼，尚在建设当中;G.vex[18].sight=至公大道;G.vex[18].info=正对学校正大门的道路;G.vex[19].sight=行政办公楼;G.vex[19].info=学校行政办公部门所在地;G.vex[20].sight=云大北门;G.vex[20].info=学校正大门;G.vex[21].sight=文汇楼;G.vex[21].info=文科学院教学楼;G.vex[22].sight=余味堂;7G.vex[22].info=学生吃饭的地方，设有二个一般食堂和一个清真食堂;G.vex[23].sight=梓苑超市;G.vex[23].info=超市，为学生提供各种生活学习用品;G.vex[24].sight=梓苑;G.vex[24].info=公管学院、人文学院、艺术学院、外国语学院和法学院的学生生活区;G.vex[25].sight=钟楼;G.vex[25].info=云大标志性建筑之一，每天上课的钟声从这里响起;G.vex[26].sight=校车乘车点;G.vex[26].info=可以在此乘坐校车至校本部;//这里把所有的边假定为10000，含义是这两个景点之间是不可到达for(i=0;iG.vexnum;++i)for(j=0;jG.vexnum;++j)G.arc[i][j].adj=Max;//下边是可直接到达的景点间的距离，由于两个景点间距离是互相的，所以要对图中对称的边同时赋值G.arc[0][1].adj=G.arc[1][0].adj=10;G.arc[1][2].adj=G.arc[2][1].adj=20;G.arc[2][3].adj=G.arc[3][2].adj=20;G.arc[1][4].adj=G.arc[4][1].adj=50;G.arc[4][5].adj=G.arc[5][4].adj=200;G.arc[4][6].adj=G.arc[6][4].