數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-校園導(dǎo)游咨詢

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

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

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

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

{

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

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

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

{

P[v][w]=FALSE;//設(shè)空路徑

}

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++)//對(duì)Path[i][j]進(jìn)行初始化，使其值全部為1000，便于后期的判斷

{

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

{

Path[i][j]=1000;

}

}

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

{

a[i]=1;}

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

{

Path[v][0]=v0;

}

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

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

-

1個(gè)頂點(diǎn)

{

m=MAXNUM;//當(dāng)前所知的離v0最近的距離

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

{

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

{

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

{

v=w;

m=D[w];

}

}

}

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

final[v]=TRUE;

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

{

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

{

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

int

k0=1;

a[w]=1;

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

//如果上述條件成立，Path[w]路徑需要改變，因?yàn)閺膙0到w的路徑顯然經(jīng)過了v0和v之間的所有的點(diǎn)（包括v）

{

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

k0++;

a[w]++;

}

}

}

}

cout<<"兩個(gè)景點(diǎn)之間的最短路徑為:"<<'\t';

int

k=0;

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

int

m=Path[v2][k];

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

k++;

}

cout<<endl;

cout<<"兩個(gè)景點(diǎn)之間的最短距離為:

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

cout<<"請(qǐng)選擇要進(jìn)行的操作(I:查詢景點(diǎn)信息，P:查詢兩個(gè)景點(diǎn)之間的最短路徑，Q:退出)"<<endl;

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

=

arcs[v][i];

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

=

Min{D[i]

|

vi

∈

V

–

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

=

S

∪

{j};

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

–

S

上任意頂點(diǎn)vk可到達(dá)的最短路徑的長(zhǎng)度。如果D[j]

+

arcs[j][k]

<

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

=

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

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

–

1

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

3詳細(xì)設(shè)計(jì)3.1數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)定義1.

鄰接矩陣typedef

int

AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

定義一個(gè)鄰接矩陣，用鄰接矩陣來定義和儲(chǔ)存邊的相關(guān)信息。

2.

頂點(diǎn)的結(jié)構(gòu)體

typedef

struct

Vertex//定義圖中頂點(diǎn)的數(shù)據(jù)類型

{

int

num;//景點(diǎn)編號(hào)

char

name[14];//景點(diǎn)名稱

char

introduction[100];//景點(diǎn)介紹

}Vertex;

定義一個(gè)頂點(diǎn)的結(jié)構(gòu)體，用來儲(chǔ)存景點(diǎn)的編號(hào)、景點(diǎn)得名稱和景點(diǎn)的介紹等關(guān)于景點(diǎn)的信息。

3.無向圖的結(jié)構(gòu)體

typedef

struct

//定義圖的數(shù)據(jù)類型

{

Vertex

vexs[MAX_VERTEX_NUM];//頂點(diǎn)的結(jié)構(gòu)體

AdjMatrix

arcs;//邊的鄰接矩陣

int

vexnum,arcnum;//頂點(diǎn)的個(gè)數(shù)，邊的個(gè)數(shù)

}MGraph;

定義一個(gè)圖的結(jié)構(gòu)體，用來儲(chǔ)存頂點(diǎn)的信息、邊的信息、頂點(diǎn)的個(gè)數(shù)和邊的個(gè)數(shù)等相關(guān)的信息便于我們以后在用的時(shí)候能夠方便快捷的調(diào)用。

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

參考文獻(xiàn)[1]嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學(xué)