校园导航实习报告

数据结构与VC编程实习

实习报告学生姓名：00学号：10081210专业班级：计算机二班指导教师：00・002011年7月20日实习题目 校园导航系统的设计一、 任务描述及要求以中国石油大学（青岛）为参照。合理设计窗口界面，首先构建中国石油大学校园示意图，在界面上以图形方式显示各个地点及之间的距离，并标记出距离的大小（距离由操作人员自行设置）。最短路径，以指定的某点位开始点，另一点为终点来实现操作。功能菜单或按钮自行设计，以合理为目的。在界面上动态显示出从起点到目的点的最短路径走法，地图可缩小、放大、移动、可显示某点的提示信息等。二、 概要设计校园旅游模型是由各个景点和景点以及场所和场所之间的路径组成的，所以这完全可以用数据结构中的图来模拟。用图的结点代表景点或场所，用图的边代表景点或场所之间的路径。首先，应该创建图。结点值代表景点信息，边的权值代表景点间的距离。本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线。计算最短路线时可用迪杰斯特拉（Dijkastra）算法算法实现。

1.抽象数据类型有：CMyView类：voidRoad_ModifyValue(CPointpoint);//修改权值voidRoad_Add(CPointpoint);〃添加路径voidRoad_Delete(CPointpoint);〃删除路径voidBuilding_add();//添加建筑voidBuilding_move(CPointpoint);//建筑移动voidBuilding_modify(CPointpoint);//建筑修改哦voidBuilding_Delete(CPointpoint);〃建筑删除voidgraph_map_move();〃地图移动voidgraph_map_bigger();〃地图放大voidgraph_map_smaller();〃地图缩小voidpath_f(CPointpoint);//寻找最短路径的全局函数intshortestPath(inti,intj,intn);〃最短路径查找算法dijskavoidDraw_graph_Verges(CDC*pDC);//画建筑节点voidDraw_graph_Edges(CDC*pDC);〃画无向边，即道路voidDraw_graph_kuangjia(CDC*pDC);//画整体框架voidDraw_graph_kuangjia_1(CDC*pDC);〃框架1voidDraw_graph_kuangjia_2(CDC*pDC);〃框架2voidDraw_graph_direction(CDC*pDC);//画方向〃北〃intFind_Verge(CPointp); //对坐标p寻找其对应节点的序号，找不到返回-1Graph类：(画图类)voidmake_tu(); 〃初始化总函数，里面调用了voidmake_iniVerges();//初始化节点voidmake_iniEdges();//初始化图的边Node类：(节点类)Node();virtual~node();intx1,y1; 〃左上角坐标intx2,y2; 〃右上角坐标intcolor; //颜色CStringname; 〃建筑名称CStringstr; 〃介绍简介dialog_building_information (建筑信息类)dialog_road_modifyValue(修改路权值的对话框类)2.整个程序包含功能模块及模块间的调用关系本系统分为3个模块：导航操作，最小路径，地图重置。校园导航模块包括：地图操作(放大，缩小，重置，移动)，校园风景(增加建筑物，修改建筑，移动建筑，删除建筑物)，路径操作(添加路径，删除路径，修改权值)，游客帮助(温饱问题，了解校园)。。还拥有：显示鼠标坐标功能，显示时间，显示建筑信息等功能。二、详细设计最短路径功能：在菜单中选择“最短路径”即可求得路径，鼠标选中一个建造物拖动到另一个建筑物中，然后松手就可显示最短距离及动态路径。原理：选择“最短路径”功能，响应下面函数voidCMyView::OnPath()(//TODO:Addyourcommandhandlercodeherem_tags=5;｝在菜单中响应然后在OnLButtonUp(UINTnFlags,CPointpoint)中执行if(m_tags==5) 〃求最短路径(Path_f(point);Invalidate();｝鼠标左键响应然后voidCMyView::path_f(CPointpoint)(〃寻找源点节点和终点坐标inti,tag1,tag2,souPoint,desPoint;//寻找源点节点tag1=0;tags=0;for(i=1;i<=A.VergeNumbers;i++)if(A.Verge[i].x1<point0.x&&point0.x<A.Verge[i].x2&&A.Verge[i].y1<point0.y&&point0.y<A.Verge[i].y2)(tag1=1;souPoint=i;break;}}for(i=1;i<=A.VergeNumbers;i++)(if(A.Verge[i].x1<point.x&&point.x<A.Verge[i].x2&&A.Verge[i].y1<point.y&&point.y<A.Verge[i].y2)(tag2=1;desPoint=i;break;}}if(tag1&&tag2)//坐标位置正确以下进行最短路径查找(intcout=shortestPath(souPoint,desPoint,A.VergeNumbers);//最短路径查找算法dijskaCStringstr;str.Format("从%s到%s需要花费%d个单位距离〃,A.Verge[souPoint].name,A.Verge[desPoint].name,cout);MessageBox(str);path_cost=cout;//记录路径花费}else{MessageBox(〃没有找到正确的起点位置坐标！");}//没有找到起点位置}intCMyView::shortestPath(inti,intj,intn)(//A.edge□口，A.Verge口，起点节点i,终点节点j节点个数n已经知道//visit口标志节点是否被访问//path口记录路径//dist[]源点i到各个节点的最短花费//sumi到j的权值花费最小和intp,q;〃节点是从1到nboolvisit[100];intpath[100],dist[100],sum,maxValue=100000;for(p=1;p<=n;p++)//初试化(visit[p]=false;dist[p]=A.edge[i][p];//if(p==i)path[p]=-1;//elsepath[p]=i;if(p!=i&&dist[p]<maxValue)path[p]=i;elsepath[p]=-1;}visit[i]=true;dist[i]=0;for(p=1;p<=n-1;p++)(intmin=maxValue;intminj=i;for(q=1;q<=n;q++)if(visit[q]==false&&dist[q]<min)(min=dist[q];minj=q;}visit[minj]=true;for(q=1;q<=n;q++)//松弛选择调整剩下的未加入集合的节点的dist[q]值(if(visit[q]==false&&A.edge[minj][q]<maxValue&&dist[minj]+A.edge[minj][q]<dist[q])(dist[q]=dist[minj]+A.edge[minj][q];//调整valuepath[q]=minj; //记录节点j的前一个节点}}}sum=dist[j];〃对path[]数组进行处理导出正确路径顺序stack<int>Stack1; //调用临时栈pathCurrentPos=0; //指向path_[]的位置inttmp=j;while(j!=-1)(Stack1.push(j);j=path[j];}while(!Stack1.empty())(j=Stack1.top();Stack1.pop();path_[pathCurrentPos++]=j;}returnsum;}使用path函数确定起点和终点，再利用shortestpath函数求出最短路径。同时OnLButtonUp(UINTnFlags,CPointpoint)调用重画函数，进而调用OnDraw函数。voidCMyView::OnDraw(CDC*pDC)(CMyDoc*pDoc=GetDocument();ASSERT_VALID(pDoc);//TODO:adddrawcodefornativedatahereif(m_tags==5)Draw_graph_active_path(pDC);}用Draw_graph_active_path(pDC)实现动态路径voidCMyView::Draw_graph_active_path(CDC*pDC)(//在地图底部写出路线CStringstring1,string2;string1="最短路径为：〃；for(intu=0;u<pathCurrentPos;u++)(string2.Format(〃％s〃，A.Verge[path_[u]].name);if(u!二pathCurrentPos-1)string2+二〃一";string1+=string2;}string2.Format(〃最小总花费为：％d〃，path_cost);pDC->TextOut(10,600,string1);pDC->TextOut(500,630,string2);〃地图上动态显示路径走法pDC->SelectStockObject(LTGRAY_BRUSH);CPenNewPen3,OldPen3; //将画笔选入设备上下文NewPen3.CreatePen(PS_SOLID,6,RGB(255,0,0));//创建深蓝色实心画刷pDC->SelectObject(&NewPen3);//path_[]pathCurrentPosCPointp0,p1;p0.x=(A.Verge[path_[0]].x1+A.Verge[path_[0]].x2)/2;//画第一个节点图像p0.y=(A.Verge[path_[0]].y1+A.Verge[path_[0]].y2)/2;draw_man(p0,pDC);for(inti=1;i<=pathCurrentPos-1;i++)(draw_man(p0,pDC);p0.x=(A.Verge[path_[i-1]].x1+A.Verge[path_[i-1]].x2)/2;p0.y=(A.Verge[path_[i-1]].y1+A.Verge[path_[i-1]].y2)/2;p1.x=(A.Verge[path_[i]].x1+A.Verge[path_[i]].x2)/2;p1.y=(A.Verge[path_[i]].y1+A.Verge[path_[i]].y2)/2;intcount=20000;//计时器while(count--)(pDC->MoveTo(p0);pDC->LineTo(p1);}}draw_man2(p1,pDC);//画最后一个节点图像}用drawman2(p0,pDC)画出成功到达图片，最短路径及动态显示就完成了初始地图的建立：原理：在CMyView类中定义了graph类型的A,在CMyView::CMyView()对A进行初始化：(//TODO:addconstructioncodehereA.make_tu();}然后voidGraph::make_tu()(//初始化EdgeNumbers，VergeNumbers，edge[999][999]，Verge[999]VergeNumbers=31;EdgeNumbers=62; 〃初始化框架，右下角坐标kj_x=1300;kj_y=600;make_iniVerges();//初始化节点Verge[]make_iniEdges();//初始化图的边Edge[]}地图的放大点击菜单中的“中国石油大学校园导航图”，地图操作，放大(缩小，移动同理)即可实现功能・原理：放大功能响应类向导，赋值m_tags=8,然后在CMyView::OnLButtonUp(UINTnFlags,CPointpoint)判断m_tags=8;//m_tags=3标志是响应地图放大函数执行MapBigger();voidCMyView::graph_map_bigger(){floatdist=2;inti;intdx,dy;dialog_map_distdlg;if(dlg.DoModal()==IDOK){//单击了Okfor(i=1;i<=A.VergeNumbers;i++)(dx二A.Verge[i].x1-50;//左上角的坐标放大dist倍dy二A.Verge[i].y1-30;dx*二dist;dy*二dist;A.Verge[i].x1=50+dx;A.Verge[i].y1=50+dy;dx二A.Verge[i].x2-50;//右下角的坐标放大dist倍dy二A.Verge[i].y2-30;dx*=dist;dy*=dist;A.Verge[i].x2=50+dx;A.Verge[i].y2=50+dy;}}Invalidate();}建筑物的添加，修改与拖动在菜单中可分别选择建筑物的添加，修改与拖动这3个功能。如：点击添加功能，下一步在弹出来的对话框中写下左下坐标，右上坐标，建筑名称，简介信息。点击确定即可实现功能。原理：接下来分2个方向：在ResourceView中的添加建造信息的表上双击，创建类(同时在MemberVariables更改x1，x2，y1，y2，等)。当点击"确定”添加后响应类向导，附值m_tags=12.执行下面语句：if(m_tags==12) 〃增加建筑物(Building_add();}接下来voidCMyView::Building_add() //增加建筑(dialog_building_informationdlg;if(dlg.DoModal()==IDOK)(A.VergeNumbers++;intt=A.VergeNumbers;A.Verge[t].x1=dlg.m_x1;A.Verge[t].x2=dlg.m_x2;A.Verge[t].y1=dlg.m_y1;A.Verge[t].y2=dlg.m_y2;A.Verge[t].name=dlg.m_building_name;A.Verge[t].str=dlg.m_building_infoumation;//注释单词写错了}}四、调试分析程序在调试过程中出现的问题及解决方法经常打错字母，导致我检查时，很头痛，所以我得多练练才好。在实现所有操作以后发现自己的图跳得厉害，经过检查，我找出了错误，它们都和Invalidate。的调用有关。在理解最短路径的算法时，看了好久才看懂，不过自己很高兴的。O我把自己写好的程序不断地修改，最终做出了还算可以的作品。算法的时间复杂度分析(e为顶点数,n为边数)考虑到路网多是稀疏网，故采用邻接多重表存储结构，其空间复杂度为O(e),此时的时间复杂度也为O(e)。构建邻接多重表的时间复杂度为O(n+e),输出路径时间复杂度为 O(n)。由此，本程序的时间复杂度为O(n+e)。由于本程序在实际执行时，需要根据用户的鼠标使用求最短路径。因此，迪杰特拉斯算法的时间复杂度比佛洛伊德算法低，但每求一条最短路径都必须重新搜索一遍，在频繁查询时会导致查询效率降低，而佛洛伊德算法只要计算一次，即可求出每一对顶点之间的最短路径，虽然时间复杂度O(n2),但是以后每次查询都只要查表即可，极大的提高了查询效率，而求，佛洛伊德算法还支持带负权的图的最短路径的计算。由此可见，在选择算法时，不能单纯的只考虑算法的渐近时间复杂度，有时还必须综合考虑各种因素。修改景点信息，增加景点，删除景点，增加道路，删除道路，修改路权值，浏览所有景点：其时间复杂度为0（1），空间复杂度为0（1）；五、 测试结果根据一组提供的测试数据得到什么样的结果最短路径：起点：北门终点：南门结果：路径为：1北门-〉2讲堂群-〉13南堂-〉20唐岛湾餐厅-〉5南教-〉6创造太阳-〉南门最小距离：400.通过显示的淡黄色线条完成动态路径，并在终点显示成功标志。放大功能可以放大n倍（n可以取任意值）。缩小功能可以缩小n倍（n可以取任意值）。可任意移动地图。可重置地图。可任意拖动建筑物，路线也随着移动。可通过鼠标增加建筑物；可输入坐标增加建筑物；可删除建筑物；可修改建筑物信息，大小。可以添加路，删除路，修改权值（初始值是原有权值）。六、 心得体会当初自己选择自己要做的软件时，感觉校园导航系统很贴切生活，所以自己选择了它。感觉为我们石大做一个导航系统不但能帮助游客导航，而且可以锻炼自己的能力。在设计校园图示的时候，整个逻辑非常的混乱，设想了各种树，图以及网的遍历问题。在经过网上资料的查询后，终于确定用花矩形来确定节点（矩形的中心就是节