校園導航系統(tǒng)數(shù)據(jù)結構課程設計

校園導航系統(tǒng)數(shù)據(jù)結構課程設計前言現(xiàn)代社會，新興科技日新月異，信息千變?nèi)f化，人們在渴望得到最多最廣的信息的同時又渴望得到信息的路徑能越來越簡單，易操作，而且能在簡易的操作中得到更多的信息。這就要求信息咨詢系統(tǒng)的開發(fā)者在開發(fā)之時能盡可能的全面理解客戶的想法要求，而且在開發(fā)的時候能更簡易的操作和更新，這種思想都符程序設計的開發(fā)思想。本次設計任務是設計學校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同的路，且路長也可能不同，找出從任意場所到達另一場所的最正確路徑〔最短路徑〕，其實就是數(shù)據(jù)結構中圖類的問題。將校園景點作為圖的結點，將景點間的路徑作為圖的邊，路徑距離作為邊的權值。這樣一來，求兩景點間最短路徑的問題就抽象成了求圖中一結點到另一結點的問題。關鍵字：校園導航數(shù)據(jù)結構C語言目錄1引言62程序設計62.1設計時間62.2設計目的62.3設計任務62.4需求分析62.5概要設計72.5.1.設計思路和主要步驟7程序流程圖82.6詳細設計8學校整體局部8打印圖10導航函數(shù)11查找路徑12記錄最短路徑133調(diào)試分析134附錄17總結23參考文獻241引言本概要設計說明書基于之前建立的軟件需求設計根底上，對“蚌埠學院校園導航系統(tǒng)”做出概要分析。主要解決了實現(xiàn)該系統(tǒng)需求的程序模塊設計問題。包括如何把該系統(tǒng)劃分成假設干個模塊、決定各個模塊之間的接口、模塊之間傳遞的信息，以及數(shù)據(jù)結構、模塊結構的設計等。在以下的概要設計報告中將對在本階段中對系統(tǒng)所做的所有概要設計進行詳細的說明。2程序設計2.1設計時間2015-06-01—2015-06-152.2設計目的加深對《數(shù)據(jù)結構》這門課程的進一步理解與穩(wěn)固通過課程設計，培養(yǎng)自己的編程能力以及團隊協(xié)作能力加強自己對實際問題的分析能力，以及如何更好的將一些經(jīng)典的算法應用于實際2.3設計任務該導航系統(tǒng)為參觀者提供校園主要建筑的根本信息及各建筑間的距離，同時通過該系統(tǒng)計算出所在位置到目的地的最短路徑。2.4需求分析1.程序表達的功能：(1)main()——主函數(shù)(2)navigate()——導航函數(shù)(3)pri()——打印校園平面圖函數(shù)(4)visit()——遞歸查找路線函數(shù)2.正確輸入與輸出形式：如：執(zhí)行建筑查詢功能：輸入為：sod輸出為：該建筑所在的坐標為78種有花草和一些藝術標記物輸入為：ld輸出為：該位置沒有找到你找的建筑沒有找到 執(zhí)行導航功能： 輸入為：請輸入你所在位置：gym 輸入你要的目的地：sod 輸出為：打印并給出所有可能走通的線路， 計算出兩地間的最短路徑〔距離〕 執(zhí)行顯示最短路徑功能： 輸入為：請輸入你所在位置：sod 輸入你要的目的地：office 輸出為：其中最短路徑為： 平面圖中包含最短線路圖， 其行走的距離為450米2.5概要設計2.5.1.設計思路和主要步驟按照需求分析，首先我們先要把學校的整體布局給設計出來，即用一個二維數(shù)組chararr[17][22]表示學校的整體布局，并將每個建筑物用特殊的符號表示：/*2為墻壁■A辦公樓◆c教學區(qū)●g草坪△p操場▓0路b圖書館★M門□m食堂○h為宿舍☆T為體育館▲l為實驗室╳*/，然后要打印出學校的整體布局,設計一個pri〔char，int〕打印出學校的整體布局。在學校里，最重要的是校園的導航系統(tǒng)，這樣可以使人耳目一新的知道某個地方的某個地方的路徑，所以設計校園導航函數(shù)是必須的，因此我們設計voidnavigate(intx)函數(shù)，在圖的應用中，一個最重要的知識就是求最短路徑，我們并沒有用迪杰斯特拉的算法和弗洛伊德算法來實現(xiàn)這個功能，而是利用了迷宮求解問題中的遞歸意義來實現(xiàn)求最短路徑的功能voidvisit(intqiX,intqiY,intzhX,intzhY,intx)用于查找某地點到某地點的所有路徑，然后進行比擬，將最短路徑用函數(shù)voidfuzhi(將最短路徑存放在一個數(shù)組中)。程序流程圖2.6詳細設計按照需求分析中的需求，和概要設計中的各流程圖的模塊，進行詳細設計，完善各流程的代碼，詳細設計如下：2.6.1學校整體局部chararr[17][22]={ /*2為墻壁■A辦公樓◆c教學區(qū)●g草坪△p操場▓0路b圖書館★M門□m食堂○h為宿舍☆T為體育館▲l為實驗室╳*/ //0123456789101112131415161718192021 {'2','2','2','2','2','2','2','2','2','2','2','2','2','M','2','2','2','2','2','2','2','2'}, {'2','A','A','A','0','c','c','c','c','c','c','c','c','0','2','p','p','p','p','p','p','2'}, {'2','A','A','A','0','c','c','c','c','c','c','c','c','0','2','p','p','p','p','p','p','2'}, {'2','A','A','A','0','c','c','c','c','c','c','c','c','0','2','p','p','p','p','p','p','2'}, {'2','A','A','A','0','0','0','0','0','0','0','0','0','0','2','p','p','p','p','p','p','2'}, {'2','A','A','A','0','g','g','g','g','g','g','g','g','0','2','2','2','0','2','2','2','2'}, {'M','0','0','0','0','g','g','g','g','g','g','g','g','0','0','0','0','0','0','0','m','2'}, {'2','l','l','l','0','0','0','0','0','0','0','0','0','0','h','h','h','h','h','0','m','2'}, {'2','l','l','l','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'}, {'2','l','l','l','0','b','b','b','b','b','b','b','b','0','0','0','0','0','0','0','m','2'}, {'2','l','l','l','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','0','2'}, {'2','0','0','0','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'}, {'2','T','T','T','0','b','b','b','b','b','b','b','b','0','0','0','0','0','0','0','m','2'}, {'2','T','T','T','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'}, {'2','T','T','T','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'}, {'2','T','T','T','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','M'}, {'2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2'},};4.3.2：校園建筑信息structConstructconstruct[]={ {3,4,"office", "\n|一層為經(jīng)管系辦公室|\n|二層為外語系辦公室|\n|三層為文教系辦公室|\n|四層為計算機科學與技術系辦公室|\n|五樓為數(shù)理系辦公室|\n\n"}, //辦公室 {4,8,"classroom","學生上課的主要區(qū)域"},//教學樓A {1,13,"northDoor","是學生經(jīng)常出入的門，人流量較大"},//北門 {5,17,"playground","體育課上課的場所，學生健身的去處。"},//操場 {6,1,"westDoor","是學校的正門,前方有一個面具很多的停車區(qū)"},//西門 {7,8,"sod","種有花草和一些藝術標記物"},//草坪 {9,4,"lab","學生動手實踐的教室"},//實驗室 {9,7,"library","開放時間為：每天的8:00~21:00\n是老師和學生學習的好去處"},//圖書館 {9,16,"Whostel","女生宿舍樓"},//宿舍樓A {7,19,"SdiningRoom","靠近女生宿舍的食堂,飯菜口味比擬可口\n人流量較大,但只在供餐時間較短"},//食堂A {12,16,"Mhostel","男生宿舍樓"},//宿舍樓B {15,16,"Thostel","教師公寓樓"},//宿舍樓C {13,19,"TdiningRoom","靠近男生宿舍樓,供餐時間較長,隨時去隨時有飯"},//食堂B {14,4,"gym","內(nèi)部體育設施齊全,在里面可以打籃球、打排球、打羽毛球等等"},//體育館 {15,20,"eastDoor","學校正門，老師班車出入。"},//東門 {-1,-1,"Nofound","你找的建筑沒有找到"},};打印圖voidpri(chara[17][22],intbushu){ inti,j; for(i=0;i<17;i++){ for(j=0;j<22;j++){ switch(a[i][j]){ case'2':printf("■");break; case'A':printf("◆");break; case'c':printf("●");break; case'g':printf("△");break; case'p':printf("▓");break; case'0':printf("");break; case'b':printf("★");break; case'M':printf("□");break; case'm':printf("○");break; case'h':printf("☆");break; case'T':printf("▲");break; case'l':printf("╳");break; case'1':printf("╬");break; } } printf("\n"); } if(bushu>0){ printf("其行走的距離為%d米\n",bushu*50); } printf("備注:\n■為墻壁,◆辦公樓,●為教學區(qū),△為草坪,▓為操場,\n"); printf("★為圖書館,□為門,○為食堂,◆為宿舍,▲為體育館\n╳為實驗室\n");}導航函數(shù)voidnavigate(intx){ shortbushu=1000;/*用于記錄最短步數(shù)*/ structConstruct*qi; structConstruct*zh; intqiX,qiY,zhX,zhY; intc; inti=1; while(i==1){ printf("請輸入你所在位置:"); qi=selectName(15); if((-1)==qi->x){ printf("是否重新輸入你所在地:(1/0)\n"); scanf("%d",&c); if(c==1){ i=1;}else{return;}} else i=0; }; i=1; while(i==1){ printf("輸入你要的目的地:"); zh=selectName(15); if((-1)==zh->x){ printf("是否重新輸入你的目的地:(1/0)\n");scanf("%d",&c); if(c==1){ i=1;}else{return;}} else i=0; } qiX=qi->x; qiY=qi->y; zhX=zh->x;zhY=zh->y;num=1; visit(qiX,qiY,zhX,zhY,x); printf("其中最短路徑為:\n"); pri(jilu,shortbushu);}查找路徑voidvisit(intqiX,intqiY,intzhX,intzhY,intx){ //x為標志，用于控制要不要顯示所有的路徑 當其非0是顯示所有的路徑charn=arr[qiX][qiY]; arr[qiX][qiY]='1'; bushu++; if(qiX==zhX&&qiY==zhY){ if(x){ printf("第%d條線路\n",(num++)); pri(arr,bushu); } if(shortbushu>bushu){ shortbushu=bushu; fuzhi(); } } if(arr[qiX][qiY+1]=='0')visit(qiX,qiY+1,zhX,zhY,x); if(arr[qiX+1][qiY]=='0')visit(qiX+1,qiY,zhX,zhY,x); if(arr[qiX][qiY-1]=='0')visit(qiX,qiY-1,zhX,zhY,x); if(arr[qiX-1][qiY]=='0')visit(qiX-1,qiY,zhX,zhY,x); arr[qiX][qiY]=n; bushu--;}記錄最短路徑voidfuzhi(){ inti,j; for(i=0;i<17;i++){ for(j=0;j<22;j++){ jilu[i][j]=arr[i][j]; } }}3調(diào)試分析4附錄程序源代碼：#include<stdio.h>#include<string.h>#include<stdlib.h>charjilu[17][22];/*用于記錄最短路徑*/voidfuzhi();/*用于給最短路徑賦值*/intshortbushu=1000;/*用于記錄最短步數(shù)*/intnum=1;/*記錄多少條路*/intbushu=0;/*記錄走了多遠*/structConstructselectName(int*a,intn);/*根據(jù)名字查詢位置*/voidnavigate(intx);/*導航*/voidpri(char[][22],int);//打印圖voidadd();//增加建筑信息voidvisit(int,int,int,int,int);//遞歸查找路線chararr[17][22]={ /*2為墻壁■A辦公樓◆c教學區(qū)●g草坪△p操場▓0路b圖書館★M門□m食堂○h為宿舍☆T為體育館▲l為實驗室╳*/ //0123456789101112131415161718192021 {'2','2','2','2','2','2','2','2','2','2','2','2','2','M','2','2','2','2','2','2','2','2'}, {'2','A','A','A','0','c','c','c','c','c','c','c','c','0','2','p','p','p','p','p','p','2'}, {'2','A','A','A','0','c','c','c','c','c','c','c','c','0','2','p','p','p','p','p','p','2'}, {'2','A','A','A','0','c','c','c','c','c','c','c','c','0','2','p','p','p','p','p','p','2'}, {'2','A','A','A','0','0','0','0','0','0','0','0','0','0','2','p','p','p','p','p','p','2'}, {'2','A','A','A','0','g','g','g','g','g','g','g','g','0','2','2','2','0','2','2','2','2'}, {'M','0','0','0','0','g','g','g','g','g','g','g','g','0','0','0','0','0','0','0','m','2'}, {'2','l','l','l','0','0','0','0','0','0','0','0','0','0','h','h','h','h','h','0','m','2'}, {'2','l','l','l','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'}, {'2','l','l','l','0','b','b','b','b','b','b','b','b','0','0','0','0','0','0','0','m','2'}, {'2','l','l','l','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','0','2'}, {'2','0','0','0','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'}, {'2','T','T','T','0','b','b','b','b','b','b','b','b','0','0','0','0','0','0','0','m','2'}, {'2','T','T','T','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'}, {'2','T','T','T','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'}, {'2','T','T','T','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','M'}, {'2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2'},};structConstruct{ intx; inty; charname[25]; charmiaoshu[10000];};structConstructconstruct[]={ {3,4,"office", "\n|一層為經(jīng)管系辦公室|\n|二層為外語系辦公室|\n|三層為文教系辦公室|\n|四層為計算機科學與技術系辦公室|\n|五樓為數(shù)理系辦公室|\n\n"}, //辦公室 {4,8,"classroom","學生上課的主要區(qū)域"},//教學樓A {1,13,"northDoor","是學生經(jīng)常出入的門，人流量較大"},//北門 {5,17,"playground","體育課上課的場所，學生健身的去處。"},//操場 {6,1,"westDoor","是學校的正門,前方有一個面具很多的停車區(qū)"},//西門 {7,8,"sod","種有花草和一些藝術標記物"},//草坪 {9,4,"lab","學生動手實踐的教室"},//實驗室 {9,7,"library","開放時間為：每天的8:00~21:00\n是老師和學生學習的好去處"},//圖書館 {9,16,"Whostel","女生宿舍樓"},//宿舍樓A {7,19,"SdiningRoom","靠近女生宿舍的食堂,飯菜口味比擬可口\n人流量較大,但只在供餐時間較短"},//食堂A {12,16,"Mhostel","男生宿舍樓"},//宿舍樓B {15,16,"Thostel","教師公寓樓"},//宿舍樓C {13,19,"TdiningRoom","靠近男生宿舍樓,供餐時間較長,隨時去隨時有飯"},//食堂B {14,4,"gym","內(nèi)部體育設施齊全,在里面可以打籃球、打排球、打羽毛球等等"},//體育館 {15,20,"eastDoor","學校正門，老師班車出入。"},//東門 {-1,-1,"Nofound","你找的建筑沒有找到"},};voidar(){ intm,n; for(m=0;m<17;m++){ for(n=0;n<22;n++){ printf("%c",arr[m][n]); } printf("\n"); }}structConstruct*selectName(intn)/*根據(jù)名字查詢位置*/{ inti; charname[15]; scanf("%s",&name); for(i=0;i<n;i++){ if(strcmp(construct[i].name,name)==0){ return&construct[i]; }} printf("給位置沒有找到\n"); return&construct[15];}intmain(){ inti; intn=15; structConstruct*jianzhu; while(1){ printf("歡送來到蚌埠學院,我們將為你提供貼心的導航效勞\n"); printf("*********************************************\n"); printf("1.學校整體布局\n"); printf("2.建筑查詢\n"); printf("3.導航\n"); printf("4.顯示最短路徑\n"); printf("5.退出\n"); printf("*********************************************\n"); scanf("%d",&i); switch(i){ case1: printf("查詢位置\n"); pri(arr,0); break; case2:printf("請輸入查詢建筑的名稱:\n");jianzhu=selectName(n); if(-1!=jianzhu->x) printf("該建筑所在的坐標為%d%d\n",jianzhu->x,jianzhu->y); printf("%s\n",jianzhu->miaoshu); break; case3: printf("導航\n"); navigate(1); break; case4: printf("其中最短路徑為:\n"); navigate(0); //pri(jilu,shortbushu); break; case5: printf("退出"); exit(0); break; } }; return0;}voidnavigate(intx){ shortbushu=1000;/*用于記錄最短步數(shù)*/ structConstruct*qi; structConstruct*zh; intqiX,qiY,zhX,zhY; intc; inti=1; while(i==1){ printf("請輸入你所在位置:"); qi=selectName(15); if((-1)==qi->x){ printf("是否重新輸入你所在地:(1/0)\n"); scanf("%d",&c); if(c==1){ i=1;}else{return;}} else i=0; }; i=1; while(i==1){ printf("輸入你要的目的地:"); zh=selectName(15); if((-1)==zh->x){ printf("是否重新輸入你的目的地:(1/0)\n");scanf("%d",&c); if(c==1){ i=1;}else{return;}} else i=0; } qiX=qi->x; qiY=qi->y; zhX=zh->x;zhY=zh->y;num=1; visit(qiX,qiY,zhX,zhY,x); printf("其中最短路徑為:\n"); pri(jilu,shortbushu);}/*2為墻壁■A辦公樓◆c教學區(qū)●g草坪△p操場▓0路b圖書館★M門□m食堂○h為宿舍◆T為體育館▲*/voidpri(chara[17][22],intbushu){ inti,j; for(i=0;i<17;i++){ for(j=0;j<22;j++){ switch(a[i][j]){ case'2':printf("■");break; case'A':printf("◆");break; case'c':printf("●");break; case'g':printf("△");break; case'p':printf("▓");break; case'0':printf("");break; case'b':printf("★");break; case'M':printf("□");break; case'm':printf("○");break; case'h':printf("☆");break; case'T':printf("▲");br