圖的基本操作

哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院實驗報告課程名稱：數(shù)據(jù)結(jié)構(gòu)課程類型：必修實驗工程名稱：第三次實驗實驗題目：圖的根本操作班級：10803102學(xué)號：1080310225 姓名：陳虞付設(shè)計成績報告成績指導(dǎo)老師實驗?zāi)康膶崿F(xiàn)有向圖、無向圖的根本操作。實驗要求及實驗環(huán)境實驗要求：實現(xiàn)有向圖、無向圖的根本操作〔建立連接表，鄰接矩陣，深度優(yōu)先搜索， 廣度優(yōu)先搜索等〕。實驗環(huán)境：windows平臺、code：：blocks集成開發(fā)環(huán)境。三、設(shè)計思想〔本程序中的用到的所有數(shù)據(jù)類型的定義，主程序的流程圖及各程序模塊之間的調(diào)用關(guān)系〕1．邏輯設(shè)計主程序的流程：定義鄰接表gl、bool型數(shù)組visited[]。程序開始時，先初始化鄰 接表，然后提示圖是否有向，輸入選擇，調(diào)用MainMenue()函數(shù) 到主菜單的選擇界面，根據(jù)輸入的選擇調(diào)用相應(yīng)的函數(shù)、實現(xiàn)相 應(yīng)的邏輯功能。物理設(shè)計程序功能：以文件方式方式輸入的無/有向圖，實現(xiàn)無/有向圖的鄰接表、鄰接矩 陣求解及對圖的深度優(yōu)先遍歷、廣度優(yōu)先遍歷操作。輸入：將要求解的無/有向圖按規(guī)那么輸入對應(yīng)的文件輸出：通過主菜單的選擇，按需實現(xiàn)對圖的各種操作，顯示結(jié)果并保存到相應(yīng)的 文件中。 源程序說明： 頭文件：graphics.h 函數(shù)實現(xiàn)：graphics.cpp 主函數(shù)：main.cpp存放的文件說明： 無向圖：graphics1.txt 存放格式為第一行存放圖的頂點數(shù)n，邊數(shù)b，下面每行存放兩個相鄰頂點：Vi,Vj 有向圖：graphics2.txt 存放格式為第一行存放圖的頂點數(shù)n，下面每行存放兩個相鄰頂點Vi-->Vj：Vi,Vj 無向圖鄰接表：adjlist1.txt 有向圖鄰接表：adjlist2.txt 無向圖鄰接矩陣：adjmatrix1.txt 有向圖鄰接矩陣：adjmatrix2.txt所有抽象數(shù)據(jù)類型的定義如下：//定義鄰接表的邊節(jié)點類型structEdgeNode{intadjvex;EdgeNode*next;};//定義鄰接表類型typedefEdgeNode**ADJLIST;各模塊的具體實現(xiàn)程序是：Graphicscpp各模塊的的功能及參數(shù)說明：graphics.h如下：//對圖操作的主菜單voidMainMenue();//初始化鄰接表voidInitialAdjList(ADJLIST&GL,intn);//以文件方式輸入圖//boolInputGraphics();//建立圖的鄰接表voidCreatAdjList(ADJLIST&GL,int&n,intm);//建立圖的鄰接矩陣voidCreatAdjMatrix(ADJLIST&GL,int&n,intm);//從初始點出發(fā)深度優(yōu)先搜索由鄰接表GL表示的圖voidDFSAdjList(ADJLISTGL,bool*&visited,inti,intn);//從初始點出發(fā)廣度優(yōu)先搜索由鄰接表GL表示的圖voidBFSAdjList(ADJLISTGL,bool*&visited,inti,intn);測試結(jié)果圖是否有向的選擇、主菜單界面：建立鄰接表的測試結(jié)果：建立鄰接矩陣的測試結(jié)果：廣度優(yōu)先搜索的測試結(jié)果：深度優(yōu)先搜索的測試結(jié)果：退出界面：系統(tǒng)缺乏與經(jīng)驗體會系統(tǒng)缺乏：異常處理不夠健壯，不能夠用很形象的方式打印圖的直觀圖。經(jīng)驗體會：通過這次實驗使我對圖有了比擬深入的了解，熟悉了圖的根本操 作，同時也感受到了看似簡單的程序?qū)崿F(xiàn)，真正做起來很費力，有很多的困難需要去克服。附錄：源代碼〔帶注釋〕graphics.h源代碼如下：#ifndefGRAPHICS_H#defineGRAPHICS_HstructEdgeNode{intadjvex;EdgeNode*next;};//定義鄰接表的邊節(jié)點類型//定義鄰接表類型typedefEdgeNode**ADJLIST;//對圖操作的主菜單voidMainMenue();//初始化鄰接表voidInitialAdjList(ADJLIST&GL,intn);//以文件方式輸入圖//boolInputGraphics();//建立圖的鄰接表voidCreatAdjList(ADJLIST&GL,int&n,intm);//建立圖的鄰接矩陣voidCreatAdjMatrix(ADJLIST&GL,int&n,intm);//從初始點出發(fā)深度優(yōu)先搜索由鄰接表GL表示的圖voidDFSAdjList(ADJLISTGL,bool*&visited,inti,intn);//從初始點出發(fā)廣度優(yōu)先搜索由鄰接表GL表示的圖voidBFSAdjList(ADJLISTGL,bool*&visited,inti,intn);#endifGraphics.cpp源代碼如下：#include<iostream>#include<stdio.h>#include<stdlib.h>#include<stdio.h>#include"graphics.h"#defineMAX_SIZE100usingnamespacestd;//局部函數(shù)原型聲明voidCheck(intn,int&i,int&j);voidInitialAdjList(ADJLIST&GL,intn);//全局變量,控制遞歸函數(shù)中提示符的輸出intflag=1;voidMainMenue()//對圖操作的主菜單{cout<<"\n***************************************"<<endl;cout<<"****"<<endl;cout<<"**1.建立圖的鄰接表。**"<<endl;cout<<"**2.建立圖的鄰接矩陣。**"<<endl;cout<<"**3.深度優(yōu)先遍歷圖。**"<<endl;cout<<"**4.廣度優(yōu)先遍歷圖。**"<<endl;cout<<"**5.退出。**"<<endl;cout<<"****"<<endl;cout<<"************fulme********************"<<endl;}/*EndofMainMuenue()*/voidInitialAdjList(ADJLIST&GL,intn)//初始化圖的鄰接表{GL=newEdgeNode*[n];for(inti=1;i<=n;i++)GL[i]=NULL;}/*EndofInitialAdjlist()*/voidCreatAdjList(ADJLIST&GL,int&n,intm)//建立圖的鄰接表{FILE*in1;FILE*in2;FILE*out1;FILE*out2;inti;intj;intk;intb;charch;intflag=0;if(m==0)//建立無向圖的鄰接表{if((in1=fopen("graphics1.txt","rb"))==NULL){cout<<"翻開graphics1.txt失??！"<<endl;exit(1);}if((out1=fopen("adjlist1.txt","wb"))==NULL){cout<<"翻開adjlist1.txt失??！"<<endl;flag=1;}//讀入頂點的個數(shù),",",邊數(shù)fscanf(in1,"%d",&n);fscanf(in1,"%c",&ch);fscanf(in1,"%d",&b);for(k=0;k<b;k++){fscanf(in1,"%d",&i);fscanf(in1,"%c",&ch);fscanf(in1,"%d",&j);Check(n,i,j);//向序號為i的單鏈表的表頭插入一個邊結(jié)點EdgeNode*p=newEdgeNode;p->adjvex=j;p->next=GL[i];GL[i]=p;//向序號為j的單鏈表的表頭插入一個節(jié)點p=newEdgeNode;p->adjvex=i;p->next=GL[j];GL[j]=p;}//輸出鄰接表,并保存到adjlist1.txt中cout<<endl<<"\n====================="<<endl;cout<<"無向圖的鄰接表為："<<endl;for(i=1;i<=n;i++){EdgeNode*p=GL[i];cout<<i-1<<"|"<<"V"<<i;fprintf(out1,"%c",'V');fprintf(out1,"%d",i);for(p=GL[i];p!=NULL;p=p->next){cout<<"|-|->|"<<p->adjvex;fprintf(out1,"%s","|-|->|");fprintf(out1,"%d",p->adjvex);}cout<<"|^|"<<endl;fprintf(out1,"%s","|^|");fprintf(out1,"\r\n");}if(flag)cout<<"無向圖的鄰接表已保存到adjlist1.txt中"<<endl;fclose(in1);fclose(out1);}elseif(m==1)//建立有向圖的鄰接表{if((in2=fopen("graphics2.txt","rb"))==NULL){cout<<"翻開graphics2.txt失??！"<<endl;exit(1);}if((out2=fopen("adjlist2.txt","wb"))==NULL){cout<<"翻開adjlist2.txt失??！"<<endl;flag=1;}//讀入頂點的個數(shù),",",邊數(shù)fscanf(in2,"%d",&n);fscanf(in2,"%c",&ch);fscanf(in2,"%d",&b);for(k=0;k<b;k++){fscanf(in2,"%d",&i);fscanf(in2,"%c",&ch);fscanf(in2,"%d",&j);Check(n,i,j);//向序列號為i的表頭插入一個邊節(jié)點EdgeNode*p=newEdgeNode;p->adjvex=j;p->next=GL[i];GL[i]=p;}//輸出圖的鄰接表cout<<endl<<"\n====================="<<endl;cout<<"有向圖的鄰接表為："<<endl;for(i=1;i<=n;i++){EdgeNode*p=GL[i];cout<<i-1<<"|"<<"V"<<i;fprintf(out2,"%c",'V');fprintf(out2,"%d",i);for(p=GL[i];p!=NULL;p=p->next){cout<<"|-|->|"<<p->adjvex;fprintf(out2,"%s","|-|->|");fprintf(out2,"%d",p->adjvex);}cout<<"|^|"<<endl;fprintf(out2,"%s","|^|");fprintf(out2,"\r\n");}if(flag)cout<<"有向圖的鄰接表已保存到adjlist2.txt"<<endl;fclose(in2);fclose(out2);}}/*EndofCreatAdjList()*/voidCreatAdjMatrix(ADJLIST&GL,int&n,intm)//建立圖的鄰接矩陣{intmatrix[MAX_SIZE+1][MAX_SIZE+1];FILE*in1;FILE*in2;FILE*out1;FILE*out2;inti;intj;intk;intb;charch;intflag=0;//初始化圖的鄰接矩陣for(i=1;i<=MAX_SIZE;i++){for(j=1;j<=MAX_SIZE;j++){matrix[i][j]=0;}}if(m==0)//建立無向圖的鄰接矩陣{if((in1=fopen("graphics1.txt","rb"))==NULL){cout<<"翻開graphics1.txt失??！"<<endl;exit(1);}if((out1=fopen("adjlmatrix1.txt","wb"))==NULL){cout<<"翻開adjmatrix1.txt失??！"<<endl;flag=1;}//讀入頂點的個數(shù),",",邊數(shù)fscanf(in1,"%d",&n);fscanf(in1,"%c",&ch);fscanf(in1,"%d",&b);for(k=0;k<b;k++){fscanf(in1,"%d",&i);fscanf(in1,"%c",&ch);fscanf(in1,"%d",&j);Check(n,i,j);matrix[i][j]=matrix[j][i]=1;}for(i=1;i<=b;i++){for(j=1;j<=n;j++){cout<<matrix[i][j]<<'';fprintf(out1,"%d",matrix[i][j]);}cout<<endl;fprintf(out1,"\r\n");}cout<<"無向圖的鄰接矩陣已保存到adjmatrix1.txt中！"<<endl;}elseif(m==1)//建立有向圖的鄰接矩陣{if((in2=fopen("graphics2.txt","rb"))==NULL){cout<<"翻開graphics2.txt失??！"<<endl;exit(1);}if((out2=fopen("adjmatrix2.txt","wb"))==NULL){cout<<"翻開adjmatrix2.txt失??！"<<endl;flag=1;}//讀入頂點的個數(shù),",",邊數(shù)fscanf(in2,"%d",&n);fscanf(in1,"%c",&ch);fscanf(in1,"%d",&b);for(k=1;k<=b;k++){fscanf(in2,"%d",&i);fscanf(in2,"%c",&ch);fscanf(in2,"%d",&j);Check(n,i,j);matrix[i][j]=1;}for(i=1;i<=b;i++){for(j=1;j<=n;j++){cout<<matrix[i][j]<<'';fprintf(out2,"%d",matrix[i][j]);}cout<<endl;fprintf(out2,"\r\n");}cout<<"有向圖已保存到adjmatrix2.txt中！"<<endl;}}/*EndofCreatAdjMatrix()*/voidDFSAdjList(ADJLISTGL,bool*&visited,inti,intn)//從初始點出發(fā)遞歸深度優(yōu)先搜索鄰接表GL表示的圖{if(flag){flag=0;cout<<"\n================================="<<endl;cout<<"\n圖的深度優(yōu)先遍歷序列："<<endl;}cout<<i<<'';visited[i]=true;EdgeNode*p=GL[i];while(p!=NULL){intj=p->adjvex;//j為Vi的一個鄰接點的序號if(!visited[j])DFSAdjList(GL,visited,j,n);p=p->next;}}/*EndofDFSAdjList()*/voidBFSAdjList(ADJLISTGL,bool*&visited,inti,intn)//從初始點開始廣度優(yōu)先搜索鄰接表GL表示的圖{intj;constintMaxLength=100;//定義一個隊列q,其元素類型為整型intq[MaxLength]={0};//定義隊首和對尾指針intfront=0,rear=0;cout<<"\n================================="<<endl;cout<<"\n圖的廣度優(yōu)先遍歷序列："<<endl;for(j=1;j<=n;j++)visited[j]=false;cout<<i<<'';//訪問Vivisited[i]=true;q[++rear]=i;while(front!=rear)//當(dāng)隊列非空時進行循環(huán)處理{//刪除隊首元素，第一次執(zhí)行時k的值為ifront=(front+1)%MaxLength;intk=q[front];//取鄰接表的表頭指針EdgeNode*p=GL[k];while(p!=NULL)//依次搜索Vk的每個節(jié)點{//Vj為Vk的一個鄰接節(jié)點intj=p->adjvex;if(!visited[j]){cout<<j<<'';visited[j]=true;rear=(rear+1)%MaxLength;q[rear]=j;}p=p->next;}}cout<<endl;}/*EndofBFSAdjList()*/voidCheck(intn,int&i,in