蒲玉婷-0907100213-課程設(shè)計(jì)報(bào)告(校園導(dǎo)航系統(tǒng))

蒲玉婷-0907100213-課程設(shè)計(jì)報(bào)告(校園導(dǎo)航系統(tǒng))西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告——校園導(dǎo)航系統(tǒng)班級(jí)：電子商務(wù)0902班姓名：蒲玉婷學(xué)號(hào)：09071002132010年12月1西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告................................................................................................................1二、概要設(shè)計(jì)...............................................................................................................................................3、結(jié)構(gòu)體的定義...................................................................................................................................3、常量的定義.......................................................................................................................................3各個(gè)函數(shù)的定義..................................................................................................................................4三.詳細(xì)設(shè)計(jì)................................................................................................................................................10、主要函數(shù)的說(shuō)明.............................................................................................................................10主函數(shù)對(duì)各個(gè)函數(shù)的調(diào)用工作........................................................................................................16四．調(diào)試分析.............................................................................................................................................174.1.、測(cè)試數(shù)據(jù)及其輸出結(jié)果................................................................................................................17、時(shí)間復(fù)雜度分析.............................................................................................................................17、調(diào)試中存在的問(wèn)題.........................................................................................................................17五、運(yùn)行環(huán)境.............................................................................................................................................18六、算法的流程圖.....................................................................................................................................18、求最短路徑算法流程圖.................................................................................................................18、輸出函數(shù)算法流程圖.....................................................................................................................22七、程序源代碼.........................................................................................................................................232西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)一、需求分析此次課程設(shè)計(jì)的題目是校園導(dǎo)航系統(tǒng)，所謂系統(tǒng)其實(shí)也不盡然，只不過(guò)是個(gè)小小的提示，為來(lái)訪的客人提供各種信息查詢服務(wù)。主要包括：1.查看學(xué)校的地圖2.各個(gè)景點(diǎn)的簡(jiǎn)介3.查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的最短路徑。輸入：對(duì)于功能1的輸入形式?jīng)]什么要求，主要就是根據(jù)菜單中的提示輸入相應(yīng)的數(shù)字選擇相應(yīng)的功能。功能2.本應(yīng)該由使用者輸入相應(yīng)的景點(diǎn)編號(hào)，但是考慮到系統(tǒng)只是對(duì)學(xué)校的景點(diǎn)做簡(jiǎn)介，景點(diǎn)信息可以一次全部輸出在屏幕上，為了使系統(tǒng)結(jié)構(gòu)清晰，我們決定采用由用戶直接在菜單選擇相應(yīng)功能就全部輸出學(xué)校景點(diǎn)簡(jiǎn)介的方式。至于功能3，要想查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的最短路徑當(dāng)然需要輸入起始景點(diǎn)和目的景點(diǎn)的編號(hào)。此程序在輸入形式上都沒(méi)什么特殊的要求只是一些簡(jiǎn)單的數(shù)字就可以搞定一切。輸出：功能1，查看學(xué)校地圖就是輸出由字符構(gòu)成的一幅簡(jiǎn)易圖，形式比較單一；景點(diǎn)的簡(jiǎn)介方面輸出景點(diǎn)的簡(jiǎn)單信息就可以了；要查詢最短路徑的話輸出的自然是從起始景點(diǎn)到目的地的最短路徑中所途經(jīng)的各個(gè)景點(diǎn)及距離。本系統(tǒng)采用圖來(lái)作為學(xué)校的結(jié)構(gòu)，校園的道路是雙向通行的，可設(shè)校園平面圖是一個(gè)無(wú)向網(wǎng)。頂點(diǎn)包含相關(guān)景點(diǎn)的信息，如景點(diǎn)編號(hào)及景點(diǎn)名稱等信息。邊即包含相應(yīng)兩個(gè)景點(diǎn)的距離信息。用鄰接矩陣的權(quán)值來(lái)表示景點(diǎn)之間的距離。在矩陣中用INF代表INFINITY最大距離，表示這兩個(gè)景點(diǎn)之間是不可以直接到達(dá)的。用實(shí)際的權(quán)值來(lái)表示兩個(gè)景點(diǎn)之間的距離，且是可達(dá)的。二、概要設(shè)計(jì)、結(jié)構(gòu)體的定義typedefstructVertexType{intnumber;char*sight;}VertexType;typedefstruct{VertexTypevex[NUM];intarcs[NUM][NUM];intvexnum;}MGraph;、常量的定義#defineMax32767#defineNUM183西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)各個(gè)函數(shù)的定義voidCreateMGraph(intv){inti,j;G.vexnum=v;for(i=1;i<G.vexnum;++i)G.vex[i].number=i;G.vex[0].sight="各個(gè)景點(diǎn)名字";G.vex[1].sight="大門(mén)口";G.vex[2].sight="行政辦公樓";G.vex[3].sight="北區(qū)教室實(shí)訓(xùn)中心";G.vex[4].sight="一號(hào)教學(xué)樓";G.vex[5].sight="二號(hào)教學(xué)樓";G.vex[6].sight="實(shí)驗(yàn)樓";G.vex[7].sight="三號(hào)教學(xué)樓";G.vex[8].sight="圖書(shū)館";G.vex[9].sight="開(kāi)水房";G.vex[10].sight="超市";G.vex[11].sight="榴馨苑";G.vex[12].sight="洗浴中心";G.vex[13].sight="驪秀苑";[14].sight="綜合樓";G.vex[15].sight="游泳池";G.vex[16].sight="主田徑場(chǎng)";G.vex[17].sight="綜合文體館";for(i=1;i<G.vexnum;++i){for(j=1;j<G.vexnum;++j)G.arcs[i][j]=Max;}G.arcs[1][2]=G.arcs[2][1]=255;G.arcs[1][4]=G.arcs[4][1]=501;G.arcs[1][5]=G.arcs[5][1]=535;G.arcs[1][6]=G.arcs[6][1]=705;G.arcs[1][7]=G.arcs[7][1]=722;G.arcs[1][8]=G.arcs[8][1]=790;G.arcs[2][3]=G.arcs[3][2]=314;G.arcs[2][4]=G.arcs[4][2]=450;G.arcs[2][5]=G.arcs[5][2]=484;G.arcs[2][6]=G.arcs[6][2]=654;G.arcs[2][7]=G.arcs[7][2]=663;G.arcs[2][8]=G.arcs[8][2]=748;G.arcs[3][17]=G.arcs[17][3]=1054;G.arcs[4][5]=G.arcs[5][4]=272;4西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)G.arcs[4][6]=G.arcs[6][4]=178;G.arcs[4][7]=G.arcs[7][4]=442;G.arcs[4][8]=G.arcs[8][4]=527;G.arcs[5][6]=G.arcs[6][5]=476;G.arcs[5][7]=G.arcs[7][5]=187;G.arcs[5][8]=G.arcs[8][5]=561;G.arcs[6][7]=G.arcs[7][6]=289;G.arcs[6][8]=G.arcs[8][6]=374;G.arcs[6][9]=G.arcs[9][6]=520;G.arcs[7][8]=G.arcs[8][7]=382;G.arcs[8][14]=G.arcs[14][8]=365;G.arcs[8][17]=G.arcs[17][8]=1096;G.arcs[9][10]=G.arcs[10][9]=297;G.arcs[10][11]=G.arcs[11][10]=178;G.arcs[10][12]=G.arcs[12][10]=331;G.arcs[12][13]=G.arcs[13][12]=383;G.arcs[13][14]=G.arcs[14][13]=340;G.arcs[13][15]=G.arcs[15][13]=1003;G.arcs[13][16]=G.arcs[16][13]=833;G.arcs[14][17]=G.arcs[17][14]=646;G.arcs[15][16]=G.arcs[16][15]=714;G.arcs[16][17]=G.arcs[17][16]=688;}voidMap(){printf("\n\n\n");printf("\t***********************西安科技大學(xué)*************************");printf("\n\n\n");printf("━━━━━━━━━━━━━━━15游泳池\n");printf("┃┃\n");printf("┃┃\n");printf("12洗浴中心━━━━━━━━━━13驪繡苑━━━━━━━━━━━━━16主田徑場(chǎng)\n");printf("┃┃┃\n");printf("┃14綜合樓┃\n");printf("10超市━━━11榴馨苑┃┃\n");printf("┃┃┃━━━━━━━━━━━━━━17綜合文體館\n");printf("9開(kāi)水房┃┃┃\n");5西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)printf("┃━━━━━━━━━8圖書(shū)館┃\n");printf("┃┃┃\n");printf("┃┃┃\n");printf("━━━━━━━6實(shí)驗(yàn)樓━━━━━┃━━━━━7三號(hào)教學(xué)樓┃\n");printf("┃┃┃┃\n");printf("\n");printf("\n");printf("4\n");printf("\n");printf("\n");printf("\n");printf("\n");printf("\n");printf("\n");printf("\n");printf("1\n");}voidInfo(){printf("1printf("2printf("3printf("4printf("5printf("6printf("7printf("8printf("9printf("10┃┃┃┃┃┃┃┃一號(hào)教學(xué)樓━━━━━┃━━━━━5二號(hào)教學(xué)樓┃┃┃┃┃┃┃┃┃┃━━2行政樓━━━━━━━━━━━━3北區(qū)┃┃大門(mén)口大門(mén)口：出入學(xué)校的必經(jīng)之路\n");行政辦公樓：學(xué)校最氣派的建筑之一\n");北區(qū)：金工實(shí)訓(xùn)中心，還有幾排具有歷史滄桑感的教室\n");一號(hào)教學(xué)樓：主要有小教室，用來(lái)上英語(yǔ)課和專業(yè)課\n");二號(hào)教學(xué)樓：主要用來(lái)上專業(yè)課，五六樓有語(yǔ)音室\n");實(shí)驗(yàn)樓：學(xué)生上各種實(shí)驗(yàn)課的地點(diǎn)\n");三號(hào)教學(xué)樓：有大教室，一般安排用來(lái)上基礎(chǔ)課\n");圖書(shū)館：學(xué)校為同學(xué)們提供學(xué)習(xí)和自習(xí)的地方，也是學(xué)校的藏書(shū)最多的地方\n");開(kāi)水房：學(xué)校唯一一個(gè)為同學(xué)提供熱水的地點(diǎn)\n");超市：學(xué)校唯一一個(gè)中型超市，在這里可以買到各種生活用品\n");6西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)printf("11榴馨苑：環(huán)境較好的學(xué)生食堂，這里因?yàn)殡x女生公寓較近，所以這個(gè)食堂女生較多\n");printf("12洗浴中心：環(huán)境還行就是規(guī)模太小，每天都是供不應(yīng)求\n");printf("13驪秀苑：主要經(jīng)營(yíng)面食。我校的物美價(jià)廉的食堂,位于男生公寓區(qū)，大部分男生在此就餐\n");printf("14綜合樓：歷史較為悠久的一棟教學(xué)樓，旁邊有學(xué)生第二俱樂(lè)部，學(xué)校的晚會(huì)都在這里舉行\(zhòng)n");printf("15游泳池：大一學(xué)生上游泳課的地點(diǎn)\n");printf("16主田徑場(chǎng)：標(biāo)準(zhǔn)的400m跑道，學(xué)生上室外體育課的地點(diǎn)\n");printf("17綜合文體館：上室內(nèi)體育課的地方，是新建成的較為氣派\n");}voidDijkstra(intnum){intv,w,i,t;intfinal[NUM];intmin;for(v=1;v<NUM;v++){final[v]=0;D[v]=G.arcs[num][v];for(w=1;w<NUM;w++)P[v][w]=0;if(D[v]<32767){P[v][num]=1;P[v][v]=1;}}D[num]=0;final[num]=1;for(i=1;i<NUM;++i){min=Max;for(w=1;w<NUM;++w)if(!final[w])if(D[w]<min){v=w;min=D[w];}final[v]=1;for(w=1;w<NUM;++w)if(!final[w]&&((min+G.arcs[v][w])<D[w])){D[w]=min+G.arcs[v][w];for(t=0;t<NUM;t++)7西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)P[w][t]=P[v][t];P[w][w]=1;}}}charMenu(){charc;intflag;do{flag=1;Map();printf("\t\t歡迎使用西安科技大學(xué)導(dǎo)航圖系統(tǒng)\n");printf("\t\t1.查詢地點(diǎn)路徑\n");printf("\t\t2.地點(diǎn)信息簡(jiǎn)介\n");printf("\t\te.退出\n");printf("\t***********************西安科技大學(xué)*************************\n");printf("\t\t\t請(qǐng)輸入您的選擇：");scanf("%c",&c);if(c=='1'||c=='2'||c=='e')flag=0;}while(flag);returnc;}voidDisplay(intsight1,intsight2)inta,b,c,d,q=0;a=sight2;if(a!=sight1){printf("\n\t從%s到%s的最短路徑是",G.vex[sight1].sight,G.vex[sight2].sight);printf("\t(最短距離為%dm.)\n\n\t",D[a]);printf("\t%s",G.vex[sight1].sight);d=sight1;for(c=0;c<NUM;++c){P[a][sight1]=0;for(b=0;b<NUM;b++){if(G.arcs[d][b]<32767&&P[a][b]){printf("-->%s",G.vex[b].sight);q=q+1;P[a][b]=0;d=b;8西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)}}if(q%8==0)printf("\n");}}}主函數(shù)的定義voidmain(){intv0,v1;chare;charck;CreateMGraph(NUM);do{system("cls");ck=Menu();switch(ck){case'1':gate:system("cls");Map();do{printf("\n\n\t\t\t請(qǐng)選擇出發(fā)地序號(hào)（1～17）：");scanf("%d",&v0);if(v0<1||v0>17)printf("\n\n\t\t\t\t輸入錯(cuò)誤!\n");}while(v0<1||v0>17);do{printf("\t\t\t請(qǐng)選擇目的地序號(hào)（1～17）：");scanf("%d",&v1);if(v1<1||v1>17||v1==v0)printf("\n\n\t\t\t\t輸入錯(cuò)誤!\n");}while(v1<1||v1>17||v1==v0);Dijkstra(v0);Display(v0,v1);printf("\n\n\t\t\t\t請(qǐng)按任意鍵繼續(xù),按e退回首頁(yè)\n");getchar();scanf("%c",&e);if(e=='e')break;gotogate;case'2':9西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)}system("cls");Info();printf("\n\n\t\t\t\t請(qǐng)按回車鍵退回首頁(yè)鍵繼續(xù)...\n");getchar();getchar();break;};}while(ck!='e');三.詳細(xì)設(shè)計(jì)、主要函數(shù)的說(shuō)明#defineMax32767{用Max來(lái)表示權(quán)值為此時(shí)的兩點(diǎn)間直接不可達(dá)}#defineNUM18{選取了學(xué)校的十七個(gè)地點(diǎn)用數(shù)組存儲(chǔ)，其中數(shù)組第一個(gè)元素不存儲(chǔ)地點(diǎn)以方便操作}typedefstructVertexType{intnumber;char*sight;}VertexType;{定義頂點(diǎn)的結(jié)構(gòu)體類型，number表示頂點(diǎn)編號(hào)，字符數(shù)組表示頂點(diǎn)的名稱}typedefstruct{VertexTypevex[NUM];intarcs[NUM][NUM];intvexnum;}MGraph;{定義圖的結(jié)構(gòu)體類型，vex[NUM]數(shù)組存儲(chǔ)頂點(diǎn)，arcsp[NUM][NUM]矩陣存儲(chǔ)邊的權(quán)值，vexnum表示頂點(diǎn)的個(gè)數(shù)}MGraphG;{生成G表示結(jié)構(gòu)體變量MGraph}intP[NUM][NUM];{定義全局變量P[NUM][NUM]存儲(chǔ)點(diǎn)之間的最短路徑}longintD[NUM];{定義全局變量D[NUM]存儲(chǔ)點(diǎn)之間最短路徑的權(quán)值}voidCreateMGraph(intv){創(chuàng)建圖的函數(shù)，其中v表示圖中的頂點(diǎn)數(shù)}{inti,j;G.vexnum=v;for(i=1;i<G.vexnum;++i)G.vex[i].number=i;{初始化各個(gè)頂點(diǎn)的編號(hào)為1～17}G.vex[0].sight="各個(gè)景點(diǎn)名字";{為各個(gè)頂點(diǎn)的名稱賦值，其中G.vex[0].sight不作地點(diǎn)名賦值}G.vex[1].sight="大門(mén)口";G.vex[2].sight="行政辦公樓";G.vex[3].sight="北區(qū)教室實(shí)訓(xùn)中心";G.vex[4].sight="一號(hào)教學(xué)樓";G.vex[5].sight="二號(hào)教學(xué)樓";G.vex[6].sight="實(shí)驗(yàn)樓";10西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)G.vex[7].sight="三號(hào)教學(xué)樓";G.vex[8].sight="圖書(shū)館";G.vex[9].sight="開(kāi)水房";G.vex[10].sight="超市";G.vex[11].sight="榴馨苑";G.vex[12].sight="洗浴中心";G.vex[13].sight="驪秀苑";G.vex[14].sight="綜合樓";G.vex[15].sight="游泳池";G.vex[16].sight="主田徑場(chǎng)";G.vex[17].sight="綜合文體館";for(i=1;i<G.vexnum;++i){for(j=1;j<G.vexnum;++j)G.arcs[i][j]=Max;{初始化各條邊的權(quán)值為Max}}G.arcs[1][2]=G.arcs[2][1]=255;{按實(shí)際大小為邊賦權(quán)值，因?yàn)槭菬o(wú)向圖故cs[7][1]=722;G.arcs[1][8]=G.arcs[8][1]=790;G.arcs[2][3]=G.arcs[3][2]=314;G.arcs[2][4]=G.arcs[4][2]=450;G.arcs[2][5]=G.arcs[5][2]=484;G.arcs[2][6]=G.arcs[6][2]=654;G.arcs[2][7]=G.arcs[7][2]=663;G.arcs[2][8]=G.arcs[8][2]=748;G.arcs[3][17]=G.arcs[17][3]=1054;G.arcs[4][5]=G.arcs[5][4]=272;G.arcs[4][6]=G.arcs[6][4]=178;G.arcs[4][7]=G.arcs[7][4]=442;G.arcs[4][8]=G.arcs[8][4]=527;G.arcs[5][6]=G.arcs[6][5]=476;G.arcs[5][7]=G.arcs[7][5]=187;G.arcs[5][8]=G.arcs[8][5]=561;G.arcs[6][7]=G.arcs[7][6]=289;G.arcs[6][8]=G.arcs[8][6]=374;G.arcs[6][9]=G.arcs[9][6]=520;G.arcs[7][8]=G.arcs[8][7]=382;G.arcs[8][14]=G.arcs[14][8]=365;G.arcs[8][17]=G.arcs[17][8]=1096;G.arcs[9][10]=G.arcs[10][9]=297;G.arcs[10][11]=G.arcs[11][10]=178;G.arcs[10][12]=G.arcs[12][10]=331;G.arcs[12][13]=G.arcs[13][12]=383;11西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)G.arcs[13][14]=G.arcs[14][13]=340;G.arcs[13][15]=G.arcs[15][13]=1003;G.arcs[13][16]=G.arcs[16][13]=833;G.arcs[14][17]=G.arcs[17][14]=646;G.arcs[15][16]=G.arcs[16][15]=714;G.arcs[16][17]=G.arcs[17][16]=688;}voidMap(){地圖展示函數(shù),用于輸出西安科技大學(xué)的平面簡(jiǎn)略圖}{printf("\n\n\n");printf("\t***********************西安科技大學(xué)*************************");printf("\n\n\n");printf("━━━━━━━━━━━━━━━15游泳池\n");printf("┃┃\n");printf("┃┃\n");printf("12洗浴中心━━━━━━━━━━13驪繡苑━━━━━━━━━━━━━16主田徑場(chǎng)\n");printf("┃┃┃\n");printf("┃14綜合樓┃\n");printf("10超市━━━11榴馨苑┃┃\n");printf("┃┃┃━━━━━━━━━━━━━━17綜合文體館\n");printf("9開(kāi)水房┃┃┃\n");printf("┃━━━━━━━━━8圖書(shū)館┃\n");printf("┃┃┃\n");printf("┃┃┃\n");printf("━━━━━━━6實(shí)驗(yàn)樓━━━━━┃━━━━━7三號(hào)教學(xué)樓┃\n");printf("┃┃┃┃\n");printf("┃┃┃┃\n");printf("┃┃┃┃\n");printf("4一號(hào)教學(xué)樓━━━━━┃━━━━━5二號(hào)教學(xué)樓┃\n");printf("┃┃12西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)\n");printf("┃┃\n");printf("┃┃\n");printf("┃┃\n");printf("┃━━2行政樓━━━━━━━━━━━━3北區(qū)\n");printf("┃\n");printf("┃\n");printf("1大門(mén)口\n");}voidInfo(){資料介紹函數(shù)，用于當(dāng)用戶選擇查詢地點(diǎn)資料時(shí)輸出地點(diǎn)的資料信息}{printf("1大門(mén)口：出入學(xué)校的必經(jīng)之路\n");printf("2行政辦公樓：學(xué)校最氣派的建筑之一\n");printf("3北區(qū)：金工實(shí)訓(xùn)中心，還有幾排具有歷史滄桑感的教室\n");printf("4一號(hào)教學(xué)樓：主要有小教室，用來(lái)上英語(yǔ)課和專業(yè)課\n");printf("5二號(hào)教學(xué)樓：主要用來(lái)上專業(yè)課，五六樓有語(yǔ)音室\n");printf("6實(shí)驗(yàn)樓：學(xué)生上各種實(shí)驗(yàn)課的地點(diǎn)\n");printf("7三號(hào)教學(xué)樓：有大教室，一般安排用來(lái)上基礎(chǔ)課\n");printf("8圖書(shū)館：學(xué)校為同學(xué)們提供學(xué)習(xí)和自習(xí)的地方，也是學(xué)校的藏書(shū)最多的地方\n");printf("9開(kāi)水房：學(xué)校唯一一個(gè)為同學(xué)提供熱水的地點(diǎn)\n");printf("10超市：學(xué)校唯一一個(gè)中型超市，在這里可以買到各種生活用品\n");printf("11榴馨苑：環(huán)境較好的學(xué)生食堂，這里因?yàn)殡x女生公寓較近，所以這個(gè)食堂女生較多\n");printf("12洗浴中心：環(huán)境還行就是規(guī)模太小，每天都是供不應(yīng)求\n");printf("13驪秀苑：主要經(jīng)營(yíng)面食。我校的物美價(jià)廉的食堂,位于男生公寓區(qū)，大部分男生在此就餐\n");printf("14綜合樓：歷史較為悠久的一棟教學(xué)樓，旁邊有學(xué)生第二俱樂(lè)部，學(xué)校的晚會(huì)都在這里舉行\(zhòng)n");printf("15游泳池：大一學(xué)生上游泳課的地點(diǎn)\n");printf("16主田徑場(chǎng)：標(biāo)準(zhǔn)的400m跑道，學(xué)生上室外體育課的地點(diǎn)\n");printf("17綜合文體館：上室內(nèi)體育課的地方，是新建成的較為氣派\n");}voidDijkstra(intnum){通過(guò)迪杰斯特拉算法求num點(diǎn)到其余點(diǎn)的最短路徑，并將最短路徑保存在數(shù)組P[NUM][NUM]中，將最短路徑的權(quán)值保存在數(shù)組D[NUM]中}{intv,w,i,t;intfinal[NUM];intmin;for(v=1;v<NUM;v++){13西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)final[v]=0;{置空最短路徑終點(diǎn)集}D[v]=G.arcs[num][v];{置初始的最短路徑長(zhǎng)度}for(w=1;w<NUM;w++)P[v][w]=0;{置空最短路徑}if(D[v]<32767){P[v][num]=1;P[v][v]=1;}}D[num]=0;final[num]=1;{初始化num頂點(diǎn)屬于S集}for(i=1;i<NUM;++i){開(kāi)始循環(huán),每次求得num到某個(gè)頂點(diǎn)的最短路徑,并添加到S集}{min=Max;{min為當(dāng)前所知的num到頂點(diǎn)的最短距離}for(w=1;w<NUM;++w)if(!final[w]){w頂點(diǎn)在V-S集中}if(D[w]<min){v=w;min=D[w];}final[v]=1;{與num相距最近的頂點(diǎn)并入S集}for(w=1;w<NUM;++w){更新最短路徑}if(!final[w]&&((min+G.arcs[v][w])<D[w])){修改D[w]和P[w]，w在V-S集中}{D[w]=min+G.arcs[v][w];for(t=0;t<NUM;t++)P[w][t]=P[v][t];P[w][w]=1;}}}charMenu(){主菜單顯示于操作界面從而讓用戶選擇查詢路徑功能或者查詢地點(diǎn)信息功能}{charc;intflag;{定義標(biāo)志flag確定循環(huán)條件}do{flag=1;Map();printf("\t\t歡迎使用西安科技大學(xué)導(dǎo)航圖系統(tǒng)\n");printf("\t\t1.查詢地點(diǎn)路徑\n");printf("\t\t2.地點(diǎn)信息簡(jiǎn)介\n");printf("\t\te.退出\n");printf("\t***********************西安科技大學(xué)*************************\n");printf("\t\t\t請(qǐng)輸入您的選擇：");14西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)scanf("%c",&c);if(c=='1'||c=='2'||c=='e')flag=0;}while(flag);returnc;}voidDisplay(intsight1,intsight2){輸出函數(shù)用于通過(guò)數(shù)組P[NUM][NUM]提取出從點(diǎn)sight1到點(diǎn)sight2的最短路徑，從D[NUM]中輸出點(diǎn)sight1到點(diǎn)sight2的最短路徑的權(quán)值}{inta,b,c,d,q=0;a=sight2;if(a!=sight1){printf("\n\t從%s到%s的最短路徑是",G.vex[sight1].sight,G.vex[sight2].sight);printf("\t(最短距離為%dm.)\n\n\t",D[a]);{從D[NUM]中提取出sight1到sight2的最短距離的權(quán)值輸出}printf("\t%s",G.vex[sight1].sight);d=sight1;for(c=0;c<NUM;++c){P[a][sight1]=0;for(b=0;b<NUM;b++){if(G.arcs[d][b]<32767&&P[a][b]){printf("-->%s",G.vex[b].sight);{通過(guò)P[NUM][NUM]確定sight1到sight2的最短路徑}q=q+1;P[a][b]=0;d=b;if(q%8==0)printf("\n");}}}}}voidmain()//主函數(shù){intv0,v1;chare;charck;CreateMGraph(NUM);do{用dowhile循環(huán)確保循環(huán)至少進(jìn)行一次}{system("cls");{用system("cls")清屏使屏幕簡(jiǎn)潔}ck=Menu();15西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)switch(ck){用switch語(yǔ)句確定用戶選擇功能}{case'1':gate:{門(mén)函數(shù)使程序退回到gate位置}system("cls");Map();do{printf("\n\n\t\t\t請(qǐng)選擇出發(fā)地序號(hào)（1～17）：");scanf("%d",&v0);if(v0<1||v0>17)printf("\n\n\t\t\t\t輸入錯(cuò)誤!\n");}while(v0<1||v0>17);do{printf("\t\t\t請(qǐng)選擇目的地序號(hào)（1～17）：");scanf("%d",&v1);if(v1<1||v1>17||v1==v0)printf("\n\n\t\t\t\t輸入錯(cuò)誤!\n");}while(v1<1||v1>17||v1==v0);Dijkstra(v0);Display(v0,v1);printf("\n\n\t\t\t\t請(qǐng)按任意鍵繼續(xù),按e退回首頁(yè)\n");getchar();scanf("%c",&e);if(e=='e'){當(dāng)標(biāo)識(shí)符e等于e時(shí)跳出語(yǔ)句}break;gotogate;case'2':system("cls");Info();printf("\n\n\t\t\t\t請(qǐng)按回車鍵退回首頁(yè)...\n");getchar();getchar();break;};}while(ck!='e');{當(dāng)標(biāo)識(shí)符ck不等于e時(shí)繼續(xù)循環(huán)}}主函數(shù)對(duì)各個(gè)函數(shù)的調(diào)用工作Main()西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)Map(),Dijkstra(),Display()Info()四．調(diào)試分析4.1.、測(cè)試數(shù)據(jù)及其輸出結(jié)果（1）.進(jìn)入程序首頁(yè)后選擇1，進(jìn)入查詢路徑界面，然后分別輸入1，17，可得從大門(mén)口到綜合文體館的最短路徑及距離。（2）.然后按任意鍵繼續(xù)查詢，分別輸入2，8，可得從行政樓到圖書(shū)館的最短路徑及距離（3）.按e鍵退出到主頁(yè)面選擇2可查詢相關(guān)地點(diǎn)的資料信息。（4）.其余數(shù)據(jù)經(jīng)測(cè)試基本正確，不一一列舉。、時(shí)間復(fù)雜度分析（1）.VoidCreateMGraph(intv)其中為頂點(diǎn)賦值用了一次for循環(huán)，為鄰接矩陣賦值用了兩次for循環(huán)且相互嵌套,故時(shí)間復(fù)雜度為O（n+n）（2）.voidDijkstra(intnum)其中為置空初始值用了兩次for循環(huán)且相互嵌套，更新路徑長(zhǎng)度用了四次for循環(huán)且相互嵌套,故其時(shí)間復(fù)雜度為O(n?n)（3）.VoidDisplay(intsight1,intsight2)其中輸出最短路徑用了兩次for循環(huán)且相互嵌套，故時(shí)間復(fù)雜度為O(n)2242、調(diào)試中存在的問(wèn)題（1）.頂點(diǎn)類型的結(jié)構(gòu)體中一開(kāi)始定義為typedefstructVertexType{intnumber;charsight[20];}VertexType;但是在賦初值時(shí)沒(méi)有使用strcpy（）函數(shù)，后來(lái)將結(jié)構(gòu)體改為typedefstructVertexType{intnumber;char*sight;}VertexType;能直接將字符串賦給sight變量。17西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)（2）.用鄰接矩陣存儲(chǔ)路徑信息在初使化邊的信息時(shí)，剛開(kāi)始是使用直接給矩陣初始化數(shù)據(jù)：{/*012345678910111213141516*/{INF,255,INF,501,535,705,722,790,INF,INF,INF,INF,INF,INF,INF,INF,INF},{255,INF,314,450,484,654,663,748,INF,INF,INF,INF,INF,INF,INF,INF,INF},{INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,1003,INF,INF,714,INF},...{INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,833,INF,714,INF,688},{INF,INF,1054,INF,INF,INF,INF,1096,INF,INF,INF,INF,INF,646,INF,688,INF},};但是后來(lái)在測(cè)試時(shí)發(fā)現(xiàn)有很多錯(cuò)誤，這些都是由于粗心造成的。比如查詢最短路徑從校門(mén)口到圖書(shū)館，顯然應(yīng)該是直接到達(dá)，但是程序顯示到水房再過(guò)去。還有在查詢兩個(gè)地點(diǎn)的最短路徑時(shí)，交換起始點(diǎn)和終點(diǎn)的順序后程序顯示的是不同的路徑，這說(shuō)明在初始化數(shù)據(jù)時(shí)矩陣沒(méi)有對(duì)稱。最后為了確保輸入的數(shù)據(jù)的準(zhǔn)確性，我們經(jīng)過(guò)討論修改了賦方式。首先將路徑的權(quán)值定為無(wú)限大。再將不是無(wú)限大的邊的信息用對(duì)稱賦值：G.arcs[1][2]=G.arcs[2][1]=255（3）一開(kāi)始的時(shí)候沒(méi)有對(duì)錯(cuò)誤的輸入作出相應(yīng)提示,后來(lái)在main()函數(shù)中添加了相應(yīng)的錯(cuò)誤處理機(jī)制（4）源程序沒(méi)有使用system(“cls”)，屏幕看著混亂不簡(jiǎn)潔，后面的程序在相應(yīng)地方加上了system(“cls”)五、運(yùn)行環(huán)境六、算法的流程圖、求最短路徑算法流程圖18西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)假西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)21西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)、輸出函數(shù)算法流程圖西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)真七、程序源代碼#include<stdio.h>#include<string.h>#include<stdlib.h>#defineMax32767#defineNUM18typedefstructVertexType{23西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)intnumber;char*sight;}VertexType;typedefstruct{VertexTypevex[NUM];intarcs[NUM][NUM];intvexnum;}MGraph;MGraphG;intP[NUM][NUM];longintD[NUM];voidCreateMGraph(intv)//創(chuàng)建圖的函數(shù){inti,j;G.vexnum=v;for(i=1;i<G.vexnum;++i)G.vex[i].number=i;G.vex[0].sight="各個(gè)景點(diǎn)名字";G.vex[1].sight="大門(mén)口";G.vex[2].sight="行政辦公樓";G.vex[3].sight="北區(qū)教室實(shí)訓(xùn)中心";G.vex[4].sight="一號(hào)教學(xué)樓";G.vex[5].sight="二號(hào)教學(xué)樓";G.vex[6].sight="實(shí)驗(yàn)樓";G.vex[7].sight="三號(hào)教學(xué)樓";G.vex[8].sight="圖書(shū)館";G.vex[9].sight="開(kāi)水房";G.vex[10].sight="超市";G.vex[11].sight="榴馨苑";G.vex[12].sight="洗浴中心";G.vex[13].sight="驪秀苑";G.vex[14].sight="綜合樓";G.vex[15].sight="游泳池";G.vex[16].sight="主田徑場(chǎng)";G.vex[17].sight="綜合文體館";for(i=1;i<G.vexnum;++i){for(j=1;j<G.vexnum;++j)G.arcs[i][j]=Max;24西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)}G.arcs[1][2]=G.arcs[2][1]=255;G.arcs[1][4]=G.arcs[4][1]=501;G.arcs[1][5]=G.arcs[5][1]=535;G.arcs[1][6]=G.arcs[6][1]=705;G.arcs[1][7]=G.arcs[7][1]=722;G.arcs[1][8]=G.arcs[8][1]=790;G.arcs[2][3]=G.arcs[3][2]=314;G.arcs[2][4]=G.arcs[4][2]=450;G.arcs[2][5]=G.arcs[5][2]=484;G.arcs[2][6]=G.arcs[6][2]=654;G.arcs[2][7]=G.arcs[7][2]=663;G.arcs[2][8]=G.arcs[8][2]=748;G.arcs[3][17]=G.arcs[17][3]=1054;G.arcs[4][5]=G.arcs[5][4]=272;G.arcs[4][6]=G.arcs[6][4]=178;G.arcs[4][7]=G.arcs[7][4]=442;G.arcs[4][8]=G.arcs[8][4]=527;G.arcs[5][6]=G.arcs[6][5]=476;G.arcs[5][7]=G.arcs[7][5]=187;G.arcs[5][8]=G.arcs[8][5]=561;G.arcs[6][7]=G.arcs[7][6]=289;G.arcs[6][8]=G.arcs[8][6]=374;G.arcs[6][9]=G.arcs[9][6]=520;G.arcs[7][8]=G.arcs[8][7]=382;G.arcs[8][14]=G.arcs[14][8]=365;G.arcs[8][17]=G.arcs[17][8]=1096;G.arcs[9][10]=G.arcs[10][9]=297;G.arcs[10][11]=G.arcs[11][10]=178;G.arcs[10][12]=G.arcs[12][10]=331;G.arcs[12][13]=G.arcs[13][12]=383;G.arcs[13][14]=G.arcs[14][13]=340;G.arcs[13][15]=G.arcs[15][13]=1003;G.arcs[13][16]=G.arcs[16][13]=833;G.arcs[14][17]=G.arcs[17][14]=646;G.arcs[15][16]=G.arcs[16][15]=714;G.arcs[16][17]=G.arcs[17][16]=688;}voidMap()//地圖展示函數(shù){printf("\n\n\n");printf("\t***********************西安科技大學(xué)*************************");printf("\n\n\n");printf("━━━━━━━━━━━━━━━15游泳池printf("┃┃25\n");\n");西安科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)printf("┃┃\n");printf("12洗浴中心━━━━━━━━━━13驪繡苑━━━━━━━━━━━━━16主田徑場(chǎng)\n");printf("┃┃┃\n");printf("┃14綜合樓┃\n");printf("10超市━━━11榴馨苑┃┃\n");printf("┃┃┃━━━━━━━━━━━━━━17綜合文體館\n");printf("9開(kāi)水房┃┃┃\n");printf("┃━━━━━━━━━8圖書(shū)館┃\n");printf("┃┃┃\n");printf("┃┃┃\n");printf("━━━━━━━6實(shí)驗(yàn)樓━━━━━┃━━━━━7三號(hào)教學(xué)樓┃\n");printf("┃┃┃┃\n");printf("┃┃┃┃\n");printf("┃┃┃┃\n");printf("4一號(hào)教學(xué)樓━━━━━┃━━━━━5二號(hào)教學(xué)樓┃\n");printf("┃┃\n");printf("┃┃\n");printf("┃┃\n");printf("┃┃\n");printf("┃━━2行政樓━━━━━━━━━━━━3北區(qū)\n");printf("┃\n");printf("┃\n");printf("1大門(mén)口\n");}voidInfo()//資料介紹函數(shù){printf("1大門(mén)口：出入學(xué)校的必經(jīng)之路\n");printf("2行政辦公樓：學(xué)校最氣派的建筑之一\n");printf("3北區(qū)：金工實(shí)訓(xùn)中心，還有幾排具有歷史滄桑感的教室\n");printf("4一號(hào)教學(xué)樓：主要有小教室，用來(lái)上英語(yǔ)課和專業(yè)課\n");printf("5二號(hào)教學(xué)樓：主要用來(lái)上專業(yè)課，五六樓有語(yǔ)音室\n");printf("6實(shí)驗(yàn)樓：學(xué)生上各種實(shí)驗(yàn)課的地點(diǎn)\n");printf("7三號(hào)教學(xué)樓：有大教室，一般安排用來(lái)上基礎(chǔ)課\n");printf("8圖書(shū)館：學(xué)校為同學(xué)們提供學(xué)習(xí)和自習(xí)的地方，也是學(xué)校的藏書(shū)最多的地方\n");printf("9開(kāi)水房：學(xué)校唯一一個(gè)為同學(xué)提供熱水的地點(diǎn)\n");