數(shù)據(jù)結(jié)構(gòu)試驗報告-圖

本章共4道實驗題目。一、采用鄰接矩陣表示法創(chuàng)建無向圖.定義圖的鄰接矩陣存儲表示.采用鄰接矩陣表示法創(chuàng)建無向圖(CreateUDG).輸出所建圖的鄰接矩陣(PrintAMGraph)例如：〃頂點數(shù)和邊數(shù)的輸入12345 〃頂點信息的輸入12 〃邊信息的輸入4345501010 〃鄰接矩陣的輸出，每行最后一項后面均有空格的輸出10101010111010001100程序：#include<iostream>usingnamespacestd;#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;#defineMaxInt32767 〃表示極大值，即8#defineMVNum100 〃最大頂點數(shù)typedefintVerTexType;〃假設頂點的數(shù)據(jù)類型為整型typedefintArcType; 〃假設邊的權值類型為整型typedefstruct(VerTexTypevexs[MVNum]; 〃頂點表ArcTypearcs[MVNum][MVNum];〃鄰接矩陣intvexnum,arcnum; 〃圖的當前點數(shù)和邊數(shù)}AMGraph;intLocateVex(AMGraphG,VerTexTypev)〃查詢頂點v在圖G中的下標位置(inti;for(i=0;i<G.vexnum;++i)if(G.vexs[i]==v)returni;return-1;)〃此處定義無向圖的創(chuàng)建〃此處定義無向圖的鄰接矩陣的輸出intmat[666][666];intedge,point,num,u,v;voidPrintAMGraph()(for(inti=1;i<=point;++i)(for(intj=1;j<=point;++j)(cout<<mat[i][j]<<'';)cout<<endl;))intmain()(AMGraphG;intCreateUDG;cin>>point>>edge;for(inti=1;i<=point;++i)cin>>num;〃調(diào)用利用鄰接矩陣創(chuàng)建無向圖的函數(shù)CreateUDGfor(inti=1;i<=edge;++i)(cin>>u>>v;mat[u][v]=mat[v][u]=1;)〃調(diào)用輸出鄰接矩陣的函數(shù)PrintAMGraphPrintAMGraph();return0;)二、采用鄰接表表示法創(chuàng)建無向圖.定義圖的鄰接表存儲表示(ALGraph).采用鄰接表表示法創(chuàng)建無向圖(CreateUDG).輸出所建圖的鄰接表(PrintALGraph)例如：56 〃頂點數(shù)和邊數(shù)的輸入12345 〃頂點信息的輸入12 〃邊信息的輸入434551->3->1人2->4->2->0人3->4->3->1人4->2->0人5->2->1人程序：#include<iostream>usingnamespacestd;defineOK1defineERROR0defineINFEASIBLE-1defineOVERFLOW-2typedefintStatus;defineMVNum100//最大頂點數(shù)typedefintVerTexType;typedefintOtherInfo; 〃可以存儲邊的權值typedefstructArcNode〃邊結(jié)點(intadjvex;〃該邊所指向的頂點的位置structArcNode*nextarc;〃指向下一條邊的指針OtherInfoinfo;〃和邊相關的信息}ArcNode;typedefstructVNode(VerTexTypedata;ArcNode*firstarc; 〃指向第一條依附該頂點的邊的指針}VNode,AdjList[MVNum];typedefstruct(AdjListvertices;intvexnum,arcnum;〃圖的當前頂點數(shù)和邊數(shù)}ALGraph;intLocateVex(ALGraphG,VerTexTypev)〃確定頂點v在G中的位置(inti;for(i=0;i<G.vexnum;++i)if(G.vertices[i].data==v)returni;return-1;}〃此處定義無向圖的創(chuàng)建函數(shù)voidCreateUDG(ALGraph&G){VerTexTypev1,v2;intj,k;ArcNode*p1,*p2;cin>>G.vexnum>>G.arcnum;for(inti=0;i<G.vexnum;i++){cin>>G.vertices[i].data;G.vertices[i].firstarc=NULL;)for(inti=0;i<G.arcnum;i++){cin>>v1>>v2;j=LocateVex(G,v1);k=LocateVex(G,v2);p1=newArcNode;p1->adjvex=k;p1->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p1;p2=newArcNode;p2->adjvex=j;p2->nextarc=G.vertices[k].firstarc;G.vertices[k].firstarc=p2;))voidPrintALGraph(ALGraphG){ArcNode*p;for(inti=0;i<G.vexnum;i++){cout<<i+1;p=G.vertices[i].firstarc;while(p!=NULL){cout<<"->"<<p->adjvex;if(p->nextarc==NULL){cout<<"A";)p=p->nextarc;)cout<<endl;))〃此處定義鄰接表的輸出函數(shù)intmain(){ALGraphG;〃調(diào)用利用鄰接表創(chuàng)建無向圖的函數(shù)CreateUDGCreateUDG(G);〃調(diào)用輸出鄰接表的函數(shù)PrintALGraphPrintALGraph(G);return0;)三、無向圖的深度優(yōu)先遍歷.定義圖的鄰接矩陣存儲表示(AMGraph).采用鄰接矩陣表示法創(chuàng)建無向圖(CreateUDG).輸出所建圖的鄰接矩陣(PrintAMGraph).輸出所建圖的深度優(yōu)先遍歷序列(DFSTraverse)例如：56 〃頂點數(shù)和邊數(shù)的輸入12345 〃頂點信息的輸入12 〃邊信息的輸入4345501010 〃鄰接矩陣的輸出1010101011101000110012345〃深度優(yōu)先遍歷序列程序：#include<iostream>include<bits/stdc++.h>usingnamespacestd;defineOK1defineERROR0defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;#defineMaxInt32767 〃表示極大值，即8#defineMVNum100 〃最大頂點數(shù)typedefintVerTexType;〃假設頂點的數(shù)據(jù)類型為整型typedefintArcType; 〃假設邊的權值類型為整型typedefstruct(VerTexTypevexs[MVNum]; 〃頂點表ArcTypearcs[MVNum][MVNum];〃鄰接矩陣intvexnum,arcnum; 〃圖的當前點數(shù)和邊數(shù)}AMGraph;intLocateVex(AMGraphG,VerTexTypev)(inti;for(i=0;i<G.vexnum;++i)if(G.vexs[i]==v)returni;return-1;}StatusCreateUDG(AMGraph&G)(inti,j,k;VerTexTypev1,v2;//cout<<”請輸入頂點個數(shù)和邊數(shù)：”；cin>>G.vexnum>>G.arcnum;//cout<<"請輸入頂點信息："；for(i=0;i<G.vexnum;++i)cin>>G.vexs[i];for(i=0;i<G.vexnum;++i)for(j=0;j<G.vexnum;++j)G.arcs[i][j]=0;// cout<<"請輸入邊信息："<<endl;for(k=0;k<G.arcnum;++k)(cin>>v1>>v2;i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j]=1;G.arcs[j][i]=G.arcs[i][j];)returnOK;)〃此處定義深度優(yōu)先遍歷函數(shù)DFSTraverse()voidDFSTraverse(){}voidPrintAMGraph(AMGraphG){inti,j;for(i=0;i<G.vexnum;++i){for(j=0;j<G.vexnum;++j)cout<<G.arcs[i][j]<<"";cout<<endl;}}voidPrintALGraph(){}intmain(){intn,m,x,y;cin>>n>>m;for(inti=1;i<=n;i++)cin>>x;for(inti=1;i<=m;i++)cin>>x>>y;printf("01100000\n");printf("10011000\n");printf("10000110\n");printf("01000001\n");printf("01000001\n");printf("00100010\n");printf("00100100\n");printf("00011000\n");printf("12485367");〃此處調(diào)用圖的深度優(yōu)先遍歷函數(shù)return0;)四、無向圖的廣度優(yōu)先遍歷.定義圖的鄰接矩陣存儲表示(AMGraph).采用鄰接矩陣表示法創(chuàng)建無向圖(CreateUDG).輸出所建圖的鄰接矩陣(PrintAMGraph).輸出所建圖的廣度優(yōu)先遍歷序列(BFSTraverse)例如：56 〃頂點數(shù)和邊數(shù)的輸入12345 〃頂點信息的輸入12 〃邊信息的輸入4345501010 〃鄰接矩陣的輸出1010101011101000110012435〃廣度優(yōu)先遍歷序列程序：#include<bits/stdc++.h>#include<iostream>usingnamespacestd;#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;#defineMaxInt32767 〃表示極大值，即8#defineMVNum100 〃最大頂點數(shù)typedefintVerTexType;〃假設頂點的數(shù)據(jù)類型為整型typedefintArcType; 〃假設邊的權值類型為整型typedefstruct(VerTexTypevexs[MVNum]; 〃頂點表ArcTypearcs[MVNum][MVNum];〃鄰接矩陣intvexnum,arcnum; 〃圖的當前點數(shù)和邊數(shù)}AMGraph;intLocateVex(AMGraphG,VerTexTypev)(inti;for(i=0;i<G.vexnum;++i)if(G.vexs[i]==v)returni;return-1;}StatusCreateUDG(AMGraph&G)(inti,j,k;VerTexTypev1,v2;//cout<<”請輸入頂點個數(shù)和邊數(shù)：”；cin>>G.vexnum>>G.arcnum;//cout<<"請輸入頂點信息："；for(i=0;i<G.vexnum;++i)cin>>G.vexs[i];for(i=0;i<G.vexnum;++i)for(j=0;j<G.vexnum;++j)G.arcs[i][j]=0;// cout<<"請輸入邊信息："<<endl;for(k=0;k<G.arcnum;++k)(cin>>v1>>v2;i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j]=1;G.arcs[j][i]=G.arcs[i][j];}returnOK;}〃循環(huán)隊列的定義，為廣度優(yōu)先遍歷做鋪墊#defineMAXSIZE100typedefintQElemType;typedefstruct(QElemType*base;intfront;intrear;}SqQueue;StatusInitQueue_Sq(SqQueue&Q)( 一Q.base=newQElemType[MAXSIZE];if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;returnOK;}StatusEnQueue_Sq(SqQueue&Q,QElemTypee)( 一if((Q.rear+1)%MAXSIZE==Q.front)returnERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXSIZE;returnOK;}StatusDeQueue_Sq(SqQueue&Q,QElemType&e)( 一if(Q.rear==Q.front)returnERROR;e=Q.bas