校園導航系統(tǒng)課程設(shè)計

PAGE0PAGE25軟件學院課程設(shè)計報告書課程名稱數(shù)據(jù)結(jié)構(gòu)設(shè)計題目校園導航系統(tǒng)專業(yè)班級軟件班學號姓名指導教師目錄1.設(shè)計時間………………22.設(shè)計目的………………23.設(shè)計任務(wù)………………24.設(shè)計內(nèi)容………………24.1需求分析…………………24.2總體設(shè)計…………………34.3詳細設(shè)計…………………44.4測試與分析………………124.4.1測試…………124.4.2分析…………134.5附錄………145總結(jié)與展望……………206.參考文獻………………217.成績評定………………211設(shè)計時間2設(shè)計目的1．加深對《數(shù)據(jù)結(jié)構(gòu)》這一課程所學內(nèi)容的進一步理解與鞏固2．通過完成課程設(shè)計，逐漸培養(yǎng)自己的編程能力；3．培養(yǎng)給出題目后，構(gòu)建框架，用計算機解決的能力；4．通過調(diào)試程序積累調(diào)試C程序設(shè)計的經(jīng)驗；3設(shè)計任務(wù)給出校園各主要建筑的名稱信息及有線路聯(lián)通的建筑之間的距離，利用校園導航系統(tǒng)計算出給定的起點到終點之間的最近距離及線路。4設(shè)計內(nèi)容4.1需求分析1．程序所能達到的功能：(1)map——輸出遼寧工程技術(shù)大學平面圖。(2)init()——按相應(yīng)編號輸入各個節(jié)點內(nèi)容，對相應(yīng)路徑賦值的函數(shù)。(3)menu()——菜單函數(shù)(4)information()——輸出簡介的函數(shù)(5)way()——最短路徑的輸出函數(shù)(6)shortestpath()——調(diào)用弗洛伊德和最短路徑輸出的函數(shù)(7)main()——主函數(shù)2．輸入的形式和輸入值的范圍：輸入數(shù)字和字母：字母：以s查詢最短路徑；以i查詢信息；以e退出程序。數(shù)字：從1到11輸入。3．輸出的形式：從A到B得最短路徑為：A-到-C-到-D-到-B最短距離為：xxx米。4．測試數(shù)據(jù)包括在正確的輸入及輸出結(jié)果及含有錯誤的輸入及輸出結(jié)果：當輸入為：s111輸出為：從浴池到靜遠樓的最短路徑為：浴池-到-B寢室樓-到-一食堂-到-綜合樓-到-靜遠樓最短距離為：180米。數(shù)據(jù)均為測試數(shù)據(jù)，與實際有誤差，敬請諒解。當輸入為：i1輸出為：名稱：浴池簡介：洗澡，吃飯，超市，一應(yīng)俱全當輸入為：e輸出為：謝謝使用！當輸入為：i13輸出為：輸入有誤！請輸入查詢地點的編號：4.2總體設(shè)計1．抽象數(shù)據(jù)類型定義有向網(wǎng)節(jié)點結(jié)構(gòu)體類型typedefstruct{ charname[10]; intnumber;charintroduce[100];}vertex;2．主程序模塊的整體流程1、進入主函數(shù)，調(diào)用init，map和menu函數(shù)。2、選擇“s”，調(diào)用shortestpath函數(shù)，并同時調(diào)用floyd和way函數(shù)。并返回調(diào)用menu函數(shù)。3、選擇“i”，調(diào)用information函數(shù)。并返回調(diào)用menu函數(shù)。4、選擇“e”，退出。3.各模塊調(diào)用關(guān)系如下：主函數(shù)主函數(shù)shortestpathExitinformationsei4.3詳細設(shè)計1.有向網(wǎng)節(jié)點結(jié)構(gòu)體類型定義：typedefstruct{ charname[10]; intnumber;charintroduce[100];}vertex;2.主程序和其它主要函數(shù)偽碼算法1）主程序intmain()/*主函數(shù)*/{ chari; printf("\t\t\t歡迎使用遼寧工程技術(shù)大學導航系統(tǒng)\n\n"); init(); map();/*輸出地圖，提示使用者*/ while(1) { i=menu(); switch(i) { case's':shortestpath();break; case'i':information();break; case'e':printf("\n\n\n\t\t\t\t謝謝使用!\n");return(0); default:printf("輸入錯誤！\n");break; } }}2）賦值init函數(shù)voidinit(){ inti,j;/*從41到73行，對平面圖中的各個地點信息進行輸入，運用strcpy函數(shù)*/ ver[1].number=1; strcpy(ver[1].name,"浴池"); strcpy(ver[1].introduce,"洗澡，吃飯，超市，一應(yīng)具全\n"); ver[2].number=2; strcpy(ver[2].name,"老操場"); strcpy(ver[2].introduce,"懷念一下學長們的艱苦生活\n"); ver[3].number=3; strcpy(ver[3].name,"新體育場"); strcpy(ver[3].introduce,"假草，球門，盡情施展腳法的好地方\n"); ver[4].number=4; strcpy(ver[4].name,"B寢室樓"); strcpy(ver[4].introduce,"女寢，不解釋\n"); ver[5].number=5; strcpy(ver[5].name,"一食堂"); strcpy(ver[5].introduce,"飯吶，不好吃\n"); ver[6].number=6; strcpy(ver[6].name,"綜合樓"); strcpy(ver[6].introduce,"超市，有日用品，各種食品，還有各種營業(yè)廳，眼鏡店，書店，水果店\n"); ver[7].number=7; strcpy(ver[7].name,"南大門"); strcpy(ver[7].introduce,"學校最宏偉的建筑，校友捐贈\n"); ver[8].number=8; strcpy(ver[8].name,"A寢室樓"); strcpy(ver[8].introduce,"男寢，我的家\n"); ver[9].number=9; strcpy(ver[9].name,"爾雅"); strcpy(ver[9].introduce,"教學樓，有我最愛的411，是基礎(chǔ)教學部老師大展身手的地方\n"); ver[10].number=10; strcpy(ver[10].name,"耘慧樓"); strcpy(ver[10].introduce,"教學樓，各種上機實驗的地方\n"); ver[11].number=11; strcpy(ver[11].name,"靜遠樓"); strcpy(ver[11].introduce,"教學樓，內(nèi)涵圖書館，足夠驚喜\n");for(i=1;i<=Num;i++)/*對存儲距離的距離矩陣取值進行初始化，全定義為最大*/{for(j=1;j<=Num;j++){edge[i][j]=Maxedge;}}for(i=1;i<=Num;i++)/*對存儲距離的矩陣的取值進行正確賦值，由于我校均來回可達，顧對路徑正反同時賦值*/ { edge[i][i]=0; } edge[1][2]=edge[2][1]=20; edge[2][3]=edge[3][2]=50; edge[2][5]=edge[5][2]=50; edge[3][4]=edge[4][3]=100; edge[3][6]=edge[6][3]=300; edge[1][4]=edge[4][1]=20; edge[4][5]=edge[5][4]=30; edge[5][6]=edge[6][5]=10; edge[6][7]=edge[7][6]=200; edge[6][11]=edge[11][6]=120; edge[4][8]=edge[8][4]=10; edge[8][9]=edge[9][8]=250; edge[9][10]=edge[10][9]=50; edge[10][11]=edge[11][10]=50; edge[7][11]=edge[11][7]=100;}3）輸出遼寧工程技術(shù)大學平面圖的map函數(shù)voidmap()/*遼寧工程技術(shù)大學平面圖，給使用程序者以直觀認識*/{ printf("\t\t遼寧工程技術(shù)大學大學平面圖(括號內(nèi)為相對應(yīng)的數(shù)字編號)\n\n"); printf("浴池(1)——————老體育場(2)————新體育場(3)————\n"); printf("||||\n"); printf("||||\n"); printf("B寢室樓(4)————一食堂(5)——————綜合樓(6)————————南大門(7)\n"); printf("||\n"); printf("A寢室樓(8)|\n"); printf("||\n"); printf("——爾雅樓(9)——————耘慧樓(10)——————靜遠樓(11)\n\n");}4）菜單menu函數(shù)charmenu()/*菜單函數(shù)*/{ chari; printf("輸入“s”以查詢最短路徑\n"); printf("輸入“i”以查詢信息\n"); printf("輸入“e”以退出程序\n"); printf("請輸入對應(yīng)的英文小寫字母，謝謝：\n\t"); scanf("%s",&i); returni;}5）輸出地點信息的information函數(shù)voidinformation()/*輸出簡介函數(shù)*/{ inti; while(1) {printf("請輸入查詢地點的編號：\n\t"); scanf("%d",&i); if(i<=Num&&i>=1) { printf("\n@名稱：%s\n#簡介：%s\n",ver[i].name,ver[i].introduce); return; } else { printf("輸入有誤！"); } }}6）最短路徑floyd函數(shù)voidfloyd()/*弗洛伊德算法*/{ inti=1,j=1,k=1,l=1; for(i=1;i<=Num;i++) { for(j=1;j<=Num;j++) { shortest[i][j]=edge[i][j]; path[i][j]=0; } } for(k=1;k<=Num;k++) { for(i=1;i<=Num;i++) { for(j=1;j<=Num;j++) { if(shortest[i][j]>(shortest[i][k]+shortest[k][j])) { shortest[i][j]=(shortest[i][k]+shortest[k][j]); path[i][j]=path[j][i]=k; } } } }}7）輸出路徑way算法voidway(inti,intj)/*最短路徑的輸出*/{ intk=0,a=i,b=j; if(shortest[i][j]!=Maxedge) { printf("\n%從%s到%s的最短路徑為:\n",ver[i].name,ver[j].name); printf("%s",ver[i].name); while(path[i][j]!=0) { k=path[i][j]; while(path[i][k]!=0) { k=path[i][k]; } printf("-到-%s",ver[k].name); i=k; } printf("-到-%s;\n",ver[j].name); printf("\n最短距離為：%d米。\n",shortest[a][b]); printf("\n數(shù)據(jù)均為測試數(shù)據(jù)，與實際有誤差，敬請諒解.\n\n"); } else printf("從%s不能到達%s。",ver[i].name,ver[j].name);}8）調(diào)用floyd和way的最短路徑shortestpath算法voidshortestpath()/*尋找最短路徑*/{ inti=0,j=0; while(1) { printf("請輸入要查詢的兩點的編號：（以空格間隔）"); scanf("%d%d",&i,&j); if(i<=Num&&i>0&&j<=Num&&j>0) { floyd(); way(i,j); return; } }}3.函數(shù)的調(diào)用關(guān)系exitexitmainexitexitmaininitmapmenuexitinformationshortestpathfloydwaySei4.4測試與分析4.4.1測試1）打開程序后，出現(xiàn)我校平面圖和菜單選項，如圖所示2）選“i”，查詢對應(yīng)地點的信息，如輸入“3”3）選“s”，查詢兩點之間的信息，如輸入“111”，而后會繼續(xù)輸出菜單，4）選“e”，推出程序，如圖所示4.4.2分析1.本次作業(yè)的核心是利用弗洛伊德算法計算給定有向網(wǎng)中兩點最短距離；給出有向網(wǎng)中所要求點的信息。在調(diào)試過程中，除了簡單語法錯誤外，就是對弗洛伊德算法的理解和實現(xiàn)，以及菜單的設(shè)置，這是我以前沒有實現(xiàn)過的。出于簡單化，并沒有對有向圖中各個點進行輸入，而是在程序中直接賦值。2.在對各個功能操作的實現(xiàn)上，由于有弗洛伊德算法時間復(fù)雜度大多數(shù)是O(n3)，空間上增加了二維數(shù)組，空間復(fù)雜度為O(n+s)。4.5附錄源程序代碼及必要注釋。#include<stdio.h>#include<string.h>#defineNum11/*測試使用十一個地點，直接定義*/#defineMaxedge32760/*最大距離*/typedefstruct/*定義對各個地點信息存儲的結(jié)構(gòu)體類型*/{ charname[10]; intnumber;charintroduce[100];}vertex;vertexver[Num];/*定義結(jié)構(gòu)體數(shù)組*/intedge[Num][Num];intshortest[Num][Num];intpath[Num][Num];voidmap()/*遼寧工程技術(shù)大學平面圖，給使用程序者以直觀認識*/{ printf("\t\t遼寧工程技術(shù)大學大學平面圖(括號內(nèi)為相對應(yīng)的數(shù)字編號)\n\n"); printf("浴池(1)——————老體育場(2)————新體育場(3)————\n"); printf("||||\n"); printf("||||\n"); printf("B寢室樓(4)————一食堂(5)——————綜合樓(6)————————南大門(7)\n"); printf("||\n"); printf("A寢室樓(8)|\n"); printf("||\n"); printf("——爾雅樓(9)——————耘慧樓(10)——————靜遠樓(11)\n\n");}voidinit(){ inti,j;/*從41到73行，對平面圖中的各個地點信息進行輸入，運用strcpy函數(shù)*/ ver[1].number=1; strcpy(ver[1].name,"浴池"); strcpy(ver[1].introduce,"洗澡，吃飯，超市，一應(yīng)具全\n"); ver[2].number=2; strcpy(ver[2].name,"老操場"); strcpy(ver[2].introduce,"懷念一下學長們的艱苦生活\n"); ver[3].number=3; strcpy(ver[3].name,"新體育場"); strcpy(ver[3].introduce,"假草，球門，盡情施展腳法的好地方\n"); ver[4].number=4; strcpy(ver[4].name,"B寢室樓"); strcpy(ver[4].introduce,"女寢，不解釋\n"); ver[5].number=5; strcpy(ver[5].name,"一食堂"); strcpy(ver[5].introduce,"飯吶，不好吃\n"); ver[6].number=6; strcpy(ver[6].name,"綜合樓"); strcpy(ver[6].introduce,"超市，有日用品，各種食品，還有各種營業(yè)廳，眼鏡店，書店，水果店\n"); ver[7].number=7; strcpy(ver[7].name,"南大門"); strcpy(ver[7].introduce,"學校最宏偉的建筑，校友捐贈\n"); ver[8].number=8; strcpy(ver[8].name,"A寢室樓"); strcpy(ver[8].introduce,"男寢，我的家\n"); ver[9].number=9; strcpy(ver[9].name,"爾雅"); strcpy(ver[9].introduce,"教學樓，有我最愛的411，是基礎(chǔ)教學部老師大展身手的地方\n"); ver[10].number=10; strcpy(ver[10].name,"耘慧樓"); strcpy(ver[10].introduce,"教學樓，各種上機實驗的地方\n"); ver[11].number=11; strcpy(ver[11].name,"靜遠樓"); strcpy(ver[11].introduce,"教學樓，內(nèi)涵圖書館，足夠驚喜\n");for(i=1;i<=Num;i++)/*對存儲距離的距離矩陣取值進行初始化，全定義為最大*/{for(j=1;j<=Num;j++){edge[i][j]=Maxedge;}}for(i=1;i<=Num;i++)/*對存儲距離的矩陣的取值進行正確賦值，由于我校均來回可達，顧對路徑正反同時賦值*/ { edge[i][i]=0; } edge[1][2]=edge[2][1]=20; edge[2][3]=edge[3][2]=50; edge[2][5]=edge[5][2]=50; edge[3][4]=edge[4][3]=100; edge[3][6]=edge[6][3]=300; edge[1][4]=edge[4][1]=20; edge[4][5]=edge[5][4]=30; edge[5][6]=edge[6][5]=10; edge[6][7]=edge[7][6]=200; edge[6][11]=edge[11][6]=120; edge[4][8]=edge[8][4]=10; edge[8][9]=edge[9][8]=250; edge[9][10]=edge[10][9]=50; edge[10][11]=edge[11][10]=50; edge[7][11]=edge[11][7]=100;}charmenu()/*菜單函數(shù)*/{ chari; printf("輸入“s”以查詢最短路徑\n"); printf("輸入“i”以查詢信息\n"); printf("輸入“e”以退出程序\n"); printf("請輸入對應(yīng)的英文小寫字母，謝謝：\n\t"); scanf("%s",&i); returni;}voidinformation()/*輸出簡介函數(shù)*/{ inti; while(1) {printf("請輸入查詢地點的編號：\n\t"); scanf("%d",&i); if(i<=Num&&i>=1) { printf("\n@名稱：%s\n#簡介：%s\n",ver[i].name,ver[i].introduce); return; } else { printf("輸入有誤！"); } }}voidfloyd()/*弗洛伊德算法*/{ inti=1,j=1,k=1,l=1; for(i=1;i<=Num;i++) { for(j=1;j<=Num;j++) { shortest[i][j]=edge[i][j]; path[i][j]=0; } } for(k=1;k<=Num;k++) { for(i=1;i<=Num;i++) { for(j=1;j<=Num;j++) { if(shortest[i][j]>(shortest[i][k]+shortest[k][j])) { shortest[i][j]=(shortest[i][k]+shortest[k][j]); path[i][j]=path[j][i]=k; } } } }}voidway(inti,intj)/*最短路徑的輸出*/{ intk=0,a=i,b=j; if(shortest[i][j]!=Maxedge) { printf("\n%從%s到%s的最短路徑為:\n",ver[i].name,ver[j].name); printf("%s",ver[i].name); while(path[i][j]!=0) { k=path[i][j]; while(path[i][k]!=0) { k=path[i][k]; } printf("-到-%s",ver[k].name); i=k; } printf("-到-%s;\n",ver[j].name); printf("\n最短距