数据结构-实验3-图形结构及其应用

哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构与算法课程类型：必修实验项目名称：图形结构及其应用实验题目：图型结构的建立与遍历设计成绩报告成绩指导老师

目录：目录： 2一、实验目的 3二、实验要求及实验环境 31.实验内容： 32.实验要求： 33.实验环境 3三、设计思想 41．逻辑设计 4(1)邻接矩阵 4(2)邻接表 4(3)队列 5(4)队列堆栈 52．物理设计 6(1)数据读入 6(2)广度优先搜索 9(3)深度优先搜索——递归实现 12(4)深度优先搜索——非递归实现 14四、测试结果 17初始化与图的读入 17展示邻接表读入结果 17展示邻接矩阵读入结果 18初始提示 18提示输入指令： 18非法输入 19广度优先搜索 19深度优先搜索：二层选择 19-递归深度优先搜索 20-非递归深度优先搜索 20展示：二层选择 20-展示邻接表读入结果（同前） 20-展示邻接矩阵读入结果（同前） 20退出及退出确认 21五、系统不足与经验体会 21六、附录： 21源代码：main.cpp 21输入 21输出 21

一、实验目的通过实现图形结构，掌握逻辑结构、储存结构及其应用。二、实验要求及实验环境1.实验内容：树型结构的建立与遍历：图的遍历（搜索）算法是图型结构算法的基础，本实验要求编写程序演示图的存储结构的建立和遍历（搜索）过程。2.实验要求：(1)能够建立（有向和无向）图的邻接矩阵和邻接表存储结构(2)能够在邻接矩阵和邻接表存储结构上对（有向和无向）图进行深度优先（递归和非递归都要求）和广度优先搜索(3)能够存储和显示相应的搜索结果（深度优先或广度优先生成森林（或生成树）、深度优先或广度优先序列和编号）(4)以文件形式输入图的顶点和边，并显示相应的结果。要求顶点不少于10个，边不少于13个(5)软件功能结构安排合理，界面友好，便于使用3.实验环境MicrosoftWindows7,Code：：Blocks10.05

三、设计思想1．逻辑设计(1)邻接矩阵一个|V|×|V|的二维数组AM，满足：AM[i][j]= 1，<i,j>是有向图的边 0，<i,j>不是有向图的边(2)邻接表数据成员：00NextRead1NextRead2NextRead……NumbNextNumbNextRead：阅读标记，表明一个单元是否已读Next：指针。从邻接表中的单元作为头节点，借助指针各自建立链表，每个链表内头节点以外的节点即头节点的可达节点Numb：节点的序号基本操作：插入边：对图中的新有向边<i,j>，令i,节点对应链表插入一个j广度优先搜索深度优先搜索（递归）深度优先搜索（非递归）(3)队列数据数据数据数据数据…………头结点数据成员：头结点：指向队首，以方便操作。基本操作：入队：将一个元素插入队首出队：从队尾取出一个元素(4)队列堆栈头结点头结点数据数据数据…………数据数据数据数据…………数据数据数据数据…………数据数据数据数据…………头结点头结点…………数据成员：头结点：每个头结点指向一个队列，只有堆栈顶层的头节点对应的队列才能进行出队、入队操作。基本操作：入栈：头结点压入堆栈出栈：弹出头节点，对头节点对应队列进行操作2．物理设计(1)数据读入有向图以边序列的形式从文件输入，共有17个顶点，30条边：I.邻接表单元：邻接表的基本单位。每个单位包含结点序号和下一单元的指针。邻接表：包含一个单元数组和布尔数组。单元数组中，每个单元代表单元序号对应的结点；每个单元都是一个链表的表头；这一链表储存的是头结点可到达的结点。布尔数组中，每个元素代表其序号对应的结点，用于记录每个结点是否已被读取。操作——增加边：对新的有向边<a,b>，将b插入邻接表中a作为头结点的链表。II.邻接矩阵由于只是一个二维数组，因此其内容可在程序内直接调用、修改。需要进行初始化。III.读入函数为了方便，本程序同时将图读入邻接矩阵和邻接表。

(2)广度优先搜索I.邻接表上的广度优先搜索由于广度优先搜索要多次发起搜索，所以采用主从函数形式：Master：对布尔数组和搜索顺序数组进行初始化，并调用Servant进行广度优先搜索。对每个未被从函数访问的结点，调用从函数，以其为根结点进行广度优先搜索。把广度优先搜索结果输出到文件。

Servant：以输入结点为根结点，进行广度优先搜索。将输入结点标记为已读，同时建立队列。建立队列，以根据根结点为最初元素，每次出队一个元素，把这一结点可达而又未读过的结点添加到队列中，如此循环，直到队列清空。

II.邻接矩阵上的广度优先搜索沿用主从函数形式。原理类似。区别主要在于，每次读取根结点的可达点，依据的是邻接矩阵。(3)深度优先搜索——递归实现I.邻接表实现Master：初始化相关记录数组，并启动从函数。Servant：II.邻接矩阵实现Master：Servant：(4)深度优先搜索——非递归实现I.邻接表实现此处不使用真正的堆栈进行实现，而仅仅建立一个队列头结点数组。对每个未被读取的结点，建立一个队列头结点“栈”，而将结点加入栈最底层的头节点对应的队列，然后开始下列循环：从栈最上层的头节点对应的队列中，取出队尾元素，并将向栈中压入一个新的队列头结点，将取出的其所有可达点加入队列中；如果发现队列已空而栈未空，则可以弹出栈顶队列头结点，从队列中取出一个元素，继续进行上述操作；如果队列、栈都已空，结束循环。II.邻接矩阵实现原理与邻接表类似，只是读取数据时利用的是邻接矩阵而非邻接表。四、测试结果初始化与图的读入展示邻接表读入结果展示邻接矩阵读入结果（节点个数过多，而窗口无法拉宽，故形成如此效果）初始提示提示输入指令：非法输入广度优先搜索深度优先搜索：二层选择-递归深度优先搜索-非递归深度优先搜索展示：二层选择-展示邻接表读入结果（同前）-展示邻接矩阵读入结果（同前）退出及退出确认五、系统不足与经验体会1.未建立图的生成树与生成森林；2.输出中，广度优先搜索队列、深度优先搜索队列（递归法）都没有体现图中存在两个连通分量；3.未实现对有向图的处理，事实上，对任意有向图，只要将每一条无向边分别用相反的两条有向边替换，就可以把有向图转换为无向图；4.运行程序时必须预先知道有向图图的节点、有向边的数目。六、附录：源代码：main.cpp输入原图：Graph.txt输出图的矩阵储存：AjMatrix.txt图的邻接链表储存：AjList.txt广度优先搜索列表：ALBFSList.txt深度优先搜索列表（递归方式）：ALDFSRList.txt深度优先搜索列表（非递归方式）：ALDFSE.txt#include<iostream>#include<fstream>usingnamespacestd;constintV_CARD=17;constintE_CARD=30;typedefintindx;structALUnit{indxnumb;ALUnit*next;};classAjList{public:AjList(){indxi=0;for(i=0;i<V_CARD;i++){unit[i].numb=0;unit[i].next=NULL;read[i]=0;}};~AjList(){indxi=0;ALUnit*CurrUnit=NULL,*NextUnit=NULL;for(i=0;i<V_CARD;i++){CurrUnit=unit[i].next;delete&unit[i];while(CurrUnit!=NULL){NextUnit=CurrUnit->next;deleteCurrUnit;CurrUnit=NextUnit;}}};voidInAL(indxInV0,indxInV1);voidDisplayAL();voidALBFS_M();voidALBFS_S(indxCurrNode);voidALDFSR_M();voidALDFSR_S(indxCurrNode);voidALDFSE();private:ALUnitunit[V_CARD];boolread[V_CARD];intBFSList[V_CARD];indxBFSIndx;intDFSRList[V_CARD];indxDFSRIndx;};AjListAL;intAM[V_CARD][V_CARD];boolAMRead[V_CARD];voidAMInnitial();voidReadGraph();voidSelection();structQNode{indxdata;QNode*next;};classQueue{ public: Queue() { head=new(QNode); head->data=0; head->next=NULL; }; ~Queue() { if(head->next==NULL) { deletehead; } else { QNode*curr; do { curr=head->next; head->next=curr->next; deletecurr; }while(head->next!=NULL); deletehead; } }; voidQIn(indxInData); indxQOut(); boolIsEmpty() { if(head->next==NULL)return1; elsereturn0; } voidDisplay(); private: QNode*head;};voidSelection();voidAMBFS_M();voidAMBFS_S(indxCurrNode);voidALBFS();voidAMDFSR_M();voidAMDFSR_S(indxCurrNode);voidAMDFSE();voidAMDisplay();intmain(){cout<<"Helloworld!"<<endl;AMInnitial();cout<<"GraphInnitialized."<<endl;ReadGraph();cout<<"GraphLoaded."<<endl; cout<<"GraphofKirov_Tujin."<<endl <<"Orders:"<<endl <<"B.BreadthfirstSearch."<<endl <<"D.DeepthfirstSearch."<<endl <<"P.GraphDisplay."<<endl <<"Q.Quittheprogram."<<endl;Selection();return0;}voidSelection(){ boolSelecting=1; charOrder=0; while(Selecting) { cout<<"InputyourOrder."<<endl; cin>>Order; switch(Order) { case'B': { cout<<"BreadthfirstSearch."<<endl;AMBFS_M();cout<<"AMBFSFinished."<<endl;AL.ALBFS_M(); break; } case'D': { cout<<"DepthfirstSearch."<<endl<<">R.RecursiveDepthfirstSearch."<<endl<<">E.ExcursiveDepthfirstSearch."<<endl;cout<<">DepthfirstSearch:InputyourOrder."<<endl;cin>>Order;switch(Order){case'R':{cout<<">RecursiveDepthfirstSearch."<<endl;AMDFSR_M();AL.ALDFSR_M();break;}case'E':{cout<<">ExcursiveDepthfirstSearch."<<endl;AMDFSE();AL.ALDFSE();break;}} break; } case'P': { cout<<"Display."<<endl//????????????????????????????????????<<">M.DisplayAdjacencyMatrix."<<endl<<">L.DisplayAdjacencyList."<<endl;cout<<">Display:InputyourOrder."<<endl;cin>>Order;switch(Order){case'M':{cout<<">M.DisplayAdjacencyMatrix."<<endl;AMDisplay();break;}case'L':{cout<<">L.DisplayAdjacencyList."<<endl;AL.DisplayAL();break;}} break; cout<<"Displaying."<<endl; AL.DisplayAL(); break; } case'Q': { cout<<"Quit?('Y'toQuit.)"<<endl; cin>>Order; if(Order=='Y') { Selecting=0; } break; } default: { cout<<"IllegalInput."<<endl; } } }cout<<"Selectionended."<<endl; return;}voidQueue::QIn(indxInData){ QNode*InNode=new(QNode); InNode->data=InData; InNode->next=head->next; head->next=InNode; return;}indxQueue::QOut(){ QNode*curr,*tran,*form; form=NULL; curr=head; tran=curr->next; while(tran!=NULL) { form=curr; curr=tran; tran=curr->next; } if(form==NULL) { cout<<"EmptyList."<<endl; returnNULL; } indxOutData; OutData=curr->data; deletecurr;form->next=NULL; returnOutData;}voidQueue::Display(){ QNode*curr,*tran; curr=head; tran=curr->next; while(tran!=NULL) { cout<<curr->data; curr=tran; tran=curr->next; } cout<<curr->data<<endl; return;}voidAjList::InAL(indxInV0,indxInV1){ALUnit*InUnit=new(ALUnit);InUnit->numb=InV1;InUnit->next=NULL;ALUnit*CurrUnit=NULL,*NextUnit=NULL;CurrUnit=&unit[InV0];NextUnit=CurrUnit->next;while(NextUnit!=NULL){CurrUnit=NextUnit;NextUnit=CurrUnit->next;}CurrUnit->next=InUnit;return;}voidAjList::DisplayAL(){indxi=0;ofstreamOut_File("AjList.txt");ALUnit*CurrUnit=NULL,*NextUnit=NULL;for(i=0;i<V_CARD;i++){cout<<i<<"->";Out_File<<i<<"->";CurrUnit=&unit[i];NextUnit=CurrUnit->next;while(NextUnit!=NULL){CurrUnit=NextUnit;NextUnit=CurrUnit->next;cout<<CurrUnit->numb<<',';Out_File<<CurrUnit->numb<<',';}cout<<'#'<<endl;Out_File<<'#'<<endl;}Out_File.close();return;}voidAjList::ALBFS_M(){inti=0;for(i=0;i<V_CARD;i++){BFSList[i]=0;read[i]=0;}for(i=0;i<V_CARD;i++){if(read[i]==0){ALBFS_S(i);cout<<'#'<<endl;}}//???????????????????????????????????????????????????????????????????ofstreamOUT_FILE("ALBFSList.txt");for(i=0;i<V_CARD;i++){OUT_FILE<<BFSList[i]<<',';}OUT_FILE<<'#';OUT_FILE.close();return;}voidAjList::ALBFS_S(indxCurrNode){cout<<"ALBFS_Servanton."<<endl;QueueQ1;Q1.QIn(CurrNode);read[CurrNode]=1;cout<<'>';while(Q1.IsEmpty()!=1){CurrNode=Q1.QOut();cout<<CurrNode<<'-';BFSList[BFSIndx]=CurrNode;BFSIndx++;ALUnit*NextPTR=NULL,*CurrPTR=NULL;CurrPTR=&unit[CurrNode];NextPTR=unit[CurrNode].next;while(NextPTR!=NULL){CurrPTR=NextPTR;if(read[CurrPTR->numb]!=1){Q1.QIn(CurrPTR->numb);read[CurrPTR->numb]=1;}NextPTR=CurrPTR->next;}}return;}voidAjList::ALDFSR_M(){cout<<"ALDFSR_Masteron."<<endl;inti=0;for(i=0;i<V_CARD;i++){DFSRList[i]=0;read[i]=0;}for(i=0;i<V_CARD;i++){if(read[i]==0){cout<<'>'<<i;ALDFSR_S(i);cout<<'#'<<endl;}}//???????????????????????????????????????????????????????????????????ofstreamOUT_FILE("ALDFSRList.txt");for(i=0;i<V_CARD;i++){OUT_FILE<<DFSRList[i]<<',';}OUT_FILE<<'#';OUT_FILE.close();return;}voidAjList::ALDFSR_S(indxCurrNode){ALUnit*NextPTR=NULL,*CurrPTR=NULL;CurrPTR=&unit[CurrNode];NextPTR=unit[CurrNode].next;read[CurrNode]=1;DFSRList[DFSRIndx]=CurrNode;DFSRIndx++;while(NextPTR!=NULL){CurrPTR=NextPTR;if(read[CurrPTR->numb]==0){cout<<'-'<<CurrPTR->numb;ALDFSR_S(CurrPTR->numb);read[CurrPTR->numb]=1;}NextPTR=CurrPTR->next;}return;}voidAjList::ALDFSE(){indxi=0;for(i=0;i<V_CARD;i++){read[i]=0;}ofstreamOUT_File("ALDSFE.txt");for(i=0;i<V_CARD;i++){if(read[i]==0){cout<<'>';OUT_File<<'>';QueueQ2[V_CARD];indxQFlag=0;Q2[QFlag].QIn(i);indxCurrUnit;while((Q2[QFlag].IsEmpty()==0)||(QFlag>0)){if(Q2[QFlag].IsEmpty()==0){CurrUnit=Q2[QFlag].QOut();if(read[CurrUnit]==0){cout<<CurrUnit<<'-';OUT_File<<CurrUnit<<'-';read[CurrUnit]=1;QFlag++;ALUnit*CurrPTR=NULL,*NextPTR=NULL;CurrPTR=&unit[CurrUnit];NextPTR=CurrPTR->next;while(NextPTR!=NULL){CurrPTR=NextPTR;if(read[CurrPTR->numb]==0){Q2[QFlag].QIn(CurrPTR->numb);}NextPTR=CurrPTR->next;}}}else{QFlag--;}}cout<<'#'<<endl;OUT_File<<'#'<<endl;}}OUT_File.close();return;}voidReadGraph(){fstreamInFile("Graph.txt");cout<<"ReadGraph:Graphopened."<<endl;inti=0;intCurrEdge[2];charspace=0;for(i=0;i<E_CARD;i++){InFile>>CurrEdge[0]>>space>>CurrEdge[1];AL.InAL(CurrEdge[0]-1,CurrEdge[1]-1);AM[CurrEdge[0]-1][CurrEdge[1]-1]=1;}cout<<"ReadGraph:Graphloaded."<<endl;AL.DisplayAL();ofstreamOut_File_1_2("AjMatrix.txt");for(i=0;i<V_CARD;i++){for(intj=0;j<V_CARD;j++){cout<<"\t"<<AM[i][j];Out_File_1_2<<"\t"<<AM[i][j];}cout<<endl<<endl;Out_File_1_2<<endl<<endl;}Out_File_1_2.close();return;}voidAMInnitial(){inti=0,j=0;for(i=0;i<V_CARD;i++){AMRead[i]=0;for(j=0;j<V_CARD;j++){AM[i][j]=0;}}return;}voidAMBFS_M(){indxi=0;for(i=0;i<V_CARD;i++){AMRead[i]=0;}for(i=0;i<V_CARD;i++){if(AMRead[i]==0){AMBFS_S(i);cout<<'#'<<endl;}}return;}voidAMBFS_S(indxCurrNode){cout<<"AMBFS_Servanton."<<endl;QueueQ1;Q1.QIn(CurrNode);AMRead[CurrNode]=1;cout<<'>';while(Q1.IsEmpty()!=1){CurrNode=Q1.QOut();cout<<CurrNode<<'-';indxj=0;for(j=0;j<V_CARD;j++){if((AM[CurrNode][j]==1)&&(AMRead[j]==0)){Q1.QIn(j);AMRead[j]=1;}}}return;}voidAMDFSR_M(){cout<<"AMDFSR_Masteron."<<endl;indxi=0;for(i=0;i<V_CARD;i++)