基于C語言的數(shù)字校園問題

1、課程設(shè)計報告 報告名稱：基于C語言的數(shù)字校園問題： 學(xué)號：【摘要】本文利用C語言，設(shè)計了一個可供游人查詢校園內(nèi)道路選擇的系統(tǒng)，可以查詢查詢圖中任意兩個地點間的所有路徑，并求出最短路徑，同時增加、刪除、更新有關(guān)地點和道路的信息。通過模擬得到測試結(jié)果。關(guān)鍵詞：數(shù)字校園、最短路徑一、設(shè)計目標(biāo) 事實上，如果是初來乍到的人到電子科大來，難免會遇到迷路或者不知道走哪條路最近的問題。本設(shè)計就是為了到達(dá)給他們提供這樣信息的目的，設(shè)計一個方便查詢各地點路徑的系統(tǒng)。即設(shè)計一個簡易的數(shù)字校園系統(tǒng),實現(xiàn)道路的選擇。二、設(shè)計要求設(shè)計一個系統(tǒng)，要求完成以下功能：1、查詢各地點的相關(guān)信息 2、查詢圖中任意兩個地點間的最短路

2、徑。 3、查詢圖中任意兩個地點間的所有路徑。 4、增加、刪除、更新有關(guān)地點和道路的信息。為了到達(dá)這些功能，我們可以將宿舍樓,教學(xué)樓,主樓,圖書館,食堂,超市,等等作為節(jié)點，各節(jié)點之間有道路相連,每條道路有長度，則問題轉(zhuǎn)化為最優(yōu)路線規(guī)劃問題。因為在學(xué)校里面，人流量不算很多，車流量也可以得到控制，行人的出行基本不受干擾，則可以忽略人流量的問題。則我們需要做的工作是：1、輸出頂點信息：將校園內(nèi)各位置輸出。2、輸出邊的信息：將校園內(nèi)每兩個位置假設(shè)兩個位置之間有直接路徑的距離輸出。3、修改：修改兩個位置假設(shè)兩個位置之間有直接路徑的距離，并重新輸出每兩個位置假設(shè)兩個位置之間有直接路徑的距離。4、求最短路徑

3、：輸出給定兩點之間的最短路徑的長度及途徑的地點或輸出任意一點與其它各點的最短路徑。5、刪除：刪除任意一條邊。6、插入：插入任意一條邊。三、程序功能1、查詢地點的信息 2、查詢?nèi)我鈨傻攸c之間的最短路徑及路徑長度。 3、查詢?nèi)我鈨傻攸c之間的所有路線。 4、在已有的校園導(dǎo)游圖中添加新的地點及該地點到其他景點的路徑長度。5、在已有的校園導(dǎo)游圖中刪除已有的地點及以該地點為端點的路徑。 6、修改已有校園導(dǎo)游圖中的任意一個地點的名稱和地點信息或任意一條路徑的長度。7、重新創(chuàng)建一個新的學(xué)校的導(dǎo)游圖。四、系統(tǒng)設(shè)計1、系統(tǒng)總圖 圖1該程序運用數(shù)據(jù)結(jié)構(gòu)中的圖的鄰接表的存儲方式用頂點來存儲地點的名稱和地點信息等用邊來

4、存儲路徑的長度等信息。之后以有向圖的鄰接矩陣的方式用Dijkstra算法來求圖的最短路徑問題以及圖的遍歷來求兩點間的所有路徑問題。最后用圖的添加、刪除、修改等基本操作完成對校園導(dǎo)游圖的修改和重新創(chuàng)建。2、程序設(shè)計#include "stdio.h" #include "stdio.h" #include "malloc.h" #include "stdlib.h" #define Max 20000 typedef struct ArcCell int adj; /* 相鄰接的地點之間的路程 */ ArcCell;

5、 /* 定義邊的類型 */ typedef struct VertexType int number; /* 地點編號 */ char sight100; /* 地點名稱 */ char description1000; /* 地點描述 */ VertexType; /* 定義頂點的類型 */ typedef struct VertexType vex20; /* 圖中的頂點即為地點 */ ArcCell arcs2020; /* 圖中的邊即為地點間的距離 */ int vexnum,arcnum; /* 頂點數(shù)邊數(shù) */ MGraph; /* 定義圖的類型 */ MGraph G; /* 把

6、圖定義為全局變量 */ char nameofschool100; int NUM=9; int P2020; /* */ int p20;/*全局?jǐn)?shù)組用來存放路徑上的各頂點*/ int visited20;/*全局?jǐn)?shù)組用來記錄各頂點被訪問的情況*/ int a=0;/*全局變量用來記錄每對頂點之間的所有路徑的條數(shù)*/ long int D20; /* 輔助變量存儲最短路徑長度 */ int x20=0; void CreateUDN(int v,int a); /* 造圖函數(shù) */ void narrate(); /*說明函數(shù)*/ void ShortestPath(int num); /*

7、最短路徑函數(shù)*/ void output(int sight1,int sight2); /*輸出函數(shù)*/ char Menu(); /* 主菜單 */ void search(); /* 查詢地點信息 */ char SearchMenu(); /* 查詢子菜單 */ void HaMiTonian(int); /* 哈密爾頓圖的遍歷 */ void Searchpath1(MGraph g);/*查詢兩個地點間的所有路徑*/ void disppath(MGraph g,int i,int j); void path(MGraph g,int i,int j,int k);/*確定路徑上第

8、k+1個頂點的序號*/ void NextValue(int); void display(); /* 顯示遍歷結(jié)果 */ int Addnewsight(int n); /*添加新的地點和路徑*/ int Deletesight(int n); /*刪除地點和路徑*/ void Changesight(); /*修改地點和路徑*/ char Changemenu(); /*修改路徑或頂點的選擇菜單*/ char Sightmenu(); /*選擇需該地點的菜單*/ void NewCreateUDN(); /*創(chuàng)建新的導(dǎo)游圖*/ void main() /* 主函數(shù) */ int v0,v1

9、; char ck; system("color 2"); CreateUDN(NUM,11); do ck=Menu(); switch(ck) case '1': search(); break; case '2': system("cls"); narrate(); printf("nnttt請選擇起點地點0%d",NUM-1); scanf("%d",&v0); printf("ttt請選擇終點地點0%d",NUM-1); scanf("

10、%d",&v1); ShortestPath(v0); /* 計算兩個地點之間的最短路徑 */ output(v0,v1); /* 輸出結(jié)果 */ printf("nntttt請按任意鍵繼續(xù).n"); getchar(); getchar(); break; case '3': system("cls"); narrate(); x0=1; Searchpath1(G); printf("nntttt請按任意鍵繼續(xù).n"); getchar(); getchar(); break; case'

11、4': system("cls"); narrate(); NUM=Addnewsight(NUM); system("cls"); narrate(); break; case'5': NUM=Deletesight(NUM); break; case'6': Changesight(); break; case'7': NewCreateUDN(); break; ; while(ck!='e'); char Menu() /* 主菜單 */ char c; int flag;

12、do flag=1; system("cls"); narrate(); printf("ntttn"); printf("ttt n"); printf("ttt 1、查詢地點信息 n"); printf("ttt 2、查詢兩地點間最短路徑 n"); printf("ttt 3、查詢兩地點間所有路線 n"); printf("ttt 4、添加新的地點和路徑 n"); printf("ttt 5、刪除已有地點和路徑 n"); print

13、f("ttt 6、修改已有地點和路徑 n"); printf("ttt 7、創(chuàng)建新的校園導(dǎo)游圖 n"); printf("ttt e、退出 n"); printf("ttt n"); printf("tttn"); printf("tttt請輸入您的選擇"); scanf("%c",&c); if(c='1'|c='2'|c='3'|c='4'|c='5'|c='

14、;6'|c='7'|c='e') flag=0; while(flag); return c; char SearchMenu() /* 查詢子菜單 */ char c; int flag; do flag=1; system("cls"); narrate(); printf("ntttn"); printf("ttt n"); printf("ttt 1、按照地點編號查詢 n"); printf("ttt 2、按照地點名稱查詢 n"); printf(

15、"ttt e、返回 n"); printf("ttt n"); printf("tttn"); printf("tttt請輸入您的選擇"); scanf("%c",&c); if(c='1'|c='2'|c='e') flag=0; while(flag); return c; void search() /* 查詢地點信息 */ int num; int i; char c; char name20; do system("cl

16、s"); c=SearchMenu(); switch (c) case '1': system("cls"); narrate(); printf("nntt請輸入您要查找的地點編號"); scanf("%d",&num); for(i=0;i<NUM;i+) if(num=G.vexi.number) printf("nnttt您要查找地點信息如下:"); printf("nnttt%-25snn",G.vexi.description); print

17、f("nttt按任意鍵返回."); getchar(); getchar(); break; if(i=NUM) printf("nnttt沒有找到"); printf("nnttt按任意鍵返回."); getchar(); getchar(); break; case '2': system("cls"); narrate(); printf("nntt請輸入您要查找的地點名稱"); scanf("%s",name); for(i=0;i<NUM;i+

18、) if(!strcmp(name,G.vexi.sight) printf("nnttt您要查找地點信息如下:"); printf("nnttt%-25snn",G.vexi.description); printf("nttt按任意鍵返回."); getchar(); getchar(); break; if(i=NUM) printf("nnttt沒有找到"); printf("nnttt按任意鍵返回."); getchar(); getchar(); break; while(c!=&#

19、39;e'); void CreateUDN(int v,int a) /* 造圖函數(shù) */ int i,j; strcpy(nameofschool,"電子科技大學(xué)"); G.vexnum=v; /* 初始化結(jié)構(gòu)中的地點數(shù)和邊數(shù) */ G.arcnum=a; for(i=0;i<20;+i) G.vexi.number=i; /* 初始化每一個地點的編號 */ /* 初始化每一個地點名及其地點描述 */ strcpy(G.,"銀杏大道"); strcpy(G.,"活動中心");

20、strcpy(G.,"圖書館"); strcpy(G.,"學(xué)子食堂"); strcpy(G.,"教學(xué)區(qū)"); strcpy(G.,"體育館"); strcpy(G.,"實驗樓"); strcpy(G.,"校醫(yī)院"); strcpy(G.ro,":擁有全國最多的銀杏樹"); strcpy(G.ro,&qu

21、ot;:學(xué)生組織最多的地方"); strcpy(G.ro,":藏書最多的地方"); strcpy(G.ro,":一食堂 "); strcpy(G.ro,":品學(xué)樓"); strcpy(G.ro,":有室內(nèi)籃球場、乒乓球場、羽毛球場"); strcpy(G.ro,":實驗室最多的地方"); strcpy(G.ro,":就是醫(yī)院啦 "); /* 這里把所有的邊假定

22、為20000含義是這兩個地點之間是不可到達(dá) */ for(i=0;i<20;+i) for(j=0;j<20;+j) G.arcsij.adj=Max; /* 下邊是可直接到達(dá)的地點間的距離。由于兩個地點間距離是互相的所以要對圖中對稱的邊同時賦值。 */ G.arcs01.adj=G.arcs10.adj=50; G.arcs13.adj=G.arcs31.adj=200; G.arcs06.adj=G.arcs30.adj=300; G.arcs14.adj=G.arcs41.adj=150; G.arcs24.adj=G.arcs42.adj=100; G.arcs35.adj

23、=G.arcs53.adj=200; G.arcs52.adj=G.arcs25.adj=100; G.arcs46.adj=G.arcs64.adj=75; G.arcs47.adj=G.arcs74.adj=300; G.arcs27.adj=G.arcs72.adj=600; void narrate() /* 說明函數(shù) */ int i,k=0; printf("nt*歡送使用%s校園導(dǎo)游程序*n",nameofschool); printf("t_n"); printf("tt地點名稱tttt地點描述tttn"); prin

24、tf("t_|_n"); for(i=0;i<NUM;i+) printf("t%c (%2d)%-10stt|t%-25s%cn",3,i,G.vexi.sight,G.vexi.description,3); /* 輸出地點列表 */ k=k+1; printf("t_|_n"); void ShortestPath(int num) /* 迪杰斯特拉算法最短路徑函數(shù) num為入口點的編號 */ int v,w,i,t; /* i、w和v為計數(shù)變量 */ int final20; /* */ int min; for(v=0

25、;v<NUM;v+) finalv=0; /* 假設(shè)從頂點num到頂點v沒有最短路徑 */ Dv=G.arcsnumv.adj;/* 將與之相關(guān)的權(quán)值放入D中存放 */ for(w=0;w<NUM;w+) /* 設(shè)置為空路徑 */ Pvw=0; if(Dv<20000) /* 存在路徑 */ Pvnum=1; /* 存在標(biāo)志置為一 */ Pvv=1; /* 自身到自身 */ Dnum=0; finalnum=1; /* 初始化num頂點屬于S集合 */ /* 開始主循環(huán)每一次求得num到某個頂點的最短路徑并將其加入到S集合 */ for(i=0;i<NUM;+i) /*

26、 其余G.vexnum-1個頂點 */ min=Max; /* 當(dāng)前所知離頂點num的最近距離 */ for(w=0;w<NUM;+w) if(!finalw) /* w頂點在v-s中 */ if(Dw<min) /* w頂點離num頂點更近 */ v=w; min=Dw; finalv=1; /* 離num頂點更近的v加入到s集合 */ for(w=0;w<NUM;+w) /* 更新當(dāng)前最短路徑極其距離 */ if(!finalw&&(min+G.arcsvw.adj)<Dw)/* 不在s集合并且比以前所找到的路徑都短就更新當(dāng)前路徑 */ Dw=min

27、+G.arcsvw.adj; for(t=0;t<NUM;t+) Pwt=Pvt; Pww=1; void output(int sight1,int sight2) /* 輸出函數(shù) */ int a,b,c,d,q=0; a=sight2; /* 將地點二賦值給a */ if(a!=sight1) /* 如果地點二不和地點一輸入重合則進(jìn)行. */ printf("nt從%s到%s的最短路徑是",G.vexsight1.sight,G.vexsight2.sight);/* 輸出提示信息 */ printf("t(最短距離為 %dm.)nnt",D

28、a); /* 輸出sight1到sight2的最短路徑長度存放在D數(shù)組中 */ printf("t%s",G.vexsight1.sight); /* 輸出地點一的名稱 */ d=sight1; /* 將地點一的編號賦值給d */ for(c=0;c<NUM;+c) gate:; /* 標(biāo)號可以作為goto語句跳轉(zhuǎn)的位置 */ Pasight1=0; for(b=0;b<NUM;b+) if(G.arcsdb.adj<20000&&Pab) /* 如果地點一和它的一個臨界點之間存在路徑且最短路徑 */ printf("->%

29、s",G.vexb.sight); /* 輸出此節(jié)點的名稱 */ q=q+1; /* 計數(shù)變量加一滿8控制輸出時的換行 */ Pab=0; d=b; /* 將b作為出發(fā)點進(jìn)行下一次循環(huán)輸出如此反復(fù) */ if(q%8=0) printf("n"); goto gate; void Searchpath1(MGraph g)/*查詢兩個地點間的所有路徑*/ int l=0; int k=0; int i,j; printf("選擇出發(fā)地點"); scanf("%d",&i); printf("選擇目地地點&q

30、uot;);scanf("%d",&j); for(;k<g.vexnum;k+)/*g.vexnumber表示網(wǎng)中的頂點個數(shù)*/ if(i=g.vexk.number) i=k;/*在網(wǎng)中找到其編號與輸入的出發(fā)地點的編號相同的頂點*/ for(;l<g.vexnum;l+) if(j=g.vexl.number) j=l;/*在網(wǎng)中找到其編號與輸入的目地地點的編號相同的頂點*/ printf("n從%s到%s的所有游覽路徑有:nn",g.vexi.sight,g.vexj.sight);/*輸出出發(fā)地點和目地地點的名稱*/ disp

31、path(g,i,j);/*調(diào)用disppath函數(shù),用來輸出兩個地點間的所有路徑*/ void disppath(MGraph g,int i,int j) int k; p0=i; for(k=0;k<g.vexnum;k+) visitedi=0;/*初始化各頂點的訪問標(biāo)志位即都為未訪問過的*/ a=0;/*初始化路徑的條數(shù)*/ path(g,i,j,0);/*通過調(diào)用path函數(shù)找到從vi到vj的所有路徑并輸出*/ void path(MGraph g,int i,int j,int k) /*確定路徑上第k+1個頂點的序號*/ int s; if(pk=j)/*找到一條路徑*/

32、 a+;/*路徑的條數(shù)值加1*/ printf("第%d條:t",a); for(s=0;s<=k-1;s+)/*輸出一條路徑*/ printf("%s",g.vexps.sight); printf("->"); /cout<<g.vexps.sight; printf("%sn",g.vexps.sight); s=0; while(s<g.vexnum) if(s!=i)/*保證找到的是簡單路徑*/ if(g.arcspks.adj!=Max&&visiteds=

33、0) /*當(dāng)vk與vs之間有邊存在且vs未被訪問過*/ visiteds=1;/*置訪問標(biāo)志位為1,即已訪問的*/ pk+1=s;/*將頂點s加入到p數(shù)組中*/ path(g,i,j,k+1);/*遞歸調(diào)用之*/ visiteds=0;/*重置訪問標(biāo)志位為0即未訪問的以便該頂點能被重新使用*/ s+; int Addnewsight(int n) int i; char sight100,description1000; int length; printf("請輸入新地點的名稱n"); scanf("%s",&sight); printf(&q

34、uot;請輸入新地點的相關(guān)信息n"); scanf("%s",&description); strcpy(G.vexn.sight,sight); strcpy(G.vexn.description,description); G.vexn.number=n; for(i=0;i<n;i+) system("cls"); narrate(); printf("請輸入此地點到第%d個地點的距離單位m同一地點或不可到達(dá)用20000表示n",i); scanf("%d",&length);

35、 if(length!=20000) G.arcnum+; G.arcsni.adj=G.arcsin.adj=length; n+; G.vexnum+; return n; int Deletesight(int n) int i; int j; char c; int num; char name20; system("cls"); c=SearchMenu(); switch (c) case '1': system("cls"); narrate();printf("nntt請輸入您要刪除地點的編號"); s

36、canf("%d",&num); for(i=0;i<NUM;i+) if(num=G.vexi.number) for(j=0;j<NUM;j+) if(G.arcsij.adj!=20000) G.arcnum-; G.arcsij.adj=G.arcsji.adj=20000; for(;num<NUM;num+) strcpy(G.vexnum.sight,G.vexnum+1.sight); strcpy(G.vexnum.description,G.vexnum+1.description); n-; printf("nttt

37、按任意鍵返回."); getchar(); getchar(); break; if(i=NUM) printf("nnttt沒有找到"); printf("nnttt按任意鍵返回."); getchar(); getchar(); break; case '2': system("cls"); narrate(); printf("nntt請輸入您要刪除地點的名稱"); scanf("%s",name); for(i=0;i<NUM;i+) if(!strcmp

38、(name,G.vexi.sight) num=i; for(j=0;j<NUM;j+) if(G.arcsij.adj!=20000) G.arcnum-; G.arcsij.adj=G.arcsji.adj=20000; for(;num<NUM;num+) strcpy(G.vexnum.sight,G.vexnum+1.sight); strcpy(G.vexnum.description,G.vexnum+1.description); n-; printf("nttt按任意鍵返回."); getchar(); getchar(); break; if

39、(i=NUM) printf("nnttt沒有找到"); printf("nnttt按任意鍵返回."); getchar(); getchar(); break; return n; char Changemenu() char c; int flag; do flag=1; system("cls"); narrate(); printf("ntttn"); printf("ttt n"); printf("ttt 1、修改地點信息 n"); printf("tt

40、t 2、修改道路信息 n"); printf("ttt e、返回 n"); printf("ttt n"); printf("tttn"); printf("tttt請輸入您的選擇"); scanf("%c",&c); if(c='1'|c='2'|c='e') flag=0; while(flag); return c; char Sightmenu() char c; int flag; do flag=1; system(&

41、quot;cls"); narrate(); printf("ntttn"); printf("ttt n"); printf("ttt 1、修改地點名稱 n"); printf("ttt 2、修改地點描述 n"); printf("ttt e、返回 n"); printf("ttt n"); printf("tttn"); printf("tttt請輸入您的選擇"); scanf("%c",&c)

42、; if(c='1'|c='2'|c='e') flag=0; while(flag); return c; void Changesight() int a,b,length; char sight100; char description1000; char p; char q; int i; int num; p=Changemenu(); switch(p) case'1': system("cls"); narrate(); printf("nntt請輸入您要修改的地點編號");

43、scanf("%d",&num); for(i=0;i<NUM;i+) if(G.vexi.number=num) q=Sightmenu(); if(q='1') printf("請輸入修改后的地點名稱n"); scanf("%s",&sight); strcpy(G.vexnum.sight,sight); printf("tttt修改成功n"); else if(q='2') printf("請輸入修改后的地點信息n"); scanf(

44、"%s",&description); strcpy(G.vexnum.description,description); printf("tttt修改成功n"); else if(q='e') p=Changemenu(); printf("ntt按任意鍵返回."); getchar(); getchar(); break; if(i=NUM) printf("nntttt沒有找到"); printf("nnttt按任意鍵返回."); getchar(); getchar(); break; case '2': printf("tt請輸入道路一側(cè)的地點序號"); scanf("%d",&a); printf("