石大--数据结构实验报告4

《数据结构》实验报告二级学院：计算机学院专业：指导教师：班级学号：姓名：实验四1、题目：图的设计2、问题描述：（1）定义邻接矩阵存储结构。（2）按照建立一个带权有向图的操作需要，编写在邻接矩阵存储结构下，带权有向图基本操作的实现函数（如初始化图、在图中插入一个结点、在图中插入一条边、在图中寻找序号为v的结点的第一个邻接结点、在图中寻找序号为v1结点的邻接结点v2的下一个邻接结点、图的深度优先遍历或图的广度优先遍历等）。（3）设计一个测试主函数，首先创建一个图（以图9-5为例），然后打印图的n个结点信息和e条边信息，最后打印出图的深度优先遍历或广度优先遍历的结点信息序列。3、基本要求：（1）为统一起见，创建一个以图9-5为例的图。（2）在邻接矩阵存储结构下，带权有向图基本操作的实现函数。（3）打印图的n个结点信息和e条边信息，打印出图的深度优先遍历或广度优先遍历的结点信息序列。（4）提交实验报告。4、测试数据：5、算法思想：结点结构体：存放顶点的顺序表，存放边的邻接矩阵（二维数组），边的条数。初始化函数：令邻接矩阵的元素为MaxWeight，边的条数置为0，顺序表初始化。插入结点函数：在图G中插入顶点vertex即在顺序表表尾插入顶点。插入边函数：在图G中插入边v1,v2，边v1,v2的权为weight。删除边函数：在图G中删除边v1,v2，即令对应的邻接矩阵的元素为MaxWeight。取第一个邻接顶点：在图G中寻找序号为v的顶点的第一个邻接顶点，就是邻接矩阵的顶点v行中从第一个矩阵元素开始的非0且非无穷大的顶点，如果这样的邻接顶点存在则返回该邻接顶点的序号，否则返回-1。取下一个邻接顶点：在图G中寻找v1顶点的邻接顶点v2的下一个邻接顶点，就是邻接矩阵的顶点v行中从第v2+1个矩阵元素开始的非0且非无穷大的顶点，如果这样的邻接顶点存在则返回该邻接顶点的序号，否则返回-1，这里v1和v2都是相应顶点的序号。创建图函数：在图G中插入n个顶点信息V和e条边信息E，包括顶点顺序表初始化，插入顶点，插入边。连通图的深度优先遍历函数：1）访问顶点v并标记顶点v已访问。2）查找顶点v的第一个邻接顶点w。3）若顶点v的邻接顶点w存在，则继续执行，否则算法结束。4)若顶点w尚未被访问，则深度优先遍历递归访问顶点w。5）查找顶点v的w邻接顶点的下一个邻接顶点w，转到步骤3）。非图的深度优先遍历函数：访问标记初始均为0，以每个顶点为初始顶点进行调用（调用连通图的深度优先遍历函数）。连通图的广度优先遍历函数：1）访问初始顶点v并标记顶点v为已访问。2）顶点v入队列。3）若队列非空，则继续执行，否则算法结束。4)出队列取得队头顶点u。5）查找顶点u的第一个邻接顶点w。6）若顶点u的邻接顶点w不存在，则转到步骤3），否则循环执行：(a)若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问；(b)顶点w入队列；(c)查找顶点u的w的邻接顶点后的下一个邻接顶点w，转到步骤6）。非图的广度优先遍历函数：访问标记初始均为0，以每个顶点为初始顶点进行调用（调用连通图的广度优先遍历函数）。6、模块划分：1）定义图的结点结构体。2）初始化操作函数。3）插入结点操作函数。4）插入边操作函数。5）删除边操作函数。6）取第一个邻接顶点。7）取下一个邻接顶点。8）图的深度优先遍历函数。9）图的广度优先遍历函数。10）定义边信息结构体。11）创建图函数。12）设计主函数进行测试。7、数据结构：8、源程序：#includestdio.h#includestdlib.h#includemalloc.htypedefcharDataType;#defineMaxSize100#defineMaxVertices10#defineMaxEdges100#defineMaxWeight10000#defineMaxQueueSize100#includeSeqList.h#includeSeqCQueue.htypedefstruct{SeqListVertices;/*存放顶点的顺序表*/intedge[MaxVertices][MaxVertices];/*存放边的邻接矩阵*/intnumOfEdges;/*边的条数*/}AdjMWGraph;/*图的结构体定义*/voidInitiate(AdjMWGraph*G,intn)/*初始化*/{inti,j;for(i=0;in;i++)for(j=0;jn;j++){if(i==j)G-edge[i][j]=0;elseG-edge[i][j]=MaxWeight;}G-numOfEdges=0;/*边的条数置为0*/ListInitiate(&G-Vertices);/*顺序表初始化*/}voidInsertVertex(AdjMWGraph*G,DataTypevertex)/*在图G中插入顶点vertex*/{ListInsert(&G-Vertices,G-Vertices.size,vertex);/*顺序表表尾插入*/}voidInsertEdge(AdjMWGraph*G,intv1,intv2,intweight)/*在图G中插入边v1,v2，边v1,v2的权为weight*/{if(v10||v1G-Vertices.size||v20||v2G-Vertices.size){printf(参数v1或v2越界出错!\n);exit(1);}G-edge[v1][v2]=weight;G-numOfEdges++;}voidDeleteEdge(AdjMWGraph*G,intv1,intv2)/*在图G中删除边v1,v2*/{if(v10||v1G-Vertices.size||v20||v2G-Vertices.size||v1==v2){printf(参数v1或v2越界出错!\n);exit(1);}G-edge[v1][v2]=MaxWeight;G-numOfEdges--;}voidDeleteVertex(AdjMWGraph*G,intv)//删除结点v{intn=ListLength(G-Vertices),i,j;DataTypex;for(i=0;in;i++)for(j=0;jn;j++)if((i==v||j==v)&&G-edge[i][j]0&&G-edge[i][j]MaxWeight)G-numOfEdges--;//被删除边计数for(i=v;in;i++)for(j=0;jn;j++)G-edge[i][j]=G-edge[i+1][j];//删除第v行for(i=0;in;i++)for(j=v;jn;j++)G-edge[i][j]=G-edge[i][j+1];//删除第v列ListDelete(&G-Vertices,v,&x);//删除结点v}intGetFirstVex(AdjMWGraphG,intv)/*在图G中寻找序号为v的顶点的第一个邻接顶点*//*如果这样的邻接顶点存在则返回该邻接顶点的序号，否则返回-1*/{intcol;if(v0||vG.Vertices.size){printf(参数v1越界出错!\n);exit(1);}for(col=0;col=G.Vertices.size;col++)if(G.edge[v][col]0&&G.edge[v][col]MaxWeight)returncol;return-1;}intGetNextVex(AdjMWGraphG,intv1,intv2)/*在图G中寻找v1顶点的邻接顶点v2的下一个邻接顶点*//*如果这样的邻接顶点存在则返回该邻接顶点的序号，否则返回-1*//*这里v1和v2都是相应顶点的序号*/{intcol;if(v10||v1G.Vertices.size||v20||v2G.Vertices.size){printf(参数v1或v2越界出错!\n);exit(1);}for(col=v2+1;col=G.Vertices.size;col++)if(G.edge[v1][col]0&&G.edge[v1][col]MaxWeight)returncol;return-1;}typedefstruct{introw;/*行下标*/intcol;/*列下标*/intweight;/*权值*/}RowColWeight;/*边信息三元组结构体定义*/voidCreatGraph(AdjMWGraph*G,DataTypeV[],intn,RowColWeightE[],inte)/*在图G中插入n个顶点信息V和e条边信息E*/{inti,k;Initiate(G,n);/*顶点顺序表初始化*/for(i=0;in;i++)InsertVertex(G,V[i]);/*顶点插入*/for(k=0;ke;k++)InsertEdge(G,E[k].row,E[k].col,E[k].weight);/*边插入*/}voidDepthFSearch(AdjMWGraphG,intv,intvisited[])/*连通图G以v为初始顶点的深度优先遍历*//*数组visited标记了相应顶点是否已访问过，0表示未访问，1表示已访问*/{intw;printf(%c,G.Vertices.list[v]);/*输出顶点字母*/visited[v]=1;w=GetFirstVex(G,v);while(w!=-1){if(!visited[w])DepthFSearch(G,w,visited);w=GetNextVex(G,v,w);}}voidDepthFirstSearch(AdjMWGraphG)/*非连通图G的深度优先遍历*/{inti;int*visited=(int*)malloc(sizeof(int)*G.Vertices.size);for(i=0;iG.Vertices.size;i++)visited[i]=0;for(i=0;iG.Vertices.size;i++)if(!visited[i])DepthFSearch(G,i,visited);free(visited);}voidBroadFSearch(AdjMWGraphG,intv,intvisited[])/*连通图G以v为初始顶点的广度优先遍历*//*数组visited标记了相应顶点是否已访问过，0表示未访问，1表示已访问*/{DataTypeu,w;SeqCQueuequeue;printf(%c,G.Vertices.list[v]);/*输出顶点字母*/visited[v]=1;QueueInitiate(&queue);QueueAppend(&queue,v);while(QueueNotEmpty(queue)){QueueDelete(&queue,&u);w=GetFirstVex(G,u);while(w!=-1){if(!visited[w]){printf(%c,G.Vertices.list[w]);/*输出顶点字母*/visited[w]=1;QueueAppend(&queue,w);}w=GetNextVex(G,u,w);}}}voidBroadFirstSearch(AdjMWGraphG)/*非连通图G的广度优先遍历*/{inti;int*visited=(int*)malloc(sizeof(int)*G.Vertices.size);for(i=0;iG.Vertices.size;i++)visited[i]=0;for(i=0;iG.Vertices.size;i++)if(!visited[i])BroadFSearch(G,i,visited);free(visited);}voidmain(void