版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
1、<p><b> 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計</b></p><p><b> 一 問題描述</b></p><p> 用無向網(wǎng)表示**的校園景點平面圖,圖中頂點表示主要景點,存放景點編號、名稱、簡介等信息,圖中邊表示景點間的道路,存放路徑長度信息。</p><p><b> 程序的主要功能:</b
2、></p><p> 查詢各景點的相關(guān)信息;</p><p> 查詢圖中任意兩個景點間的最短路徑;</p><p> (3) 查詢圖中任意兩個景點間的所有路徑。</p><p> **作為一個正在興起的重點學(xué)校,每年都有很多的領(lǐng)導(dǎo)來參觀和學(xué)校之間的交流學(xué)習(xí),大多數(shù)參觀者對學(xué)校的景點的相關(guān)信息并不是非常了解,所以我們設(shè)計這個校園導(dǎo)
3、游的咨詢程序,即**校園導(dǎo)游咨詢程序。</p><p><b> 二 數(shù)據(jù)結(jié)構(gòu)</b></p><p><b> 1、基本操作:</b></p><p> CreateGraph(G):創(chuàng)建圖G。</p><p> LocateVertex(G,v):確定頂點v在圖g中的位置,若圖g中沒有頂
4、點v,則函數(shù)值為“空”。</p><p> GetVertex(G,i):取出圖g中的第i個頂點的值,若i大于圖g中頂點數(shù),則函數(shù)值為“空”。 </p><p> FirstAdjVertex(G,v):求圖G頂點v的第一個鄰接點,若v無鄰接點或圖G中無頂點v,則函數(shù)值為“空”。</p><p> NextAdjVertex(G,v,w):已知w是圖G中頂點
5、v的某個鄰接點,求頂點v的下一個鄰接點(緊跟在w后面),若w是v的最后一個鄰接點,則函數(shù)值為“空”。</p><p> InsertVertex(G,u):在圖G中增加一個頂點u。</p><p> InsertArc(G,v,w):在圖G中增加一條從頂點v到頂點w的弧。</p><p> TraverseGraph(G):按照某種次序,對圖G的每個結(jié)點訪問一
6、次且僅訪問一次。 </p><p> 2、系統(tǒng)中子程序及功能要求:</p><p> ?、賞ath(MGraph g,int i,int j,int k):確定路徑上第k+1個頂點的序號,k初始值為0</p><p> ?、赼path(MGraph g,int i,int j):初始化訪問標(biāo)志與路徑條數(shù),并調(diào)用path()函數(shù)</p><
7、;p> ?、踓path(MGraph g,int path1[],int i,int v0):輸出最短路徑</p><p> ④bpath(MGraph g,int dist[],int path1[],int s[],int n,int v0,int i):由path1計算從v0到i的最短路徑</p><p> ?、軩ijkstra(MGraph g,int v0,int p):
8、采用迪杰斯特拉算法求從頂點v0到頂點p的最短路徑</p><p> ⑥chaname(MGraph g):查詢景點的信息</p><p> ?、遚hapath1(MGraph g):查詢兩個景點間的所有路徑</p><p> ?、郼hapath2(MGraph g):查詢兩個景點間的最短路徑</p><p> 3、各程序模塊之間的調(diào)用關(guān)系
9、:</p><p><b> 函數(shù)的調(diào)用關(guān)系圖</b></p><p><b> main</b></p><p> chaname ⑥ chapath1⑦ chapath2⑧</p><p> apath ④ Dijkstra⑤&l
10、t;/p><p> path ① bpath④</p><p> path ① cpath ③ </p><p><b> cpath③</b></p><p> 主函數(shù)可調(diào)用子程序⑥⑦⑧ </p>
11、<p> 子程序⑦可調(diào)用子程序④</p><p> 子程序⑧可調(diào)用子程序⑤</p><p> 子程序④可調(diào)用子程序①</p><p> 子程序①可調(diào)用子程序①</p><p> 子程序④可調(diào)用子程序③</p><p> 子程序③可調(diào)用子程序③</p><p> 子程序
12、②可調(diào)用子程序①</p><p> 子程序⑤可調(diào)用子程序④</p><p> 三 算法設(shè)計思想及流程圖</p><p> ?、彭旤c、邊和圖的類型:</p><p> typedef struct</p><p><b> {</b></p><p> int nu
13、m;/*頂點編號*/</p><p> char name[MAXSIZE];/*頂點名稱*/</p><p> char discription[MAXLEN];/*頂點信息描述*/</p><p> }VertexType; </p><p> typedef struct</p><p><b>
14、; {</b></p><p> int edges[MAXV][MAXV];</p><p> int vexnum,arcnum;</p><p> VertexType vexs[MAXV];</p><p><b> }MGraph;</b></p><p> in
15、t visited[MAXV];</p><p> int p[MAXV];</p><p><b> ?、苿?chuàng)建**地圖:</b></p><p><b> int i,j;</b></p><p> int b[11]={1,2,3,4,5,6,7,8,9,10,11};</p>
16、<p> char *c[11]={/*各個景點名稱*/};</p><p> char *d[11]={/*字符串指針數(shù)組,用來給每個頂點的簡介信息進行賦值*/};</p><p> MGraph g;/*創(chuàng)建一個無向網(wǎng)*/</p><p> int A[11][11]={/*景點的相關(guān)簡介進行賦值*/ }; </p><
17、;p> g.vexnum=頂點個數(shù);</p><p> g.arcnum=頂點邊數(shù);</p><p> /*建立無向網(wǎng)的鄰接矩陣*/</p><p> for(i=0;i<圖的頂點個數(shù);i++)</p><p><b> {</b></p><p> /*給每個頂點一個編號
18、*/</p><p> /*通過字符串復(fù)制函數(shù)給每個頂點一個名稱*/</p><p> /*通過字符串復(fù)制函數(shù)給每個頂點加上信息,即作為景點的簡介信息*/</p><p><b> }</b></p><p><b> ⑶查詢景點的信息:</b></p><p>&l
19、t;b> int i;</b></p><p><b> char s;</b></p><p><b> while(1)</b></p><p> /*可提供循環(huán)查詢,當(dāng)輸入為'N'或'n'時,結(jié)束循環(huán)*/</p><p><b&g
20、t; {</b></p><p> printf("\t\t\t 請輸入你要查詢的景點:");</p><p> scanf("%d",&i);</p><p> for(int j=0;j<圖的頂點個數(shù);j++)</p><p><b> {<
21、;/b></p><p><b> /*輸出信息*/</b></p><p><b> } </b></p><p> printf("繼續(xù)查詢?(y或n):");</p><p> scanf("%s",&s);</p>
22、<p> if(s=='N'||s=='n')</p><p><b> break;</b></p><p><b> }</b></p><p> ⑷查詢景點間的路徑:</p><p> void chapath1(MGraph g)</
23、p><p><b> int i,j;</b></p><p><b> char s;</b></p><p> while(1)/*可提供循環(huán)查詢,當(dāng)輸入為'N'或'n'時,結(jié)束循環(huán)*/</p><p><b> {</b></p&
24、gt;<p> /*輸入起點與終點*/; </p><p> disppath(g,i,j);/*調(diào)用disppath函數(shù),用來輸出兩個景點間的所有路徑*/</p><p> printf("繼續(xù)查詢?(y或n):");</p><p> scanf("%s",&s);</p>&l
25、t;p> if(s=='N'||s=='n')</p><p><b> break;</b></p><p><b> }</b></p><p><b> }</b></p><p> ?、刹樵儍蓚€景點間的最短路徑:</p
26、><p><b> int i,j;</b></p><p><b> char s;</b></p><p><b> while(1)</b></p><p> /*可提供循環(huán)查詢,當(dāng)輸入為'N'或'n'時,結(jié)束循環(huán)*/</p>
27、;<p><b> {</b></p><p> /*輸入起點與終點*/</p><p> Dijkstra(g,i,j);/*調(diào)用Dijkstra函數(shù),用來輸出兩個景點間的最短路徑*/</p><p> printf("繼續(xù)查詢?(y或n):");</p><p> scan
28、f("%s",&s);</p><p> if(s=='N'||s=='n')</p><p><b> break;</b></p><p><b> }</b></p><p><b> }</b><
29、/p><p><b> ?、手骱瘮?shù):</b></p><p> int select;/*定義一個整型變量,用來輸入不同的選擇*/</p><p> do/*可提供循環(huán)輸入選擇,當(dāng)輸入的選擇為4時,退出循環(huán)*/</p><p><b> { </b></p><p> s
30、witch(select)/*判斷select的值,根據(jù)其值跳轉(zhuǎn)到相應(yīng)的子模塊繼續(xù)執(zhí)行*/</p><p><b> {</b></p><p><b> case 1:</b></p><p> /*查詢景點的信息*/</p><p><b> break;</b>&
31、lt;/p><p><b> case 2:</b></p><p> ;/*查詢景點間的游覽路徑*/ </p><p><b> break;</b></p><p><b> case 3:</b></p><p> /*查詢景點間的最短游覽
32、路徑*/</p><p><b> break;</b></p><p> case 4:/*退出程序*/</p><p><b> break;</b></p><p><b> }</b></p><p> }while(select!=5
33、);/*當(dāng)select的值不為5時,繼續(xù)循環(huán)*/</p><p><b> }</b></p><p><b> 四 源程序</b></p><p> #include<stdio.h></p><p> #include<string.h></p>&
34、lt;p> #include <stdlib.h></p><p> #define MAXV 11</p><p> #define MAXSIZE 30</p><p> #define MAXLEN 3000</p><p> #define INF 32767</p><p><
35、;b> int a=0;</b></p><p> typedef struct </p><p><b> {</b></p><p><b> int num;</b></p><p> char name[MAXSIZE];</p><p>
36、 char xinxi[MAXLEN];</p><p> }VertexType; </p><p> typedef struct</p><p><b> {</b></p><p> int edges[MAXV][MAXV];</p><p> int vexnum,arc
37、num;</p><p> VertexType vexs[MAXV];</p><p><b> }MGraph;</b></p><p> int visited[MAXV];</p><p> int p[MAXV];</p><p> void path(MGraph g,int
38、 i,int j,int k)/*確定路徑上第k+1個頂點的序號,k初始值為0*/</p><p><b> {</b></p><p><b> int s;</b></p><p> if(p[k]==j)</p><p><b> {</b></p>
39、<p><b> a++;</b></p><p> printf("第%d條:",a);</p><p> for(s=0;s<=k-1;s++)</p><p> printf("%s->",g.vexs[p[s]].name);</p><p>
40、; printf("%s\n",g.vexs[p[s]].name);</p><p><b> }</b></p><p><b> s=0;</b></p><p> while(s<g.vexnum)</p><p><b> {</b>
41、;</p><p><b> if(s!=i)</b></p><p><b> {</b></p><p> if(g.edges[p[k]][s]!=INF&&visited[s]==0)</p><p><b> {</b></p>
42、<p> visited[s]=1;</p><p><b> p[k+1]=s;</b></p><p> path(g,i,j,k+1);</p><p> visited[s]=0;</p><p><b> }</b></p><p><b&
43、gt; }</b></p><p><b> s++;</b></p><p><b> }</b></p><p><b> }</b></p><p> void apath(MGraph g,int i,int j)/*初始化訪問標(biāo)志與路徑條數(shù),并調(diào)
44、用path()函數(shù)*/</p><p><b> {</b></p><p><b> int k;</b></p><p><b> p[0]=i;</b></p><p> for(k=0;k<g.vexnum;k++)</p><p>
45、; visited[i]=0;</p><p><b> a=0;</b></p><p> path(g,i,j,0);</p><p><b> }</b></p><p> void cpath(MGraph g,int path1[],int i,int v0)/*輸出最短路徑*/
46、</p><p><b> {</b></p><p><b> int k;</b></p><p> k=path1[i];</p><p><b> if(k==v0)</b></p><p><b> return;</
47、b></p><p> cpath(g,path1,k,v0);</p><p> printf("%s->",g.vexs[k].name);</p><p><b> }</b></p><p> void bpath(MGraph g,int dist[],int path1
48、[],int s[],int n,int v0,int i)/*由path1計算從v0到i的最短路徑*/</p><p><b> {</b></p><p> if(s[i]==1&&i!=v0)</p><p><b> {</b></p><p> printf(&qu
49、ot;從%s到%s的最短游覽路徑是:\n",g.vexs[v0].name,g.vexs[i].name);</p><p> printf("%s->",g.vexs[v0].name);</p><p> cpath(g,path1,i,v0);</p><p> printf("%s ",g
50、.vexs[i].name);</p><p> printf("路徑長度:%d米\n",dist[i]);</p><p><b> }</b></p><p><b> }</b></p><p> void Dijkstra(MGraph g,int v0,int
51、p)/*采用迪杰斯特拉算法求從頂點v0到頂點p的最短路徑*/</p><p><b> {</b></p><p> int dist[MAXV],path1[MAXV];</p><p> int s[MAXV]; </p><p> int mindis,i,j,u,n=g.vexnum;</p>
52、<p> for(i=0;i<n;i++)</p><p><b> {</b></p><p> dist[i]=g.edges[v0][i];</p><p><b> s[i]=0;</b></p><p> if(g.edges[v0][i]<INF)&l
53、t;/p><p> path1[i]=v0;</p><p><b> else </b></p><p> path1[i]=-1;</p><p><b> }</b></p><p> s[v0]=1;path1[v0]=0;</p><p&g
54、t; for(i=0;i<n;i++)</p><p><b> {</b></p><p> mindis=INF;</p><p><b> u=-1;</b></p><p> for(j=0;j<n;j++)</p><p> if(s[j]=
55、=0&&dist[j]<mindis) </p><p><b> {</b></p><p><b> u=j;</b></p><p> mindis=dist[j];</p><p><b> }</b></p><p&g
56、t;<b> s[u]=1;</b></p><p> for(j=0;j<n;j++)</p><p> if(s[j]==0)</p><p> if(g.edges[u][j]<INF&&dist[u]+g.edges[u][j]<dist[j])</p><p><
57、b> {</b></p><p> dist[j]=dist[u]+g.edges[u][j];</p><p> path1[j]=u;</p><p><b> }</b></p><p><b> }</b></p><p> bpath(
58、g,dist,path1,s,n,v0,p);</p><p><b> }</b></p><p> void chaname(MGraph g)/***各景點的相關(guān)信息*/</p><p><b> {</b></p><p> printf("您可以選擇以下任一景點:\n&q
59、uot;);</p><p> printf("--------------------------------------------------------------------------------\n");</p><p> printf("\t\t1:正門\n\t\t2:經(jīng)管教學(xué)樓\n");</p><p>
60、 printf("\t\t3:第一教學(xué)樓\n\t\t4:第二教學(xué)樓\n\t\t5:第三教學(xué)樓\n\t\t6:綜合教學(xué)樓\n\t\t7:圖書館\n");</p><p> printf("\t\t8:學(xué)生食堂\n\t\t9:大學(xué)生就業(yè)指導(dǎo)中心\n\t\t10:學(xué)生公寓\n\t\t11:東門\n");</p><p> printf("-
61、-------------------------------------------------------------------------------\n");</p><p><b> int i;</b></p><p><b> char s;</b></p><p><b> wh
62、ile(1)</b></p><p><b> {</b></p><p> printf("\t\t\t 請輸入您要查詢的景點:");</p><p> scanf("%d",&i);</p><p> for(int j=0;j<g.v
63、exnum;j++)</p><p> if(i==g.vexs[j].num)</p><p><b> {</b></p><p> printf("%s該景點的相關(guān)簡介:\n",g.vexs[j].name);</p><p> printf("----------------
64、----------------------------------------------------------------\n");</p><p> printf("%s",g.vexs[j].xinxi);</p><p> printf("\n");</p><p><b> } <
65、/b></p><p> printf("--------------------------------------------------------------------------------\n");</p><p> printf("您是否要繼續(xù)查詢?(按任意鍵繼續(xù)或按n退出):");</p><p>
66、 scanf("%s",&s);</p><p> if(s=='N'||s=='n')</p><p><b> break;</b></p><p><b> }</b></p><p><b> }</b&g
67、t;</p><p> void chapath1(MGraph g)/*查詢**各景點間的游覽路徑 */</p><p><b> {</b></p><p> printf("您可以選擇以下任一景點:\n");</p><p> printf("-----------------
68、---------------------------------------------------------------\n");</p><p> printf("\t\t1:正門\n\t\t2:經(jīng)管教學(xué)樓\n");</p><p> printf("\t\t3:第一教學(xué)樓\n\t\t4:第二教學(xué)樓\n\t\t5:第三教學(xué)樓\n\t\t6
69、:綜合教學(xué)樓\n\t\t7:圖書館\n");</p><p> printf("\t\t8:學(xué)生食堂\n\t\t9:大學(xué)生就業(yè)指導(dǎo)中心\n\t\t10:學(xué)生公寓\n\t\t11:東門\n");</p><p> printf("------------------------------------------------------------
70、--------------------\n");</p><p><b> int i,j;</b></p><p><b> char s;</b></p><p><b> while(1)</b></p><p><b> {</b&g
71、t;</p><p> printf("\t\t\t 選擇您的出發(fā)景點:");</p><p> fflush(stdin); </p><p> scanf("%d",&i);</p><p> printf("\t\t\t 選擇您的目地景點:");
72、</p><p> fflush(stdin);</p><p> scanf("%d",&j);</p><p> for(int k=0;k<g.vexnum;k++)</p><p> if(i==g.vexs[k].num) i=k;</p><p> for(int
73、 l=0;l<g.vexnum;l++)</p><p> if(j==g.vexs[l].num) j=l;</p><p> printf("從%s到%s的所有游覽路徑有:\n",g.vexs[i].name,g.vexs[j].name);</p><p> apath(g,i,j);</p><p>
74、 printf("--------------------------------------------------------------------------------\n");</p><p> printf("您是否要繼續(xù)查詢?(按任意鍵繼續(xù)或按n退出):");</p><p> scanf("%s",&
75、s);</p><p> if(s=='N'||s=='n')</p><p><b> break;</b></p><p><b> }</b></p><p><b> }</b></p><p> voi
76、d chapath2(MGraph g)/*查詢**各景點間的最短游覽路徑*/</p><p><b> {</b></p><p> printf("您可以選擇以下任一景點:\n");</p><p> printf("--------------------------------------------
77、------------------------------------\n");</p><p> printf("\t\t1:正門\n\t\t2:經(jīng)管教學(xué)樓\n");</p><p> printf("\t\t3:第一教學(xué)樓\n\t\t4:第二教學(xué)樓\n\t\t5:第三教學(xué)樓\n\t\t6:綜合教學(xué)樓\n\t\t7:圖書館\n");
78、</p><p> printf("\t\t8:學(xué)生食堂\n\t\t9:大學(xué)生就業(yè)指導(dǎo)中心\n\t\t10:學(xué)生公寓\n\t\t11:東門\n");</p><p> printf("--------------------------------------------------------------------------------\n"
79、;);</p><p><b> int i,j;</b></p><p><b> char s;</b></p><p><b> while(1)</b></p><p><b> {</b></p><p> pr
80、intf("\t\t\t 選擇您的出發(fā)景點:");</p><p> fflush(stdin);</p><p> scanf("%d",&i);</p><p> printf("\t\t\t 選擇您的目地景點:");</p><p> fflus
81、h(stdin);</p><p> scanf("%d",&j);</p><p> for(int k=0;k<g.vexnum;k++)</p><p> if(i==g.vexs[k].num) i=k; </p><p> for(int l=0;l<g.vexnum;l++)<
82、;/p><p> if(j==g.vexs[l].num) j=l; </p><p> Dijkstra(g,i,j);</p><p> printf("--------------------------------------------------------------------------------\n");</p>
83、;<p> printf("您是否要繼續(xù)查詢?(按任意鍵繼續(xù)或按n退出):");</p><p> scanf("%s",&s);</p><p> if(s=='N'||s=='n')</p><p><b> break;</b></
84、p><p><b> }</b></p><p><b> }</b></p><p> void chapath3(MGraph g)/*動態(tài)添加景點*/</p><p><b> {</b></p><p> printf("您可以添
85、加任何您想查詢的景點:\n");</p><p> printf("--------------------------------------------------------------------------------\n");</p><p> printf("尊敬的用戶,本程序暫還未能實現(xiàn)本功能,為此給您帶來的不便我表示抱歉,感謝您
86、的使用,再見\n");</p><p> printf("--------------------------------------------------------------------------------\n");</p><p> printf("請您重新運行本程序");</p><p><
87、;b> int i,j;</b></p><p><b> char s;</b></p><p><b> while(1)</b></p><p><b> {</b></p><p> scanf("\t\t\t 請輸入您要添
88、加的景點:");</p><p> scanf("--------------------------------------------------------------------------------\n");</p><p> scanf("尊敬的用戶,本程序暫還未能實現(xiàn)本功能,為此給您帶來的不便我表示抱歉,感謝您的使用,再見\n&q
89、uot;);</p><p> scanf("--------------------------------------------------------------------------------\n");</p><p><b> } </b></p><p> scanf("---------
90、-----------------------------------------------------------------------\n");</p><p> printf("您是否要繼續(xù)查詢?(按任意鍵繼續(xù)或按n退出):");</p><p> scanf("%s",&s);</p><p>
91、; if(s=='N'||s=='n');</p><p><b> }</b></p><p> void main()</p><p><b> {</b></p><p><b> int i,j;</b></p>
92、<p> int b[11]={1,2,3,4,5,6,7,8,9,10,11};</p><p> char *c[11]={"正門","經(jīng)管教學(xué)樓","第一教學(xué)樓","第二教學(xué)樓","第三教學(xué)樓","綜合教學(xué)樓","圖書館","學(xué)生食堂"
93、,"大學(xué)生就業(yè)指導(dǎo)中心","學(xué)生公寓","東門"};</p><p> char *d[11]=</p><p><b> {</b></p><p> "位于遼寧省大連市經(jīng)濟技術(shù)開發(fā)區(qū)遼河西路,校門由56個巨型石柱組成,代表了我們56個民族團結(jié)一心 ",&l
94、t;/p><p> "留學(xué)生教學(xué)中心,教學(xué)研討交流中心",</p><p> "學(xué)校重點學(xué)院理學(xué)院以及文法學(xué)院,同時給學(xué)生提供自習(xí)學(xué)習(xí)的地方",</p><p> "主要教學(xué)樓,二樓為英語教學(xué)計算機基地",</p><p> "設(shè)計學(xué)院,很多優(yōu)秀的作品創(chuàng)作于此"
95、;,</p><p> "創(chuàng)新教育中心,物理實驗室,物理與材料學(xué)院",</p><p> "圖書、資料借閱,電子閱覽室,自習(xí)室,考研自習(xí)室,曉梅英語",</p><p> "第一、第二為學(xué)生普通食堂,設(shè)有風(fēng)味特色,第三學(xué)生食堂為清真食堂",</p><p> "學(xué)生
96、就業(yè)信息咨詢,郵政快遞,比賽交流",</p><p> "現(xiàn)有1——11號學(xué)生公寓,其中1,3,5,6,7號為男生公寓",</p><p> "出門為友誼商場,大商新瑪特超市. "</p><p><b> };</b></p><p><b> MGr
97、aph g;</b></p><p> int A[11][11]={</p><p> {INF,14,INF,INF,INF,INF,INF,INF,INF,INF,17},</p><p> {14,INF,3,INF,INF,17,INF,INF,12,INF,INF},</p><p> {INF,3,INF,1
98、7,INF,INF,INF,INF,INF,INF,3},</p><p> {INF,INF,17,INF,10,INF,INF,INF,INF,INF,INF},</p><p> {INF,INF,INF,10,INF,10,8,INF,INF,INF,INF},</p><p> {INF,17,INF,INF,10,INF,INF,12,INF,IN
99、F,INF},</p><p> {INF,INF,INF,INF,8,INF,INF,18,INF,INF,INF},</p><p> {INF,INF,INF,INF,INF,12,18,INF,10,17,INF},</p><p> {INF,12,INF,INF,INF,INF,INF,10,INF,INF,INF},</p><
100、;p> {INF,INF,INF,INF,INF,INF,INF,17,INF,INF,20},</p><p> {3,INF,3,INF,INF,INF,INF,INF,INF,20,INF}}; </p><p> g.vexnum=11;</p><p> g.arcnum=17;</p><p> for(i=0;
101、i<g.vexnum;i++)</p><p> for(j=0;j<g.vexnum;j++)</p><p> g.edges[i][j]=A[i][j];</p><p> for(i=0;i<g.vexnum;i++)</p><p><b> {</b></p><
102、p> g.vexs[i].num=b[i];</p><p> strcpy(g.vexs[i].name,c[i]);</p><p> strcpy(g.vexs[i].xinxi,d[i]);</p><p><b> }</b></p><p> int select; </p>&
103、lt;p><b> do</b></p><p><b> { </b></p><p> system("cls");</p><p> printf("------------------------------**導(dǎo)游咨詢程序------------------------
104、------\n");</p><p> printf(" 作者:信息101班17題小組\n");</p><p> printf("歡迎來到**:\n");</p><p> printf("
105、;\n ############################################\n");</p><p> printf(" \n");</p><p> printf(&quo
106、t; 1、查詢**各景點相關(guān)信息 \n");</p><p> printf(" 2、查詢**景點間的游覽路徑 \n");</p><p> printf(" 3、查詢**各景點間最短路徑 \n");</
107、p><p> printf(" 4、輸入您要添加的景點 \n");</p><p> printf(" 5、退出本程序 \n");</p><p> printf("
108、 \n");</p><p> printf(" ############################################\n");</p><p> printf("----------
109、----------------------------------------------------------------------\n");</p><p> printf(" 請輸入您的選擇:");</p><p> scanf("%d",&select);
110、</p><p> switch(select) </p><p><b> {</b></p><p><b> case 1:</b></p><p> chaname(g);/*查詢民院各景點的相關(guān)信息*/</p><p><b> break;&l
111、t;/b></p><p><b> case 2:</b></p><p> chapath1(g);/*查詢民院各景點間的游覽路徑*/ </p><p><b> break;</b></p><p><b> case 3:</b></p>
112、<p> chapath2(g);/*查詢民院各景點間的最短游覽路徑*/</p><p><b> break;</b></p><p><b> case 4:</b></p><p> chapath3(g);/*查詢動態(tài)添加的景點到各景點間的游覽路徑*/</p><p>&l
113、t;b> break;</b></p><p> case 5:/*退出本程序*/</p><p><b> break;</b></p><p><b> }</b></p><p> }while(select!=5);</p><p><
114、;b> }</b></p><p><b> 五 測試情況</b></p><p> 1、**導(dǎo)游咨詢程序界面</p><p> 查詢**各景點相關(guān)信息</p><p><b> 查詢所有路徑</b></p><p><b> 查詢最
115、短路徑</b></p><p> 1、在執(zhí)行查詢景點間的游覽路徑時,我之前考慮到深度優(yōu)先遍歷,我可以以指定的為起點開始遍歷,在到達(dá)指定的終點時,讓他停止并輸出路徑,不過這之間要定義一個s,來存放訪問過的并且可走通的頂點編號,以便可以方便輸出,可是,如一個頂點有多個鄰接點,它是選取其中一條的,有可能在這個頂點可以經(jīng)過這些鄰接點照樣可以走到我們指定的終點,在這里就出現(xiàn)了問題,怎樣讓它在訪問一個鄰接點之后
116、還可以在訪問它的另外一個鄰接點。之后想到了遞歸調(diào)用,以及鄰接矩陣并通過visited[]來解決這個問題;</p><p> 2、在執(zhí)行導(dǎo)游程序時,需要根據(jù)用戶的臨時輸入求最短路徑。雖然迪杰斯特拉算法的時間復(fù)雜度比弗洛伊德算法低,但每次在求一條最短路徑時都必須重新搜索一遍,如果用戶頻繁查詢會導(dǎo)致查詢效率降低,所以,在選用算法時不能單純的只考慮算法的漸近時間復(fù)雜度,有時還必須綜合考慮各種因素。</p>
117、<p><b> 參考文獻(xiàn)</b></p><p> [1]算法與數(shù)據(jù)結(jié)構(gòu) C語言版 第二版 (陳守孔 孟佳娜 武秀川 著) 機械工業(yè) 出版社, 2005 </p><p> [2] 譚浩強 . C++ 程序設(shè)計 . 北京:清華大學(xué)出版社, 2005</p><p> [3] 嚴(yán)蔚敏,吳偉民 . 數(shù)據(jù)結(jié)構(gòu) . 北京
118、:清華大學(xué)出版社, 2004</p><p><b> 目錄</b></p><p><b> 一 問題描述1</b></p><p><b> 二 數(shù)據(jù)結(jié)構(gòu)1</b></p><p> 三 算法設(shè)計思想及流程圖3</p><p><
119、b> 四 源程序5</b></p><p><b> 五 測試情況19</b></p><p><b> 參考文獻(xiàn)22</b></p><p><b> 數(shù)據(jù)結(jié)構(gòu)與算法</b></p><p><b> 課程設(shè)計報告</b>
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--校園導(dǎo)游咨詢
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-校園導(dǎo)游咨詢
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--校園導(dǎo)游咨詢
- 校園導(dǎo)游咨詢系統(tǒng)-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
- 數(shù)據(jù)結(jié)構(gòu)校園導(dǎo)游咨詢課程設(shè)計報告
- 校園導(dǎo)游咨詢系統(tǒng)---數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計——校園導(dǎo)游咨詢系統(tǒng)
- 數(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ù)據(jù)結(jié)構(gòu)課程設(shè)計報告-校園導(dǎo)游程序
- 校園導(dǎo)游咨詢系統(tǒng)-中南大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
- 數(shù)據(jù)結(jié)構(gòu)_校園導(dǎo)游系統(tǒng)課程設(shè)計
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---校園導(dǎo)游系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu) 校園導(dǎo)游系統(tǒng)課程設(shè)計
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---校園導(dǎo)游系統(tǒng)設(shè)計
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---校園交通導(dǎo)游系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告--校園導(dǎo)游系統(tǒng)
評論
0/150
提交評論