數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---圖的建立與輸出_第1頁
已閱讀1頁,還剩16頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

1、<p><b>  數(shù)據(jù)結(jié)構(gòu)課程設(shè)計</b></p><p>  設(shè)計題目:圖的建立與輸出</p><p>  系 別: 電子與信息工程學(xué)院 </p><p>  專 業(yè): 電子信息工程 </p><p>  班 級: 2009級(1)班 </

2、p><p>  姓 名: </p><p>  學(xué) 號: </p><p>  指導(dǎo)教師: </p><p>  2011年 06 月 20日</p><p><b>  目錄</b></p>

3、;<p>  一、設(shè)計題目(任選其一)…………………………………………3</p><p>  二、運行環(huán)境(軟、硬件環(huán)境)……………………………………3</p><p>  三、算法設(shè)計的思想…………………………………………………3</p><p>  四、算法的流程圖……………………………………………………3</p><p>

4、  五、算法設(shè)計分析……………………………………………………4</p><p>  六、源代碼……………………………………………………………4</p><p>  七、運行結(jié)果分析……………………………………………………14</p><p>  八、收獲及體會………………………………………………………16</p><p>  一、設(shè)計題目(任

5、選其一)</p><p><b>  圖的建立及輸出</b></p><p>  任務(wù):建立圖的存儲結(jié)構(gòu)(圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng),學(xué)生可以任選兩種類型),能夠輸入圖的頂點和邊的信息,并存儲到相應(yīng)存儲結(jié)構(gòu)中,而后輸出圖的鄰接矩陣。 </p><p>  二、運行環(huán)境(軟、硬件環(huán)境)</p><p>&

6、lt;b>  硬件環(huán)境:</b></p><p>  CPU:1000MHz以上</p><p>  內(nèi)存:256MB以上</p><p><b>  硬盤:60G以上</b></p><p><b>  軟件環(huán)境:</b></p><p>  系統(tǒng)平臺:

7、Windows 2000 / Windows XP / Windows Vista / Windows 7 </p><p>  運行環(huán)境:TC 3.0 / Microsoft Visual C++ 6.0</p><p><b>  三、算法設(shè)計的思想</b></p><p>  1、存儲結(jié)構(gòu);鄰接矩陣 鄰接表</p><

8、p>  2、遍歷方式:深度優(yōu)先搜索(DFS) 廣度優(yōu)先搜索(BFS) 也可以對鄰接矩陣和臨界表直接輸出:其中DFS算法通過遞歸實現(xiàn),BFS算法通過隊列實現(xiàn)。</p><p>  3、拓撲排序和最小生成樹(Prime算法),具體實現(xiàn)見代碼。</p><p><b>  四、算法的流程圖</b></p><p><b>  五、算法

9、設(shè)計分析</b></p><p>  首先是建圖,圖和網(wǎng)的區(qū)別在于圖沒有權(quán)值(這里以固定值1代替),網(wǎng)有權(quán)值,有向和無向在存儲上的區(qū)別在于對于有向圖,輸入a[i][j],只存儲a[i][j],而對于無向圖還要存儲a[j][i]。</p><p>  其次是功能的實現(xiàn),鄰接表遍歷和鄰接矩陣遍歷都很簡單,按照它的存儲結(jié)構(gòu),依次輸出每個頂點和它鄰接的頂點,時間復(fù)雜度分別為O(n+e)

10、和O(n2);</p><p>  對于DFS算法是通過函數(shù)遞歸實現(xiàn)的,所采用的存儲結(jié)構(gòu)式是鄰接表,找鄰接點所需時間為O(e),其中e為無向圖的邊數(shù)或有向圖的弧數(shù),時間復(fù)雜度為O(n+e)。</p><p>  對于BFS算法是用隊列實現(xiàn)的,每個頂點至多進一次隊列。遍歷圖的過程實質(zhì)上是通過邊或弧找鄰接點的過程,因此廣度優(yōu)先搜索遍歷圖的時間復(fù)雜度和深度優(yōu)先搜索遍歷相同,兩者不同之處僅僅在于對

11、每個頂點訪問的順序不同</p><p>  對于拓撲排序,建立各項頂點的入度的時間復(fù)雜度為O(e),建零入度頂點棧的時間復(fù)雜度為O(n);在拓撲排序過程中,若有向圖無環(huán),則每個頂點進一次棧,出一次棧,入度減1的操作在while語句中總共執(zhí)行e次,所以總的時間復(fù)雜度為O(n+e)。</p><p>  對于Prime算法的最小生成樹,假設(shè)網(wǎng)中有n個頂點,則第一個進行初始化的循環(huán)語句的頻度為n

12、,第二個循環(huán)語句的頻度為n-1。其二是重新選擇具有最小代價的邊,其頻度為n。由此,Prime算法的時間復(fù)雜度為O(n2),與網(wǎng)中的邊數(shù)無關(guān),因此適用于求邊稠密的網(wǎng)的最小生成樹。</p><p><b>  六、源代碼 </b></p><p>  #include <stdio.h></p><p>  #include <

13、string.h></p><p>  #include <stdlib.h></p><p>  #include <ctype.h></p><p>  #include <queue></p><p>  #include <stack></p><p>  

14、#include <process.h></p><p>  using namespace std;</p><p>  #define MAX_VERTEX_NUM 20</p><p>  #define MAX 1000</p><p>  #define DG 1</p><p>  #defin

15、e DN 2</p><p>  #define UDG 3</p><p>  #define UDN 4</p><p>  //typedef enum{DG,DN,UDG,UDN} GraphKind;</p><p>  typedef char VertexType;</p><p>  typedef

16、int VRType;</p><p>  typedef char InfoType;</p><p>  struct Close {</p><p>  VertexType data;//頂點元素</p><p>  VRType lowcost;</p><p><b>  int j;</

17、b></p><p>  }closedge[MAX_VERTEX_NUM]; //prime算法秋最小生成樹的輔助數(shù)組</p><p>  typedef struct ArcNode{</p><p>  int adjvex;//該弧所指向的頂點的位置</p><p>  struct ArcNode *nextarc;/

18、/指向下一條弧的指針</p><p>  int adj;//對于無權(quán)圖為0 或1;對于帶權(quán)圖為權(quán)值</p><p>  InfoType *info;//該弧相關(guān)信息的指針</p><p>  }ArcNode,AdjMartrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//為簡便起見鄰接矩陣的元素類型,此時部分元素?zé)o用&l

19、t;/p><p>  typedef struct VNode{</p><p>  int outdegree,indegree;</p><p>  VertexType data;//頂點信息</p><p>  ArcNode *firstarc;//指向第一條依附該頂點的弧的指針</p><p>  }VNode

20、,AdjList[MAX_VERTEX_NUM];</p><p>  typedef struct Graph{</p><p>  AdjList vertices; //鄰接表</p><p>  AdjMartrix arcs; //鄰接矩陣</p><p>  int vexnum,arcnum; // 頂點個數(shù)及邊的數(shù)量

21、</p><p>  int kind; //圖的類型</p><p><b>  }ALGraph;</b></p><p>  int cmp(const void *a,const void *b)</p><p><b>  {</b></p><p

22、>  if( *(char *)a-*(char *)b>=0)</p><p><b>  return 1;</b></p><p>  return -1;</p><p><b>  }</b></p><p>  int LocateVex(ALGraph & G,

23、VertexType e ){</p><p>  for(int i=1;i<=G.vexnum;i++)</p><p>  if(G.vertices[i].data==e) </p><p><b>  return i;</b></p><p><b>  return 0;</b>

24、</p><p><b>  } </b></p><p>  void Input_V(AdjList & ver,int n)</p><p><b>  {</b></p><p>  bool f=false;</p><p>  char str[30];&

25、lt;/p><p>  memset(str,0,sizeof(str));</p><p>  printf("輸入每個頂點:用字母數(shù)字 如 ABCDEF 表示六個頂點:");</p><p>  while(!f&&gets(str)){</p><p>  int len=strlen(str);&

26、lt;/p><p>  if(!len){ printf("\t\t你沒有輸入數(shù)據(jù),請輸入數(shù)據(jù):"); continue;}</p><p>  if(len<n){ printf("\t\t輸入長度不夠,請重新輸入:"); continue;}</p><p>  for(int i=0;i<n;i++)</p

27、><p>  ver[i+1].data=str[i];</p><p>  for( i=0;i<len;i++)</p><p>  if(!(str[i]>='a'&&str[i]<='z'||str[i]>='A'&&str[i]<='Z'

28、;||str[i]>='0'&&str[i]<='9'))</p><p><b>  break;</b></p><p>  if(i<len) { printf("\t\t輸入非法字符,請重新輸入:"); continue;}</p><p>  

29、qsort(str,len,sizeof(char),cmp);</p><p>  for(i=0;i<len-1;i++)</p><p>  if(str[i]==str[i+1]) break;</p><p>  if(i<len-1){ printf("\t\t不能有兩個相同的字符,請重新輸入:"); continue;

30、} </p><p><b>  f=true;</b></p><p>  memset(str,0,sizeof(str));</p><p>  //puts(str);</p><p><b>  }</b></p><p><b>  }</b>

31、;</p><p>  void initGraph( ALGraph & G) // 初始化圖 包括 輸入頂點和弧的數(shù)目,并初始化鄰接表的數(shù)組</p><p><b>  {</b></p><p>  int a=-1,b=-1;</p><p>  char str[23];</p>&

32、lt;p>  printf("\t\t輸入頂點個數(shù)和弧的個數(shù):");</p><p><b>  do{</b></p><p>  scanf("%d%d%*c",&a,&b);</p><p>  if(a==-1||b==-1) {</p><p>  

33、gets(str);</p><p>  printf("\t\t輸入不合法,請重新輸入:");</p><p><b>  }</b></p><p>  else break;</p><p>  }while(1);</p><p>  printf("%d %

34、d \n",a,b);</p><p>  G.vexnum=a; G.arcnum=b;</p><p>  Input_V(G.vertices,G.vexnum);</p><p>  for(int i=1;i<=G.vexnum;i++){</p><p>  //scanf("%d",&

35、;(G.vertices[i].data));// 構(gòu)造頂點向量</p><p>  for(int j=1;j<=G.vexnum;j++){//初始化矩陣</p><p>  G.arcs[i][j].adj=MAX;</p><p>  G.arcs[i][j].info=NULL;</p><p><b>  }&

36、lt;/b></p><p>  G.vertices[i].indegree=0;</p><p>  G.vertices[i].outdegree=0;</p><p>  G.vertices[i].firstarc=NULL;</p><p><b>  }</b></p><p>

37、;<b>  }</b></p><p>  void Input(char & v1,char & v2,int &d ,ALGraph & G)</p><p><b>  {</b></p><p>  char str[30];</p><p><b

38、>  int i;</b></p><p>  bool flag=false;</p><p>  memset(str,0,sizeof(str));</p><p>  while(!flag&&gets(str)){</p><p>  int length =strlen(str);</p&g

39、t;<p>  for(i=4;i<length;i++){</p><p>  if(!isalnum(str[0])||!isalnum(str[2])) break;</p><p>  if(str[1]!=' '||str[3]!=' ') break;</p><p>  if(!isdigit(st

40、r[i])) break;</p><p><b>  }</b></p><p>  if(length<5||i<length) { printf("存在不不合法字符或輸入格式錯誤 請重新輸入\n"); continue;}</p><p>  //printf("%d %s\n",le

41、ngth,str);</p><p>  for(i=4,d=0;i<length;i++)</p><p>  d=d*10+str[i]-'0';</p><p>  if((G.kind==1||G.kind==3)&&d!=1) { printf("存在不不合法字符或輸入格式錯誤 請重新輸入\n");

42、 continue;}</p><p>  v1=str[0]; v2=str[2];</p><p>  flag=true;</p><p>  memset(str,0,sizeof(str));</p><p><b>  }</b></p><p><b>  }</b&

43、gt;</p><p>  int CreateDG_DN_UDG_UDN(ALGraph & G){ // 有向圖、有向網(wǎng)、無向圖、無向網(wǎng)以及鄰接矩陣的具體實現(xiàn)</p><p>  VertexType v1,v2;</p><p>  int weight;</p><p>  int flag=G.kind;</p&

44、gt;<p>  initGraph(G);</p><p>  int tem=G.arcnum;</p><p>  printf("每條邊依附的兩個定點及其權(quán)值(>0),無權(quán)輸入1 如 A B 20 和 A B 1 \n");</p><p>  while(tem--){</p><p>

45、  Input(v1,v2,weight,G);</p><p>  int i=LocateVex(G,v1); // 定位v1 v2在數(shù)組中的位置</p><p>  int j=LocateVex(G,v2);</p><p>  G.arcs[i][j].adj=flag==1||flag==3?1:weight; // 建立鄰接矩陣</p>

46、;<p>  if(flag==3||flag==4){</p><p>  G.arcs[j][i].adj=flag==3?1:weight;</p><p><b>  }</b></p><p>  ArcNode * q=(ArcNode *)malloc(sizeof(ArcNode));</p><

47、;p>  q->adj=weight;</p><p>  q->adjvex=j;</p><p>  q->nextarc=NULL;</p><p>  if(G.vertices[i].outdegree==0) </p><p>  G.vertices[i].firstarc=q; </p>

48、<p><b>  else{</b></p><p>  ArcNode *p=G.vertices[i].firstarc;</p><p>  while(p->nextarc)</p><p>  p=p->nextarc;</p><p>  p->nextarc=q;</

49、p><p><b>  }</b></p><p>  if(flag==3||flag==4){ // 此if 語句是為創(chuàng)建無向圖 及 無向網(wǎng)準(zhǔn)備的</p><p>  ArcNode * q=(ArcNode *)malloc(sizeof(ArcNode));</p><p>  q->adj=weigh

50、t;</p><p>  q->adjvex=i;</p><p>  q->nextarc=NULL;</p><p>  if(G.vertices[j].outdegree==0&&G.vertices[j].indegree==0) </p><p>  G.vertices[j].firstarc=q;&

51、lt;/p><p><b>  else{</b></p><p>  ArcNode *p=G.vertices[j].firstarc;</p><p>  while(p->nextarc)</p><p>  p=p->nextarc;</p><p>  p->nextar

52、c=q;</p><p><b>  }</b></p><p><b>  }</b></p><p>  G.vertices[i].outdegree++;</p><p>  if(flag==3||flag==4) G.vertices[j].outdegree++;</p>

53、<p><b>  else </b></p><p>  G.vertices[j].indegree++;</p><p><b>  }</b></p><p><b>  return 0;</b></p><p><b>  }</b>

54、;</p><p>  void VisitDG_DN_UDG_UDN(ALGraph & G,int f){ // 遍歷鄰接表,</p><p>  ArcNode *p;</p><p><b>  if(f){</b></p><p>  printf("\t\t遍歷鄰接表 :\n");

55、</p><p>  for(int i=1;i<=G.vexnum;i++){</p><p>  p=G.vertices[i].firstarc;</p><p>  printf("\t\t與第%d個頂點%c鄰接頂點有:",i,G.vertices[i].data);</p><p><b> 

56、 while(p){</b></p><p>  printf("%c ",G.vertices[p->adjvex].data);</p><p>  p=p->nextarc;</p><p><b>  }</b></p><p>  if(G.kind==3||G.ki

57、nd==4) printf("度數(shù)為 %d ",G.vertices[i].outdegree);</p><p>  else printf("出度為 %d ,入度為 %d ",G.vertices[i].outdegree,G.vertices[i].indegree);</p><p>  printf("\n");<

58、;/p><p><b>  }</b></p><p><b>  }</b></p><p><b>  else{</b></p><p>  printf("遍歷鄰接矩陣 :\n\t\t ");</p><p>  for(in

59、t i=1;i<=G.vexnum;i++)</p><p>  printf("%c %c",G.vertices[i].data,i==G.vexnum?'\n':' ');</p><p>  printf("\t\t─┼────────────────\n");</p><p>

60、;  //printf("─┼───────\n │\n │");</p><p>  for( i=1;i<=G.vexnum;i++){</p><p>  printf("\t\t%c │",G.vertices[i].data);</p><p>  for(int j=1;j<=G.vexnum;

61、j++)</p><p>  //printf("%5d%c",G.arcs[i][j].adj,j==G.vexnum?'\n':' ');</p><p>  if(G.arcs[i][j].adj==MAX) printf("∞ %c",j==G.vexnum?'\n':' '

62、);</p><p>  else printf("%d %c",G.arcs[i][j].adj,j==G.vexnum?'\n':' ');</p><p><b>  }</b></p><p><b>  }</b></p><p>&

63、lt;b>  }</b></p><p>  bool visit[MAX_VERTEX_NUM];//深度優(yōu)先搜索</p><p>  void DFS(ALGraph & G,int i){</p><p>  visit[i]=true; </p><p>  printf("%c ",G

64、.vertices[i].data);</p><p>  ArcNode * p;</p><p>  for(p=G.vertices[i].firstarc;p;p=p->nextarc){</p><p>  if(!visit[p->adjvex]) DFS(G,p->adjvex); </p><p>&

65、lt;b>  }</b></p><p><b>  } </b></p><p>  void DFSTraverse(ALGraph & G){ </p><p><b>  int i;</b></p><p>  printf("\t\t深度優(yōu)先搜索

66、:");</p><p>  for( i=0;i<MAX_VERTEX_NUM;i++)</p><p>  visit[i]=false;</p><p>  for( i=1;i<=G.vexnum;i++)</p><p>  if(!visit[i]) DFS(G,i); </p><p&

67、gt;<b>  }</b></p><p>  queue <int> Q;</p><p>  void BFSTraverse(ALGraph & G) //廣度優(yōu)先搜索</p><p><b>  {</b></p><p><b>  int i,j;<

68、;/b></p><p>  printf("\n\t\t廣度優(yōu)先搜索 :");</p><p>  for( i=0;i<MAX_VERTEX_NUM;i++)</p><p>  visit[i]=false;</p><p>  for(i=1;i<=G.vexnum;i++){</p>

69、<p>  if(!visit[i]){</p><p>  visit[i]=true; </p><p>  printf("%c ",G.vertices[i].data);</p><p>  Q.push(i);</p><p>  while(!Q.empty()){</p>&l

70、t;p>  j=Q.front();</p><p><b>  Q.pop();</b></p><p>  for(ArcNode *w=G.vertices[j].firstarc;w;w=w->nextarc)</p><p>  if(!visit[w->adjvex]){</p><p> 

71、 visit[w->adjvex]=true; </p><p>  printf("%c ",G.vertices[w->adjvex].data);</p><p>  Q.push(w->adjvex);</p><p><b>  }</b></p><p><b>

72、;  }</b></p><p><b>  }</b></p><p><b>  }</b></p><p><b>  }</b></p><p>  void MinSpanTree_PRIM(ALGraph G,VertexType u)// prim算法

73、的最小生成樹</p><p><b>  {</b></p><p>  if(G.kind!=UDN) {printf("沒有最小成樹\n");return;}</p><p>  int i,j,k;</p><p>  int mincost=0;</p><p>  p

74、rintf("\n\t\tprim算法的最小生成樹 :");</p><p>  k=LocateVex(G,u);</p><p>  for(i=1;i<=G.vexnum;i++){</p><p>  closedge[i].data=G.vertices[i].data;</p><p>  closedg

75、e[i].lowcost=G.arcs[k][i].adj;</p><p>  closedge[i].j=k;</p><p><b>  }</b></p><p>  closedge[k].lowcost=0;</p><p>  for(i=1;i<=G.vexnum;i++){</p>

76、<p>  //for(k=1;k<=G.vexnum;k++)</p><p>  //printf("(%d %d) %c",closedge[k].data,closedge[k].lowcost,k==G.vexnum?'\n':' ');</p><p><b>  k=0; </b>

77、</p><p>  for(j=1;j<=G.vexnum;j++){ //選出T的下一個結(jié)點,第k個頂點</p><p>  if(closedge[j].lowcost==0) continue;</p><p>  if(k==0){k=j;continue;}</p><p>  if(closedge[k].lowcos

78、t>closedge[j].lowcost) </p><p><b>  k=j;</b></p><p><b>  }</b></p><p>  //for(int t=1;t<=G.vexnum;t++)</p><p>  //printf("(%d %d %d%

79、c)\t",t,closedge[t].lowcost,closedge[t].j,t==G.vexnum?'\n':' ');</p><p>  if(k)printf("(%c %c %d) ",G.vertices[closedge[k].j].data,G.vertices[k].data,closedge[k].lowcost); //最

80、小生成樹的頂點向量、值、及權(quán)</p><p>  mincost+=closedge[k].lowcost;</p><p>  closedge[k].lowcost=0;</p><p>  for(j=1;j<=G.vexnum;j++)</p><p>  if(G.arcs[j][k].adj<closedge[j].l

81、owcost){</p><p>  closedge[j].data=G.vertices[j].data;</p><p>  closedge[j].lowcost=G.arcs[j][k].adj;</p><p>  closedge[j].j=k;</p><p><b>  }</b></p>

82、<p>  }printf("\n\t\t最小代價和為 :%d\n",mincost);</p><p><b>  }</b></p><p>  int TOpologicalSort(ALGraph & G)//拓撲排序</p><p><b>  {</b></p>

83、;<p>  stack <int> S;</p><p>  int i,j,count=0;</p><p>  int indegree[30];</p><p>  for(i=1;i<=G.vexnum;i++)</p><p>  indegree[i]=G.vertices[i].indegree

84、;</p><p>  if(G.kind==3||G.kind==4) {printf("無向圖不能進行拓撲排序\n");return -1;}</p><p>  printf("\n拓撲排序:");</p><p>  for(i=1;i<=G.vexnum;i++)</p><p>  i

85、f(G.vertices[i].indegree==0)S.push(i);</p><p>  while(!S.empty()){</p><p>  j=S.top(); S.pop();</p><p><b>  count++;</b></p><p>  printf("(%d %c) &quo

86、t;,j,G.vertices[j].data);</p><p>  for(ArcNode *p=G.vertices[j].firstarc;p;p=p->nextarc){</p><p>  int k=p->adjvex;</p><p>  int d=--(G.vertices[k].indegree);</p><p

87、>  if(!d)S.push(k);</p><p><b>  }</b></p><p><b>  }</b></p><p>  for(i=1;i<=G.vexnum;i++)</p><p>  G.vertices[i].indegree=indegree[i];<

88、/p><p>  if(G.vexnum==count){printf("\n"); return 1;}</p><p>  printf("失??!\n");return 0;</p><p><b>  } </b></p><p>  void Choose(ALGraph

89、&G){</p><p>  int choice=G.kind;</p><p>  char str[30];</p><p><b>  do{</b></p><p>  system("cls");</p><p>  printf("\n\n\t\

90、t▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄\n");</p><p>  printf("\t\t▌?wù)堖x擇操作:\t\t\t\t ▌\n");</p><p>  printf("\t\t▌1、用鄰接矩陣遍歷\t4、廣度優(yōu)先搜索\t ▌\n\t\t▌2、用鄰接表遍歷\t5、拓撲排序\t ▌\n");</p><p>

91、;  printf("\t\t▌3、深度優(yōu)先搜索\t6、最小生成樹\t ▌\n\t\t▌7、返回\t\t8、退出程序\t\t ▌\n");</p><p>  printf("\t\t ▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲\n\n");</p><p>  printf("\t\t請輸入你的選擇(1-7):");</p&

92、gt;<p><b>  do{</b></p><p>  memset(str,0,sizeof(str));</p><p>  gets(str);</p><p>  if(strlen(str)>1) choice=-1;</p><p>  else if(str[0]<'

93、;1'||str[0]>'8') choice=-1;</p><p>  else choice=str[0]-'0';</p><p>  if(choice==-1) printf("\t\t輸入不合法,請重新輸入:");</p><p>  else break;</p><

94、;p>  }while(1);</p><p>  switch(choice){</p><p>  case 1: VisitDG_DN_UDG_UDN(G,0); break;</p><p>  case 2: VisitDG_DN_UDG_UDN(G,1); break;</p><p>  case 3: DFSTraver

95、se(G);break;</p><p>  case 4: BFSTraverse(G); break;</p><p>  case 5:TOpologicalSort(G); break;</p><p>  case 6: MinSpanTree_PRIM(G,G.vertices[1].data);break;</p><p>  

96、case 7:return;</p><p>  case 8:exit(0);</p><p><b>  }</b></p><p>  printf("\n\t\t按回車鍵繼續(xù)....."); getchar();</p><p>  }while(1);</p><p>

97、;<b>  }</b></p><p>  void Menu(ALGraph &G){</p><p>  bool f=true;</p><p>  int choice=-1;</p><p>  char str[30];</p><p><b>  do{</

98、b></p><p>  system("cls");</p><p>  printf("\n\n\t\t╔════════════════════╗\n");</p><p>  printf("\t\t║\t\t\t\t\t ║\n");</p><p>  print

99、f("\t\t║\t\t圖的建立與操作\t\t ║\n");</p><p>  printf("\t\t║\t\t\t\t\t ║\n");</p><p>  printf("\t\t╚════════════════════╝\n\n");</p><p>  printf("\t\t請

100、選擇建圖方式:\n");</p><p>  printf("\t\t\t1、有向圖\t2、有向網(wǎng)\n");</p><p>  printf("\t\t\t3、無向圖\t4、無向網(wǎng)\n\t\t\t5、退出\n\n");</p><p>  printf("\t\t請輸入你的選擇(1-5):");

101、</p><p><b>  do{</b></p><p>  memset(str,0,sizeof(str));</p><p>  gets(str);</p><p>  if(strlen(str)>1) choice=-1;</p><p>  else if(str[0

102、]<'0'||str[0]>'9') choice=-1;</p><p>  else choice=str[0]-'0';</p><p>  if(choice<1||choice>5) </p><p>  printf("\t\t你的輸入不合法,請重新輸入(1-5):&quo

103、t;);</p><p><b>  else</b></p><p><b>  break;</b></p><p>  }while(1);</p><p>  if(choice==5) break;</p><p><b>  else{</

104、b></p><p>  G.kind=choice;</p><p>  CreateDG_DN_UDG_UDN(G);</p><p>  system("cls");</p><p>  printf("\n\n\n\n\t\t圖已建立,按回車鍵繼續(xù)其他操作...");</p>

105、<p>  getchar();</p><p>  Choose(G);</p><p><b>  }</b></p><p>  }while(1);</p><p><b>  }</b></p><p>  int main()</p>&

106、lt;p><b>  {</b></p><p>  ALGraph G;</p><p>  printf("");</p><p><b>  Menu(G); </b></p><p><b>  return 0;</b></p>

107、<p><b>  }</b></p><p><b>  七、運行結(jié)果分析</b></p><p>  測試數(shù)據(jù)及運行結(jié)果見以下截圖</p><p>  主界面的建立,可以自由選擇建立圖,輸入數(shù)據(jù)應(yīng)嚴(yán)格按照要求,否則,無法建立 </p><p>  鄰接矩陣的遍歷有邊輸出權(quán)值(對于網(wǎng))

108、或1(對于圖),無邊輸出無窮</p><p>  用鄰接表遍歷,依次輸出每個頂點的臨鄰接點,并輸出本點的出度和入度</p><p>  以下四個截圖分別是深度優(yōu)先搜索、廣度優(yōu)先搜索、拓撲排序和最小生成樹的運行結(jié)果,均用字符表示其遍歷或操作的順序</p><p><b>  其他測試數(shù)據(jù):</b></p><p><

109、b>  3</b></p><p><b>  5 8</b></p><p><b>  ABCDE</b></p><p>  D E 1 C E 1 D C 1 A E 1 B E 1 B A 1 A D 1 B C 1</p><p><b>  2

110、</b></p><p><b>  5 6</b></p><p><b>  12345</b></p><p>  1 2 1 1 3 1 2 3 1 4 5 1 5 2 1 4 3 1</p><p><b>  八、收獲及體會</b></p

111、><p>  在進行這次課程設(shè)計的過程中,我真正學(xué)到了教科書上所沒有或者真正用到了課本上的知識。這樣,既鞏固了舊知識,又掌握了新知識。所以,數(shù)據(jù)結(jié)構(gòu)課程設(shè)計是我們的重中之重,是提高我們專業(yè)知識與實踐相結(jié)合的重要手段。</p><p>  這次課程設(shè)計,對我進行了結(jié)構(gòu)化程序設(shè)計的初步訓(xùn)練,培養(yǎng)了我的數(shù)據(jù)抽象能力。在實際操作過程中,遇到很多問題,通過查書,上網(wǎng)查資料,最后問老師,把問題解決,在這個

112、過程中,把課堂上的知識很好的運用到實際上,還通過解決問題,學(xué)習(xí)到很多課外知識,引導(dǎo)和激發(fā)我對數(shù)據(jù)結(jié)構(gòu)的興趣,同時還要培養(yǎng)我搜索分析信息、查閱幫助文檔、整理經(jīng)驗編寫文檔、合作交流的能力。</p><p>  課程設(shè)計中我遇見了一些難點,比方說 輸入數(shù)據(jù)時錯誤的輸入可能就會讓程序崩潰,經(jīng)過仔細思考,查閱資料,請教同學(xué),最后都圓滿的解決當(dāng)然,這是我收獲比較大一點。除此之外,我覺得一個好程序不僅在于它的功能的實現(xiàn),更重要

溫馨提示

  • 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)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論