数据结构课程设计-拓扑排序算法实现

1、河南工程学院数据结构与算法课程设计成果报告拓扑排序算法实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1342 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目拓扑排序算法实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩

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

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

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

5、序和全序的定义：若集合X上的关系R是自反的，反对称的和传递的，则称R是集合X上的偏序关系。设R是集合X上的偏序，如果对每个x，yX必有xRy或yRx，则称R是集合X上的全序关系。直观地看，偏序指集合中仅有部分成员之间可比较，而全序指集合中全体成员之间均为可比较。例如，下图所示的两个有向图，图中弧x,y表示xy，则（a）表示偏序，（b）表示全序。若在（a）的有向图上人为地加一个表示23的弧，则（a）表示的亦为全序，且这个全序称为拓扑有序，而由偏序定义得到拓扑有序的操作便是拓扑排序。一个表示偏序的有向图可用来表示一个流程图。它或者是一个施工流程图，或者是一个产品生产流程图，再或者是一个数据流图（每

6、一个顶点表示一个过程）。图中的每一条有向边表示两个子工程之间的次序关系（领先关系）。13421234（a） （b）2.2 存储结构设计 1.采用邻接表作为有向图的存储结构，且需要编写计算顶点入度的函数FindInDegre0（）。删除入度为零的顶点，及以它为尾的弧的操作，可以换以弧头顶点入度减一来实现。避免重复检测入度为零的顶点，需另设一栈存储所有入度为零的顶点。当有向图上某一顶点入度为零则将该顶点入栈，栈不为空时输出栈顶，并将与该元素邻接的顶点的入度减一，若减一后，入度为零，则继续入栈重复上述步骤。2.操作的结果：（1）全部顶点被输出，网中没有回路。（2）未输出全部顶点，剩余顶点均有前驱，网

7、中有回路。3.主要数据结构：（1）图的邻接表存储形式;typedef char VertexType20;/顶点信息（名称）typedef struct ArcNode/链表结点int vexpos;/该弧所指向的顶点在数组中的位置struct ArcNode *next;/指向当前起点的下一条弧的指针ArcNode;typedef struct VNode/头结点VertexType name;/顶点信息（名称）int indegree;/顶点入度ArcNode *firstarc;/指向当前顶点的第一条弧的指针VNode,AdjListMAX_VERTEX_NUM;typedef stru

8、ctAdjList vexhead;/邻接表头结点数组int vexnum,arcnum;/图的顶点数和弧数ALGraph;（2）链式队列的存储类型为：typedef int ElemType;typedef struct QNodeElemType data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;2.3 算法描述1、采用邻接表存储结构实现有向图；有向图需通过顶点数、弧数、顶点以及弧等信息建立。2、拓扑排序算法void TopologicalSort(ALG

9、raph G) 中，先输出入度为零的顶点，而后输出新的入度为零的顶点，此操作可利用栈或队列实现。考虑到教学计划安排的实际情况，一般先学基础课（入度为零），再学专业课（入度不为零），与队列先进先出的特点相符，故采用队列实现。3、拓扑排序算法void TopologicalSort(ALGraph G)，大体思想为：1)遍历有向图各顶点的入度，将所有入度为零的顶点入队列；2)队列非空时，输出一个顶点，并对输出的顶点数计数；3)该顶点的所有邻接点入度减一，若减一后入度为零则入队列；4)重复2)、3)，直到队列为空，若输出的顶点数与图的顶点数相等则该图可拓扑排序，否则图中有环。4、要对教学计划安排进行

10、检验，因此编写了检测用户输入的课程序列是否是拓扑序列的算法void TopSortCheck(ALGraph G)，大体思想为：1)用户输入待检测的课程序列，将其存入数组；2)检查课程序列下一个元素是否是图中的顶点（课程），是则执行3)，否则输出“课程XX不存在”并跳出；3)判断该顶点的入度是否为零，是则执行4)，否则输出“入度不为零”并跳出；4)该顶点的所有邻接点入度减一；5)重复2)、3)、4)直到课程序列中所有元素均被遍历，则该序列是拓扑序列，否则不是拓扑序列。2.4 程序流程图当拓扑排序开始时，输入顶点的及弧信息，输入的条件符合时，将会建立新的邻接表，而当入度为零时，将其入栈，弹出栈顶

11、，将与栈顶元素邻接的顶点的入度减一，当栈不为空是继续循环，为空时则输出拓扑排序。流程图如下：图2.4-1流程图3 程序清单#include#include#define true 1#define false 0#define MAX_VEXTEX_NUM 20#define M 20#define STACK_INIT_SIZE 100#define STACKINCREMENT 10/*-图的邻接表存储结构-*/typedef struct ArcNode /*弧结点结构类型*/ int adjvex; /*该弧指向的顶点的位置*/ struct ArcNode *nextarc; /*指

12、向下一条弧的指针*/ArcNode;typedef struct VNode /*邻接表头结点类型*/ int data; /*顶点信息*/ ArcNode *firstarc; /*指向第一条依附于该点的弧的指针*/ VNode,AdjListMAX_VEXTEX_NUM; /*AdjList为邻接表类型*/typedef struct AdjList vertices; int vexnum, arcnum;ALGraph;/*-*/void CreatGraph(ALGraph *G) /*通过用户交互产生一个图的邻接表*/ int m, n, i; ArcNode *p; printf

13、(=); printf(n输入顶点数:); scanf(%d,&G-vexnum); printf(n输入边数:); scanf(%d,&G-arcnum); printf(=); for (i=1; ivexnum;i+) /*初始化各顶点*/ G-verticesi.data=i; /*编写顶点的位置序号*/ G-verticesi.firstarc=NULL; for (i=1;iarcnum;i+) /*记录图中由两点确定的弧*/ printf(n输入确定弧的两个顶点u，v:); scanf(%d %d,&n,&m); while (nG-vexnum|mG-vexnum) print

14、f(输入的顶点序号不正确 请重新输入:); scanf(%d%d,&n,&m); p=(ArcNode*)malloc(sizeof(ArcNode); /*开辟新的弧结点来存储用户输入的弧信息*/ 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

15、=1;ivexnum;i+) printf(%d,G-verticesi.data); for(p=G-verticesi.firstarc;p;p=p-nextarc) printf(-%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*s

16、izeof(int); if(!S-base) /*存储分配失败*/ printf(ERROR!); exit(1); S-top=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!); ex

17、it(1); S-top=S-base+S-stacksize; S-stacksize+=STACKINCREMENT; *S-top+=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; else return false;/*-*/

18、void FindInDegree(ALGraph G, int indegree) /*对各顶点求入度*/ int i; for(i=1; i=G.vexnum;i+) /*入度赋初值0*/ indegreei=0; for(i=1;iadjvex+; /*出度不为零，则该顶点firstarc域指向的弧指向的顶点入度加一*/ G.verticesi.firstarc = G.verticesi.firstarc-nextarc; /*-*/void TopoSort(ALGraph G) int indegreeM; int i, k, n; int count=0; *初始化输出计数器*/

19、 ArcNode *p; SqStack S; FindInDegree(G,indegree); InitStack(&S); for(i=1;i=G.vexnum;i+) printf(n); printf(indegree%d = %d n,i,indegreei); /*输出入度*/ printf(n); for(i=1;inextarc)/*n号顶点的每个邻接点入度减一*/ k=p-adjvex; if(!(-indegreek) /*若入度减为零，则再入栈*/ Push(&S,k); if(countG.vexnum)/*输出顶点数小于原始图的顶点数，有向图中有回路*/ print

20、f(ERROR 出现错误!); else printf( 排序成功!);/*-*/main(void) /*编写主调函数以调用上述被调函数*/ ALGraph G; CreatGraph(&G); /*建立邻接表*/ TopoSort(G); /*对图G进行拓扑排序*/printf(nn); system(pause); /*调用系统的dos命令：pause;显示:按任意键继续.*/ return 0;4 测试4.1 测试数据（1）当输入无回路图： 1342（2）当输入带回路图:1342（3）输入检验图：1342675由邻接表定义可以得到上图的邻接表为：1234567 4 5 其中一种拓扑序列

21、： 2 7 1 3 4 6 54.2 测试结果分析（1）当输入无回路图：图4.2-1无回路图运行结果（2）当输入带回路图:图4.2-2带回路图运行结果（3） 输入检验图：图4.2-3输入检验图运行结果5 总结伴随着数据结构实训课程的结束，数据结构一个学期的学习也将要结束了，它同样意味着大二第一个学期学习已经接近了尾声，回顾这个学期的学习，这个实训阶段的学习，让我更加的认识到了数据结构的可爱与迷人之处，这时我也才突然发现原来我已经喜欢上了这门在开始时看似异常枯燥的课程，也是在这个时候我才算是对人们经常所说的做一行爱一行，做到了皮毛而已。我之所以选择拓扑排序这个课题，是因为我对它有着独一无二的情怀

22、，对它有着十分深刻的记忆。这个课题我记得十分清楚的是在周六时的实验楼学习的课题，对于一个周末就要赖床而且十分嗜睡的人来说，早起不言而喻是一件十分困难的事情，而周末早起更是难上加难，但是那个周六我竟是起的出奇的早，不为别的就为了那天数据结构的补课，其实这件事情到现在回想起来也会令我觉得出奇的，也许冥冥之中不说别的课题，可能真的与拓扑排序有缘吧。上课的时候，老师告诉我们拓扑排序的学习不需要大家完全掌握，因为知识的难度决定了它在平时的考试中是不会出现的，但考研的试题却又是将它看作为重中之重，听到老师这么说下来我对它便产生了一丝兴趣，而开始的时候并没有报多大的决心去了解和认识它，只是想着试试看而已，但

23、结果是我被拓扑排序迷住了，被AOV网迷住了，被最短路径迷住了。那天我有不懂的问题出现时，我出奇的没有像平时那样钻牛角尖的去想，也许是因为距离老师很近的原因，我竟毫不犹豫的大胆的选择了问老师，但当听完老师的讲解后，我才是真的茅塞顿开，才是真的明白了有问题要及时向老师请教的重要性。所以当实训的题目出现拓扑排序时，我没有什么犹豫直接选择了它，当别人在劝我不要没事找事时，劝我拓扑排序很麻烦时，我没有动摇，不为别的就因为我喜欢拓扑排序，喜欢AOV网，喜欢最短路径，仅此而已。两周后的数据结构的考试即将到来，而我也要再去做好最后的复习备考工作，成绩的好坏，才正是对我这个学期学习的最直接表达，所以说什么我也会

24、更加努力的复习，不为别的就为了，从开始坐第一排时不情愿，到现在的去上数据结构就坐第一排的习惯，从开始对它的烦躁与厌恶，到现在的有一丝丝的喜欢，我也会坚持下去。参考文献1 李春葆，数据结构习题与解析（C语言版）.清华大学出版社，20022严蔚敏，数据结构（ C语言版），清华大学出版社。3谭浩强，C语言程序设计，清华大学出版社。4朱福喜.Java语言程序设计（第二版）.科学出版社#include#include#define true 1#define false 0#define MAX_VEXTEX_NUM 20#define M 20#define STACK_INIT_SIZE 100#d

25、efine STACKINCREMENT 10/*-图的邻接表存储结构-*/typedef struct ArcNode /*弧结点结构类型*/ int adjvex; /*该弧指向的顶点的位置*/ struct ArcNode *nextarc; /*指向下一条弧的指针*/ArcNode;typedef struct VNode /*邻接表头结点类型*/ int data; /*顶点信息*/ ArcNode *firstarc; /*指向第一条依附于该点的弧的指针*/ VNode,AdjListMAX_VEXTEX_NUM; /*AdjList为邻接表类型*/typedef struct A

26、djList vertices; int vexnum, arcnum;ALGraph;/*-*/void CreatGraph(ALGraph *G) /*通过用户交互产生一个图的邻接表*/ int m, n, i; ArcNode *p; printf(=); printf(n输入顶点数:); scanf(%d,&G-vexnum); printf(n输入边数:); scanf(%d,&G-arcnum); printf(=); for (i=1; ivexnum;i+) /*初始化各顶点*/ G-verticesi.data=i; /*编写顶点的位置序号*/ G-verticesi.fi

27、rstarc=NULL; for (i=1;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(ArcNode); /*开辟新的弧结点来存储用户输入的弧信息*/ if(p=NULL) printf(ERROR!); exit(1); p-adjvex=m; /*该弧指向位置编号为m的结点*/ p-next

28、arc=G-verticesn.firstarc;/*下一条弧指向的是依附于n的第一条弧*/ G-verticesn.firstarc=p; printf(=); printf(n建立的邻接表为:n); /*打印生成的邻接表（以一定的格式）*/ for(i=1;ivexnum;i+) printf(%d,G-verticesi.data); for(p=G-verticesi.firstarc;p;p=p-nextarc) printf(-%d,p-adjvex); printf(n); printf(=);/*-*/typedef struct /*栈的存储结构*/ int *base; /

29、*栈底指针*/ int *top; /*栈顶指针*/ int stacksize;SqStack;/*-*/void InitStack(SqStack *S) /*初始化栈*/ S-base=(int *)malloc(STACK_INIT_SIZE*sizeof(int); if(!S-base) /*存储分配失败*/ printf(ERROR!); exit(1); S-top=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!); exit(1); S-top=S-base+S-stacksize; S-stacksize+=STACKINCREMENT; *S-top+=e; /*e作为新的栈顶元素*/*-*/int Pop(SqStack *S,int