数据结构课程设计有向图的拓扑排序.doc

《数据结构课程设计有向图的拓扑排序.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计有向图的拓扑排序.doc（37页珍藏版）》请在三一办公上搜索。

1、沈阳航空航天大学课 程 设 计 报 告课程设计名称：数据结构课程设计课程设计题目：有向图的拓扑排序院（系）：计算机学院专 业：计算机科学与技术 班 级：学 号：姓 名： 指导教师： 此页为任务书目 录沈阳航空航天大学II第一章 需求分析11.1 题目的内容与要求11.2 程序实现的功能1第二章 概要设计22.1 算法思想22.2 系统功能模块图3第三章 详细设计52.2 系统流程设计53.2 数据结构63.2.1 图63.2.2 栈63.3 具体实现函数73.3.1 程序所需头文件及全局变量73.3.2 栈操作73.3.2 有向图(DAG)邻接表存储结构(ALG)的操作83.3.3 拓扑排序8

2、3.3.4 简单绘图函数9第四章 调试分析104.1 调试数据及结果104.2 遇到的困难、错误及修改11第五章 用户使用说明与执行结果12参考文献21附 录（关键部分程序清单）22第一章 需求分析1.1 题目的内容与要求本程序要求用合适方便的方式输入一个有向图，而且该有向图在程序中采用邻接表的存储结构存储，然后对该有向图进行拓扑排序。如果输入的有向图有环存在，程序需要给出图中有环的结果，否则，程序需要输出对图进行拓扑排序的结果。要求有向图的输入要尽量的简单、简便，能用图形形象的显示出输入的有向图，使其可以形象方便的观察。能够用动态图形形象的演示拓扑排序的具体过程。1.2 程序实现的功能1.简

3、便的输入一个有向图。2.在图形界面上显示出有向图。3.在图形界面上形象的用动态图形演示拓扑排序的具体过程。4.程序可以判断输入的有向图是否有环。有环时，输出有环无法排序的结果；无环时，输出拓扑排序的结果。第二章 概要设计2.1 算法思想1采用邻接表存储结构实现有向图；有向图需通过顶点数、弧数、顶点以及弧等信息建立。2 拓扑排序算法void TopologicalSort(ALGraph G) 中，先输出入度为零的顶点，而后输出新的入度为零的顶点，此操作可利用栈实现。3 拓扑排序算法void TopologicalSort(ALGraph G)，大体思想为： 1)遍历有向图各顶点的入度，将所有入

4、度为零的顶点入栈； 2)栈非空时，输出一个顶点，并对输出的顶点数计数； 3)该顶点的所有邻接点入度减一，若减一后入度为零则入栈； 4)重复2)、3)，直到栈为空，若输出的顶点数与图的顶点数相等则该图可拓扑排序，否则图中有环。5)重复2)、3)、4)直到序列中所有元素均被遍历，则该序列是拓扑序列，否则不是拓扑序列。4 算法的时间复杂度和空间复杂度拓扑排序实际是对邻接表表示的图G进行遍历的过程，每次访问一个入度为零的顶点，若图G中没有回路，则需扫描邻接表中的所有边结点，在算法开始时，为建立入度数组D需访问表头向量中的所有边结点，算法的时间复杂度为O(n+e)。2.2 系统功能模块结构图本程序共分为

5、4大模块，有向图创建模块、拓扑排序模块、拓扑排序核心算法模块、绘图模块。有向图创建模块输入有向图的信息将有向图信息存入邻接表中在屏幕上输出有向图图3.1.1 有向图创建模块图拓扑排序模块拓扑排序核心算法模块在屏幕上动态演示排序判断是否有环图3.1.2 拓扑排序模块图绘图模块画圆函数画线函数图3.1.3 绘图模块图拓扑排序核心算法模块栈操作求顶点入度0入度出栈，其余顶点入度减1图3.1.4 拓扑排序核心算法模块图第三章 详细设计否开始输入顶点及弧的信息输入符合条件？根据输入信息建立邻接表，建立有向图，并在图形界面上绘制出有向图。建立栈在邻接表中寻找入度为0的顶点，将其顺序入栈进行拓扑排序，将栈顶

6、元素出栈，并在图形界面当中演示排序过程；将与栈顶元素邻接的顶点的入度减一判断栈是否为空结束是否是2.2 系统流程设计图2.1 系统流程图3.2 数据结构3.2.1 图typedef char VertexTypeMAX_NAME;/ 字符串类型 typedef struct ArcNodeint adjvex;/ 该弧所指向的顶点的位置 struct ArcNode *nextarc;/ 指向下一条弧的指针 ArcNode;/ 表结点 typedef struct VNodeVertexType data;/ 顶点信息 ArcNode *firstarc;/ 第一个表结点的地址,指向第一条依附

7、该顶点的弧的指针 VNode,AdjListMAX_VERTEX_NUM;/ 头结点 typedef structAdjList vertices;int vexnum,arcnum;/ 图的当前顶点数和弧数 int kind;/ 图的种类标志 ALGraph3.2.2 栈typedef int SElemType; / 栈类型 #define STACK_INIT_SIZE 10/ 存储空间初始分配量 #define STACKINCREMENT 2/ 存储空间分配增量 / 栈的顺序存储表示typedef struct SqStackSElemType *base;/ 在栈构造之前和销毁之后

8、，base的值为NULL SElemType *top;/ 栈顶指针 int stacksize;/ 当前已分配的存储空间，以元素为单位 SqStack;/ 顺序栈3.3 具体实现函数3.3.1 程序所需头文件及全局变量#include #include #include #include #include #include #define MAX_NAME 3 / 顶点字符串的最大长度为3 #define MAX_VERTEX_NUM 20#define M 8 /800*600屏幕上定义8个点用来画顶点圆int xM= 50,250,450,650,750,650,450,250;int

9、yM=250, 50, 50,150,250,350,450,450;3.3.2 栈的操作1) int InitStack(SqStack *S)功能：初始化栈。构造一个空栈S参数：*S 待初始化的栈2) int StackEmpty(SqStack S)功能：判断空栈参数：S 待判断的栈返回值：栈为空返回 1；栈非空返回 03) int Push(SqStack *S, SElemType e)功能：元素入栈参数：*S 待操作的栈；插入元素e为新的栈顶元素4) int Pop(SqStack *S,SElemType *e)功能：元素出栈参数：*S 待操作的栈；若栈不空，则删除S的栈顶元素，

10、用e返回其值，并返回1；否则返回03.3.2 有向图(DAG)邻接表存储结构(ALG)的操作1) int LocateVex(ALGraph G,VertexType u)功能：顶点在头结点数组中的定位参数：G 待操作的图；u 要在图中定位的顶点返回值：若G中存在顶点u,则返回该顶点在图中位置;否则返回-12) int CreateGraph(ALGraph *G)功能：建立图。函数内包含了由用户输入顶点数、弧数、顶点以及弧的操作参数：*G 待操作的图返回值：图建立成功返回1；图建立失败返回03) void Display(ALGraph G)功能：输出图的邻接表G。用图形显示参数：G 待输出

11、的图4) void FindInDegree(ALGraph G,int indegree)功能：求顶点的入度参数：G 待操作的图，indegree储存每个顶点的入度的数组3.3.3 拓扑排序1) int TopologicalSort(ALGraph G)功能：实现拓扑排序，并在图形界面上演示排序过程参数：G 待进行拓扑排序的图错误判断：包含有向图是否有环的判断3.3.4 简单绘图函数1) void huayuan(int a,int b)功能：以(a,b)为圆心，半径30，画一个圆 参数：a、b圆心的x、y坐标值2) void huaxian(int a1,int b2,int c3,in

12、t d4)功能：从起点(a1,b2)到终点(c3,d4)画一条直线参数：(a1,b2) 起点坐标，(c3,d4) 终点坐标第四章 调试分析4.1 调试数据及结果1、对“建立有向图并输出”的测试 1) 正确的有向图信息 顶点数和弧数:4,3 顶点:A B C D 边: A BB CC D 结果：A B C 为一个拓扑排序序列 2) 错误的边 顶点数和弧数:4,3 顶点:A B C D 边: A BB CC E 结果：无法建立有向图 3) 错误的顶点数或弧数 顶点数和弧数:3,7 结果：此有向图有回路，无法进行拓扑排序！ 2、对“建立有向图并求一个拓扑排序序列”的测试 1) 有向图能实现拓扑排序

13、顶点数和弧数:5,5 顶点:A B C D E 边:A DD CC BE AE C 结果：B为一个拓扑排序序列 2) 有向图不能实现拓扑排序 顶点数和弧数:4,4 顶点:a b c d 边:ab ba cd dc 结果：此有向图有回路，无法进行拓扑排序！4.2 遇到的困难、错误及修改1.VC+6.0环境下无法绘图。解决办法：在上找到绘图库EasyX，可以在VC+6.0上画图。2. 在绘图界面里不好确定下一个顶点的位置。解决方法：自定义8个点用作顶点的圆心位置，放在一个数组中，使用时按顺序取用。缺点是扩展性不强。3. 画线时，线画到了顶点圆内了。解决方法：大致估算一下圆心与参考点的距离，在坐标上

14、各加减适当的距离，使线差不多与圆相切。第五章 用户使用说明与执行结果以下17张图是本程序的运行截图，本程序使用方法一目了然。图5.1图5.2图5.3图5.4图5.5图5.6图5.7图5.8图5.9图5.10图5.11图5.12图5.13图5.14图5.15图5.16.图5.17参考文献1 严蔚敏，数据结构（ C语言版），北京，清华大学出版社, 20072 谭浩强，C语言程序设计，北京，清华大学出版社， 20033 4 附 录（关键部分程序清单）/* 数据结构C语言实现版 拓扑排序 编译环境：VC+6.0 日期：2012年2月16日 */程序所需头文件/#include #include #in

15、clude #include #include #include #define MAX_NAME 3 / 顶点字符串的最大长度+1 #define MAX_VERTEX_NUM 20#define M 8 /800*600屏幕上定义8个点用来画顶点圆int xM= 50,250,450,650,750,650,450,250;int yM=250, 50, 50,150,250,350,450,450;/图的邻接表存储表示/typedef char VertexTypeMAX_NAME;/ 字符串类型 typedef struct ArcNodeint adjvex;/ 该弧所指向的顶点的位

16、置 struct ArcNode *nextarc;/ 指向下一条弧的指针 ArcNode;/ 表结点 typedef struct VNodeVertexType data;/ 顶点信息 ArcNode *firstarc;/ 第一个表结点的地址,指向第一条依附该顶点的弧的指针 VNode,AdjListMAX_VERTEX_NUM;/ 头结点 typedef structAdjList vertices;int vexnum,arcnum;/ 图的当前顶点数和弧数 int kind;/ 图的种类标志 ALGraph;/ 采用邻接表存储结构,构造图G/ 若G中存在顶点u,则返回该顶点在图中位

17、置;否则返回-1。int LocateVex(ALGraph G,VertexType u)int i;for(i=0;iG.vexnum;+i)if(strcmp(u,G.verticesi.data)=0)return i;return -1;int CreateGraph(ALGraph *G)int i,j,k;VertexType va,vb;ArcNode *p;printf(本程序为有向图的拓扑排序，请确定输入图的类型为有向图，是，请输入0:n );scanf(%d,&(*G).kind);printf(请输入有向图的顶点数和边数,中间用空格间隔开来。nn);printf(请注意

18、，本程序目前只支持绘制8个顶点的有向图，改进升级版敬请期待。n);scanf(%d%d, &(*G).vexnum, &(*G).arcnum);printf(请输入%d个顶点的值(%d个字符):n,(*G).vexnum,MAX_NAME);for(i=0; i(*G).vexnum;+i)/ 构造顶点向量 scanf(%s, (*G).verticesi.data);(*G).verticesi.firstarc = NULL;printf(请顺序输入每条弧(边)的弧尾和弧头，每一条边一行，弧尾和弧头以空格作为间隔:n);for(k=0;kadjvex = j;p-nextarc = (*

19、G).verticesi.firstarc; / 插在表头 (*G).verticesi.firstarc = p;return 1;/输出图的邻接表G。用图形显示。/void huayuan(int a,int b) /画圆函数circle(a,b,30);void huaxian(int a1,int b2,int c3,int d4) /画线函数line(a1,b2,c3,d4);void Display(ALGraph G)int i;ArcNode *p;switch(G.kind)case 0: printf(输入的是有向图。n);break; /开始用EasyX画图/initgr

20、aph(800, 600); / 初始化图形窗口setbkcolor(HSLtoRGB(180,0.5,0.5);/设置背景色cleardevice();/清屏函数setcolor(RED);/设置绘图线条的颜色printf(%d个顶点：n,G.vexnum);/先画顶点圆for(i = 0; i G.vexnum; +i)getch();huayuan(xi,yi);outtextxy(xi-5,yi-5,G.verticesi.data);printf(%s ,G.verticesi.data); /延时一秒/ /Sleep(1000);printf(n%d条弧(边):n, G.arcnu

21、m);/再画连线，找点的指针使线变for(i = 0; i G.vexnum; i+)p = G.verticesi.firstarc;while(p)if(G.kind adjvex-20,yp-adjvex+20);printf(%s%s ,G.verticesi.data,G.verticesp-adjvex.data);p=p-nextarc;printf(n);/ 求顶点的入度/void FindInDegree(ALGraph G,int indegree) int i;ArcNode *p;for(i=0;iG.vexnum;i+)indegreei=0; / 赋初值 for(i

22、=0;iadjvex+;p=p-nextarc;/.栈操作./typedef int SElemType; / 栈类型 #define STACK_INIT_SIZE 10/ 存储空间初始分配量 #define STACKINCREMENT 2/ 存储空间分配增量 / 栈的顺序存储表示typedef struct SqStackSElemType *base;/ 在栈构造之前和销毁之后，base的值为NULL SElemType *top;/ 栈顶指针 int stacksize;/ 当前已分配的存储空间，以元素为单位 SqStack;/ 顺序栈/初始化栈。构造一个空栈S。int InitSt

23、ack(SqStack *S)/ 为栈底分配一个指定大小的存储空间(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if( !(*S).base ) / 存储分配失败 printf(存储空间分配失败,请按任意键退出本程序，清空内存后，再运行本程序。n);getch();exit(0);(*S).top = (*S).base;/ 栈底与栈顶相同表示一个空栈(*S).stacksize = STACK_INIT_SIZE;return 1;/判断栈是否为空栈。若栈S为空栈（栈顶与栈底相同的），则返回1，否则返回0。

24、int StackEmpty(SqStack S)if(S.top = S.base)return 1;elsereturn 0;/入栈函数。插入元素e为新的栈顶元素。int Push(SqStack *S, SElemType e)if(*S).top - (*S).base = (*S).stacksize)/ 栈满，追加存储空间 (*S).base = (SElemType *)realloc(*S).base, (*S).stacksize + STACKINCREMENT) * sizeof(SElemType);if( !(*S).base )exit(0); / 存储分配失败 (

25、*S).top = (*S).base+(*S).stacksize;(*S).stacksize += STACKINCREMENT;*(*S).top)+=e;/ 这个等式的+ * 优先级相同，但是它们的运算方式，是自右向左return 1;/出栈函数。若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回0。int Pop(SqStack *S,SElemType *e)if(*S).top = (*S).base)return 0;*e = *-(*S).top;/ 这个等式的+ * 优先级相同，但是它们的运算方式，是自右向左return 1;/拓扑排序算法，C语言实现的。/i

26、nt TopologicalSort(ALGraph G)/有向图G采用邻接表存储结构。int i,m=0,k,count,indegreeMAX_VERTEX_NUM;SqStack S;ArcNode *p;char we2;/若G无回路，则输出G的顶点的一个拓扑排序列并返回OK，否则ERROR。 FindInDegree(G,indegree); /对各顶点求入度indegree0.vernum-1 InitStack(&S); /初始化栈for(i=0;inextarc)k=p-adjvex; /对i号顶点的每一个邻接点的入度减1 if(!(-indegreek) /若入度减为0，则入

27、栈 Push(&S,k);setcolor(HSLtoRGB(180,0.5,0.5);/设置绘图线条的颜色为背景色，使顶点消失getch(); huayuan(xk,yk);outtextxy(xk-5,yk-5,G.verticesi.data);huaxian(xi+20,yi-20,xp-adjvex-20,yp-adjvex+20);/for/whilegetch();setcolor(RED);if(countG.vexnum) /该有向图有回路outtextxy(200,550,-此有向图有回路,无法进行拓扑排序！-);printf(此有向图有回路,无法进行拓扑排序！n); re

28、turn 0;else outtextxy(200,550,为其中一个拓扑排序序列。);printf(为其中一个拓扑排序序列。n);return 1;/TopologicalSort/-主函数-/int main()ALGraph f; /创建有向图CreateGraph(&f);printf(有向图创建成功！n); /输出有向图Display(f); /对有向图进行拓扑排序，输出结果TopologicalSort(f);getch(); / 按任意键继续 closegraph(); / 关闭图形窗口system(pause);return 0; / 程序结束/课程设计总结：这次课程设计让我进

29、一步认识到数据结构与算法在程序设计中的重要作用，我所使用的绘图库和C语言知识只是工具，帮助我实现算法和思想的工具。拓扑排序在现实生活中有着广泛的应用，该算法核心比较简单，但循环思想却起着巨大的作用。平时我就比较爱好编程，有时候自己也会设想一些小程序，然后通过自己的努力来实现。在算法设计、程序调试的过程中，经常遇到看似简单但又无法解决的问题，这时候我容易灰心丧气，但我知道此时切不可烦躁，一定要冷静的思考，认真的分析；而解决问题，完成程序后，那种兴奋感与成就感也令人振奋。可以说编写程序既是一件艰苦的工作，又是一件愉快的事情。虽然平时对拓扑排序有一些了解，上课也学过，但真正应用到程序中，写出算法却一点也不简单。拓扑排序，首先需要有被排序的主体，也就是有向图，于是先要实现有向图的建立及相关操作；有向图的建立，我选择了节省存储空间的邻接表；拓扑排序要将图中零入度顶点先输出，可利用栈实现，总之，什么地方该用什么数据结构，该写出怎样的算法，都要经过精心分析和仔细考虑。在完成课程设计的过程中，我加深了对程序结构的了解程度，对各种语句理解也更透彻，学会了灵活运用全局变量。指导教师评语：指导教师(签字)： 年 月 日课程设计成绩