算法与数据结构课程设计报告书_--AOV网.docVIP

算法与数据结构 　　　　　 　课程设计报告书 　　　　姓　　名　＿＿＿＿＿＿ 　班　　级　＿＿＿＿＿＿＿ 　　　　学　　号　＿＿＿＿＿＿＿ 　　　　指导教师　＿＿＿＿＿ 问题描述： 设计程序完成如下功能：对给定的AOV网，求出该AOV网所有的拓扑序列。 设计的软、硬件环境： CPU 操作系统 Mircrosoft visual C++ ADT(数据结构与算法)设计与功能模块： 基于邻接表的存储结构 利用CreatGraph(ALGraph *G)函数，构建图-——邻接表； 用FindInDegree(ALGraph G,int indegree[]),求出入度为零的顶点，即为没有前驱的顶点，可以附设一个存放各顶点入度的数组Indegree[]； 找G中无前驱的顶点—查找indegree[i]为零的顶点vi; 删除以i为顶点的所有弧—对链在顶点i后面的所有邻接顶点k,对对应的indegree[k]减1； 利用TopologicalSort(ALGraph G)进行拓扑排序； 为了避免重复检测入度为零的顶点，再设置一个辅助栈，若某一顶点的入度为零，则将它入栈。每当输出某一入度为零的顶点时，便将它从栈中删除； 这里用到如下函数 void InitStack(SqStack *); int Pop(SqStack *, ElemType *); void Push(SqStack *,ElemType ); int StackEmpty(SqStack *); 程序输入与结果输出： 实验结果分析及收获： 首先输入了该图的顶点数和边数，假设顶点数和边数都为4，有V1,V2,V1,V3,V1,V4,V3,V4; 所以建立的邻接表为： 1 3 4 2 2 3 4 4 然后求出了各顶点的入度，即： 第1个顶点的入度为0； 第2个顶点的入度为1； 第3个顶点的入度为1； 第4个顶点的入度为2； 最后输出该拓扑序列的排列顺序：1 2 3 4 实验收获: 这次对AOV网进行拓扑排序的课程设计，让我明白了如何对一个有向无环图进行拓扑排序，以及拓扑排序的基本思想。在课程设计的过程中虽然也遇到了一些难题，但是通过看书，上网查相关资料，以及组员之间讨论，终于解决了相关问题，得出了实验结果。 附录（源程序清单） #includestdio.h #includestdlib.h #define MAX_VEXTEX_NUM 20 #define M 20 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OK 1 #define ERROR 0 typedef int ElemType; typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode { int data; ArcNode *firstarc; }VNode,AdjList[MAX_VEXTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; }ALGraph; typedef struct //构件栈 { ElemType *base; ElemType *top; int stacksize; }SqStack; void InitStack(SqStack *); //函数声明 int Pop(SqStack *, ElemType *); void Push(SqStack *,ElemType ); int StackEmpty(SqStack *); void CreatGraph(ALGraph *); void FindInDegree(ALGraph , int * ); void TopologicalSort(ALGraph ); void InitStack(SqStack *S)//初始化栈i { S-base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType)); if(!S-base) { printf(memory allocation failed, goodbye); exit(1); } S-top=S-base; S-stacksize=STACK_INIT_SIZE; } int Pop(SqStack *S,ElemType *e)//出栈操作 { if(S-top==S-base) {return ERROR;} *e=*--S-top; //p