數據結構課程設計報告：學校導游地圖院系：班級：姓名:學號：指導教師：成績評定：時間：2016年6月11日目錄設計要求………3題目設計要求……………3需求分析………3設計背景分析……………3功能需求分析……………3概要設計………3系統功能結構圖…………3系統流程圖………………4選擇的算法………………4選擇的原因………………4弗洛伊德算法的描述……………………4主要函數設計…………………5主函數的詳細設計…………………5初始化圖函數………………………5查詢景點的信息函數的詳細設計…………………5弗洛伊德算法函數詳細設計………5運行結果及分析………………6收獲及體會……8源代碼…………8設計要求題目設計要求：設計一個校園導游程序，為來訪的客人提供各種信息查詢服務。基本設計要求：（1）設計學校的校園平面圖，所含景點不少于10個。以圖中頂點表示學校各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關信息。（2）為來訪客人提供圖中任意景點的問路查詢，即查詢任意兩個景點之間的一條最短的簡單路徑。為來訪客人提供圖中任意景點相關信息的查詢。需求分析設計背景分析：因為學校將在九月份迎來新一屆的大一新生，為了方便各位各位新生和前來送新生的各位家長在校內不會走丟或者走彎路，專門開發的一款校園導游程序，共收錄了我校比較常用的十一個地點或者標志建筑物，并且還有路線的最優距離等，用來方便大家的使用。功能需求分析：要可以在先有的基礎上可以進行簡單操作就可以添加景點，并且維護簡單，運行方便概要設計系統功能結構圖系統流程圖選擇的算法弗洛伊德算法又稱為插點法，是一種用于尋找給定的加權圖中多源點之間最短路徑的算法。選擇的原因容易理解，可以算出任意兩個節點之間的最短距離，代碼編寫簡單。雖然時間復雜度較高不太適合計算大量的數據，但是校園導游程序數據頂點數不會太多，數據也不會太大，所以比較合適。弗洛伊德算法的描述a)初始化：D[u,v]=A[u,v]b)Fork:=1tonFori:=1tonForj:=1tonIfD[i,j]>D[i,k]+D[k,j]ThenD[i,j]:=D[i,k]+D[k,j];c)算法結束：D即為所有點對的最短路徑矩陣詳細設計主函數的詳細設計：主函數首先是調用初始化圖函數InitGraph()函數創建一個圖，而后調用顯示主界面函數顯示一個可視化主界面，內容包含本系統LOGO以及景點信息及操作編號的提示信息。之后，當用戶成功輸入操作編號后，使用一個switch()函數，判斷用戶所需操作，匹配成功后，調用相關函數實現用戶所需功能。初始化圖函數：InitGraph()函數首先使用MyGraph結構體聲明一個用于存儲圖中信息的結構體，而后定義結構體中的景點數量以及路徑數量，然后使用循環為景點信息和路徑長度賦值，其中賦值景點信息時使用strcpy()函數將字符串復制給G.siteArray[i].siteName以及G.siteArray[i].siteInfo兩個數組。查詢景點的信息函數的詳細設計：該函數首先定義了一個變量k(用于接收用戶輸入的查詢編號)和一個標記位flag(初始值設為1)，而后使用while()循環，判斷條件為flag=1,當輸入編號不合法時提示錯誤，當輸入合法時標記位flag置為0，此時跳出循環，調用MyGraph結構體對應編號的景點信息，以列表方式輸出。4、弗洛伊德算法函數詳細設計：之所以選擇弗洛伊德算法來實現計算最短路徑，原因在于弗洛伊德算法容易理解，可以算出任意兩個節點之間的最短距離，代碼編寫簡單。但是，弗洛伊德算法缺點在于時間復雜度過高，不適合用于計算大量數據。

Floyd算法首先將兩景點間路徑長度數據存儲于數組

D[v][w]中，而后使用一個三維數組用于存放最短路徑所經過的頂點，接下來使用三重循環判斷兩景點之間直接路徑是否大于間接路徑，若大于，則將三維數組中存放的頂點信息更改為簡介路徑所經過的頂點信息。

以上部分完成后，當用于標記輸入數據是否合法的flag=1時，輸出錯誤信息，提示用戶重新輸入，當輸入數據合法時，輸出以上程序得到結果。運行結果及分析收獲及體會通過這次對于程序的編寫我更加仔細的學習了算法的編程，也發現了算法的好處，計算方便，代碼容易編寫。并且通過資料的查詢發現了不止是課本上的方法，課本上只會講最簡單、容易理解的方法，更多的方法在于實踐之中才能學習和理解。并且因為這次用了插點法，讓我簡單的學習、了解了一下對于不同的數據量、不同的結構應該如何去選擇所用的算法，因為不同的算法可以用不同的時間、空間來完成相同的任務。雖然對于一部分的指令還是不太熟悉，但是通過對于資料的輔助還是可以編寫一些簡單的程序。在這次編寫程序的過程中，我也再次加深了對于最短路徑的理解。雖然到現在對于某些模塊還是不是很清楚，但是經過資料的幫助還是成功的完成了編程。雖然最后還是沒能成功調試，我認為主要的原因是因為對于程序的定義不太清楚，不能完全編譯成算法，也有其中的原因。還是應該更好的理解如何定義、如何編寫。源代碼#include<stdlib.h>#include<stdio.h>#include<conio.h>#include<string.h>#defineINFINITY10000//無窮大#defineMAX_VERTEX_NUM40#defineMAX40typedefstructArCell //定義用于存放權值的結構體{ intadj;//路徑長度}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct//圖中頂點表示主要景點，存放景點的編號、名稱、簡介等信息{ charname[30]; //用于存放景點的名稱 intnum; //用于存放景點的編號 charintroduction[100]; //用于存放景點的簡介}infotype;typedefstruct{ infotypevexs[MAX_VERTEX_NUM];//景點數組，用于存放景點名以及景點信息 AdjMatrixarcs; //路徑數組 intvexnum,arcnum; //路徑總數}MGraph;intmain(){ inti;MGraphb; //創建圖 b=InitGraph(); //初始化校園地圖 Menu(); scanf("%d",&i); while(i!=4) { switch(i) { case1:system("cls"); Browser(&b); Menu();break; case2:system("cls"); Floyd(&b); Menu(); break; case3:system("cls"); Search(&b); Menu(); break; case4:exit(1); break; default:break; } scanf("%d",&i); }}intMenu(){ printf("武漢紡織大學陽關校區\n"); printf("┏━━━━━━━━━━━━━━━━━━━━┓\n"); printf("┃1.瀏覽校園全景┃\n"); printf("┃2.路線導航┃\n"); printf("┃3.查看景點信息┃\n"); printf("┃4.退出系統┃\n"); printf("┗━━━━━━━━━━━━━━━━━━━━┛\n"); printf("請輸入需要進行的操作:");}intMGraphInitGraph(){ MGraphG; inti,j; G.vexnum=10; //景點數量 G.arcnum=14; //路徑數量 for(i=0;i<G.vexnum;i++) G.vexs[i].num=i; //對景點進行對應的編號 strcpy(G.vexs[0].name,"武漢紡織大學大門"); strcpy(G.vexs[0].introduction,"武漢紡織大學東大門"); strcpy(G.vexs[1].name,"三棟教學樓"); strcpy(G.vexs[1].introduction,"學校綜合教學樓"); strcpy(G.vexs[2].name,"一食堂"); strcpy(G.vexs[2].introduction,"學校最大的一個食堂"); strcpy(G.vexs[3].name,"四棟"); strcpy(G.vexs[3].introduction,"學校計算機系、電子系實驗室教學樓"); strcpy(G.vexs[4].name,"大學生活動中心"); strcpy(G.vexs[4].introduction,"學校標志性建筑、學校大型禮堂和羽毛球場"); strcpy(G.vexs[5].name,"操場"); strcpy(G.vexs[5].introduction,"田徑場，配有標準足球場，籃球場，塑膠跑步，用于學生日常鍛煉休閑"); strcpy(G.vexs[6].name,"圓形舞池"); strcpy(G.vexs[6].introduction,"學校露天舞池"); strcpy(G.vexs[7].name,"校醫院"); strcpy(G.vexs[7].introduction,"配有基礎醫療設備，能夠進行一些基礎治療以及急救，收費實惠"); strcpy(G.vexs[8].name,"圖書館"); strcpy(G.vexs[8].introduction,"藏書200萬冊，共12層，2樓為電子閱覽室"); strcpy(G.vexs[9].name,"八棟行政樓"); strcpy(G.vexs[9].introduction,"學校主要的行政辦公樓，校長辦公室、學校行政室"); strcpy(G.vexs[10].name,"八棟宿舍樓"); strcpy(G.vexs[10].introduction,"電子系男生寢室"); for(i=0;i<G.vexnum;i++) //使用循化對于路徑進行賦值，對于沒有直接路徑的，賦予無窮大 for(j=0;j<G.vexnum;j++) G.arcs[i][j].adj=INFINITY; G.arcs[0][3].adj=800; G.arcs[0][8].adj=600; G.arcs[0][9].adj=850; G.arcs[1][3].adj=200; G.arcs[1][2].adj=270; G.arcs[1][8].adj=470; G.arcs[2][4].adj=430; G.arcs[2][5].adj=240; G.arcs[4][6].adj=370; G.arcs[4][8].adj=350; G.arcs[4][7].adj=190; G.arcs[5][6].adj=290; G.arcs[7][10].adj=570; G.arcs[8][10].adj=390; G.arcs[9][10].adj=710; for(i=0;i<G.vexnum;i++) //所購造的圖為無向圖，故相反方向路徑也相同 for(j=0;j<G.vexnum;j++) G.arcs[j][i].adj=G.arcs[i][j].adj; returnG;}//InitGraphendintBrowser(MGraph*G) //調用此函數可實現輸出主界面功能{ intv; printf("┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n"); printf("┃編號┃景點名稱┃簡介┃\n"); for(v=0;v<G->vexnum;v++) printf("┃%-4d┃%-16s┃%-56s┃\n",G->vexs[v].num,G->vexs[v].name,G->vexs[v].introduction); printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");}intFloyd(MGraph*G) //使用弗洛伊德算法求出最短路徑{ intv,u,i,w,k,j; intflag=1; //用于標記輸入數據是否正確，如果輸入數據符合要求將flag置為0 intp[11][11][11],D[11][11]; for(v=0;v<G->vexnum;v++)//初始化各個相連頂點的距離 for(w=0;w<G->vexnum;w++) { D[v][w]=G->arcs[v][w].adj;//將路徑數據存放至數組D[v][w]中 for(u=0;u<G->vexnum;u++) p[v][w][u]=0; //該三維數組用于存放兩景點之間是否有直接路徑，有記為1沒有記為0 if(D[v][w]<INFINITY) { p[v][w][v]=1; p[v][w][w]=1; } } for(u=0;u<G->vexnum;u++) for(v=0;v<G->vexnum;v++) for(w=0;w<G->vexnum;w++) if(D[v][u]+D[u][w]<D[v][w]) //如果兩點之間路徑大于直接路徑，則該兩景點之間的路徑為間接路徑 { D[v][w]=D[v][u]+D[u][w]; for(i=0;i<G->vexnum;i++) p[v][w][i]=p[v][u][i]||p[u][w][i]; //獲取兩景點之間路徑所經過的景點編號 } while(flag) { printf("請輸入出發點和目的地的編號:"); scanf("%d%d",&k,&j); if(k<0||k>G->vexnum-1||j<0||j>G->vexnum-1) { printf("景點編號不存在!請重新輸入出發點和目的地的編號: