2023年全國碩士研究生考試考研英語一試題真題(含答案詳解+作文范文)_第1頁
已閱讀1頁,還剩22頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(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)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論