數(shù)據(jù)結(jié)構(gòu) 圖應(yīng)用與導(dǎo)航系統(tǒng)

1、孝感學(xué)院計(jì)算機(jī)與信息科學(xué)學(xué)院09級(jí)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題目：GPS導(dǎo)航系統(tǒng)簡(jiǎn)潔版班級(jí)：0917142學(xué)號(hào)：091714208姓名：付園園指導(dǎo)老師：李志敏首頁(yè)GPS導(dǎo)航系統(tǒng)簡(jiǎn)潔版課題：GPS導(dǎo)航系統(tǒng)與圖的應(yīng)用設(shè)計(jì)：計(jì)科學(xué)院 軟件工程091714208 付園園指導(dǎo)老師：李志敏運(yùn)用原理：圖的存儲(chǔ)與尋最短路徑描述語(yǔ)言：c程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)功能：詳見(jiàn)功能介紹目錄：目的與要求5設(shè)計(jì)及實(shí)現(xiàn)要點(diǎn)6程序設(shè)計(jì)的基本結(jié)構(gòu)：6功能介紹：9改進(jìn)創(chuàng)新：9期間遇到的問(wèn)題，解決方案，總結(jié)：9漏洞發(fā)現(xiàn)與解決txt:10源程序：10功能測(cè)試與調(diào)試：26功能測(cè)試126功能測(cè)試228功能測(cè)試328功能測(cè)試329功能測(cè)試430功能測(cè)試5

2、：30功能測(cè)試6：31功能測(cè)試7：32功能測(cè)試8：33功能測(cè)試934功能測(cè)試1035功能測(cè)試1136功能測(cè)試1237功能測(cè)試1338功能測(cè)試1439結(jié)后語(yǔ)45目的與要求目的： 1：掌握?qǐng)D結(jié)構(gòu)的存儲(chǔ) 運(yùn)用 Floyd算法的實(shí)現(xiàn)尋最短路徑；2：理解運(yùn)用圖結(jié)構(gòu)解決問(wèn)題的思想；3：運(yùn)用功能函數(shù)實(shí)現(xiàn)尋找最短路徑的方法；要求 （1）基本要求： 利用C語(yǔ)言面向過(guò)程的編程思想來(lái)完成系統(tǒng)的設(shè)計(jì)； . 突出C語(yǔ)言的函數(shù)特征，以多個(gè)函數(shù)實(shí)現(xiàn)每一個(gè)子功能； 畫(huà)出功能模塊圖； 進(jìn)行簡(jiǎn)單界面設(shè)計(jì)，能夠?qū)崿F(xiàn)友好的交互； . 具有清晰的程序流程圖和數(shù)據(jù)結(jié)構(gòu)的詳細(xì)定義； 設(shè)計(jì)及實(shí)現(xiàn)要點(diǎn)程序設(shè)計(jì)的基本結(jié)構(gòu)：GPS 導(dǎo) 航 系 統(tǒng)

3、管 理 員 端（密 碼）用 戶(hù) 端修改矩陣查看矩陣返回登錄尋最短距離路徑尋最少花費(fèi)路徑尋最短時(shí)間路徑返回登錄新建存儲(chǔ)Floyd算法 鄰接矩陣存儲(chǔ) 圖的優(yōu)先及深度遍歷 尋最短路徑數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)#define GRAPHMAX 20#define MAX 100#define FALSE 0#define TRUE 1#define QueueSize 30typedef structchar nameMAX;arcell;typedef struct arcell vexsGRAPHMAX;int edgesGRAPHMAXGRAPHMAX;int edgestimeGRAPHMAXGRAPHMA

4、X;int edgescostGRAPHMAXGRAPHMAX;int n,e; MGraph;int shortestGRAPHMAXGRAPHMAX;int costGRAPHMAXGRAPHMAX;int pathGRAPHMAXGRAPHMAX;int visited10;主體函數(shù)及說(shuō)明：void biaotu(MGraph *G).顯示表格以便用戶(hù)選擇使用；void CreateMGraph(MGraph *G)創(chuàng)建圖的鄰接矩陣存儲(chǔ)；int display( MGraph *G,int i,int j)顯示最短路徑所經(jīng)的站點(diǎn)void floyed(MGraph *G) Floyd算法

5、實(shí)現(xiàn)void juzhengvision(MGraph* G).矩陣存儲(chǔ)，以便調(diào)試查看void leastcost(MGraph *G).尋最少花費(fèi)的路徑void leasttime(MGraph *G).尋最短時(shí)間的路徑void locatetosave1(MGraph *G,int i,int j).進(jìn)行矩陣準(zhǔn)確定位以便存儲(chǔ)void locatetosave2(MGraph *G,int i,int j) .進(jìn)行矩陣準(zhǔn)確定位以便存儲(chǔ)void locatetosave3(MGraph *G,int i,int j) .進(jìn)行矩陣準(zhǔn)確定位以便存儲(chǔ)void pathvision(MGraph *G

6、)路徑展示void shortestdistance(MGraph *G )核心算法與功能功能介紹：圖的存儲(chǔ)和遍歷 1-更新鄰接矩陣 2-深度優(yōu)先遍歷 0-返回上一界面 printf("n *") 【查 詢(xún) 最 短 路 線(xiàn) (1號(hào)鍵)】 用戶(hù)端 【查 詢(xún) 最 短 時(shí) 間 (2號(hào)鍵)】 【查 詢(xún) 最 少 花 費(fèi) (3號(hào)鍵)】 【退 出 系 統(tǒng) (0號(hào)鍵) 】 printf("n *") printf("t*新建(1號(hào)鍵) 查看(2號(hào)鍵)*n");管理員端 printf("t*刪除(3號(hào)鍵) 修改(4號(hào)鍵)*n");

7、printf("t* 退出(0號(hào)鍵) *n"); 改進(jìn)創(chuàng)新： 期間遇到的問(wèn)題，解決方案，總結(jié)：漏洞發(fā)現(xiàn)與解決txt:針對(duì)以上遇到的問(wèn)題或者功能的不完善，在后期的強(qiáng)化過(guò)程中都得到解決，雖然不是超級(jí)完美但依舊是一種進(jìn)步；經(jīng)歷這么一個(gè)過(guò)程后，對(duì)c語(yǔ)言確實(shí)有了新的認(rèn)識(shí)和提高！源程序：# include <stdio.h># include <stdlib.h># include <string.h># include <iostream.h>#define GRAPHMAX 20#define MAX 100#define FALSE

8、 0#define TRUE 1#define QueueSize 30typedef structchar nameMAX;arcell;typedef struct arcell vexsGRAPHMAX;int edgesGRAPHMAXGRAPHMAX;int edgestimeGRAPHMAXGRAPHMAX;int edgescostGRAPHMAXGRAPHMAX;int n,e; MGraph;int shortestGRAPHMAXGRAPHMAX;int costGRAPHMAXGRAPHMAX;int pathGRAPHMAXGRAPHMAX;int visited10;

9、void locatetosave1(MGraph *G,int i,int j)/.準(zhǔn)確定位存儲(chǔ)距離int m=0,n=0;for(m=1;m<=G->n;m+)if(m=i)for(n=1;n<=G->n;n+)if(n=j)scanf("%d",&G->edgesmn);void locatetosave2(MGraph *G,int i,int j)/.準(zhǔn)確定位存儲(chǔ)時(shí)間int m=0,n=0;for(m=1;m<=G->n;m+)if(m=i)for(n=1;n<=G->n;n+)if(n=j)scanf

10、("%d",&G->edgestimemn);void locatetosave3(MGraph *G,int i,int j)/.準(zhǔn)確定位存儲(chǔ)花費(fèi)int m=0,n=0;for(m=1;m<=G->n;m+)if(m=i)for(n=1;n<=G->n;n+)if(n=j)scanf("%d",&G->edgescostmn); void CreateMGraph(MGraph *G)int i=0,j=0,k;printf("n 【請(qǐng) 輸 入 模 擬 導(dǎo) 航 圖 的 城 市 數(shù) 并 按 回

11、 車(chē) ：】");scanf("%d",&(G->n); printf("n 【請(qǐng) 輸 入 模 擬 導(dǎo) 航 圖 的 邊 數(shù) 并 按 回 車(chē) ：】");scanf("%d",&(G->e); /輸入定點(diǎn)數(shù)，邊數(shù)for(i=1;i<=G->n;i+) system("cls"); /輸入頂點(diǎn) printf("ntt請(qǐng)輸入第%d個(gè)城市名稱(chēng)并按回車(chē) ：",i); scanf("%s",&(G->);fo

12、r(i=1;i<=G->n;i+)for(j=1;j<=G->n;j+)G->edgestimeij=MAX;G->edgescostij=MAX;G->edgesij=MAX;for(k=1;k<=G->e;k+) printf("n請(qǐng) 輸 入 第 %d 條 邊 的 城 市 代 號(hào) ( 格 式 如 ： 1 ， 3 )：",k); printf("n請(qǐng) 輸 入 起 點(diǎn) 城 市 代 號(hào) (1-%d 內(nèi)) ",G->n); scanf("%d",&i);/連用要在一起.

13、if(i<1|i>G->n)printf("請(qǐng)重新輸入：n");scanf("%d",&i); printf("n請(qǐng) 輸 入 終 點(diǎn) 城 市 代 號(hào) (1-%d 內(nèi)) ",G->n); scanf("%d",&j); if(j<1|j>G->n)printf("請(qǐng)重新輸入：n");scanf("%d",&j); printf("n請(qǐng) 輸 入 第 %d 條 邊 %d->%d 之 間 距 離: &q

14、uot;,k,i,j); locatetosave1(G,i,j);/ 需要一個(gè)定位函數(shù)。否則不能準(zhǔn)確存值printf("n請(qǐng) 輸 入 %d->%d所 需 的 時(shí) 間 ：",i,j);locatetosave2(G,i,j);printf("n請(qǐng) 輸 入 %d->%d所 需 的 費(fèi) 用 ：",i,j);locatetosave3(G,i,j); /.如何解決不能連續(xù)輸入這個(gè)問(wèn)題.getchar() 接受任意字符. for(i=1;i<=G->n;i+) G->edgesii=0; G->edgestimeii=0; G

15、->edgescostii=0; for(i=1;i<=G->n;i+) for(j=1;j<=G->n;j+) G->edgesji=G->edgesij; G->edgestimeji=G->edgestimeij; G->edgescostji=G->edgescostij; /.實(shí)現(xiàn)互補(bǔ).floyed 算法前必不可少的更正！/.cost 數(shù)組的 賦值./*void DFSM(MGraph *G,int i) int j;printf("n深度優(yōu)先遍歷序列：%cn",G->vexsi);visit

16、edi=FALSE;printf(" DFSM n");for(j=1;j<=G->n;j+)if(G->edgesij=1&&!visitedj)DFSM(G,j);void DFSTraverseM(MGraph *G) /深度優(yōu)先遍歷 int i; for(i=1;i<=G->n;i+) visitedi=FALSE; printf(" DFST n"); for(i=1;i<=G->n;i+) if(!visitedi)DFSM(G,i);*/ void wait() int i=2000

17、00000; while(i)i-; /.時(shí)間延長(zhǎng) 以達(dá)到動(dòng)態(tài)效果.void biaotu(MGraph *G)int count;for(int i=1;i<=G->n;i+)count+;if(count%3=0)printf("n");printf("n%10s(%d)",G->,i);void floyed(MGraph *G) / flyed 算法 最短路徑求解的核心算法int i,j,k;for(i=1;i<=G->n;i+)for(j=1;j<=G->n;j+) shortest

18、ij=costij; pathij=22;/.path賦初值 22表示無(wú)路徑.for(k=1;k<=G->n;k+)for(i=1;i<=G->n;i+)for(j=1;j<=G->n;j+) if(shortestij>(shortestik+shortestkj) shortestij=shortestik+shortestkj; pathij=k; pathji=k; void pathvision(MGraph *G)int i,j;printf(" path 的存值與路徑關(guān)聯(lián) ：n"); for(i=1;i<=G-&

19、gt;n;i+)printf("n");for(j=1;j<=G->n;j+)printf("%5d",pathij); int display( MGraph *G,int i,int j)/ int a,b;int p20,count=0;/p存儲(chǔ)最短距離上的點(diǎn)，count來(lái)計(jì)數(shù)a=i;b=j;if(shortestij!=MAX)if(i<j)p0=b;count+;while(pathij!=22)pcount=pathij;count+;if(i<j)j=pathij;elsei=pathji;pcount=a;for(

20、;count>=1;count-)printf("->%5s->",G->); printf("%5s",G->);elseprintf("%5s",G->);while(pathij!=22)printf("->%5s->",G->);if(i<j)j=pathij;elsei=pathji;printf("%5s",G->vex

21、);/return shortestab;elseprintf("sorry ! 不存在此路徑n");return NULL;void leastcost(MGraph *G) int i,j;for(int m=1;m<=G->n;m+) for(int n=1;n<=G->n;n+) costmn=G->edgescostmn;printf("該導(dǎo)航圖的矩陣表示為：n");for(int k=1;k<=G->n;k+)printf("n");for(int b=1;b<

22、=G->n;b+)printf("%5d",costkb);/此處需要一個(gè)圖像顯示函數(shù)，以供用戶(hù)選擇！biaotu(G);printf("nn請(qǐng)輸入要查詢(xún)兩個(gè)城市 的起點(diǎn)城市編號(hào):【 】"); scanf("%d",&i);/連用要在一起. if(i>0&&i<=G->n) printf("nn起點(diǎn)城市在查找范圍庫(kù)!n"); else printf("nn請(qǐng)重新輸入要查詢(xún)兩個(gè)城市 的起點(diǎn)城市:");/.起點(diǎn) 與終點(diǎn)城市 不能相同 ！ scanf(&

23、quot;%d",&i); printf("nn請(qǐng)輸入要查詢(xún)兩個(gè)城市 的終點(diǎn)城市:【 】"); scanf("%d",&j); if(j>0&&j<=G->n) printf("nn終點(diǎn)城市在查找范圍庫(kù)!n"); else printf("nn請(qǐng)重新輸入要查詢(xún)兩個(gè)城市 的終點(diǎn)城市:");/.起點(diǎn) 與終點(diǎn)城市 不能相同 ！scanf("%d",&j); printf("n您所要查詢(xún)的城市是：%s -> %s &qu

24、ot;,G->,G->); floyed(G); int y= display( G,i,j);/. printf("nn城市%s(%d)->%s(%d)的最少花費(fèi)是：%d",G->,i,G->,j,y);void leasttime(MGraph *G) int i,j;for(int m=1;m<=G->n;m+) for(int n=1;n<=G->n;n+) costmn=G->edgestimemn;printf("

25、該導(dǎo)航圖的矩陣表示為：n");for(int k=1;k<=G->n;k+)printf("n");for(int b=1;b<=G->n;b+)printf("%5d",costkb);/此處需要一個(gè)圖像顯示函數(shù)，以供用戶(hù)選擇！biaotu(G);printf("nn請(qǐng)輸入要查詢(xún)兩個(gè)城市 的起點(diǎn)城市編號(hào):【 】"); scanf("%d",&i);/連用要在一起. if(i>0&&i<=G->n) printf("nn起點(diǎn)城市在

26、查找范圍庫(kù)!n"); else printf("nn請(qǐng)重新輸入要查詢(xún)兩個(gè)城市 的起點(diǎn)城市:"); scanf("%d",&i); printf("nn請(qǐng)輸入要查詢(xún)兩個(gè)城市 的終點(diǎn)城市:【 】"); scanf("%d",&j); if(j>0&&j<=G->n) printf("nn終點(diǎn)城市在查找范圍庫(kù)!n"); else printf("nn請(qǐng)重新輸入要查詢(xún)兩個(gè)城市 的終點(diǎn)城市:");/.起點(diǎn) 與終點(diǎn)城市 不能相同

27、 ！scanf("%d",&j); printf("n您所要查詢(xún)的城市是：%s -> %s ",G->,G->); floyed(G); int y= display( G,i,j);/. printf("nn城市%s(%d)->%s(%d)的最短距離是：%d",G->,i,G->,j,y);void juzhengvision(MGraph* G)/ 查看各個(gè)矩陣存儲(chǔ)情況 以便調(diào)試.int i,j;printf

28、("n路徑長(zhǎng)度存儲(chǔ)矩陣！n");for(i=1;i<=G->n;i+) printf("ntt"); for(j=1;j<=G->n;j+) printf("%5d",G->edgesij); printf("n旅途花費(fèi)存儲(chǔ)矩陣！n");for(i=1;i<=G->n;i+) printf("ntt"); for(j=1;j<=G->n;j+) printf("%5d",G->edgescostij); printf

29、("n時(shí)間花費(fèi)存儲(chǔ)矩陣！n");for(i=1;i<=G->n;i+) printf("ntt"); for(j=1;j<=G->n;j+) printf("%5d",G->edgestimeij); pathvision(G);void shortestdistance(MGraph *G ) int i,j;for(int m=1;m<=G->n;m+) for(int n=1;n<=G->n;n+) costmn=G->edgesmn;printf("該導(dǎo)航圖

30、的矩陣表示為：n");for(int k=1;k<=G->n;k+)printf("n");for(int b=1;b<=G->n;b+)printf("%5d",costkb);/此處需要一個(gè)圖像顯示函數(shù)，以供用戶(hù)選擇！biaotu(G);printf("nn請(qǐng)輸入要查詢(xún)兩個(gè)城市 的起點(diǎn)城市編號(hào):【 】"); scanf("%d",&i);/連用要在一起. if(i>0&&i<=G->n) printf("nn起點(diǎn)城市在查找范圍

31、庫(kù)!n"); else printf("nn請(qǐng)重新輸入要查詢(xún)兩個(gè)城市 的起點(diǎn)城市:");/.起點(diǎn) 與終點(diǎn)城市 不能相同 ！ scanf("%d",&i); printf("nn請(qǐng)輸入要查詢(xún)兩個(gè)城市 的終點(diǎn)城市:【 】"); scanf("%d",&j); if(j>0&&j<=G->n) printf("nn終點(diǎn)城市在查找范圍庫(kù)!n"); else printf("nn請(qǐng)重新輸入要查詢(xún)兩個(gè)城市 的終點(diǎn)城市:");/.

32、起點(diǎn) 與終點(diǎn)城市 不能相同 ！scanf("%d",&j); printf("n您所要查詢(xún)的城市是：%s -> %s n",G->,G->); floyed(G); int y= display( G,i,j);/. printf("nn城市%s(%d)->%s(%d)的最短距離是：%dn",G->,i,G->,j,y);void filesave(MGraph *G)FILE *fp;fp=fopen(&quo

33、t;a.txt","w");if(fp=fopen("a.txt","wb+")=NULL) printf("無(wú)法打開(kāi)文件!n"); for(int i=1;i<=G->n;i+) fprintf(fp,"%3s",&G->); fclose(fp); void fileoutput(MGraph *G) void wait1()printf("nt【十秒鐘后自動(dòng)返回！】n"); wait();wait();wait()

34、;wait();wait();wait();wait();wait(); int main (void)MGraph *G,a; G=&a;printf("tt*nn");wait();printf("tt|<<<<<<<<<*>>>>>>*<<<<<*>>>>>>>>>|nn");wait();printf("tt| |nn");wait();print

35、f("tt| 091714208 付園園【GPS導(dǎo)航系統(tǒng)】 |nn");wait();printf("tt| |nn");wait();printf("tt| |nn");wait();printf("tt|<<<<<<<<*>>>>>>>*<<<<<<*>>>>>>>|nn");wait(); printf("tt*n");wa

36、it();wait();system("cls"); printf("tt*nn");wait();printf("tt|<<<<<<<<<<<<<<<<*>>>>>>>>>>>>>>>|nn");wait();printf("tt| |nn");wait();printf("tt| 歡迎進(jìn)入GPS 導(dǎo)航系統(tǒng) |nn&qu

37、ot;);wait();printf("tt| |nn");wait();printf("tt|-|nn");wait(); printf("tt*n");wait(); system("cls"); char ch1; int ch2; printf("nn |自 動(dòng) 建 立 導(dǎo) 航 圖 鄰 接 矩 陣 表 示 |n"); wait(); wait(); system("cls"); CreateMGraph(G); printf("導(dǎo) 航 圖 的 鄰 接 矩 陣

38、 建 立 完 畢 n"); ch1='y' while(ch1='y'|ch1='Y') printf("n"); printf("n 圖的存儲(chǔ)和遍歷 "); printf("n *"); printf("n * 1-更新鄰接矩陣 *"); printf("n * 2-深度優(yōu)先遍歷 *"); printf("n * 0-返回上一界面 *"); printf("n *"); printf("

39、n 請(qǐng)選擇菜單號(hào)(0-3):"); scanf("%d",&ch2); getchar(); switch(ch2) case 1:system("cls");CreateMGraph(G);printf("已建立導(dǎo)航圖的鄰接矩陣存儲(chǔ)n"); break; case 2: ;break; case 0:ch1='n'break; default:printf("n輸出錯(cuò)誤！請(qǐng)重新輸入！"); system("cls"); printf("tt*nn&q

40、uot;);printf("tt| 【歡迎進(jìn)入GPS 導(dǎo)航系統(tǒng)】 |nn");printf("tt| 【請(qǐng)選擇您所登錄的界面】 |nn"); printf("tt*n");printf("ntt普通用戶(hù)請(qǐng)按1 ，管理員請(qǐng)按2，退出請(qǐng)按0nn");int choice1,choice2,choice3 ;doscanf("%d",&choice1);if(choice1>2|choice1<0)printf("ntt 普通用戶(hù)請(qǐng)按1 ，管理員請(qǐng)按2，退出請(qǐng)按0nn&q

41、uot;); scanf("%d",&choice1);system("cls");switch(choice1)case 0: ;break;/.文件保存接口./case 1 : do printf("t【 歡 迎 進(jìn) 入 GPS 導(dǎo) 航 普 通 用 戶(hù) 端!】n"); printf("nt【 請(qǐng) 稍 后！系 統(tǒng) 正 在 轉(zhuǎn) 接 中.】"); wait();wait();wait();system("cls");printf("nnt*n");printf(&quo

42、t;nnt<<<<<<<<<<<<*>>>>>>>>*<<<<<<<<<<*>>>>>>>>>n"); printf("t* 【查 詢(xún) 最 短 路 線(xiàn) (1號(hào)鍵)】 *n"); printf("t* 【查 詢(xún) 最 短 時(shí) 間 (2號(hào)鍵)】 *n"); printf("t* 【查 詢(xún) 最 少 花 費(fèi) (3號(hào)

43、鍵)】 *n"); printf("t* 【退 出 系 統(tǒng) (0號(hào)鍵) 】 *n"); printf("t*n");printf("nn請(qǐng)輸入您所要選擇的功能：n");scanf("%d",&choice3);switch(choice3)case 0: ;break;case 1:system("cls");shortestdistance(G);wait1(); break;case 2:system("cls");leasttime(G);wait1(

44、);break;case 3:system("cls");leastcost(G);wait1();break;default: printf("輸入錯(cuò)誤！請(qǐng)重新輸入！");break; wait();wait();wait();while(choice3!=0);printf("tt*nn");printf("tt| 歡迎進(jìn)入GPS 導(dǎo)航系統(tǒng) |nn");printf("tt| 請(qǐng)選擇您所登錄的界面 |nn"); printf("tt*n");printf("nt

45、t普通用戶(hù)請(qǐng)按1 ，管理員請(qǐng)按2，退出請(qǐng)按0nn");break;/*.接case 1.*/case 2:/*.管理員端接口.*/printf("tt_n");printf("tt| 歡迎進(jìn)入GPS 導(dǎo)航管理員端! |nn");printf("tt| 請(qǐng)輸入管理員登錄密碼(初始密碼123) |n"); printf("tt_n");int password ;scanf("%d",&password);if(password=123)do printf("t*n&qu

46、ot;);printf("t*新建(1號(hào)鍵) 查看(2號(hào)鍵)*n");printf("t*刪除(3號(hào)鍵) 修改(4號(hào)鍵)*n");printf("t* 退出(0號(hào)鍵) *n"); printf("t*n"); printf("nn請(qǐng)輸入您所要選擇的功能：n"); scanf("%d",&choice2);switch(choice2)case 0:filesave(G) ; break;case 1: CreateMGraph(G); break;case 2: system("cls");juzhengvision(G); break;case 3:CreateMGraph(G); break;case 4:CreateMGraph(G); break; default: printf("輸入錯(cuò)誤！請(qǐng)重新輸入！"); break; while(choice2!=0);system("cls");printf("tt*