數(shù)據(jù)結(jié)構(gòu)課程設(shè)計校園導(dǎo)航

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計校園導(dǎo)航數(shù)據(jù)結(jié)構(gòu)課程設(shè)計校園導(dǎo)航數(shù)據(jù)結(jié)構(gòu)課程設(shè)計校園導(dǎo)航數(shù)據(jù)結(jié)構(gòu)課程設(shè)計校園導(dǎo)航編制僅供參考審核批準生效日期地址：電話：傳真:郵編:一、課程設(shè)計目的本課程設(shè)計的目標就是要達到理論與實際應(yīng)用相結(jié)合，提高學(xué)生組織數(shù)據(jù)及編寫大型程序的能力，并培養(yǎng)基本的、良好的程序設(shè)計技能以及合作能力。設(shè)計中要求綜合運用所學(xué)知識，上機解決一些與實際應(yīng)用結(jié)合緊密的、規(guī)模較大的問題，通過分析、設(shè)計、編碼、調(diào)試等各環(huán)節(jié)的訓(xùn)練，使學(xué)生深刻理解、牢固掌握數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計技術(shù)，掌握分析、解決實際問題的能力。通過這次設(shè)計，要求在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計及其實現(xiàn)等方面，加深對課程基本內(nèi)容的理解。同時，在程序設(shè)計方法以及上機操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴格的訓(xùn)練。課程設(shè)計內(nèi)容1)問題描述用無向網(wǎng)表示你所在學(xué)校的校園景點平面圖，圖中頂點表示主要景點，存放景點的編號、名稱、簡介等信息，圖中的邊表示景點間的道路，存放路徑長度等信息。要求能夠回答有關(guān)景點介紹、游覽路徑等問題。2)基本要求（1）查詢各景點的相關(guān)信息；（2）查詢圖中任意兩個景點間的最短路徑。（3）查詢圖中任意兩個景點間的所有路徑。增加、刪除、更新有關(guān)景點和道路的信息三、課程設(shè)計過程1．需求分析（1）設(shè)計學(xué)校的校園平面圖，選取出若干的具有代表性的景點構(gòu)成一個抽象的無向帶權(quán)圖，頂點為景點，邊的權(quán)值代表了景點間路徑的長度。（2）將景點的序號，名稱，介紹存放起來準備查詢。（3）提供任意景點的信息；（4）提供任意經(jīng)典的路徑查詢及其最優(yōu)路線的查詢（5）平面圖景點的增加及刪除，以及邊和權(quán)值（長度）的改變2．概要設(shè)計1：第一點是主界面的設(shè)計，首先，為了該系統(tǒng)各個功能的管理，設(shè)計出含有多個菜單項的主菜單界面，可以更方便的使用該系統(tǒng)。2：第二點是存儲結(jié)構(gòu)的設(shè)計，采取了圖結(jié)構(gòu)類型（mgraph）存儲校園圖的信息，景點信息用結(jié)構(gòu)數(shù)組vexs存儲，而且利用全局變量：visited[]數(shù)組用于存儲頂點是否被訪問標志；d[]數(shù)組用于存放權(quán)值和查找路徑頂點的編號；campus是一個圖結(jié)構(gòu)的全局變量。3：第三點是設(shè)計各個功能的實現(xiàn)，學(xué)校景點的介紹通過函數(shù)browsecompus()來實現(xiàn)；查詢景點間的最段路徑通過Floyd(弗洛伊德)算法實現(xiàn)；查詢景點間的所有路徑通過allpath函數(shù)和path函數(shù)來實現(xiàn)；更改圖的信息可以由主函數(shù)changegraph以及其他函數(shù)可以實現(xiàn)。詳細設(shè)計（1）主要的操作界面的顯示以及無向網(wǎng)操作voidinitgraph(graph*ga){ inti,j; ga->n=9; ga->e=11;for(i=0;i<ga->n;i++){ ga->vexs[i].num=i;}strcpy(ga->vexs[0].name,"西門"); strcpy(ga->vexs[0].introduce,"學(xué)校的正大門，設(shè)有公交站"); strcpy(ga->vexs[1].name,"風(fēng)雨籃球場"); strcpy(ga->vexs[1].introduce,""); strcpy(ga->vexs[2].name,"田徑場"); strcpy(ga->vexs[2].introduce,"舉辦運動會，平時體育跑步鍛煉等"); strcpy(ga->vexs[3].name,"京元食堂"); strcpy(ga->vexs[3].introduce,"新食堂"); strcpy(ga->vexs[4].name,"蒼霞湖畔"); strcpy(ga->vexs[4].introduce,"戲稱“分手湖”，景色宜人"); strcpy(ga->vexs[5].name,"思源樓"); strcpy(ga->vexs[5].introduce,"學(xué)校王牌土木的教學(xué)區(qū)"); strcpy(ga->vexs[6].name,"圖書館"); strcpy(ga->vexs[6].introduce,"是大學(xué)城最高的標志性建筑"); strcpy(ga->vexs[7].name,"北教區(qū)"); strcpy(ga->vexs[7].introduce,"北校區(qū)集中的教學(xué)樓"); strcpy(ga->vexs[8].name,"禾堂餐廳"); strcpy(ga->vexs[8].introduce,"舊食堂");for(i=0;i<ga->n;i++) for(j=0;j<ga->n;j++) ga->edges[i][j]=1000; ga->edges[0][1]=1; ga->edges[1][2]=2; ga->edges[1][3]=5; ga->edges[2][4]=4; ga->edges[3][4]=9; ga->edges[4][5]=1; ga->edges[4][8]=1; ga->edges[5][6]=5; ga->edges[5][7]=7; ga->edges[7][8]=1; ga->edges[6][7]=9;for(i=0;i<ga->n;i++) for(j=0;j<ga->n;j++) ga->edges[j][i]=ga->edges[i][j];}（2）確定頂點是否存在已經(jīng)頂點是否已經(jīng)被訪問過來確定路徑voidCreate_graph(graph*ga){ inti,j,k,w; printf("請輸入頂點數(shù)和邊數(shù):\n"); scanf("%d%d",&(ga->n),&(ga->e)); printf("請輸入景點編號，景點名字，景點介紹，建立信息表:\n"); for(i=0;i<ga->n;i++) { scanf("%d",&(ga->vexs[i].num)); gets(ga->vexs[i].name); gets(ga->vexs[i].introduce); } for(i=0;i<ga->n;i++) for(j=0;j<=ga->n;j++) ga->edges[i][j]=1000; for(k=0;k<ga->e;k++) { printf("請輸入%d條邊的景點序號i，j和長度：",k+1); scanf("%d%d%d",&i,&j,&w);ga->edges[i][j]=w; ga->edges[j][i]=w; }}voidprint(graphga){inti,j;for(i=0;i<ga.n;i++) for(j=0;j<ga.n;j++) { printf("%d",ga.edges[i][j]);if(j+1==ga.n) printf("\n"); }}voidvisit(graphga){ inta; printf("請輸入景點編號："); scanf("%d",&a);inti; for(i=0;i<ga.n;i++){ if(a==ga.vexs[i].num) { printf("景點編號為%d\n",ga.vexs[i].num); printf("景點名稱為"); puts(ga.vexs[i].name); printf("景點介紹為"); puts(ga.vexs[i].introduce); break; }}if(i==ga.n)printf("無此點\n");}（3）得出景點間的最短路徑voidshortestpath_djst(graphga){}voidshortestpath_floyd(graphga){inti,j,k,v,u,w,d[35][35],p[35][35][35]; for(v=0;v<ga.n;v++) { for(w=0;w<ga.n;w++) { d[v][w]=ga.edges[v][w]; for(u=0;u<ga.n;u++) { p[v][w][u]=0; } if(d[v][w]<1000) { p[v][w][v]=1; p[v][w][w]=1; } } }for(u=0;u<ga.n;u++) { for(v=0;v<ga.n;v++) for(w=0;w<ga.n;w++) if(d[v][u]+d[u][w]<d[v][w]) { d[v][w]=d[v][u]+d[u][w]; for(i=0;i<ga.n;i++) p[v][w][i]=p[v][u][i]||p[u][w][i]; } } printf("\n請輸入出發(fā)點和目的地編號："); scanf("%d%d",&k,&j); printf("\n\n"); while(k<0||k>ga.n||j<0||j>ga.n) {printf("\n輸入的編號不存在"); printf("\n請重新輸入編號：\n\n"); scanf("%d%d",&k,&j); printf("\n\n"); } printf("%s",ga.vexs[k].name); for(u=0;u<ga.n;u++) if(p[k][j][u]&&k!=u&&j!=u) printf("--->%s",ga.vexs[u].name); printf("--->%s",ga.vexs[j].name); printf("\n\n\n總長度為%d千米\n\n\n",d[k][j]);}（4）得到景點之間的所有路徑voidpath(graphc,intm,intn,intk){ ints,x=0; intt; t=k+1; if(d[k]==n&&k<8) { for(s=0;s<k;s++) { printf("%s--->",c.vexs[d[s]].name); } printf("%s\n\n",c.vexs[d[s]].name); } else { s=0; while(s<c.n) { if((c.edges[d[k]][s]<1000)&&(visited[s]==0)) { visited[s]=1; d[k+1]=s; path(c,m,n,t); visited[s]=0; } s++; } }}voidallpath(graphc){intk,i,j,m,n; printf("\n\n請輸入您要查詢的兩個景點的編號:\n\n"); scanf("%d%d",&i,&j); printf("\n\n"); m=locatevex(c,i); n=locatevex(c,j); d[0]=m; for(k=0;k<c.n;k++) visited[k]=0; visited[m]=1; path(c,m,n,0);}（5）刪除邊intdelarc(graph&ga){ intm,n,v0,v1; if(ga.e<=0) { printf("圖中已經(jīng)無頂邊，無法刪除"); return1; } printf("\n請輸入要刪除的邊的起點和終點的編號："); scanf("%d%d",&v0,&v1);m=locatevex(ga,v0); if(m<0) { printf("此頂點%d已刪除",v0); return1; } n=locatevex(ga,v1); if(n<0) { printf("此頂點%d已刪除",v1); return1; } ga.edges[m][n]=1000; ga.edges[n][m]=1000; ga.e--; return1;}intenarc(graph&ga){ intm,n,distance; printf("請輸入邊的起點和終點編號，權(quán)值："); scanf("%d%d%d",&m,&n,&distance); while(m<0||m>ga.n||n<0||n>ga.n){ printf("輸入錯誤，請重新輸入："); scanf("%d%d",&m,&n);}if(locatevex(ga,m)<0){ printf("此節(jié)點%d已經(jīng)刪除",m); return1;}if(locatevex(ga,n)<0){ printf("此節(jié)點%d已經(jīng)刪除",n); return1;}ga.edges[m][n]=distance;ga.edges[n][m]=ga.edges[m][n];return1;}4．調(diào)試分析內(nèi)容包括：a．調(diào)試過程中遇到的問題是如何解決的以及對設(shè)計與實現(xiàn)的回顧討論和分析；b．算法的時空分析(包括基本操作和其他算法的時間復(fù)雜度和空間復(fù)雜度的分析)和改進設(shè)想；c．經(jīng)驗和體會等。用戶使用說明通過主菜單提示，選擇出你所想要知道的信息，然后通過輸入節(jié)點來代替景點，從而得到景點間的所有路徑，最短路徑等其他信息。測試結(jié)果（1）操作的主界面學(xué)校景點的介紹學(xué)校景點從西門的禾堂餐廳的所有路徑所有路徑（4）學(xué)校景點從西門的禾堂餐廳的所有路徑最短路徑圖的更改的界面（6）邊的刪除界面展示附錄#defineMAX100//數(shù)據(jù)類型的定義#include<string>#include<iostream>usingnamespacestd;intvisited[35];intd[35];structviews{intnum; charname[10]; charintroduce[100];};typedefviewsdatatype;typedefstruct{datatypevexs[MAX];intedges[MAX][MAX];intn,e;}graph;voidinitgraph(graph*ga)//主要的操作界面的顯示以及無向網(wǎng)操作{ inti,j; ga->n=9; ga->e=11;for(i=0;i<ga->n;i++){ ga->vexs[i].num=i;}strcpy(ga->vexs[0].name,"西門"); strcpy(ga->vexs[0].introduce,"學(xué)校的正大門，設(shè)有公交站"); strcpy(ga->vexs[1].name,"風(fēng)雨籃球場"); strcpy(ga->vexs[1].introduce,""); strcpy(ga->vexs[2].name,"田徑場"); strcpy(ga->vexs[2].introduce,"舉辦運動會，平時體育跑步鍛煉等"); strcpy(ga->vexs[3].name,"京元食堂"); strcpy(ga->vexs[3].introduce,"新食堂"); strcpy(ga->vexs[4].name,"蒼霞湖畔"); strcpy(ga->vexs[4].introduce,"戲稱“分手湖”，景色宜人"); strcpy(ga->vexs[5].name,"思源樓"); strcpy(ga->vexs[5].introduce,"學(xué)校王牌土木的教學(xué)區(qū)"); strcpy(ga->vexs[6].name,"圖書館"); strcpy(ga->vexs[6].introduce,"是大學(xué)城最高的標志性建筑"); strcpy(ga->vexs[7].name,"北教區(qū)"); strcpy(ga->vexs[7].introduce,"北校區(qū)集中的教學(xué)樓"); strcpy(ga->vexs[8].name,"禾堂餐廳"); strcpy(ga->vexs[8].introduce,"舊食堂");for(i=0;i<ga->n;i++) for(j=0;j<ga->n;j++) ga->edges[i][j]=1000; ga->edges[0][1]=1; ga->edges[1][2]=2; ga->edges[1][3]=5; ga->edges[2][4]=4; ga->edges[3][4]=9; ga->edges[4][5]=1; ga->edges[4][8]=1; ga->edges[5][6]=5; ga->edges[5][7]=7; ga->edges[7][8]=1; ga->edges[6][7]=9;for(i=0;i<ga->n;i++) for(j=0;j<ga->n;j++) ga->edges[j][i]=ga->edges[i][j];}intlocatevex(graphga,intv)//查找景點在圖中的序號{ inti; for(i=0;i<ga.n;i++) if(v==ga.vexs[i].num)returni; return-1;}voidCreate_graph(graph*ga){ inti,j,k,w; printf("請輸入頂點數(shù)和邊數(shù):\n"); scanf("%d%d",&(ga->n),&(ga->e)); printf("請輸入景點編號，景點名字，景點介紹，建立信息表:\n"); for(i=0;i<ga->n;i++) { scanf("%d",&(ga->vexs[i].num)); gets(ga->vexs[i].name); gets(ga->vexs[i].introduce); } for(i=0;i<ga->n;i++) for(j=0;j<=ga->n;j++) ga->edges[i][j]=1000; for(k=0;k<ga->e;k++) { printf("請輸入%d條邊的景點序號i，j和長度：",k+1); scanf("%d%d%d",&i,&j,&w);ga->edges[i][j]=w; ga->edges[j][i]=w; }}voidprint(graphga){inti,j;for(i=0;i<ga.n;i++) for(j=0;j<ga.n;j++) { printf("%d",ga.edges[i][j]);if(j+1==ga.n) printf("\n"); }}voidvisit(graphga){ inta; printf("請輸入景點編號："); scanf("%d",&a);inti; for(i=0;i<ga.n;i++){ if(a==ga.vexs[i].num) { printf("景點編號為%d\n",ga.vexs[i].num); printf("景點名稱為"); puts(ga.vexs[i].name); printf("景點介紹為"); puts(ga.vexs[i].introduce); break; }}if(i==ga.n)printf("無此點\n");}voidshortestpath_djst(graphga){}voidshortestpath_floyd(graphga){inti,j,k,v,u,w,d[35][35],p[35][35][35]; for(v=0;v<ga.n;v++) { for(w=0;w<ga.n;w++) { d[v][w]=ga.edges[v][w]; for(u=0;u<ga.n;u++) { p[v][w][u]=0; } if(d[v][w]<1000) { p[v][w][v]=1; p[v][w][w]=1; } } }for(u=0;u<ga.n;u++) { for(v=0;v<ga.n;v++) for(w=0;w<ga.n;w++) if(d[v][u]+d[u][w]<d[v][w]) { d[v][w]=d[v][u]+d[u][w]; for(i=0;i<ga.n;i++) p[v][w][i]=p[v][u][i]||p[u][w][i]; } } printf("\n請輸入出發(fā)點和目的地編號："); scanf("%d%d",&k,&j); printf("\n\n"); while(k<0||k>ga.n||j<0||j>ga.n) {printf("\n輸入的編號不存在"); printf("\n請重新輸入編號：\n\n"); scanf("%d%d",&k,&j); printf("\n\n"); } printf("%s",ga.vexs[k].name); for(u=0;u<ga.n;u++) if(p[k][j][u]&&k!=u&&j!=u) printf("--->%s",ga.vexs[u].name); printf("--->%s",ga.vexs[j].name); printf("\n\n\n總長度為%d千米\n\n\n",d[k][j]);}voidpath(graphc,intm,intn,intk){ ints,x=0; intt; t=k+1; if(d[k]==n&&k<8) { for(s=0;s<k;s++) { printf("%s--->",c.vexs[d[s]].name); } printf("%s\n\n",c.vexs[d[s]].name); } else { s=0; while(s<c.n) { if((c.edges[d[k]][s]<1000)&&(visited[s]==0)) { visited[s]=1; d[k+1]=s; path(c,m,n,t); visited[s]=0; } s++; } }}voidallpath(graphc){intk,i,j,m,n; printf("\n\n請輸入您要查詢的兩個景點的編號:\n\n"); scanf("%d%d",&i,&j); printf("\n\n"); m=locatevex(c,i); n=locatevex(c,j); d[0]=m; for(k=0;k<c.n;k++) visited[k]=0; visited[m]=1; path(c,m,n,0);}voidnewgraph(graph&ga){ intchangenum; inti,m,n,t,distance,v0,v1; printf("\n請輸入要修改景點的個數(shù)：\n"); scanf("%d",&changenum); while(changenum<0||changenum>ga.n) { printf("\n輸入錯誤！請重新輸入"); scanf("%d",&changenum); } for(i=0;i<changenum;i++) { printf("\n請輸入景點的編號："); scanf("%d,&m"); t=locatevex(ga,m); printf("\n請輸入景點的名稱："); scanf("%s",ga.vexs[t].name); printf("\n請輸入景點簡介："); scanf("%s",ga.vexs[t].introduce); } printf("\n請輸入您要更新的邊數(shù)"); scanf("%d",&changenum); while(changenum<0||changenum>ga.n) { printf("輸入錯誤，請重新輸入："); scanf("%d",&changenum); } printf("\n請輸入更新邊的信息：\n"); for(i=1;i<=changenum;i++) { printf("\n修改的第%d條邊的起點終點長度為：",i); scanf("%d%d%d",&v0,&v1,&distance); m=locatevex(ga,v0); n=locatevex(ga,v1); if(m>=0&&n>=0) { ga.edges[m][n]=distance; ga.edges[n][m]=ga.edges[m][n]; } } }intdelvex(graph&ga)//刪除頂點{ inti=0,j; intm,v; if(ga.n<=0) { printf("圖中已經(jīng)無頂點"); return1; } printf("\n請輸入要刪除的景點編號："); scanf("%d",&v); while(v<0||v>ga.n) {printf("\n輸入錯誤，請重新輸入");scanf("%d",&v); } m=locatevex(ga,v); if(m<0) { printf("此頂點%d已刪除",v); return1; } for(i=m;i<ga.n-1;i++) { strcpy(ga.vexs[i].name,ga.vexs[i+1].name); strcpy(ga.vexs[i].introduce,ga.vexs[i+1].introduce); } for(i=m;i<ga.n-1;i++) for(j=0;j<ga.n;j++) ga.edges[i][j]=ga.edges[i+1][j]; for(i=m;i<ga.n-1;i++) for(j=0;j<ga.n;j++) ga.edges[j][i]=ga.edges[j][i+1]; ga.n--; return1;}intdelarc(graph&ga)//刪除邊{ intm,n,v0,v1; if(ga.e<=0) { printf("圖中已經(jīng)無頂邊，無法刪除"); return1; } printf("\n請輸入要刪除的邊的起點和終點的編號："); scanf("%d%d",&v0,&v1);m=locatevex(ga,v0); if(m<0) { printf("此頂點%d已刪除",v0); return1; } n=locatevex(ga,v1); if(n<0) { printf("此頂點%d已刪除",v1); return1; } ga.edges[m][n]=1000; ga.edges[n][m]=1000; ga.e--; return1;}intenarc(graph&ga){ intm,n,distance; printf("請輸入邊的起點和終點編號，權(quán)值："); scanf("%d%d%d",&m,&n,&distance); while(m<0||m>ga.n||n<0||n>ga.n){ printf("輸入錯誤，請重新輸入："); scanf("%d%d",&m,&n);}if(locatevex(ga,m)<0){ printf("此節(jié)點%d已經(jīng)刪除",m); return1;}if(locatevex(ga,n)<0){ printf("此節(jié)點%d已經(jīng)刪除",n); return1;}ga.edges[m][n]=distance;ga.edges[n][m]=ga.edges[m][n];return1;}intenvex(graph&ga)//增加節(jié)點{ inti; printf("請輸入增加節(jié)點的信息："); printf("\n編號："); scanf("%d",&ga.vexs[ga.n].num); printf("名稱："); scanf("%s",ga.vexs[ga.n].name); printf("簡介："); scanf("%s",ga.vexs[ga.n].introduce); ga.n++; for(i=0;i<ga.n;i++) { ga.edges[ga.n-1][i]=1000; ga.edges[i][ga.n-1]=1000; }return1;}intchangegraph(graph&ga){ intyourchoice; printf("\n請選擇\n\n(1)刪除結(jié)點(2)刪除邊\n"); printf("\n(3)增加結(jié)點(4)增加邊\n"); printf("\n(5)更新信息(6)返回\n\n"); scanf("%d",&yourchoice); printf("\n\n"); while(!(yourchoice==1||yourchoice==2||yourchoice==3||yourchoice==4||yourchoice==5||yourchoice==6) printf("請重新輸入："); scanf("%d",&yourchoice); } while(1) { switch(yourchoice) { case1:delvex(ga);break; case2:delarc(ga);break; case3:envex(ga);break; case4:enarc(ga);break; case5:newgraph(ga);break;case6:return1; } printf("\n請選擇\n\n(1)刪除結(jié)點(2)刪除邊\n"); printf("\n(3)增加結(jié)點(4)增加邊\n"); printf("\n(5)更新信息(6)返回\n\n"); scanf("%d",&yourchoice);printf("\n\n"); while(!(yourchoice==1||yourchoice==2||yourchoice==3||yourchoice==4||yourchoice==5|