拓扑排序算法实现1.docx

《拓扑排序算法实现1.docx》由会员分享，可在线阅读，更多相关《拓扑排序算法实现1.docx（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、河南工程学院数据结构与算法课程设计成果报告拓扑排序算法实现2014年12月29日G-verticesi. data=i ;/*编写顶点的位置序号*/G-vertices i. firstarc=NULL;)for (i=l; iarcnum; i+)/*记录图中由两点确定的弧*/(printf (n输入确定弧的两个顶点u, v:);scanf (%d %d，&n, &m);while (nG-vexnum| mG-vexnum) (printf(输入的顶点序号不正确 请重新输入:)； scanf (级d%d，&n, &m);p= (ArcNode*) malloc (sizeof (ArcNo

2、de) ; /*开辟新的弧结点来存 储用户输入的弧信息*/if(p=NULL)(printf (ERROR!);exit (1);)p-adjvex=m;/*该弧指向位置编号为m的结点*/p-nextarc=G-verticesn. firstarc;/*下一条弧指向的是依附于n的第一条弧*/ G-verticesn. firstarc=p;)printf (=)；printf (n建立的邻接表为:n);/*打印生成的邻接表(以一定的格式)*/ for (i=l;ivexnum;i+)(printf (级d, G-vertices i. data);for(p=G-verticesi. fir

3、starc;p;p=p-nextarc)printf (，z-%d, p-adjvex);printf(n);printf ( */typedef struct/*栈的存储结构*/int *base;int *top;int stacksize;/*栈底指针*/*栈顶指针*/*栈底指针*/*栈顶指针*/SqStack;void InitStack(SqStack *S)/*初始化栈*/(S-base=(int *)malloc(STACK_INIT_SIZE*sizeof(int);if (!S-base)/*存储分配失败*/printf (ERROR !z/);exit (1);S-top=

4、S-base;S-stacksize=STACK_INIT_SIZE;/*/void Push(SqStack *S, int e)/*压入新的元素为栈顶*/(if (S-top-S-base=S-stacksize)(S-base=(int*)realloc(S-base, (S-stacksize+STACKINCREMENT)*sizeof(int);/*追加新空间*/if (! S-base)/*存储分配失败*/(printf (ERROR!，z);exit (1);)S-top=S-base+S-stacksize;S-stacksize+=STACKINCREMENT;)*S-to

5、p+=e;/*e作为新的栈顶元素*/int Pop (SqStack *S, int *e)/*弹出栈顶，用e返回*/)/*栈为空*/if(S-top=S-base)return false;*e=*一S-top;return 0;)/*/int StackEmpty (SqStack S) /*判断栈是否为空，为空返回1,不为空返回0*/ if (S-top-S-base)return true;elsereturn false;void FindlnDegree (ALGraph G, int indegree)/*对各顶点求入度*/int i;for (i=l; i=G. vexnum;

6、 i+)/*入度赋初值 0*/indegreei=0;)for(i=l;iadjvex+;/*出度不为零，那么该顶点firstarc域指向的弧指向的顶点入度加一*/G.verticesi. firstarc =G.verticesi. firstarc-nextarc;void TopoSort(ALGraph G)int indegreeM;int i, k, n;int count=0;*初始化输出计数器*/ArcNode *p;SqStack S;FindlnDegree(G, indegree);InitStack(&S);for (i=l;i=G. vexnum;i+)(printf

7、(n);printf (z，indegree%d二 %d n，z, i, indegreei) ;/*输出入度*/printf (n);for (i=l; inextarc)/*n号顶点的每个邻接点入度减一*/k=p-adjvex;if (! (-indegreek)/*假设入度减为零，那么再入栈*/|Push(&S, k);if (count3224344 indegree1 = 0 indegree2 = 1indegree3 = 1indegree4 = 2拓扑排序序列为：123 4排序成功?图4. 2-1无回路图运行结果13(2)当输入带回路图：输入顶点数：4输入边数：4输入确定弧的两

8、个顶点j v：l 3输入确定弧的两个顶点j v：3 2输入确定弧的两个顶点5 v：2 1输入确定弧的两个顶点j v：2 4港立前如1324132 4indegree1 = 1indegree L2 = 1indegree3 = 1indegree C4 = 1拓扑排序序列为:error出现错误？图4. 2-2带回路图运行结果(3)输入检验图：输入确定弧的两个顶点：7 63港立根曦虹13275334-4655 p|17 6KiSKa5550=第2个点的入度为。第3个点的入度为2第4个点的入度为1第5个点的入度为2第6个点的入度为2第7个点的入度为1拓扑排序序列为：2713456排序成功？1I2J

9、 色图4. 2-3输入检验图运行结果145总结伴随着数据结构实训课程的结束，数据结构一个学期的学习也将要结束了， 它同样意味着大二第一个学期学习已经接近了尾声，回顾这个学期的学习，这个 实训阶段的学习，让我更加的认识到了数据结构的可爱与迷人之处，这时我也才 突然发现原来我已经喜欢上了这门在开始时看似异常枯燥的课程，也是在这个时 候我才算是对人们经常所说的做一行爱一行，做到了皮毛而已。我之所以选择拓 扑排序这个课题，是因为我对它有着独一无二的情怀,对它有着十分深刻的记忆。 这个课题我记得十分清楚的是在周六时的实验楼学习的课题，对于一个周末就要 赖床而且十分嗜睡的人来说，早起不言而喻是一件十分困难

10、的事情，而周末早起 更是难上加难，但是那个周六我竟是起的出奇的早，不为别的就为了那天数据结 构的补课，其实这件事情到现在回想起来也会令我觉得出奇的，也许冥冥之中不 说别的课题，可能真的与拓扑排序有缘吧。上课的时候，老师告诉我们拓扑排序 的学习不需要大家完全掌握，因为知识的难度决定了它在平时的考试中是不会出 现的，但考研的试题却又是将它看作为重中之重，听到老师这么说下来我对它便 产生了一丝兴趣，而开始的时候并没有报多大的决心去了解和认识它，只是想着 试试看而已，但结果是我被拓扑排序迷住了，被AOV网迷住了，被最短路径迷住 To那天我有不懂的问题出现时，我出奇的没有像平时那样钻牛角尖的去想，也 许

11、是因为距离老师很近的原因，我竟毫不犹豫的大胆的选择了问老师，但当听完 老师的讲解后，我才是真的茅塞顿开，才是真的明白了有问题要及时向老师请教 的重要性。所以当实训的题目出现拓扑排序时，我没有什么犹豫直接选择了它， 当别人在劝我不要没事找事时，劝我拓扑排序很麻烦时，我没有动摇，不为别的 就因为我喜欢拓扑排序，喜欢A0V网，喜欢最短路径，仅此而已。两周后的数据 结构的考试即将到来，而我也要再去做好最后的复习备考工作，成绩的好坏，才 正是对我这个学期学习的最直接表达，所以说什么我也会更加努力的复习，不为 别的就为了，从开始坐第一排时不情愿，到现在的去上数据结构就坐第一排的习 惯，从开始对它的烦躁与厌

12、恶，到现在的有一丝丝的喜欢，我也会坚持下去。15参考文献1李春葆，数据结构习题与解析（C语言版）.清华大学出版社，20022严蔚敏，数据结构（C语言版），清华大学出版社。3谭浩强，C语言程序设计，清华大学出版社。4朱福喜.Java语言程序设计（第二版）.科学出版社16题目拓扑排序算法实现考核工程考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、 基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答下列问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报

13、告源代码（5分）按照规范要求完成课程设计源代码的排版总评成绩指导教师评语：日期：年 月 日目录31课程设计目标与任务11.1 课程设计目标11.2 课程设计任务11.3 课程设计基本要求12分析与设计22.1 题目需求分析22.2 存储结构设计22.4 程序流程图43程序清单54测试124.1 测试数据124.2 测试结果分析13参考文献161课程设计目标与任务1.1课程设计目标数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学 是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计 基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作 方法学

14、生通过数据结构课程设计各方面得到锻炼：（1）能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算 法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决 问题的有效算法；（2）通过上机实习，验证自己设计的算法的正确性，学会有效利用基本调试 方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进 一步提高程序设计水平；（4）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图 形方式显示出来,将复杂的运行过程以动态方式显示出来，获得算法的直观感受。 1. 2课程设计任务设计拓扑排序算法的相关函数库，以便在程序设计

15、中调用，要求：（1）选择合适的结构存储图，在此基础上实现拓扑排序算法；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图 形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出假设干例程，演示通过调用自己所缩写程序来实现相关问题的求解。1. 3课程设计基本要求严格按照题意要求，独立进行设计，不能随意更改。假设确因条件所限，必须 要改变课题要求时，应在征得指导教师同意的前提下进行。学生应制定设计工作 计划，认真完成设计的各个环节，并在老师的指导下认真组织设计工作，撰写设 计报告，做好设计总结。2分析与设计1题目需求分析什么是拓扑排序？简单地说，由某个集合上的一个偏序得到该

16、集合上的一个 全序，这个操作称之为拓扑排序。回顾离散数学中关于偏序和全序的定义：假设集合X上的关系R是自反的，反对称的和传递的，那么称R是集合X上的偏 序关系O设R是集合X上的偏序，如果对每个x, yX必有xRy或yRx,那么称R是集 合X上的全序关系。直观地看，偏序指集合中仅有局部成员之间可比拟，而全序指集合中全体成 员之间均为可比拟。例如，下列图所示的两个有向图，图中弧x,y表示xWy,那么 （a）表示偏序，（b）表示全序。假设在（a）的有向图上人为地加一个表示2W3 的弧，那么（a）表示的亦为全序，且这个全序称为拓扑有序，而由偏序定义得到 拓扑有序的操作便是拓扑排序。一个表示偏序的有向图

17、可用来表示一个流程图。它或者是一个施工流程图， 或者是一个产品生产流程图，再或者是一个数据流图（每一个顶点表示一个过 程）。图中的每一条有向边表示两个子工程之间的次序关系（领先关系）。(a)(b)2存储结构设计1 .采用邻接表作为有向图的存储结构，且需要编写计算顶点入度的函数 FindlnDegreO （）。删除入度为零的顶点，及以它为尾的弧的操作，可以换以弧 头顶点入度减一来实现。防止重复检测入度为零的顶点，需另设一栈存储所有入 度为零的顶点。当有向图上某一顶点入度为零那么将该顶点入栈，栈不为空时输出 栈顶，并将与该元素邻接的顶点的入度减一，假设减一后，入度为零，那么继续入栈 重复上述步骤。

18、2 .操作的结果：（1）全部顶点被输出，网中没有回路。（2）未输出全部顶点，剩余顶点均有前驱，网中有回路。3 .主要数据结构：（1）图的邻接表存储形式；typedef char VertexType20;顶点信息（名称）typedef struct ArcNode链表结点 int vexpos;该弧所指向的顶点在数组中的位置struct ArcNode *next;指向当前起点的下一条弧的指针ArcNode;typedef struct VNode头结点 VertexType name;顶点信息（名称） int indegree;顶点入度ArcNode *firstarc; 指向当前顶点的第一

19、条弧的指针 VNode, AdjListMAX_VERTEX_NUM;typedef struct AdjList vexhead;邻接表头结点数组 int vexnum, arcnum;图的顶点数和弧数 ALGraph;（2）链式队列的存储类型为：typedef int ElemType;typedef struct QNode ElemType data;struct QNode *next; QNode, *QueuePtr;typedef struct QueuePtr front;QueuePtr rear; LinkQueue;2. 3算法描述1、采用邻接表存储结构实现有向图；有向

20、图需通过顶点数、弧数、顶点以 及弧等信息建立。2、拓扑排序算法void TopologicalSort （ALGraph G）中，先输出入度为零 的顶点，而后输出新的入度为零的顶点，此操作可利用栈或队列实现。考虑到教 学计划安排的实际情况，一般先学基础课（入度为零），再学专业课（入度不为 零），与队列先进先出的特点相符，故采用队列实现。3、拓扑排序算法void TopologicalSort （ALGraph G）,大体思想为：1）遍历有向图各顶点的入度，将所有入度为零的顶点入队列；2）队列非空时，输出一个顶点，并对输出的顶点数计数；3）该顶点的所有邻接点入度减一，假设减一后入度为零那么入队列

21、；4）重复2）、3）,直到队列为空，假设输出的顶点数与图的顶点数相等那么该图 可拓扑排序，否那么图中有环。4、要对教学计划安排进行检验，因此编写了检测用户输入的课程序列是否 是拓扑序列的算法void TopSortCheck （ALGraph G）,大体思想为：1）用户输入待检测的课程序列，将其存入数组；2）检查课程序列下一个元素是否是图中的顶点（课程），是那么执行3）,否 那么输出“课程XX不存在”并跳出；3）判断该顶点的入度是否为零，是那么执行4）,否那么输出“入度不为零”并 跳出；4）该顶点的所有邻接点入度减一；5）重复2）、3）、4）直到课程序列中所有元素均被遍历，那么该序列是拓扑序

22、列，否那么不是拓扑序列。2.4程序流程图当拓扑排序开始时，输入顶点的及弧信息，输入的条件符合时，将会建立新 的邻接表，而当入度为零时，将其入栈，弹出栈顶，将与栈顶元素邻接的顶点的 入度减一，当栈不为空是继续循环，为空时那么输出拓扑排序。流程图如下:图2.47流程图3程序清单#include#include#define true 1#define false 0ftdefine MAX_VEXTEX_NUM 20define M 20ftdefine STACK_INIT_SIZE 100ftdefine STACKINCREMENT 10图的邻接表存储结构typedef struct Arc

23、Node int adjvex;struct ArcNode *nextarc;ArcNode;typedef struct VNodeint data;ArcNode *firstarc;VNode, AdjListMAX_VEXTEX_NUM;typedef structAdjList vertices;int vexnum, arcnum;ALGraph;/*void CreatGraph(ALGraph *G)(int m, n, i;ArcNode *p;typedef struct ArcNode int adjvex;struct ArcNode *nextarc;ArcNode

24、;typedef struct VNodeint data;ArcNode *firstarc;VNode, AdjListMAX_VEXTEX_NUM;typedef structAdjList vertices;int vexnum, arcnum;ALGraph;/*void CreatGraph(ALGraph *G)(int m, n, i;ArcNode *p;/*弧结点结构类型*/ *该弧指向的顶点的位置*/*指向下一条弧的指针*/*邻接表头结点类型*/*顶点信息*/*指向第一条依附于该点的弧的指针*/AAdjList为邻接表类型*/*通过用户交互产生一个图的邻接表*/printf；printf (n输入顶点数:);scanf (/d, &G-vexnum);printf (n 输入边数:);scanf(d，&G-arcnum);for (i=l; ivexnum; i+)/*初始化各顶点*/