中北大學數據結構課程設計說明書

學生姓名:郭燕文學號：1021011720學院:軟件學院專業:軟件工程題目:圖的遍歷和生成樹求解實現成績指導教師尹四清、薛海麗

2011年12月19日設計目的：《數據結構》課程主要介紹最常用的數據結構，闡明各種數據結構內在的邏輯關系，討論其在計算機中的存儲表示，以及在其上進行各種運算時的實現算法，并對算法的效率進行簡單的分析和討論。進行數據結構課程設計要達到以下目的：了解并掌握數據結構與算法的設計方法，具備初步的獨立分析和設計能力；初步掌握軟件開發過程的問題分析、系統設計、程序編碼、測試等基本方法和技能；提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；訓練用系統的觀點和軟件開發一般規范進行軟件開發，培養軟件工作者所應具備的科學的工作方法和作風。2設計內容和要求設計內容：采用合適的存儲結構來創建圖，并實現圖的遍歷；（2）計算圖的最小生成樹，求聯通分量設計要求：（1）先任意創建一個圖；（2)

圖的DFS,BFS的遞歸和非遞歸算法的實現（3)

最小生成樹（兩個算法）的實現，求連通分量的實現（4)

要求用鄰接矩陣、鄰接表、十字鏈表多種結構存儲實現3．本設計所采用的數據結構：本程序是采用鄰接矩陣、鄰接表、十字鏈表等多種結構存儲來實現對圖的存儲。對圖的遍歷分別采用了廣度優先遍歷和深度優先遍歷。4.1詳細設計思想這次課程設計我們主要是應用以前學習的數據結構與面向對象程序設計知識，結合起來才完成了這個程序。因為圖是一種較線形表和樹更為復雜的數據結構。在線形表中，數據元素之間僅有線性關系，每個元素只有一個直接前驅和一個直接后繼，并且在圖形結構中，節點之間的關系可以是任意的，圖中任意兩個數據元素之間都可能相關。因此，本程序是采用鄰接矩陣、鄰接表、十字鏈表等多種結構存儲來實現對圖的存儲。采用鄰接矩陣即為數組表示法，鄰接表和十字鏈表都是圖的一種鏈式存儲結構。對圖的遍歷分別采用了廣度優先遍歷和深度優先遍歷。開始開始創建圖G表存儲圖Ify=’y’NY顯示圖的鄰接矩陣KRUSCAL算法顯示圖的鄰接表深度優先遍歷廣度優先遍歷最小生成樹PRIM輸入字母Ify=’y’結束NY圖的連通分量輸入一個數20134564.3核心代碼#include<iostream>#include<malloc.h>usingnamespacestd;#defineint_max10000#defineinf9999#definemax20//…………鄰接矩陣定義……typedefstructArcCell22{ intadj;char*info;}ArcCell,AdjMatrix[20][20];typedefstruct{charvexs[20];AdjMatrixarcs;intvexnum,arcnum;//有向圖的當前頂點數和弧數}MGraph_L;//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^intlocalvex(MGraph_LG,charv)//返回V的位置{inti=0;while(G.vexs[i]!=v){++i;}returni;}intcreatMGraph_L(MGraph_L&G)//創建圖用鄰接矩陣表示{charv1,v2;inti,j,w;cout<<"…………創建無向圖…………"<<endl<<"請輸入圖G頂點和弧的個數:(46)不包括"<<endl;cin>>G.vexnum>>G.arcnum;for(i=0;i!=G.vexnum;++i){cout<<"輸入頂點"<<i<<endl;cin>>G.vexs[i];}for(i=0;i!=G.vexnum;++i)for(j=0;j!=G.vexnum;++j){G.arcs[i][j].adj=int_max;G.arcs[i][j].info=NULL;}for(intk=0;k!=G.arcnum;++k){cout<<"輸入一條邊依附的頂點和權:(ab3)不包括"<<endl;cin>>v1>>v2>>w;//輸入一條邊依附的兩點及權值i=localvex(G,v1);//確定頂點V1和V2在圖中的位置j=localvex(G,v2);G.arcs[i][j].adj=w;G.arcs[j][i].adj=w;}cout<<"圖G鄰接矩陣創建成功！"<<endl;returnG.vexnum;}voidljjzprint(MGraph_LG){inti,j;for(i=0;i!=G.vexnum;++i){for(j=0;j!=G.vexnum;++j)cout<<G.arcs[i][j].adj<<"";cout<<endl;}}intvisited[max];//訪問標記intwe;typedefstructarcnode//弧結點{intadjvex;//該弧指向的頂點的位置structarcnode*nextarc;//弧尾相同的下一條弧char*info;//該弧信息}arcnode;typedefstructvnode//鄰接鏈表頂點頭接點{chardata;//結點信息arcnode*firstarc;//指向第一條依附該結點的弧的指針}vnode,adjlist;typedefstruct//圖的定義{adjlistvertices[max];intvexnum,arcnum;intkind;}algraph;//…………隊列定義……typedefstructqnode{intdata;structqnode*next;}qnode,*queueptr;typedefstruct{queueptrfront;queueptrrear;}linkqueue;//………………………typedefstructacr{intpre;//弧的一結點intbak;//弧另一結點intweight;//弧的權}edg;intcreatadj(algraph&gra,MGraph_LG)//用鄰接表存儲圖{inti=0,j=0;arcnode*arc,*tem,*p;for(i=0;i!=G.vexnum;++i){gra.vertices[i].data=G.vexs[i];gra.vertices[i].firstarc=NULL;}for(i=0;i!=G.vexnum;++i){for(j=0;j!=G.vexnum;++j){if(gra.vertices[i].firstarc==NULL){if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum){arc=(arcnode*)malloc(sizeof(arcnode));arc->adjvex=j;gra.vertices[i].firstarc=arc;arc->nextarc=NULL;p=arc;++j;while(G.arcs[i][j].adj!=int_max&&j!=G.vexnum){tem=(arcnode*)malloc(sizeof(arcnode));tem->adjvex=j;gra.vertices[i].firstarc=tem;tem->nextarc=arc;arc=tem;++j;}--j;}}else{if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum){arc=(arcnode*)malloc(sizeof(arcnode));arc->adjvex=j;p->nextarc=arc;arc->nextarc=NULL;p=arc;}}}}gra.vexnum=G.vexnum;gra.arcnum=G.arcnum;/*for(i=0;i!=gra.vexnum;++i){arcnode*p;cout<<i<<"";p=gra.vertices[i].firstarc;while(p!=NULL){cout<<p->adjvex;p=p->nextarc;}cout<<endl;}*/cout<<"圖G鄰接表創建成功！"<<endl;return1;}voidadjprint(algraphgra){inti;for(i=0;i!=gra.vexnum;++i){arcnode*p;cout<<i<<"";p=gra.vertices[i].firstarc;while(p!=NULL){cout<<p->adjvex;p=p->nextarc;}cout<<endl;}}intfirstadjvex(algraphgra,vnodev)//返回依附頂點V的第一個點//即以V為尾的第一個結點{if(v.firstarc!=NULL)returnv.firstarc->adjvex;}intnextadjvex(algraphgra,vnodev,intw)//返回依附頂點V的相對于W的下一個頂點{arcnode*p;p=v.firstarc;while(p!=NULL&&p->adjvex!=w){p=p->nextarc;}if(p->adjvex==w&&p->nextarc!=NULL){p=p->nextarc;returnp->adjvex;}if(p->adjvex==w&&p->nextarc==NULL)return-10;}intinitqueue(linkqueue&q)//初始化隊列{q.rear=(queueptr)malloc(sizeof(qnode));q.front=q.rear;if(!q.front)return0;q.front->next=NULL;return1;}intenqueue(linkqueue&q,inte)//入隊{queueptrp;p=(queueptr)malloc(sizeof(qnode));if(!p)return0;p->data=e;p->next=NULL;q.rear->next=p;q.rear=p;return1;}intdequeue(linkqueue&q,int&e)//出隊{queueptrp;if(q.front==q.rear)return0;p=q.front->next;e=p->data;q.front->next=p->next;if(q.rear==p)q.rear=q.front;free(p);return1;}intqueueempty(linkqueueq)//判斷隊為空{if(q.front==q.rear)return1;return0;}voidbfstra(algraphgra)//廣度優先遍歷{inti,e;linkqueueq;for(i=0;i!=gra.vexnum;++i)visited[i]=0;initqueue(q);for(i=0;i!=gra.vexnum;++i)if(!visited[i]){visited[i]=1;cout<<gra.vertices[i].data;enqueue(q,i);while(!queueempty(q)){dequeue(q,e);//cout<<""<<e<<"";for(we=firstadjvex(gra,gra.vertices[e]);we>=0;we=nextadjvex(gra,gra.vertices[e],we)){if(!visited[we]){visited[we]=1;cout<<gra.vertices[we].data;enqueue(q,we);}}}}}intdfs(algraphgra,inti);//聲明DFSintdfstra(algraphgra){inti,j;for(i=0;i!=gra.vexnum;++i){visited[i]=0;}for(j=0;j!=gra.vexnum;++j){if(visited[j]==0)dfs(gra,j);}return0;}intdfs(algraphgra,inti){visited[i]=1;intwe1;//cout<<i<<visited[i]<<endl;cout<<gra.vertices[i].data;//cout<<endl;for(we=firstadjvex(gra,gra.vertices[i]);we>=0;we=nextadjvex(gra,gra.vertices[i],we)){//cout<<we<<visited[we]<<endl;we1=we;//cout<<nextadjvex(gra,gra.vertices[i],we)<<endl;if(visited[we]==0)//cout<<dfs(gra,we);//<<endl;//cout<<i<<we1<<endl;we=we1;//cout<<nextadjvex(gra,gra.vertices[i],we)<<endl;}return12;}intbfstra_fen(algraphgra)//求連通分量{inti,j;for(i=0;i!=gra.vexnum;++i){visited[i]=0;}for(j=0;j!=gra.vexnum;++j){if(visited[j]==0){dfs(gra,j);cout<<endl;}}return0;}typedefstruct{intadjvex;intlowcost;}closedge;/*intminimum(closedge*p);intminispantree(MGraph_LG,charu){intk,j,i;closedgeclosedge_a[20];k=localvex(G,u);//cout<<k<<endl;for(j=0;j!=G.vexnum;++j){if(j!=k){closedge_a[j].adjvex=u;closedge_a[j].lowcost=G.arcs[k][j].adj;}for(i=1;i!=G.vexnum;++i){k=minimum(closedge_a);cout<<k;cout<<closedge_a[k].adjvex<<""<<G.vexs[k]<<endl;closedge_a[k].lowcost=0;for(j=0;j!=G.vexnum;++j)if(G.arcs[k][j].adj<closedge_a[j].lowcost){closedge_a[j].adjvex=G.vexs[k];closedge_a[j].lowcost=G.arcs[k][j].adj;}}}return0;}intminimum(closedge*p){ints=10000;for(;p!=NULL;++p){if(s>p->lowcost)s=p->lowcost;}returns;}*/intprim(intg[][max],intn)//最小生成樹PRIM算法{intlowcost[max],prevex[max];//LOWCOST[]存儲當前集合U分別到剩余結點的最短路徑//prevex[]存儲最短路徑在U中的結點inti,j,k,min;for(i=2;i<=n;i++)//n個頂點，n-1條邊{lowcost[i]=g[1][i];//初始化prevex[i]=1;//頂點未加入到最小生成樹中}lowcost[1]=0;//標志頂點1加入U集合for(i=2;i<=n;i++)//形成n-1條邊的生成樹{min=inf;k=0;for(j=2;j<=n;j++)//尋找滿足邊的一個頂點在U,另一個頂點在V的最小邊if((lowcost[j]<min)&&(lowcost[j]!=0)){min=lowcost[j];k=j;}printf("(%d,%d)%d\t",prevex[k]-1,k-1,min);lowcost[k]=0;//頂點k加入Ufor(j=2;j<=n;j++)//修改由頂點k到其他頂點邊的權值if(g[k][j]<lowcost[j]){lowcost[j]=g[k][j];prevex[j]=k;}printf("\n");}return0;}intacrvisited[100];//kruscal弧標記數組intfind(intacrvisited[],intf){while(acrvisited[f]>0)f=acrvisited[f];returnf;}voidkruscal_arc(MGraph_LG,algraphgra){edgedgs[20];inti,j,k=0;for(i=0;i!=G.vexnum;++i)for(j=i;j!=G.vexnum;++j){if(G.arcs[i][j].adj!=10000){edgs[k].pre=i;edgs[k].bak=j;edgs[k].weight=G.arcs[i][j].adj;++k;}}intx,y,m,n;intbuf,edf;for(i=0;i!=gra.arcnum;++i)acrvisited[i]=0;for(j=0;j!=G.arcnum;++j){m=10000;for(i=0;i!=G.arcnum;++i){if(edgs[i].weight<m){m=edgs[i].weight;x=edgs[i].pre;y=edgs[i].bak;n=i;}}//cout<<x<<y<<m;//cout<<endl;buf=find(acrvisited,x);edf=find(acrvisited,y);//cout<<buf<<""<<edf<<endl;edgs[n].weight=10000;if(buf!=edf){acrvisited[buf]=edf;cout<<"("<<x<<","<<y<<")"<<m;cout<<endl;}}}voidmain(){algraphgra;MGraph_LG;inti,d,g[20][20];chara='a';d=creatMGraph_L(G);creatadj(gra,G);vnodev;cout<<endl<<"……####注意：若該圖為非強連通圖(含有多個連通分量)時"<<endl<<"最小生成樹不存在,則顯示為非法值。"<<endl<<endl;cout<<"…菜單……"<<endl<<endl;cout<<"0、顯示該圖的鄰接矩陣……"<<endl;cout<<"1、顯示該圖的鄰接表……"<<endl;cout<<"2、深度優先遍歷…………"<<endl;cout<<"3、廣度優先遍歷…………"<<endl;cout<<"4、最小生成樹PRIM算法…"<<endl;cout<<"5、最小生成樹KRUSCAL算法………………"<<endl;cout<<"6、該圖的連通分量………"<<endl<<endl;ints;chary='y';while(y='y'){cout<<"請選擇菜單："<<endl;cin>>s;switch(s){case0:cout<<"鄰接矩陣顯示如下："<<endl;ljjzprint(G);break;case1:cout<<"鄰接表顯示如下："<<endl;adjprint(gra);break;case2:cout<<"廣度優先遍歷：";bfstra(gra);cout<<endl;break;case3:for(i=0;i!=