數(shù)據(jù)結(jié)構(gòu)公園導(dǎo)游（精編版）

1、1. 課程設(shè)計(jì)的目的(1) 熟練使用 c + 語言編寫程序，解決實(shí)際問題;(2) 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力 ;(3) 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、 程序編碼、 測(cè)試等基本方法和技能 ;(4) 提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力;2. 需求分析(1 ）設(shè)計(jì)所在公園的公園平面圖，所含景點(diǎn)不少于十個(gè)。以圖中頂點(diǎn)表示園內(nèi)各景點(diǎn)，存放景點(diǎn)名稱、代號(hào)、簡介等信息；以邊表示路徑，存放路徑長度等信息。（ 2）為來訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。（ 3）為來訪客人提供圖中任意景點(diǎn)的問路查詢，即查詢?nèi)我鈨蓚€(gè)頂點(diǎn)之間的一條最短的簡單路

2、徑。（4） ）公園導(dǎo)游圖的景點(diǎn)和道路的修改擴(kuò)充功能。（5） ）擴(kuò)充道路信息，如道路類別（車道、人行道），以致可按客人所需分別查詢?nèi)诵新窂交蜍囆新窂?。?6）擴(kuò)充每個(gè)景點(diǎn)的林潔景點(diǎn)的方向等信息，使得路徑查詢結(jié)果能提供詳盡的導(dǎo)向信息。圖 1-1函數(shù)調(diào)用圖4. 調(diào)試分析（ 7）實(shí)現(xiàn)公園導(dǎo)游的仿真界面。3. 公園導(dǎo)游問題的設(shè)計(jì)圖 1-2圖 1-3圖 1-4圖 1-5圖 1-65. 小結(jié)數(shù)據(jù)結(jié)構(gòu)書中的迪杰斯特拉算法只能求出最短路徑中有哪個(gè)景 點(diǎn)，但無法求出這幾個(gè)景點(diǎn)的經(jīng)過順序，所以先利用迪杰斯特拉算法記錄下某個(gè)頂點(diǎn)求出到最短路徑的順序，然后再比對(duì)哪幾個(gè)景點(diǎn)是最短路徑里所經(jīng)過的得出最短路徑及景點(diǎn)路過的順序

3、。6、參考文獻(xiàn)1 嚴(yán)蔚敏，吳偉民編著.數(shù)據(jù)結(jié)構(gòu) (c語言版 )-北京:清華大學(xué)出版社， 2007.22 嚴(yán)蔚敏，吳偉民米 寧 編 著.數(shù)據(jù)結(jié)構(gòu)題集 (c語言版 )-北京:清華大學(xué)出版社 ， 2007.33 網(wǎng)上搜索相關(guān)程序作為參考附錄：#define infinity 1000#define maxvertexnum 35#define max 40#include<stdio.h>#include<stdlib.h>#include<conio.h>#include<string.h>#include<iostream>using

4、namespace std;typedef struct arcell/邊的權(quán)值信息int adj;/arcell,adjmatrixmaxvertexnummaxvertexnum;/權(quán)值圖的鄰接矩陣類型typedef struct vexsinfo/頂點(diǎn)信息int position;/景點(diǎn)的編號(hào)char name32;/景點(diǎn)的名稱char introduction256;/景點(diǎn)的介紹vexsinfo;typedef struct mgraph/圖結(jié)構(gòu)信息vexsinfo vexsmaxvertexnum;/頂點(diǎn)向量 ( 數(shù)組)adjmatrix arcs;/鄰接矩陣int vexnum,a

5、rcnum;/分別指定頂點(diǎn)數(shù)和邊數(shù)mgraph;/ 全局變量int visited35;/用于標(biāo)志是否已經(jīng)訪問過int d35;/用于存放權(quán)值或存儲(chǔ)路徑頂點(diǎn)編號(hào)mgraph campus;/圖變量 ( 大公園園 )/ (1)對(duì)圖初始化mgraph initgraph()int i=0,j=0;mgraph c;c.vexnum =28;c.arcnum =39;/頂點(diǎn)個(gè)數(shù)邊的個(gè)數(shù)for(i=0;i<c.vexnum ;i+)/依次設(shè)置頂點(diǎn)編號(hào)c.vexsi.position =i;/ 依次輸入頂點(diǎn)信息strcpy( ,"小 西 南 門 ");

6、strcpy(roduction ,"離公交站近 "); strcpy( ,"公園南正門 ");strcpy(roduction ,"公園大門、公園班車進(jìn)出口"); strcpy( ,"東坡亭 ");strcpy(roduction ,"東坡亭，亭高3 層"); strcpy( ,"西 施 坡 "); strcpy(r

7、oduction ,"西施坡 , 風(fēng)光優(yōu)美 "); strcpy( ,"黃蓉亭 ");strcpy(roduction ,"黃蓉亭，名字來自于射雕英雄傳"); strcpy(,"荷花塘 ");strcpy(roduction ,"荷花塘，里面有很多荷花"); strcpy( ,"廣場(chǎng) ");strcpy(roduction ,"很

8、大的一塊空地"); strcpy(,"花 壇 "); strcpy(roduction ,"里面有很多花"); strcpy( ,"長椅 ");strcpy(roduction ,"這兒有很多椅子，有人可以做"); strcpy(, "慈悲庵 ");strcpy(roduction , "慈悲庵，慈悲庵是創(chuàng)建于元代的古剎");st

9、rcpy( ,"云繪樓 ");strcpy(roduction ,"云繪樓是一座皇家園林建筑"); strcpy( ,"九龍壁 ");strcpy(roduction ,"整壁用彩色琉璃瓦鑲砌而成"); strcpy( ,"白塔 ");strcpy(roduction ,"白塔，高5 層 "); strcpy(c.vexs13.

10、name ,"游 泳 館 "); strcpy(roduction ,"室內(nèi)小型游泳館"); strcpy( ,"彩 虹 橋 "); strcpy(roduction ,"彩虹橋，橋上有彩虹燈"); strcpy( ,"小 木 橋 "); strcpy(roduction ,"小木橋，環(huán)境優(yōu)雅"); strcpy( ,"

11、;沙灘 ");strcpy(roduction ,"河邊的沙灘 ");strcpy( ,"奇 石 "); strcpy(roduction ,"奇石大石頭 ");strcpy( ,"超 市 "); strcpy(roduction ,"超 市 "); strcpy( ,"歐 陽 亭 "); strcpy(c.vexs1

12、9.introduction ,"亭高 3 樓"); strcpy( ,"明 光 塔 "); strcpy(roduction ,"明光塔 "); strcpy( ,"雷 峰 塔 "); strcpy(roduction ,"雷鋒塔 "); strcpy( ,"洞 庭 湖 "); strcpy(roduction ,"

13、洞庭湖 "); strcpy( ,"蘇 提 "); strcpy(roduction ,"蘇 提 "); strcpy( ,"燈 塔 "); strcpy(roduction ,"燈 塔 "); strcpy( ,"");strcpy(roduction ,""); strcpy( ,&quo

14、t;樹 林 "); strcpy(roduction ,"有很多樹 "); strcpy( ,""); strcpy(roduction ,"");/ 依次輸入邊上的權(quán)值信息for(i=0;i<c.vexnum ;i+) for(j=0;j<c.vexnum ;j+)c.arcs ij.adj =infinity; /先初始化圖的鄰接矩陣/ 部分弧長c.arcs02.adj=50;c.arcs03.adj=60; c.arcs14.adj=

15、90;c.arcs23.adj=60;c.arcs28.adj=40;c.arcs34.adj=60;c.arcs36.adj=40;c.arcs45.adj=70;c.arcs49.adj=70;c.arcs410.adj=80; c.arcs417.adj=200;c.arcs57.adj=70;c.arcs69.adj=40;c.arcs718.adj=190;c.arcs811.adj=50;c.arcs912.adj=40;c.arcs1018.adj=70;c.arcs1112.adj=60;c.arcs1114.adj=50;c.arcs1115.adj=50; c.arcs12

16、16.adj=50;c.arcs1314.adj=40;c.arcs1322.adj=60;c.arcs1415.adj=50;c.arcs1420.adj=90;c.arcs1516.adj=60;c.arcs1521.adj=40; c.arcs1617.adj=60;c.arcs1718.adj=80;c.arcs1819.adj=60;c.arcs2021.adj=60;c.arcs2024.adj=80;c.arcs2223.adj=60;c.arcs2225.adj=80; c.arcs2324.adj=60;c.arcs2426.adj=100; c.arcs2427.adj=1

17、00; c.arcs2526.adj=90;c.arcs2627.adj=90;for(i=0;i<c.vexnum ;i+)/鄰接矩陣是對(duì)稱矩陣，對(duì)稱賦值for(j=0;j<c.vexnum ;j+) c.arcsji.adj =c.arcsij.adj ;return c;/initgraph/ (2)查找景點(diǎn)在圖中的序號(hào)int locatevex(mgraph c,int v)int i;for(i=0;i<c.vexnum ;i+) if(v=c.vexsi.position)return i;/找到，返回頂點(diǎn)序號(hào)ireturn -1;/否則，返回 -1/(3)、(4

18、)求兩景點(diǎn)間的所有路徑/ (3)打印序號(hào)為m,n 景點(diǎn)間的長度不超過8 個(gè)景點(diǎn)的路徑void path(mgraph c, int m,int n,int k)int s,x=0;int t=k+1;/t記載路徑上下一個(gè)中間頂點(diǎn)在d 數(shù)組中的下標(biāo)if(dk=n && k<8)/dk存儲(chǔ)路徑頂點(diǎn)。若dk 是終點(diǎn) n 且景點(diǎn)個(gè)數(shù) <=8，則輸出該路徑/遞歸出口，找到一條路徑for(s=0;s<k;s+)printf("%s->",);/輸出該路徑。 s=0 時(shí)為起點(diǎn)m printf("%s",

19、);/輸出最后一個(gè)景點(diǎn)名( 即頂點(diǎn)n的名字，此時(shí)s=k)printf("nn");elses=0;while(s<c.vexnum)/從第m 個(gè)頂點(diǎn)，試探至所有頂點(diǎn)是否有路徑if(c.arcsdks.adj<infinity)&& (visiteds=0)/ 初態(tài)：頂點(diǎn)m到頂點(diǎn) s 有邊，且未被訪問visiteds=1;dk+1=s;/存儲(chǔ)頂點(diǎn)編號(hào)s 至 dk+1 中path(c,m,n,t);/求從下標(biāo)為t=k+1 的第 dt個(gè)頂點(diǎn)開始的路徑 ( 遞歸調(diào)用 ) ，同時(shí)打印出一條m至 n 的路徑visiteds=0;/將

20、找到的路徑上頂點(diǎn)的訪問標(biāo)志重新設(shè)置為 0，以用于試探新的路徑s+;/試探從下一個(gè)頂點(diǎn)s開始是否有到終點(diǎn)的路徑/endwhile/endelse/endpath/(4)打印兩景點(diǎn)間的景點(diǎn)個(gè)數(shù)不超過8 的所有路徑。調(diào)用(3) int allpath(mgraph c)int k,i,j,m,n;printf("nn請(qǐng)輸入你要查詢的兩個(gè)景點(diǎn)編號(hào):nn"); scanf("%d%d",&i,&j);printf("nn");m=locatevex(c,i);/調(diào)用 (2) ，確定該頂點(diǎn)是否存在。若存在，返回該頂點(diǎn)編號(hào)n=loc

21、atevex(c,j);d0=m;/存儲(chǔ)路徑起點(diǎn)m (int d數(shù)組是全局變量 )for(k=0;k<c.vexnum;k+)/全部頂點(diǎn)訪問標(biāo)志初值設(shè)為0visitedk=0;visitedm=1;/第 m個(gè)頂點(diǎn)訪問標(biāo)志設(shè)置為1path(c,m,n,0);/調(diào)用 (3) 。k=0 ，對(duì)應(yīng)起點(diǎn)d0=m 。k 為 d 數(shù)組下標(biāo)return 1;/ (5)用迪杰斯特拉算法，求出一個(gè)景點(diǎn)到其他景點(diǎn)間的最短路徑，并打印void shortestpath_dij(mgraph c)/ 迪杰斯特拉算法，求從頂點(diǎn)v0 到其余頂點(diǎn)的最短路經(jīng)及其帶權(quán)長度dv/ 若 pvw為 1，則 w 是從 v0 到 v

22、的最短路經(jīng)上的頂點(diǎn)/finalv類型用于設(shè)置訪問標(biāo)志int v,w,i,min,t=0,x,flag=1,v0;/vo為起始景點(diǎn)的編號(hào)int final35,d35,p3535;printf("n請(qǐng)輸入一個(gè)起始景點(diǎn)的編號(hào)：");scanf("%d",&v0);printf("nn"); while(v0<0|v0>c.vexnum)printf("n你所輸入的景點(diǎn)編號(hào)不存在n"); printf("請(qǐng)重新輸入： ");scanf("%d",&v0)

23、;/while for(v=0;v<c.vexnum ;v+)dvfinalv=0;/初始化各頂點(diǎn)訪問標(biāo)志dv=c.arcsv0v.adj;/v0到各頂點(diǎn)v的權(quán)值賦值給for(w=0;w<c.vexnum;w+)/初始化 p數(shù)組， 各頂點(diǎn)間的路徑全部設(shè)置為空路徑0pvw=0;if(dv<infinity)/v0到v有邊相連，修改pvv0的值為 1pvv0=1;pvv=1;/各頂點(diǎn)自己到自己要連通/fordv0=0;/自己到自己的權(quán)值設(shè)為0finalv0=1;/v0的訪問標(biāo)志設(shè)為1，v 屬于 s集for(i=1;i<c.vexnum ;i+)/對(duì)其余 c.vexnum-1

24、個(gè)頂點(diǎn) w，依次求 v到 w 的最短路徑min=infinity;for(w=0;w<c.vexnum ;w+)/在未被訪問的頂點(diǎn)中，查找與v0 最近的頂點(diǎn)vif(!finalw)if(dw<min)/v0到 w ( 有邊 ) 的權(quán)值 <minv=w; min=dw;/iffinalv=1;/v的訪問標(biāo)志設(shè)置為 1， v 屬于 s 集for(w=0;w<c.vexnum ;w+)/修改 v0 到其余各頂點(diǎn) w 的最短路徑權(quán)值dwif(!finalw&&(min+c.arcsvw.adj <dw) /若 w 不屬于s，且 v到 w 有邊相連的權(quán)值 d

25、wdw=min+c.arcsvw.adj;/修 改 v0 到 wfor(x=0;x<c.vexnum ;x+)/所有 v0 到 v 的最短路徑上的頂點(diǎn)x，都是 v0 到 w 的最短路徑上的頂點(diǎn)pwx=pvx; pww=1;/if/forfor(v=0;v<c.vexnum;v+)/輸出 v0到其它頂點(diǎn)v 的最短路徑if(v!=v0)printf("%s",);/輸出景點(diǎn)v0的景點(diǎn)名for(w=0;w<c.vexnum ;w+)/對(duì)圖中每個(gè)頂點(diǎn)w，試探w是否是 v0到 v 的最短路徑上的頂點(diǎn)輸出該景點(diǎn)if(pvw &&

26、; w!=v0 && w!=v)/若 w 是且 w 不等于 v0，則printf("->%s",);printf(">%s",);printf("n總路線長為 %d米nn",dv);/for/shortestpath/ (12)輸出圖的鄰接矩陣的值/void printmatrix(mgraph c)int i,j,k=0;/k用于計(jì)數(shù)，控制換行for(i=0;i<c.vexnum ;i+) for(j=0;j<c.vexnum ;j+)if(c.

27、arcsij.adj =infinity) printf("");elsek+;printf("%4d",c.arcsij.adj);/printpathif(k%c.vexnum =0) printf("n");void shortestpath_floyd(mgraph c)/ 用 floyd算法求各對(duì)頂點(diǎn)v 和 w 間的最短路經(jīng)及其帶權(quán)長度的dvw。/ 若 pvwu=1；則 u 是 v 到 w 的當(dāng)前求得的最短路經(jīng)上的頂點(diǎn)int i,j,k,d3535,p353535;int v,u,w;for(v=0;v<c.vexnu

28、m ;v+)/初始化各對(duì)頂點(diǎn)v ， w 之間的起始距離dvw及 路 徑 pvw數(shù)組for(w=0;w<c.vexnum ;w+)分量全部清0dvw=c.arcsvw.adj;/dvw中存放 v至 w 間初始權(quán)值for(u=0;u<c.vexnum;u+)/初始化最短路徑pvw數(shù)組，第 3個(gè)pvwu=0;if(dvw<infinity)/如果 v至 w 間有邊相連pvwv=1;pvww=1;/ v/ w是 v是 v至 w最短路徑上的頂點(diǎn)至 w最短路徑上的頂點(diǎn)for(u=0;u<c.vexnum;u+)/求 v 至 w的最短路徑及距離。對(duì)任意頂點(diǎn)u，試探其是否為 v 至 w

29、 最短路徑上的頂點(diǎn)for(v=0;v<c.vexnum ;v+) for(w=0;w<c.vexnum ;w+)if(dvu+duw<dvw) /從 v經(jīng) u到 w 的一條路徑更短dvw=dvu+duw; /修改 v至 w 的最短路徑長度for(i=0;i<c.vexnum ;i+) /修改 v至 w 的最短路徑數(shù)組。若i 是 v 至 u 的最短路徑上的頂點(diǎn),pvwi=pvui|puwi;/ 或 i 是 u 至 w 的最短路徑上的頂點(diǎn),則 i 是 v 至 w 的最短路徑上的頂點(diǎn)/endforprintf("n請(qǐng)輸入出發(fā)點(diǎn)和目的地編號(hào)："); scan

30、f("%d%d",&k,&j);printf("nn"); while(k<0|k>c.vexnum|j<0|j>c.vexnum)printf("n你所輸入的景點(diǎn)編號(hào)不存在！"); printf("n請(qǐng)重新輸入出發(fā)點(diǎn)和目的地編號(hào)：nn"); scanf("%d%d",&k,&j);printf("nn");printf("%s", );/輸出出發(fā)景點(diǎn)名稱for(u=0;u&l

31、t;c.vexnum ;u+)if(pkju && k!=u && j!=u)/輸出最短路徑上中間景點(diǎn)名稱printf("->%s", );printf("->%s", );/輸出目的地景點(diǎn)名稱printf("nnn總長為 %d米nnn",dkj);/shortestpath_floyd/ (15)查詢景點(diǎn)的信息void seeabout(mgraph c)int k;printf("n請(qǐng)輸入要查詢的景點(diǎn)編號(hào)："); sca

32、nf("%d",&k);while(k<0|k>c.vexnum)printf("n你所輸入的景點(diǎn)編號(hào)不存在！"); printf("n請(qǐng)重新輸入：");scanf("%d",&k);printf("nn編 號(hào) ： %-4dn",c.vexsk.position ); printf("nn景點(diǎn)名稱： %-10sn", ); printf("nn介紹： %-80snn",roducti

33、on );/seeabout/ (16)顯示所有景點(diǎn)信息void browsecompus(mgraph c)int i;printf(" nn編號(hào)景點(diǎn)名稱簡介 n");printf(" n"); for(i=0;i<c.vexnum ;i+)printf("%-10d%-25s%-80sn",c.vexsi.position,, roduction);printf(" nn");/browsecompus/ (17)主要工作函數(shù)。操作區(qū)用戶界面void main

34、work()int yourchoice; campus=initgraph();printf("n-歡迎使用公園導(dǎo)游程序-n");printf("n歡 迎 來 到 公 園!nn");printf("n菜單選擇nn");printf("1.公園景點(diǎn)介紹2.查看游覽路線n");n");n");printf("3.查詢景點(diǎn)間最短路徑4.景點(diǎn)信息查詢printf("5.查詢景點(diǎn)間可行路徑6.打印鄰接矩陣printf("7.退出n"); printf("n-n");printf("請(qǐng)輸入你的選擇