浙大城院数据结构实验报告report13

浙江大学城市学院实验报告课程名称数据结构基础实验项目名称实验十三图的基本操作—邻接表存储结构学生姓名专业班级学号实验成绩指导老师（签名）日期头文件AdjLink.h，在该文件中定义图的邻接表存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度图的深度优先遍历函数与广度优先遍历函数等基本操作实现函数。同时在主函数文件test5_2.cpp中调用这些函数进行验证。三.函数的功能说明及算法思路（包括每个函数的功能说明，及一些重要函数的算法实现思路）这里针对的都是无向无权图结构类型定义//边表结点//顶点表结点//图类型typedefstructnodetypedefstruct{typedefstruct{{intadjvex;//邻接点域 VertexTypevertex;//顶点域AdjListadjlist;//邻接表node*next;//链域EdgeNode*firstedge;//边表头指针intn,e;//图中当前顶点数和边数}EdgeNode;}VertexNode;}ALGraph;//图类型typedefVertexNodeAdjList[MaxVertexNum];//AdjList是邻接表类型基本面函数1.voidCreatALGraph(ALGraph*G)//构造图{定义边表结点s；读入顶点数和边数；读入顶点信息，并将边表置为空；依次读入<入度点vi，出度点vj>边的信息直到输入的边数达到要求{ 为s开辟新空间，邻接点序号为j，并将邻接点指针为i顶点的头指针值，将新结点*S插入顶点Vi的边表头部 为s再开辟新空间，邻接点序号为i，并将邻接点指针为j顶点的头指针值，将新结点*S插入顶点Vj的边表头部}}voidDFS(ALGraph*G,inti)//以Vi为出发点对邻接链表表示的图G进行DFS搜索voidDFSTraverseM(ALGraph*G)//对整个图进行深度搜索4.voidBFS(ALGraph*G,intk)//以Vk为源点对用邻接链表表示的图G进行广度优先搜索5.voidBFSTraverseM(ALGraph*G){//对整个图进行广度搜索广度搜索时要建立队列并写队列的相应函数6.voidPrintALGraph(ALGraph*G){//输出表四.实验结果与分析（包括运行结果截图、结果分析等）五.心得体会（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）失败点:1.scanf();输入格式上面出错，没有严格按照要求输出所以常常运行到一半就出错误2.在刚开始的时候以为顶点Vertexnode中VerTex输入的是地址值，学习点：1.typedefenum{FALSE,TRUE}Boolean;声明了一个枚举类型一般形式为：enum[枚举名]{枚举元素列表}；

也可以声明没有枚举名的枚举类型，就是像你给的那种，后边的bool是枚举类型的变量，可以对其进行赋值，不过只能用FALSE或者TRUE进行赋值。【附录----源程序】test5_2.cpp#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include"AdjLink.h"voidmain(){inti;ALGraph*G=(ALGraph*)malloc(sizeof(ALGraph));CreatALGraph(G);PrintALGraph(G);printf("PrintGraphDFS:\n");DFSTraverseM(G);printf("\n");printf("PrintGraphBFS:\n");BFSTraverseM(G);printf("\n");}AdjLink.h#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum100#defineQueueSize30typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];typedefcharVertexType;typedefintEdgeType;typedefstructnode//边表结点{intadjvex;//邻接点域node*next;//链域}EdgeNode;typedefstruct{//顶点表结点VertexTypevertex;//顶点域EdgeNode*firstedge;//边表头指针}VertexNode;typedefVertexNodeAdjList[MaxVertexNum];//AdjList是邻接表类型typedefstruct{AdjListadjlist;//邻接表intn,e;//图中当前顶点数和边数}ALGraph;//图类型/*=========建立无向图邻接表算法=======*/voidCreatALGraph(ALGraph*G){inti,j,k;EdgeNode*s;//定义边表结点printf("请输入顶点数和边数(输入格式为:顶点数，边数):\n");scanf("%d,%d",&(G->n),&(G->e));//读入顶点数和边数printf("请输入顶点信息(输入格式为:顶点号<CR>)每个顶点以回车作为结束:\n");for(i=0;i<G->n;i++)//建立边表{ scanf("\n%c",&(G->adjlist[i].vertex));//读入顶点信息 G->adjlist[i].firstedge=NULL;//边表置为空表}printf("请输入边的信息(输入格式:i,j):\n");for(k=0;k<G->e;k++){//建立边表 scanf("\n%d,%d",&i,&j);//读入边（Vi，Vj）的顶点对序号 s=newEdgeNode; s->adjvex=j;//邻接点序号为j s->next=G->adjlist[i].firstedge; G->adjlist[i].firstedge=s;//将新结点*S插入顶点Vi的边表头部 s=newEdgeNode; s->adjvex=i;//邻接点序号为i s->next=G->adjlist[j].firstedge; G->adjlist[j].firstedge=s;//将新结点*S插入顶点Vj的边表头部}}voidPrintALGraph(ALGraph*G){//输出表 inti; for(i=0;i<G->n;i++){ printf("%d->",i); while(G->adjlist[i].firstedge!=NULL){ printf("%d->",G->adjlist[i].firstedge->adjvex); G->adjlist[i].firstedge=G->adjlist[i].firstedge->next; } printf("\n");}}/*=======深度优先遍历的递归算法======*/voidDFS(ALGraph*G,inti){//以Vi为出发点对邻接链表表示的图G进行DFS搜索EdgeNode*p;printf("vsitvertex:%c\n",G->adjlist[i].vertex);//访问顶点Vivisited[i]=TRUE;//标记Vi已访问p=G->adjlist[i].firstedge;//取Vi边表的头指针while(p){//依次搜索Vi的邻接点Vj，这里j=p->adjvex if(!visited[p->adjvex])//若Vj尚未被访问 DFS(G,p->adjvex);//则以Vj为出发点向纵深搜索 p=p->next;//找Vi的下一个邻接点}}voidDFSTraverseM(ALGraph*G){inti;for(i=0;i<G->n;i++) visited[i]=FALSE;//标志向量初始化for(i=0;i<G->n;i++) if(!visited[i])//Vi未访问过 DFS(G,i);//以Vi为源点开始DFS搜索}/*==========BFS：广度优先遍历=========*/typedefstruct{ intfront; intrear; intcount; intdata[QueueSize];}CirQueue;voidInitQueue(CirQueue*Q){ Q->front=Q->rear=0; Q->count=0;}intQueueEmpty(CirQueue*Q){ returnQ->count=QueueSize;}intQueueFull(CirQueue*Q){ returnQ->count==QueueSize;}voidEnQueue(CirQueue*Q,intx){ if(QueueFull(Q)) printf("Queueoverflow"); else { Q->count++; Q->data[Q->rear]=x; Q->rear=(Q->rear+1)%QueueSize; }}intDeQueue(CirQueue*Q){ inttemp; if(QueueEmpty(Q)) { printf("Queueunderflow"); returnNULL; } else { temp=Q->data[Q->front]; Q->count--; Q->front=(Q->front+1)%QueueSize; returntemp; }}voidBFS(ALGraph*G,intk){//以Vk为源点对用邻接链表表示的图G进行广度优先搜索inti; CirQueueQ; EdgeNode*p; InitQueue(&Q);//队列初始化 printf("Visitvertex:%c\n",G->adjlist[k].vertex); visited[k]=TRUE; EnQueue(&Q,k); while(!QueueEmpty(&Q)){ i=DeQueue(&Q); p=G->adjlist[i].firstedge; while(p){ if(!vi