校園導(dǎo)航實(shí)習(xí)報(bào)告

數(shù)據(jù)結(jié)構(gòu)與VC編程實(shí)習(xí)

實(shí)習(xí)報(bào)告學(xué)生姓名：00學(xué)號(hào)：10081210專業(yè)班級(jí)：計(jì)算機(jī)二班指導(dǎo)教師：00?002011年7月20日實(shí)習(xí)題目 校園導(dǎo)航系統(tǒng)的設(shè)計(jì)一、 任務(wù)描述及要求以中國(guó)石油大學(xué)（青島）為參照。合理設(shè)計(jì)窗口界面，首先構(gòu)建中國(guó)石油大學(xué)校園示意圖，在界面上以圖形方式顯示各個(gè)地點(diǎn)及之間的距離，并標(biāo)記出距離的大?。ň嚯x由操作人員自行設(shè)置）。最短路徑，以指定的某點(diǎn)位開(kāi)始點(diǎn)，另一點(diǎn)為終點(diǎn)來(lái)實(shí)現(xiàn)操作。功能菜單或按鈕自行設(shè)計(jì)，以合理為目的。在界面上動(dòng)態(tài)顯示出從起點(diǎn)到目的點(diǎn)的最短路徑走法，地圖可縮小、放大、移動(dòng)、可顯示某點(diǎn)的提示信息等。二、 概要設(shè)計(jì)校園旅游模型是由各個(gè)景點(diǎn)和景點(diǎn)以及場(chǎng)所和場(chǎng)所之間的路徑組成的，所以這完全可以用數(shù)據(jù)結(jié)構(gòu)中的圖來(lái)模擬。用圖的結(jié)點(diǎn)代表景點(diǎn)或場(chǎng)所，用圖的邊代表景點(diǎn)或場(chǎng)所之間的路徑。首先，應(yīng)該創(chuàng)建圖。結(jié)點(diǎn)值代表景點(diǎn)信息，邊的權(quán)值代表景點(diǎn)間的距離。本系統(tǒng)需要查詢景點(diǎn)信息和求一個(gè)景點(diǎn)到另一個(gè)景點(diǎn)的最短路徑長(zhǎng)度及路線。計(jì)算最短路線時(shí)可用迪杰斯特拉（Dijkastra）算法算法實(shí)現(xiàn)。

1.抽象數(shù)據(jù)類(lèi)型有：CMyView類(lèi)：voidRoad_ModifyValue(CPointpoint);//修改權(quán)值voidRoad_Add(CPointpoint);〃添加路徑voidRoad_Delete(CPointpoint);〃刪除路徑voidBuilding_add();//添加建筑voidBuilding_move(CPointpoint);//建筑移動(dòng)voidBuilding_modify(CPointpoint);//建筑修改哦voidBuilding_Delete(CPointpoint);〃建筑刪除voidgraph_map_move();〃地圖移動(dòng)voidgraph_map_bigger();〃地圖放大voidgraph_map_smaller();〃地圖縮小voidpath_f(CPointpoint);//尋找最短路徑的全局函數(shù)intshortestPath(inti,intj,intn);〃最短路徑查找算法dijskavoidDraw_graph_Verges(CDC*pDC);//畫(huà)建筑節(jié)點(diǎn)voidDraw_graph_Edges(CDC*pDC);〃畫(huà)無(wú)向邊，即道路voidDraw_graph_kuangjia(CDC*pDC);//畫(huà)整體框架voidDraw_graph_kuangjia_1(CDC*pDC);〃框架1voidDraw_graph_kuangjia_2(CDC*pDC);〃框架2voidDraw_graph_direction(CDC*pDC);//畫(huà)方向〃北〃intFind_Verge(CPointp); //對(duì)坐標(biāo)p尋找其對(duì)應(yīng)節(jié)點(diǎn)的序號(hào)，找不到返回-1Graph類(lèi)：(畫(huà)圖類(lèi))voidmake_tu(); 〃初始化總函數(shù)，里面調(diào)用了voidmake_iniVerges();//初始化節(jié)點(diǎn)voidmake_iniEdges();//初始化圖的邊Node類(lèi)：(節(jié)點(diǎn)類(lèi))Node();virtual~node();intx1,y1; 〃左上角坐標(biāo)intx2,y2; 〃右上角坐標(biāo)intcolor; //顏色CStringname; 〃建筑名稱CStringstr; 〃介紹簡(jiǎn)介dialog_building_information (建筑信息類(lèi))dialog_road_modifyValue(修改路權(quán)值的對(duì)話框類(lèi))2.整個(gè)程序包含功能模塊及模塊間的調(diào)用關(guān)系本系統(tǒng)分為3個(gè)模塊：導(dǎo)航操作，最小路徑，地圖重置。校園導(dǎo)航模塊包括：地圖操作(放大，縮小，重置，移動(dòng))，校園風(fēng)景(增加建筑物，修改建筑，移動(dòng)建筑，刪除建筑物)，路徑操作(添加路徑，刪除路徑，修改權(quán)值)，游客幫助(溫飽問(wèn)題，了解校園)。。還擁有：顯示鼠標(biāo)坐標(biāo)功能，顯示時(shí)間，顯示建筑信息等功能。二、詳細(xì)設(shè)計(jì)最短路徑功能：在菜單中選擇“最短路徑”即可求得路徑，鼠標(biāo)選中一個(gè)建造物拖動(dòng)到另一個(gè)建筑物中，然后松手就可顯示最短距離及動(dòng)態(tài)路徑。原理：選擇“最短路徑”功能，響應(yīng)下面函數(shù)voidCMyView::OnPath()(//TODO:Addyourcommandhandlercodeherem_tags=5;｝在菜單中響應(yīng)然后在OnLButtonUp(UINTnFlags,CPointpoint)中執(zhí)行if(m_tags==5) 〃求最短路徑(Path_f(point);Invalidate();｝鼠標(biāo)左鍵響應(yīng)然后voidCMyView::path_f(CPointpoint)(〃尋找源點(diǎn)節(jié)點(diǎn)和終點(diǎn)坐標(biāo)inti,tag1,tag2,souPoint,desPoint;//尋找源點(diǎn)節(jié)點(diǎn)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)//坐標(biāo)位置正確以下進(jìn)行最短路徑查找(intcout=shortestPath(souPoint,desPoint,A.VergeNumbers);//最短路徑查找算法dijskaCStringstr;str.Format("從%s到%s需要花費(fèi)%d個(gè)單位距離〃,A.Verge[souPoint].name,A.Verge[desPoint].name,cout);MessageBox(str);path_cost=cout;//記錄路徑花費(fèi)}else{MessageBox(〃沒(méi)有找到正確的起點(diǎn)位置坐標(biāo)！");}//沒(méi)有找到起點(diǎn)位置}intCMyView::shortestPath(inti,intj,intn)(//A.edge□口，A.Verge口，起點(diǎn)節(jié)點(diǎn)i,終點(diǎn)節(jié)點(diǎn)j節(jié)點(diǎn)個(gè)數(shù)n已經(jīng)知道//visit口標(biāo)志節(jié)點(diǎn)是否被訪問(wèn)//path口記錄路徑//dist[]源點(diǎn)i到各個(gè)節(jié)點(diǎn)的最短花費(fèi)//sumi到j(luò)的權(quán)值花費(fèi)最小和intp,q;〃節(jié)點(diǎn)是從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++)//松弛選擇調(diào)整剩下的未加入集合的節(jié)點(diǎn)的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];//調(diào)整valuepath[q]=minj; //記錄節(jié)點(diǎn)j的前一個(gè)節(jié)點(diǎn)}}}sum=dist[j];〃對(duì)path[]數(shù)組進(jìn)行處理導(dǎo)出正確路徑順序stack<int>Stack1; //調(diào)用臨時(shí)棧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函數(shù)確定起點(diǎn)和終點(diǎn)，再利用shortestpath函數(shù)求出最短路徑。同時(shí)OnLButtonUp(UINTnFlags,CPointpoint)調(diào)用重畫(huà)函數(shù)，進(jìn)而調(diào)用OnDraw函數(shù)。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)實(shí)現(xiàn)動(dòng)態(tài)路徑voidCMyView::Draw_graph_active_path(CDC*pDC)(//在地圖底部寫(xiě)出路線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(〃最小總花費(fèi)為：％d〃，path_cost);pDC->TextOut(10,600,string1);pDC->TextOut(500,630,string2);〃地圖上動(dòng)態(tài)顯示路徑走法pDC->SelectStockObject(LTGRAY_BRUSH);CPenNewPen3,OldPen3; //將畫(huà)筆選入設(shè)備上下文NewPen3.CreatePen(PS_SOLID,6,RGB(255,0,0));//創(chuàng)建深藍(lán)色實(shí)心畫(huà)刷pDC->SelectObject(&NewPen3);//path_[]pathCurrentPosCPointp0,p1;p0.x=(A.Verge[path_[0]].x1+A.Verge[path_[0]].x2)/2;//畫(huà)第一個(gè)節(jié)點(diǎn)圖像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;//計(jì)時(shí)器while(count--)(pDC->MoveTo(p0);pDC->LineTo(p1);}}draw_man2(p1,pDC);//畫(huà)最后一個(gè)節(jié)點(diǎn)圖像}用drawman2(p0,pDC)畫(huà)出成功到達(dá)圖片，最短路徑及動(dòng)態(tài)顯示就完成了初始地圖的建立：原理：在CMyView類(lèi)中定義了graph類(lèi)型的A,在CMyView::CMyView()對(duì)A進(jìn)行初始化：(//TODO:addconstructioncodehereA.make_tu();}然后voidGraph::make_tu()(//初始化EdgeNumbers，VergeNumbers，edge[999][999]，Verge[999]VergeNumbers=31;EdgeNumbers=62; 〃初始化框架，右下角坐標(biāo)kj_x=1300;kj_y=600;make_iniVerges();//初始化節(jié)點(diǎn)Verge[]make_iniEdges();//初始化圖的邊Edge[]}地圖的放大點(diǎn)擊菜單中的“中國(guó)石油大學(xué)校園導(dǎo)航圖”，地圖操作，放大(縮小，移動(dòng)同理)即可實(shí)現(xiàn)功能?原理：放大功能響應(yīng)類(lèi)向?qū)?，賦值m_tags=8,然后在CMyView::OnLButtonUp(UINTnFlags,CPointpoint)判斷m_tags=8;//m_tags=3標(biāo)志是響應(yīng)地圖放大函數(shù)執(zhí)行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;//左上角的坐標(biāo)放大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;//右下角的坐標(biāo)放大dist倍dy二A.Verge[i].y2-30;dx*=dist;dy*=dist;A.Verge[i].x2=50+dx;A.Verge[i].y2=50+dy;}}Invalidate();}建筑物的添加，修改與拖動(dòng)在菜單中可分別選擇建筑物的添加，修改與拖動(dòng)這3個(gè)功能。如：點(diǎn)擊添加功能，下一步在彈出來(lái)的對(duì)話框中寫(xiě)下左下坐標(biāo)，右上坐標(biāo)，建筑名稱，簡(jiǎn)介信息。點(diǎn)擊確定即可實(shí)現(xiàn)功能。原理：接下來(lái)分2個(gè)方向：在ResourceView中的添加建造信息的表上雙擊，創(chuàng)建類(lèi)(同時(shí)在MemberVariables更改x1，x2，y1，y2，等)。當(dāng)點(diǎn)擊"確定”添加后響應(yīng)類(lèi)向?qū)В街祄_tags=12.執(zhí)行下面語(yǔ)句：if(m_tags==12) 〃增加建筑物(Building_add();}接下來(lái)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;//注釋單詞寫(xiě)錯(cuò)了}}四、調(diào)試分析程序在調(diào)試過(guò)程中出現(xiàn)的問(wèn)題及解決方法經(jīng)常打錯(cuò)字母，導(dǎo)致我檢查時(shí)，很頭痛，所以我得多練練才好。在實(shí)現(xiàn)所有操作以后發(fā)現(xiàn)自己的圖跳得厲害，經(jīng)過(guò)檢查，我找出了錯(cuò)誤，它們都和Invalidate。的調(diào)用有關(guān)。在理解最短路徑的算法時(shí)，看了好久才看懂，不過(guò)自己很高興的。O我把自己寫(xiě)好的程序不斷地修改，最終做出了還算可以的作品。算法的時(shí)間復(fù)雜度分析(e為頂點(diǎn)數(shù),n為邊數(shù))考慮到路網(wǎng)多是稀疏網(wǎng)，故采用鄰接多重表存儲(chǔ)結(jié)構(gòu)，其空間復(fù)雜度為O(e),此時(shí)的時(shí)間復(fù)雜度也為O(e)。構(gòu)建鄰接多重表的時(shí)間復(fù)雜度為O(n+e),輸出路徑時(shí)間復(fù)雜度為 O(n)。由此，本程序的時(shí)間復(fù)雜度為O(n+e)。由于本程序在實(shí)際執(zhí)行時(shí)，需要根據(jù)用戶的鼠標(biāo)使用求最短路徑。因此，迪杰特拉斯算法的時(shí)間復(fù)雜度比佛洛伊德算法低，但每求一條最短路徑都必須重新搜索一遍，在頻繁查詢時(shí)會(huì)導(dǎo)致查詢效率降低，而佛洛伊德算法只要計(jì)算一次，即可求出每一對(duì)頂點(diǎn)之間的最短路徑，雖然時(shí)間復(fù)雜度O(n2),但是以后每次查詢都只要查表即可，極大的提高了查詢效率，而求，佛洛伊德算法還支持帶負(fù)權(quán)的圖的最短路徑的計(jì)算。由此可見(jiàn)，在選擇算法時(shí)，不能單純的只考慮算法的漸近時(shí)間復(fù)雜度，有時(shí)還必須綜合考慮各種因素。修改景點(diǎn)信息，增加景點(diǎn)，刪除景點(diǎn)，增加道路，刪除道路，修改路權(quán)值，瀏覽所有景點(diǎn)：其時(shí)間復(fù)雜度為0（1），空間復(fù)雜度為0（1）；五、 測(cè)試結(jié)果根據(jù)一組提供的測(cè)試數(shù)據(jù)得到什么樣的結(jié)果最短路徑：起點(diǎn)：北門(mén)終點(diǎn)：南門(mén)結(jié)果：路徑為：1北門(mén)-〉2講堂群-〉13南堂-〉20唐島灣餐廳-〉5南教-〉6創(chuàng)造太陽(yáng)-〉南門(mén)最小距離：400.通過(guò)顯示的淡黃色線條完成動(dòng)態(tài)路徑，并在終點(diǎn)顯示成功標(biāo)志。放大功能可以放大n倍（n可以取任意值）?？s小功能可以縮小n倍（n可以取任意值）?？扇我庖苿?dòng)地圖?？芍刂玫貓D?？扇我馔蟿?dòng)建筑物，路線也隨著移動(dòng)?？赏ㄟ^(guò)鼠標(biāo)增加建筑物；可輸入坐標(biāo)增加建筑物；可刪除建筑物；可修改建筑物信息，大小。可以添加路，刪除路，修改權(quán)值（初始值是原有權(quán)值）。六、 心得體會(huì)當(dāng)初自己選擇自己要做的軟件時(shí)，感覺(jué)校園導(dǎo)航系統(tǒng)很貼切生活，所以自己選擇了它。感覺(jué)為我們石大做一個(gè)導(dǎo)航系統(tǒng)不但能幫助游客導(dǎo)航，而且可以鍛煉自己的能力。在設(shè)計(jì)校園圖示的時(shí)候，整個(gè)邏輯非常的混亂，設(shè)想了各種樹(shù)，圖以及網(wǎng)的遍歷問(wèn)題。在經(jīng)過(guò)網(wǎng)上資料的查詢后，終于確定用花矩形來(lái)確定節(jié)點(diǎn)（矩形的中心就是節(jié)