數(shù)據(jù)結(jié)構(gòu)課設(shè) 2

參考文獻(xiàn)[1]嚴(yán)蔚敏吳偉民，數(shù)據(jù)結(jié)構(gòu)（C語言版）［M］.北京：清華大學(xué)出版社，2006[2]張千帆，數(shù)據(jù)結(jié)構(gòu)與算法（C語言實(shí)現(xiàn)）[M].北京：科學(xué)出版社，2009[3]呂國英，算法設(shè)計(jì)與分析[M].北京：清華大學(xué)出版社，2006[4]徐寶文李志，C程序設(shè)計(jì)語言[M].北京：機(jī)械工業(yè)出版社，2004[5]張長海陳娟，C程序設(shè)計(jì)語言[M].北京：高等教育出版社，2004沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告附錄#include<stdio.h>#include<string.h>#include<stdlib.h>typedefstructnode/*構(gòu)造一個(gè)結(jié)構(gòu)體，兩個(gè)城市可以看成起點(diǎn)和終點(diǎn)，之間的道路可以看成一個(gè)邊*/{ intst;/*起點(diǎn)*/ inted;/*終點(diǎn)*/ intdis;/*距離*/}node;nodep[1000],temp; /*p記錄城市信息*/intpre[1000],rank[1000];/*用于判斷是否構(gòu)成回路*/intn=0,a[100][100];/*n表示城市個(gè)數(shù)，a[][]記錄城市間權(quán)值*/intmenu()/*菜單函數(shù)*/{ intm; printf("求最小生成樹\n"); printf("________________________________\n\n"); printf("1輸入城市之間的信息\n"); printf("2判斷是否能構(gòu)成一個(gè)最小生成樹\n"); printf("3遍歷所有城市生成最小生成樹\n"); printf("4退出\n"); printf("________________________________\n\n"); printf("請(qǐng)輸入所選功能--4\n"); scanf("%d",&m); returnm;}/*下面三個(gè)函數(shù)作用是檢驗(yàn)當(dāng)一條邊添加進(jìn)去，是否會(huì)產(chǎn)生回路*/voidset(intx)/*初始化*/{ pre[x]=x; rank[x]=0;}intfind(intx)/*找到這個(gè)點(diǎn)的祖先*/{ if(x!=pre[x])pre[x]=find(pre[x]); returnpre[x];}voidUnion(intx,inty)/*將這兩個(gè)添加到一個(gè)集合里去*/{ x=find(x); y=find(y); if(rank[x]>=rank[y]) { pre[y]=x; rank[x]++;} elsepre[y]=x; }voidKruskal() { intans=0,i,j,k=0; /*ans用來記錄生成最小樹的權(quán)總值*/ intindex; intcount=0; /*記錄打印邊的條數(shù)*/ for(i=1;i<=n;i++)/*初始化數(shù)組pre[x],rank[x]*/ set(i); for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { p[++k].st=i; p[k].ed=j; p[k].dis=a[i][j];/*先把所有城市之間的路段看成一個(gè)邊*/ } } for(i=1;i<=k;i++) /*把所有的邊按從小到大進(jìn)行排序*/ { index=i; for(j=i+1;j<=k;j++)if(p[j].dis<p[index].dis)index=j; temp=p[index]; p[index]=p[i]; p[i]=temp; } for(i=1;i<=k;i++) { if(find(p[i].st)!=find(p[i].ed))/*如果這兩點(diǎn)連接在一起不構(gòu)成一個(gè)回路，則執(zhí)行下面操作*/ { printf("\t第%d條路段為：%d--%d,權(quán)值為%d\n",++count,p[i].st,p[i].ed,p[i].dis);/*將這條邊的起點(diǎn)、終點(diǎn)打印出來*/ ans+=p[i].dis; /*說明這條路段要用*/ Union(p[i].st,p[i].ed); } } printf("\t遍歷所有城市得到最小生成樹的代價(jià)為:%d\n\n",ans); }voidcreate() /*輸入城市信息*/ { inti,j; if(n!=0) { charstr[100]; printf("是否要確定輸入新的城市之間的信息?(y/n)?\n"); scanf("%s",str); if(strcmp(str,"n")==0) return; } printf("請(qǐng)輸入城市的個(gè)數(shù):\n"); scanf("%d",&n); printf("輸入%d個(gè)城市的鄰接矩陣:\n",n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) scanf("%d",&a[i][j]); } }voiddisplay() /*顯示生成的最小生成樹*/ { if(n==0) { printf("這里沒有城市之間的信息\n"); return; } printf("遍歷所有城市得到最小生成樹為：\n\n\n"); Kruskal(); }voidjudge()/*判斷是否能夠生成最小生成樹*/ { intclose[100],low[100],i,j,ans=0;/*close[j]表示離j最近的頂點(diǎn)，low[j]表示離j最短的距離*/ intuse[100]; use[1]=1; for(i=2;i<=n;i++) {low[i]=a[1][i];/*初始化*/close[i]=1;use[i]=0; } for(i=1;i<n;i++) { intmin=100000000,k=0; for(j=2;j<=n;j++) { if(use[j]==0&&min>low[j])/*找到最小的low[]值，并記錄*/ { min=low[j]; k=j; } } for(j=2;j<=n;j++) { if(use[j]==0&&low[j]>a[k][j]) { low[j]=a[k][j];/*修改low[]值和close[]值*/ close[j]=k; }} ans+=a[close[k]][k]; } if(ans>=100000000) printf("不能構(gòu)成最小生成樹\n");else printf("能構(gòu)成最小生成樹\n"); }intmain()/*主函數(shù)*/{while(1){switch(menu()){case1:create();break;/*輸入城市信息*/case2:judge();break;/*判斷是否能夠生成最小生成樹*/case3:display();break;/*顯示生成的最小生成樹*/case4:exit(0);}}return0;} 課程設(shè)計(jì)總結(jié)：通過兩周的數(shù)據(jù)結(jié)構(gòu)課程實(shí)訓(xùn)，我不僅對(duì)圖的概念有了一個(gè)新的認(rèn)識(shí)，而且對(duì)算法和C語言有了更深的理解，在學(xué)習(xí)離散數(shù)學(xué)的時(shí)候，總覺得圖是很抽象的東西，但是在學(xué)習(xí)了《數(shù)據(jù)結(jié)構(gòu)》這門課后，我慢慢地體會(huì)到了其中的奧妙，圖能夠在計(jì)算機(jī)中存在，首先要捕捉他有哪些具體化、數(shù)字化的信息，比如說權(quán)值、頂點(diǎn)個(gè)數(shù)等，這也是說明了想要把生活中的信息轉(zhuǎn)化成到計(jì)算機(jī)中必須用數(shù)字來完整的構(gòu)成一個(gè)信息庫，而圖的存在，又涉及到了頂點(diǎn)之間的聯(lián)系，圖分為有向圖和無向圖，而無向圖又是有向圖在權(quán)值雙向相等下的一種特例。在這次求可使構(gòu)成n個(gè)城市的最小生成樹的程序設(shè)計(jì)中，我采用了a[i][j]數(shù)組利用鄰接矩陣方式來儲(chǔ)存城市與城市