綜合性實驗報告離散數(shù)學(xué)

離散實驗課程——實驗報告專業(yè)：計算機(jī)科學(xué)與技術(shù)班級：計科096姓名：杜曉甜，毛亞瓊，莫金雪，王佳星學(xué)號：2009081603（杜曉甜）,2009081613（毛亞瓊）,2009081614（莫金雪）,2009081621（王佳星）指導(dǎo)教師簽名：實驗成績：實驗日期：2010-12-任課教師：王波一、實驗?zāi)康模?．熟悉Visualstudio6.0集成開發(fā)環(huán)境；2..求出加權(quán)圖的最小生成樹。實驗方案設(shè)計二、描述問題：1、設(shè)計思想:①存儲結(jié)構(gòu)：結(jié)構(gòu)存儲。②主要算法思想：設(shè)所給定無向連通加權(quán)圖具有n個結(jié)點(diǎn)，m條邊，首先，將各條邊的權(quán)按從小到大的順序排序。然后依次將這些邊按所給圖的結(jié)構(gòu)放到生成樹中去。如果在放置某一條邊時，使得生成樹形成回路，則刪除這條邊。這樣，直至生成樹具有n-1條邊時，我們所得到的就是一棵最小生成樹。③流程圖：三、實驗結(jié)果：①運(yùn)行結(jié)果：②源程序：#include<iostream.h>structarc{ intx,y,w;};arce[100];intrank[100];intfather[100];intcmp(constvoid*a,constvoid*b){if((*(arc*)a).w==(*(arc*)b).w){return(*(arc*)a).x-(*(arc*)b).x;}return(*(arc*)a).w-(*(arc*)b).w;}intFindSet(intx){if(x!=father[x]){father[x]=FindSet(father[x]);}returnfather[x];}voidUnion(intx,inty,intw){if(x==y)return; if(rank[x]>rank[y]){father[y]=x;}else{ if(rank[x]==rank[y]){rank[y]++;}father[x]=y;}}intmain(){intn;intx,y;charchx,chy,cha,chb,ch;while(n){ cin>>n for(inti=0;i<n;i++) {while(cin>>cha) {if(cha!='') {chx=cha; break; } } while(cin>>chb) {if(chb!='') {chy=chb; break; } } cin>>e[i].w; e[i].x=chx-'A'; e[i].y=chy-'A'; father[i]=i; rank[i]=0; } cout<<"最小生成樹為："<<endl; qsort(e,n,sizeof(arc),cmp); for(i=0;i<n;i++) {x=FindSet(e[i].x); y=FindSet(e[i].y); if(x!=y) {printf("%c-%c:%d\n",e[i].x+'A',e[i].y+'A',e[i].w); Union(x,y,e[i].w);} } cout<<"繼續(xù)請輸入Y，退出請輸入N。"<<endl; cin>>ch; if(ch=='N') break; if(ch=='Y') cout<<"請輸入邊的數(shù)目:"<<endl;}return0; }四、實驗心得體會：試驗在調(diào)試過程中，有些細(xì)節(jié)錯誤，鍛煉了細(xì)心和耐心，同時，在編程的過程中，遇