数据结构拓扑排序课程设计.doc

课题二 拓扑排序21 问题的提出2.1 问题的提出 任务：编写函数实现图的拓扑排序。程序所实现的功能：建立对应的邻接表，对该图进行拓扑排序，并显示排序结果。输入：顶点数, 边数及各顶点信息(数据格式为整形) 输出： 拓扑排序结果。 2. 2 概要设计 1.拓扑排序是指由某个集合上的一个偏序得到该集合上的一个全序。更直观地讲，一个偏序是自反的、反对称的，用图表示时每个点都有环且只有单向边。拓扑排序的任务是在这个偏序上得到一个全序，即得到一个完成整个项目的各步骤的序列。2解决拓扑排序的方法如下：（1）在有向图中选一个没有前驱的顶点且输出之。（2）从图中删除该顶点和所有以它为尾的弧。重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。具体的算法实现参照源程序。3构造邻接表图：typedef struct AdjList vertices; int vexnum,arcnum;Graph;/邻接表图 4. 为了避免重复检测入度为零的顶点，源程序中设了一个栈，暂存所有入度为零的顶点：typedef struct stackint *base;int *top;int stacksize;sqstack;/栈的结构，存储图的顶点序号23 流程图2.根据算法思想，画流程图如下：开始设辅助数组indegree记录图的各顶点的入度值，并将indegree数组各变量赋初值。输入图的顶点数、边数建立一个栈，存储图的顶点的序号用邻接表法建图，并计算出indegree数组中各变量值根据indegree数组将入度为0的顶点入栈count对输出顶点计数0=count栈不空删除栈顶元素,赋给icount+将与第i个顶点链接的各顶点入度减1输出第i个顶点值顶点入度为0顶点序号入栈countG.vexnum输出“拓扑排序成功”输出“拓扑排序不成功”结束24 源代码/采用尾插法创的邻接图#includeusing namespace std;const int MAX=20;const int STACK_INIT_SIZE=100;const int ERROR=0;typedef struct stackint *base;int *top;int stacksize;sqstack;/栈的结构，存储图的顶点序号typedef struct lnodeint adjvex;struct lnode *next;ArcNode;/弧结点typedef struct node2char data;ArcNode *fristarc;VNode,AdjListMAX;/顶点数组,fristarc指向与顶点邻接的第一条弧typedef struct AdjList vertices; int vexnum,arcnum;Graph;/邻接表图void Initstack(sqstack &s)s.base=new int;if(!s.base)exit(0);s.top=s.base;s.stacksize= STACK_INIT_SIZE;void Push(sqstack &s,int &e)*s.top+=e;int Emptystack(sqstack &s)if(s.base=s.top)return 1;elsereturn 0;int Pop(sqstack &s,int &e)if(s.base=s.top)return ERROR;e=*-s.top;void CreatGraph(Graph &G,int *indegree) cout请输入图的顶点数和弧数(且顶点数不能超过MAX)G.vexnumG.arcnum;cout请输入顶点值:endl;for(int i=0;iG.verticesi.data;G.verticesi.fristarc=NULL;indegreei=0;for(i=0;iG.arcnum;i+)/输入图的弧int m,n;ArcNode *p;cout请输入第i+1条弧的弧尾和弧头:mn;p=new ArcNode;if(!p)exit(0);indegreen-1+;/求每个顶点的入度值p-adjvex=n-1;p-next=G.verticesm-1.fristarc;G.verticesm-1.fristarc=p;int Toposort(Graph &G,int *indegree)sqstack S;Initstack(S);for(int i=0;iG.vexnum;i+)/0入度顶点入栈if(!indegreei)Push(S,i); int count=0; while(!Emptystack(S) Pop(S,i); coutG.verticesi.datanext)/把与顶点 /相邻接的顶点的入度 int k=p-adjvex; if(!(-indegreek) Push(S,k); if(countG.vexnum) return 0; else return 1;int main() Graph G; int *indegree; indegree=new int; CreatGraph(G,indegree); if(!Toposort(G,indegree) coutendl; cout拓扑排序不成功!endl; else coutendl; cout拓扑排序成功!endl; return 0;25 结果与分析2.4 测试及性能分析1它的时间复杂度是O(G.vexnum+G.arcnum)。2. 整个程序的关键就是采用尾插法创的邻接表图，运用栈来实现各个数值的输入输出及存储。3注意*的使用，并不是什么情况下都用*，它有时候会造成数据破坏，利用破坏的值进行运算，结果可想而知，所以，如果没返回值时，一般不要用。4 为了避免重复检测入度为零的顶点，源程序中设了一个栈，暂存所有入度为零的顶点，此程序段书写如下：InitStack(S); for (i=0;inext)k=p-adj;