石大数据结构实验报告

1、 数据结构实验报告二级学院： 计算机学院 专 业： 指导教师： 班级学号： 姓 名： 实验四1、题目：图的设计2、问题描述： （1）定义邻接矩阵存储结构。（2）按照建立一个带权有向图的操作需要，编写在邻接矩阵存储结构下，带权有向图基本操作的实现函数（如初始化图、在图中插入一个结点、在图中插入一条边、在图中寻找序号为v的结点的第一个邻接结点、在图中寻找序号为v1结点的邻接结点v2的下一个邻接结点、图的深度优先遍历或图的广度优先遍历等）。（3）设计一个测试主函数，首先创建一个图（以图9-5为例），然后打印图的n个结点信息和e条边信息，最后打印出图的深度优先遍历或广度优先遍历的结点信息序列。3、基本

2、要求：（1）为统一起见，创建一个以图9-5为例的图。（2）在邻接矩阵存储结构下，带权有向图基本操作的实现函数。（3）打印图的n个结点信息和e条边信息，打印出图的深度优先遍历或广度优先遍历的结点信息序列。（4）提交实验报告。4、测试数据：5、算法思想：结点结构体：存放顶点的顺序表，存放边的邻接矩阵（二维数组），边的条数。初始化函数：令邻接矩阵的元素为MaxWeight，边的条数置为0，顺序表初始化。插入结点函数：在图G中插入顶点vertex即在顺序表表尾插入顶点。插入边函数：在图G中插入边，边的权为weight。删除边函数：在图G中删除边，即令对应的邻接矩阵的元素为MaxWeight。取第一个邻

3、接顶点：在图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的第一个邻接顶

4、点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)顶点

5、w入队列；(c)查找顶点u的w的邻接顶点后的下一个邻接顶点w，转到步骤6）。 非图的广度优先遍历函数：访问标记初始均为0，以每个顶点为初始顶点进行调用（调用连通图的广度优先遍历函数）。6、模块划分：1）定义图的结点结构体。2）初始化操作函数。3）插入结点操作函数。4）插入边操作函数。5）删除边操作函数。6）取第一个邻接顶点。7）取下一个邻接顶点。8）图的深度优先遍历函数。9）图的广度优先遍历函数。10）定义边信息结构体。11）创建图函数。12）设计主函数进行测试。7、数据结构： 8、源程序：#include #include #include typedef char DataType;#de

6、fine MaxSize 100#define MaxVertices 10#define MaxEdges 100#define MaxWeight 10000#define MaxQueueSize 100#include SeqList.h#include SeqCQueue.htypedef struct SeqList Vertices;/*存放顶点的顺序表*/int edgeMaxVerticesMaxVertices;/*存放边的邻接矩阵*/int numOfEdges;/*边的条数*/AdjMWGraph;/*图的结构体定义*/void Initiate(AdjMWGraph

7、*G, int n)/*初始化*/int i, j;for(i = 0; i n; i+)for(j = 0; j edgeij = 0;else G-edgeij = MaxWeight;G-numOfEdges = 0;/*边的条数置为0*/ListInitiate(&G-Vertices);/*顺序表初始化*/void InsertVertex(AdjMWGraph *G, DataType vertex)/*在图G中插入顶点vertex*/ListInsert(&G-Vertices, G-Vertices.size, vertex);/*顺序表表尾插入*/void InsertEdg

8、e(AdjMWGraph *G, int v1, int v2, int weight)/*在图G中插入边，边的权为weight*/if(v1 G-Vertices.size | v2 G-Vertices.size)printf(参数v1或v2越界出错!n);exit(1);G-edgev1v2 = weight;G-numOfEdges+;void DeleteEdge(AdjMWGraph *G, int v1, int v2)/*在图G中删除边*/if(v1 G-Vertices.size | v2 G-Vertices.size | v1 = v2)printf(参数v1或v2越界出

9、错!n);exit(1);G-edgev1v2 = MaxWeight;G-numOfEdges-;void DeleteVertex(AdjMWGraph *G, int v)/删除结点vint n = ListLength(G-Vertices), i, j;DataType x;for(i = 0; i n; i+)for(j = 0; j edgeij 0 & G-edgeij numOfEdges-;/被删除边计数for(i = v; i n; i+)for(j = 0; j edgeij = G-edgei+1j;/删除第v行for(i = 0; i n; i+)for(j = v

10、; j edgeij = G-edgeij+1;/删除第v列ListDelete(&G-Vertices, v, &x);/删除结点vint GetFirstVex(AdjMWGraph G, int v)/*在图G中寻找序号为v的顶点的第一个邻接顶点*/*如果这样的邻接顶点存在则返回该邻接顶点的序号，否则返回-1*/int col;if(v G.Vertices.size)printf(参数v1越界出错!n);exit(1);for(col = 0; col 0 & G.edgevcol MaxWeight) return col;return -1;int GetNextVex(AdjMW

11、Graph G, int v1, int v2)/*在图G中寻找v1顶点的邻接顶点v2的下一个邻接顶点*/*如果这样的邻接顶点存在则返回该邻接顶点的序号，否则返回-1*/*这里v1和v2都是相应顶点的序号*/int col;if(v1 G.Vertices.size | v2 G.Vertices.size)printf(参数v1或v2越界出错!n);exit(1);for(col = v2+1; col 0 & G.edgev1col MaxWeight) return col;return -1;typedef struct int row;/*行下标*/int col;/*列下标*/in

12、t weight;/*权值*/RowColWeight;/*边信息三元组结构体定义*/void CreatGraph(AdjMWGraph *G, DataType V, int n, RowColWeight E, int e)/*在图G中插入n个顶点信息V和e条边信息E*/int i, k;Initiate(G, n);/*顶点顺序表初始化*/for(i = 0; i n; i+)InsertVertex(G, Vi);/*顶点插入*/for(k = 0; k e; k+)InsertEdge(G, Ek.row, Ek.col, Ek.weight);/*边插入*/void DepthF

13、Search(AdjMWGraph G, int v, int visited)/*连通图G以v为初始顶点的深度优先遍历*/*数组visited标记了相应顶点是否已访问过，0表示未访问，1表示已访问*/int w;printf(%c , G.Vertices.listv);/*输出顶点字母*/visitedv = 1;w = GetFirstVex(G, v);while(w != -1)if(! visitedw) DepthFSearch(G, w, visited);w = GetNextVex(G, v, w);void DepthFirstSearch(AdjMWGraph G)/*

14、非连通图G的深度优先遍历*/int i;int *visited = (int *)malloc(sizeof(int)*G.Vertices.size);for(i = 0; i G.Vertices.size; i+)visitedi = 0;for(i = 0; i G.Vertices.size; i+)if(! visitedi) DepthFSearch(G, i, visited);free(visited);void BroadFSearch(AdjMWGraph G, int v, int visited)/*连通图G以v为初始顶点的广度优先遍历*/*数组visited标记了

15、相应顶点是否已访问过，0表示未访问，1表示已访问*/DataType u, w;SeqCQueue queue;printf(%c , G.Vertices.listv);/*输出顶点字母*/visitedv = 1;QueueInitiate(&queue);QueueAppend(&queue, v);while(QueueNotEmpty(queue)QueueDelete(&queue, &u);w = GetFirstVex(G, u);while(w != -1)if(!visitedw)printf(%c , G.Vertices.listw);/*输出顶点字母*/visited

16、w = 1;QueueAppend(&queue, w);w = GetNextVex(G, u, w);void BroadFirstSearch(AdjMWGraph G)/*非连通图G的广度优先遍历*/int i;int *visited = (int *)malloc(sizeof(int)*G.Vertices.size);for(i = 0; i G.Vertices.size; i+)visitedi = 0;for(i = 0; i G.Vertices.size; i+)if(!visitedi) BroadFSearch(G, i, visited);free(visite

17、d);void main(void)AdjMWGraph g1;DataType a = A,B,C,D,E;RowColWeight rcw = 0,1,1,0,2,1,0,3,1,0,4,1,2,4,1,3,1,1;int n = 5, e = 6;int i, j;CreatGraph(&g1, a, n, rcw, e);printf(顶点集合为：);for(i = 0; i g1.Vertices.size; i+)printf(%c , g1.Vertices.listi);printf(n);printf(边的集合为：n);for(i = 0; i g1.Vertices.size; i+)for(j = 0; j g1.Vertices.size; j+)prin