实验六 图的应用及其实现.docVIP

实验六 图的应用及其实现 一、实验目的 1．进一步功固图常用的存储结构。 2．熟练掌握在图的邻接表实现图的基本操作。 3．理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。 实验内容 [题目一]：从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网的类型定义和基本操作,完成上述功能。 测试数据：教材图7.28 实验步骤 ㈠数据结构与核心算法的设计描述 #define MAX_VERTEX_NUM 20 typedef struct ArcNode //弧结点定义 { int adjvex; //该弧所指向的顶点的位置 struct ArcNode *nextarc;//指向下一条弧的指针 //InfoType *info; }ArcNode; typedef struct VNode //顶点结点定义 { char data; //顶点信息 ArcNode *firstarc; //指向第一条依附该顶点的弧的指针 }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct //图的定义 { AdjList vertices; int vexnum,arcnum; //图的当前顶点数和弧数 int kind; //图的种类标志 }ALGraph; ALGraph G; //定义图变量 bool visited[MAX_VERTEX_NUM]; //访问标志数组 int indegree[20]; //各结点入度数组 struct Stack //栈类型定义 { int s[21]; int top; }; Stack stack; 相关函数声明： void CreateGraph(MGraph G) // 输入图的顶点和边的信息,建立图 int LocateVertices(ALGraph G,char a) //查找字符a在图中的位置 int FirstAdjVex(ALGraph G,int v) //查找图中位置v的第一个邻接点在图中所在的位置 int NextAdjVex(ALGraph G,int v,int w) //查找相对于图中位置v的邻接点w的下一邻接点在图中的位置 void DestroyGraph(ALGraph G) //销毁图 void InitStack(Stack stack) //初始化栈 void PushStack(Stack stack,int i) //元素i入栈 void PopStack(Stack stack,int i) //栈顶元素出栈 int StackEmpty(Stack stack) //判断栈是否为空，若为空则返回1，否则返回0 void FindInDegree(ALGraph G,int *indegree) //求图中各个顶点的入度，并相应的存入入度数组中indegree[] int TopologicalSort(ALGraph G) //对图进行拓扑排序，并输出相应的拓扑序列 ㈡函数调用及主函数设计 ㈢ 程序调试及运行结果分析 ㈣ 实验总结 这次的实验使得我对图的定义及其更多的操作有了更深入的了解，运用起来更加地熟练，掌握了拓扑排序的书写，利用栈实现图的拓扑排序的算法与分析问题的能力，让我能够对以前的知识有所复习，例如：栈的使用。对以前的知识有了更深入的理解，例如：图的数据结构及算法实现，图的存储结构。这是我收获最大的地方。 程序清单 #includeiostream.h #includestdlib.h #define MAX_VERTEX_NUM 20 typedef struct ArcNode //弧结点定义 { int adjvex; //该弧所指向的顶点的位置 struct ArcNode *nextarc;//指向下一条弧的指针 //InfoType *info; }ArcNode; typedef struct VNode //顶点结点定义 { char data; //顶点信息 ArcNode *firstarc; //指向第