数据结构实验图.docx
- 文档编号:16851087
- 上传时间:2023-07-19
- 格式:DOCX
- 页数:19
- 大小:224.70KB
数据结构实验图.docx
《数据结构实验图.docx》由会员分享,可在线阅读,更多相关《数据结构实验图.docx(19页珍藏版)》请在冰点文库上搜索。
数据结构实验图
实验7:
图的应用
一、实验目的
图是应用极为广泛的数据结构,也是这门课程的重点,继续使学生更了解数据结构加操作的程序设计观点。
二、问题描述
给出一张某公园的导游图,游客通过终端询问可知:
a)从某一景点到另一个景点的最短路径。
b)游客从公园大门进入,选一条最佳路线,使游客可以不重复的游览各景点,最后回到出口。
三、实验要求
1、将导游图看作一张带权无向图,顶点表示公园的各个景点,边表示各景点之间的道路,边上的权值表示距离,选择适当的数据结构。
2、为游客提供图中任意景点相关信息的查询;
1、为游客提供任意两个景点之间的一条最短的简单路径。
2、为游客选择最佳游览路径。
四、实验环境
PC微机
DOS操作系统或Windows操作系统
TurboC程序集成环境或VisualC++程序集成环境
五、实验步骤
1、设计公园平面图,图中顶点表示公园的各个景点,存放名称、代号、简介等信息;边表示各景点之间的道路,边上的权值表示距离,选择适当的数据结构;
2、设计图的最短路径算法,如果有几条路径长度相同,选择途径景点较少的路径给游客;
3、设计图的深度优先搜索算法,如果有多种路径可选,则选带权路径最短的路线给游客;
4、选择适当语言实现算法;
3、调试程序。
六、测试数据
可根据实际情况指定。
测试数据见南昌大学平面示意图。
七、实验报告要求
1、问题描述;
该程序包扩以下内容:
(1)设计学校的校园平面图,所含景点为9个。
(2)以图中顶点表示校内各景点,存放景点名称、代号、间介等信息;以边表示路径,存放路径长度等相关信息。
(3)为来访客人提供图中任意景点相关信息的查询。
(4)提供途中任意景点问路查询,即求任意两个景点间的一条最短的简单路径。
(5)提供途中任意景点问路查询,即求任意两个景点间的所有路径。
(6)提供校园图中多个景点的最佳访问路线查询,即求途经这多个景点的最佳(短)路径。
设计思路:
对系统功能抽象,分析问题描述。
首先,平面图用输出模拟;存储景点信息采用结构体;对各景点用字母代替,字母组成图,通过对图的操作,狄克斯特拉算法求出指定最短路径及一点到其它所有点的最短路径,递归进行图的遍历求两点所有路径。
由此可实现以上所有功能。
2、图的建立
图的建立:
这是一个无向带权图,实际上无向带权图与有向带权图相似,采用邻接矩阵存储比较方便。
邻接矩阵的结点结构体如下:
其赋值如下:
3、图的最短路径算法
算法思想:
设置两个结点集合S和T,集合S中存放已找到的最短路径的结点,集合T中存放当前还没找到的最短路径的结点。
初始状态时,集合S中只包含源点,没为v0,然后不断的从集合T中选择到源点v0的路径长度最短的结点u加入到集合S中,集合S中每加入一新的结点u,都要修改源点v0到集合T中剩余结点的当前最短路径长度值,集合T中各点的新的当前最短路径长度值为原来的当前最短路径长度值,与结点u的最短路径长度值加上结点u到该结点的路径长度值(即为从源点结点u到达该结点的路径长度)中的较小者。
此过程不断重复,直到集合T中的对号点全部加到集合S中为止。
算法实现如下:
voidDijkstra(MGraphg,intv,intto)
"<<<<"\n简介:
"<<< } voidbrowse()览学校景点2.查找单个景点信息│"< cout<<"│3.学校地图平面示意图4.路线推荐│"< cout<<"│5.景点最短线路6.两景点所有路径│"< cout<<"│7.退出系统│"< cout<<"└────────────────────────────────┘"< } voidFunMenue2()学校大门B.和平女神像"< cout<<"C.体育馆D.游泳馆"< cout<<"E.商业街F.教学主楼"< cout<<"G.正气广场H.图书馆"< cout<<"I.天健园"< } SightC_IN2()//字母转换为景点 { charkey; cin>>key; switch(key) { case'A': returnA;break; case'B': returnB;break; case'C': returnC;break; case'D': returnD;break; case'E': returnE;break; case'F': returnF;break; case'G': returnG;break; case'H': returnH;break; case'I': returnI;break; default: cout<<"您的输入有误! 请选择A~I! \n";system("pause");system("cls");FunMenue2();C_IN2(); } } intSprint(charitem)//对字母表示的景点输出 { switch(item) { case'A': cout<<<<;break; case'B': cout<<<<;break; case'C': cout<<<<;break; case'D': cout<<<<;break; case'E': cout<<<<;break; case'F': cout<<<<;break; case'G': cout<<<<;break; case'H': cout<<<<;break; case'I': cout<<<<;break; default: cout<<"无此景点\n";return1;break; } return0; } #endif //构造图及图的相关操作,由狄克斯拉算法改成。 #include"" #defineMAXV100 #defineINF32767 typedefintInfoType; //邻接矩阵存储方法 typedefstruct { intedges[MAXV][MAXV]; intn; }MGraph; //狄克斯特拉算法 voidPpath(intpath[],inti,intv) { intk; k=path[i]; if(k==v)return; Ppath(path,k,v); Sprint(k+'A'); cout< } voidDispath(intdist[],intpath[],ints[],intn,intv,inti)//对最短路径输出 { if(s[i]==1) { cout<<""; Sprint(v+'A'); cout< Sprint(i+'A'); cout< "< "; Sprint(v+'A'); cout< Ppath(path,i,v); Sprint(i+'A'); cout< } else cout<<"从"< cout<<"────────────────────────────────────"; } voidDijkstra(MGraphg,intv,intto)//Dijkstrag图中v为起点求出到所有点的最短路径 { intdist[MAXV],path[MAXV];//dist存路径path存顶点 ints[MAXV];//标记 intmindis,i,j,u; for(i=0;i<;i++) { dist[i]=[v][i]; s[i]=0; if[v][i] elsepath[i]=-1; } s[v]=1;path[v]=0; for(i=0;i<;i++) { mindis=INF; for(j=0;j<;j++) { if(s[j]==0&&dist[j] { u=j; mindis=dist[j]; } } s[u]=1; for(j=0;j<;j++) { if(s[j]==0) { if[u][j] { dist[j]=dist[u]+[u][j]; path[j]=u; } } } } Dispath(dist,path,s,,v,to); } voidDijkstra(MGraphg,intv)//重载,当只有一点求最短路径时,用到 { intto; for(to=0;to<;to++) { if(to==v)continue; Dijkstra(g,v,to); } } ////////////////////////////////////////////////////////////////////////////// intpath[10]; intpathF[10]={0}; intBPsize=0; intEofV(MGraphg,intstart) { intcon=0; for(intj=0;j<;j++) if[start][j]! =0&&[start][j] con++; returncon; } intNest(MGraphg,intstart,inti) { intcon=0; for(intj=0;j<;j++) { if[start][j]! =0&&[start][j] con++; if(con==i) returnj; } return0; } voidPrint(MGraphg)//打印找到路径 { intTVal=0; for(intj=0;j { TVal=TVal+[path[j]][path[j+1]]; Sprint(path[j]+'A'); cout<<"---->"; } Sprint(path[j]+'A'); cout<<"\n总长: "< } voidFindAllWay(MGraphg,intstart,intend,intn)//寻找所有路径 { inti; if(start==end) { path[n]=start; BPsize=n+1; Print(g); return; } intnum=EofV(g,start); path[n]=start; for(i=1;i<=num;i++) { if(pathF[Nest(g,start,i)]! =1) { pathF[start]=1; FindAllWay(g,Nest(g,start,i),end,n+1); pathF[start]=0; } } } ////////////////////////////// //Shortest函数 intShortest(intchoice)//最短路径函数 { charfrom,to; inti,j,n; MGraphg;n=9;//图信息 for(i=0;i for(j=0;j if(i! =j) [i][j]=32767; else [i][j]=0; [0][1]=[1][0]=100; [0][2]=[2][0]=500; [0][6]=[6][0]=200; [0][7]=[7][0]=350; [2][3]=[3][2]=150; [3][5]=[5][3]=250; [4][5]=[5][4]=200; [4][8]=[8][4]=800; [5][7]=[7][5]=600; [6][7]=[7][6]=400; [7][8]=[8][7]=300; =n; if(choice==5) { cout<<"请输入起点和终点: "< cin>>from>>to; cout<<"+++++++++++++++++++++++++++++竭诚为您提供最短路径+++++++++++++++++++++++++++++++"; i=from-'A';j=to-'A'; Dijkstra(g,i,j); cout< } if(choice==4) { cout<<"请输入起点: "< cin>>from; system("cls"); cout<<"++++++++++++++++++++++我为您提供这里到学校其它景点最好选择++++++++++++++++++++++"; cout<<"您选择了"; if(Sprint(from)==1)return0; cout<<"为起点\n"; i=from-'A'; Dijkstra(g,i); cout< } if(choice==6) { cout<<"请输入起点和终点: "< charfrom,to; cin>>from>>to; intf,t; f=from-'A'; t=to-'A'; FindAllWay(g,f,t,0); } return0; } #include"" #include"" voidexc(); voidC_IN(void)//对主选单操作 { charkey; cin>>key; switch(key) { case'1': browse();break; case'2': FunMenue2();S_print(C_IN2());system("pause");system("cls");break; case'3': Gprint();break; case'4': FunMenue2();Shortest(4);system("pause");system("cls");break; case'5': FunMenue2();Shortest(5);system("pause");system("cls");break; case'6': FunMenue2();Shortest(6);system("pause");system("cls");break; case'7': cout<<"\n\n------欢迎您的到来,谢谢您的使用! ---------\n"; cout<<"学校主页: "; exc(); default: cout<<"您的输入有误! 请选择1~4! \n";system("pause");system("cls");FunMenue();C_IN(); } } voidexc() { cout<<"确认退出(Y/N): "; charkey; cin>>key; while(key! ='Y'&&key! ='N') cin>>key; if(key=='Y') exit (1); if(key=='N') {system("cls");FunMenue();C_IN();} } intmain()//主函数 { while (1) { FunMenue(); C_IN(); } return0; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验