數據結構課程設計-校園導游咨詢

PAGEPAGE1學號武漢科技大學城市學院課程設計報告課程名稱數據結構課程設計題目校園導游咨詢學部專業(yè)班級姓名指導教師2016年6月12日數據結構課程設計任務書課程設計名稱：校園導游咨詢課程設計開發(fā)平臺與工具：MicrosoftVisualC++6.01.課程設計任務設計學校的校園平面圖，所含景點不少于10個。以圖中頂點表示學校各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關信息。為來訪客人提供圖中任意景點的問路查詢，即查詢任意兩個景點之間的一條最短的簡單路徑。為來訪客人提供圖中任意景點相關信息的查詢。2.課程設計功能說明（1）輸入數據：景點個數，景點信息結構（包含名稱、代號、簡介等信息）（2）輸入約束：景點個數為整形；校園景點平面圖用圖的形式存儲;（3）實現(xiàn)以下功能：a)查詢校園地圖；b)查詢單個景點的相關信息如名稱或簡介等；c)查詢從某個景點到其他所有景點最短路徑長度即最短距離和途中要經歷的景點；d)查詢學校里任意兩個景點之間的最短距離和途經點。3.設計內容及步驟（1）分析問題，給出數學模型，設計相應的數據結構。a)分析問題的特點，用數學表達式或其它形式描述其數學模型。b)選擇能夠體現(xiàn)問題本身特點的邏輯結構。c)在邏輯結構確定的情況下，為算法的設計選擇相應的存儲結構，順序存儲結構和鏈式存儲結構的不同存儲方式，其對應的算法也不同。（2）在已經選擇好數據結構的前提下，為解決的問題設計算法。a)確定所需要的模塊b)對于稍復雜的問題，要充分利用模塊化程序設計方法，自頂向下，逐步細化，在整體思路確定的情況下，考慮所需模塊數，各模塊完成功能以及模塊之間的數據聯(lián)系和調用關系。c)各子模塊功能描述：給出主要模塊的算法描述，用流程圖或偽代碼表示。d)模塊之間的調用關系：給出算法各模塊之間的關系圖示。（3）編寫程序為了提高工作效率，要求學生充分利用上機調試程序的時間。（4）用測試數據去驗證算法及程序的正確性（5）算法分析：分析算法的時間復雜度和空間復雜度。目錄一需求分析 2二概要設計 4三詳細設計 5四測試分析 6五小結 6參考文獻 7課設計評分表 8

1需求分析1.1需求分析來訪我校的游客可能剛到學校不了解學校里的景點，為了給游客提供一條最短的游覽路徑，結合對校園平面圖的分析，將其轉化為數據并保存在系統(tǒng)中，使顧客可以找到游玩景點最省市，最高效的路徑。1.2功能需求描述<1>設計學校的校園平面圖，所含景點10個。<2>為來訪的客人提供圖中任意景點相關信息的查詢。<3>為來訪客人提供任意景點的問路查詢。即查詢任意兩個景點之間的一個最短的簡單路徑，并提示出個經典之間的防衛(wèi)關系，行走方向。2概要設計2.1抽象數據類型定義#include<stdio.h>#include<process.h>/*定義符號常量*/#defineINT_MAX10000#definen10/*定義全局變量*/intcost[n][n];/*邊的值*/intshortest[n][n];/*兩點間的最短距離*/intpath[n][n];/*經過的景點*/開始2.2模塊結構開始顯示查詢信息顯示查詢信息加入文字加入文字文件讀取顯示最短路徑顯示最短路徑退出退出圖2.2模塊圖2.3函數的詳細調用處理流程當游客選擇了要查找景點的信息的介紹這一項功能的時候，程序就會調用DisIntroduction(G);函數進入到查找景點的介紹的界面，當游客輸入了需要查找的景點的名稱的時候，程序利用for();循環(huán)語句來查找是否有這個景點for(int

i=0;i<G.vexnum;i++)

{

int

m

=

strcmp(G.vexs[i].name,n1);

if(m==0)

{

v1=i;

count1=count1+1;

}}找到將它的編號返回，并輸出它的介紹，沒有找到這輸出錯誤提示，提醒游客進行相關的操作進入正確的操作過程當中。當游客選擇了要查找兩個景點之間的最短距離這一項功能的時候，程序就會調用DisPath(G)；函數進入到查找兩個景點之間的最短距離的操作界面當中，當游客輸入了兩個景點的名稱過后，程序會調用strcmp();函數查看是否有這兩個景點，如果有則返回他們各自的編號，并調用ShortPath_DIJ(G,v1,v2);函數進入到查找最短路徑問題的程序當中。

for(v=0;v<G.vexnum;v++)//各對節(jié)點之間初始已知路徑及距離

{

final[v]=FALSE;//從V出發(fā)的最短路徑的空集合

D[v]=G.arcs[v0][v];//從V出發(fā)到圖上其余各個定點v0可能到達的最短路徑的初始值

for(w=0;w<G.vexnum;w++)

{

P[v][w]=FALSE;//設空路徑

}

if(D[v]<MAXNUM)

{

P[v][v0]=TRUE;

P[v][v]=TRUE;

}

}

D[v0]=0;

final[v0]=TRUE;

int

a[20];

for(i=0;i<G.vexnum;i++)//對Path[i][j]進行初始化，使其值全部為1000，便于后期的判斷

{

for(j=0;j<G.vexnum;j++)

{

Path[i][j]=1000;

}

}

for(i=0;i<G.vexnum;i++)//對數組進行初始化，以便對Path[i][j]進行描述

{

a[i]=1;}

for(v=0;v<G.vexnum;v++)//各條路線的初始節(jié)點為v0

{

Path[v][0]=v0;

}

//開始主循環(huán)，每次求解得到v0到某個v頂點的最短路徑，并加入到S集合中

for(i=1;i<G.vexnum;i++)//其余G.vexnum

-

1個頂點

{

m=MAXNUM;//當前所知的離v0最近的距離

for(w=0;w<G.vexnum;w++)

{

if(!final[w])//w頂點在V-S中

{

if(D[w]<m)//w頂點離v0頂點更近

{

v=w;

m=D[w];

}

}

}

Path[v][a[v]]=v;//離v0頂點最近的v加入s集合

final[v]=TRUE;

for(w=0;w<G.vexnum;w++)//更新當前最短路徑及距離

{

if((!final[w])&&(m+G.arcs[v][w]<D[w]))

{

D[w]=m+G.arcs[v][w];//修改當前的最短路徑的值

int

k0=1;

a[w]=1;

while(Path[v][k0]!=1000)

//如果上述條件成立，Path[w]路徑需要改變，因為從v0到w的路徑顯然經過了v0和v之間的所有的點（包括v）

{

Path[w][k0]=Path[v][k0];

k0++;

a[w]++;

}

}

}

}

cout<<"兩個景點之間的最短路徑為:"<<'\t';

int

k=0;

while(Path[v2][k]!=1000){

int

m=Path[v2][k];

cout<<G.vexs[m].name<<'\t';

k++;

}

cout<<endl;

cout<<"兩個景點之間的最短距離為:

"<<D[v2]<<"M"<<endl;

cout<<"請選擇要進行的操作(I:查詢景點信息，P:查詢兩個景點之間的最短路徑，Q:退出)"<<endl;

(1)假設用帶權的鄰接矩陣arcs來表示帶權的有向圖，arcs[i][j]表示?。╲i,vj）上的權值。若(vi,vj)不存在，則置arcs[i][j]為無窮大。S為已找到從v出發(fā)的最短路徑的終點集合，它的初始狀態(tài)為空集。那么，從v出發(fā)到圖上其余各個定點vi可能到達的最短路徑長度的初始值為：D[i]

=

arcs[v][i];

(2)選擇vj,使得D[j]

=

Min{D[i]

|

vi

∈

V

–

S}vj就是當前求得的一條從v出發(fā)的最短路徑的終點。令S

=

S

∪

{j};

(3)修改從v出發(fā)到集合V

–

S

上任意頂點vk可到達的最短路徑的長度。如果D[j]

+

arcs[j][k]

<

D[k]則修改D[k]為D[k]

=

D[j]+arcs[j][k];

(4)重復操作(2)、(3)共n

–

1

次，由此求得從v到圖上其余各個頂點的最短路徑是依路徑長度遞增的序列。從而求得了從一個景點到另一個景點的最短路徑的問題。

3詳細設計3.1數據結構存儲定義1.

鄰接矩陣typedef

int

AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

定義一個鄰接矩陣，用鄰接矩陣來定義和儲存邊的相關信息。

2.

頂點的結構體

typedef

struct

Vertex//定義圖中頂點的數據類型

{

int

num;//景點編號

char

name[14];//景點名稱

char

introduction[100];//景點介紹

}Vertex;

定義一個頂點的結構體，用來儲存景點的編號、景點得名稱和景點的介紹等關于景點的信息。

3.無向圖的結構體

typedef

struct

//定義圖的數據類型

{

Vertex

vexs[MAX_VERTEX_NUM];//頂點的結構體

AdjMatrix

arcs;//邊的鄰接矩陣

int

vexnum,arcnum;//頂點的個數，邊的個數

}MGraph;

定義一個圖的結構體，用來儲存頂點的信息、邊的信息、頂點的個數和邊的個數等相關的信息便于我們以后在用的時候能夠方便快捷的調用。

定義好這些結構體后，當我們以后需要調用的時候，我們就能夠方便快捷的調用這些結構體，從而使得我們在運行程序的時候能夠更加的快速能夠提高我們的程序的運行效率，大大的節(jié)省了我們的時間還使得程序變得更加的簡單3.2算法設計voidfloyed(){/*用floyed算法求兩個景點的最短路徑*/inti,j,k;for(i=1;i<=n;i++)for(j=1;j<=n;j++){shortest[i][j]=cost[i][j];path[i][j]=0;}for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(shortest[i][j]>(shortest[i][k]+shortest[k][j])){/*用path[][]記錄從i到j的最短路徑上點j的前驅景點的序號*/shortest[i][j]=shortest[i][k]+shortest[k][j];path[i][j]=k;path[j][i]=k;}}3.3界面設計3.3.1主界面圖3.1主界面3.3.2查詢圖3.2查詢界面3.3.3查找最短路徑圖3.3查找最短路徑界面3.3.4退出圖3.4退出4測試分析調試過程中難免會遇到這樣或者那樣的問題，一個很低級的錯誤就是在字符串的賦值上居然還會出錯，本來是不可以像int型數據那樣直接用等號賦值的，可是剛開始由于食物卻犯了這樣低級的錯誤結果導致出現(xiàn)一百多個錯誤，當時還莫名其妙，仔細看了幾遍后才把問題想明白，字符串賦值必須用strcpy函數?？磥砘竟€是相當重要的。5小結在本次的實驗過程當中，雖然有各種各樣的問題在困擾著我，但是好在我的身邊總會有人在這個時候出現(xiàn)為我解決這些問題，而他們就我的老師和同學們，一個人做事的時候總是會遇到問題的，有問題并不可怕只要我們相信我們不是一個人在戰(zhàn)斗而是有很多的同學和老師與我們站在一起的樣我們就能夠戰(zhàn)勝各種困難，感謝我的老師和我的同學們。是他們在我遇到問題的時候給我指明了解決的方法，從而克服了一個又一個的問題最終解決了所有的問題實現(xiàn)了程序所需要的功能，感謝我的同學們，不論是上課還是下課，只要是遇到了困難找到他們的時候只要是能夠解決的他們會義不容辭的獻出自己的力量。感謝老師們的諄諄教誨，他們不辭辛勞為了我們能夠順利的解決問題無時刻不在我們的身邊，當我們一遇到問題的時候他就會出現(xiàn)，從沒有半點怨言。最后還要感謝學校感謝給我們提供了良好的實驗環(huán)境，使我們能夠安心輕松的在好的額環(huán)境當中完成我們的實驗。

參考文獻[1]嚴蔚敏,吳偉民.數據結構（C語言版）.清華大學