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

沈阳航空航天大学 课课 程程 设设 计计 报报 告告 课程设计名称：数据结构课程设计数据结构课程设计 课程设计题目：有向图的拓扑排序有向图的拓扑排序 院（系）：计算机学院 专 业：计算机科学与技术 班 级： 学 号： 姓 名： 指导教师： 沈阳航空航天大学课程设计报告 i 此页为任务书 沈阳航空航天大学课程设计报告 ii 目目 录录 沈阳航空航天大学沈阳航空航天大学ii 第一章第一章 需求分析需求分析.1 1.1 题目的内容与要求 .1 1.2 程序实现的功能 .1 第二章第二章 概要设计概要设计.2 2.1 算法思想.2 2.2 系统功能模块图.3 第三章第三章 详细设计详细设计.5 2.2 系统流程设计.5 3.2 数据结构.6 3.2.1 图6 3.2.2 栈6 3.3 具体实现函数 .7 3.3.1 程序所需头文件及全局变量7 3.3.2 栈操作7 3.3.2 有向图(dag)邻接表存储结构(alg)的操作8 3.3.3 拓扑排序8 3.3.4 简单绘图函数9 第四章第四章 调试分析调试分析.10 4.1 调试数据及结果 .10 4.2 遇到的困难、错误及修改 .11 沈阳航空航天大学课程设计报告 iii 第五章第五章 用户使用说明与执行结果用户使用说明与执行结果.12 参考文献参考文献.21 附附 录（关键部分程序清单）录（关键部分程序清单）.22 沈阳航空航天大学课程设计报告 1 第一章 需求分析 1.1 题目的内容与要求题目的内容与要求 本程序要求用合适方便的方式输入一个有向图，而且该有向图在程序中采用 邻接表的存储结构存储，然后对该有向图进行拓扑排序。 如果输入的有向图有环存在，程序需要给出图中有环的结果，否则，程序需 要输出对图进行拓扑排序的结果。 要求有向图的输入要尽量的简单、简便，能用图形形象的显示出输入的有向 图，使其可以形象方便的观察。能够用动态图形形象的演示拓扑排序的具体过程。 1.2 程序实现的功能程序实现的功能 1.简便的输入一个有向图。 2.在图形界面上显示出有向图。 3.在图形界面上形象的用动态图形演示拓扑排序的具体过程。 4.程序可以判断输入的有向图是否有环。有环时，输出有环无法排序的结果； 无环时，输出拓扑排序的结果。 沈阳航空航天大学课程设计报告 2 第二章 概要设计 2.1 算法思想算法思想 1 采用邻接表存储结构实现有向图；有向图需通过顶点数、弧数、顶点以及 弧等信息建立。 2 拓扑排序算法 void topologicalsort(algraph g) 中，先输出入度为零的顶 点，而后输出新的入度为零的顶点，此操作可利用栈实现。 3 拓扑排序算法 void topologicalsort(algraph g)，大体思想为： 1)遍历有向图各顶点的入度，将所有入度为零的顶点入栈； 2)栈非空时，输出一个顶点，并对输出的顶点数计数； 3)该顶点的所有邻接点入度减一，若减一后入度为零则入栈； 4)重复 2)、3)，直到栈为空，若输出的顶点数与图的顶点数相等则该图 可拓扑排序，否则图中有环。 5)重复 2)、3)、4)直到序列中所有元素均被遍历，则该序列是拓扑序列， 否则不是拓扑序列。 4 算法的时间复杂度和空间复杂度 拓扑排序实际是对邻接表表示的图 g 进行遍历的过程，每次访问一个入度为 零的顶点，若图 g 中没有回路，则需扫描邻接表中的所有边结点，在算法开始时， 为建立入度数组 d 需访问表头向量中的所有边结点，算法的时间复杂度为 o(n+e)。 沈阳航空航天大学课程设计报告 3 2.2 系统功能模块结构图系统功能模块结构图 本程序共分为 4 大模块，有向图创建模块、拓扑排序模块、拓扑排序核心算 法模块、绘图模块。 有向图创建模块 输入有向图的信息将有向图信息存入邻 接表中 在屏幕上输出有向图 图图 3.1.1 有向图创建模块图有向图创建模块图 拓扑排序模块 拓扑排序核心算法 模块 在屏幕上动态演示 排序 判断是否有环 图图 3.1.2 拓扑排序模块图拓扑排序模块图 沈阳航空航天大学课程设计报告 4 绘图模块 画圆函数画线函数 图图 3.1.3 绘图模块图绘图模块图 拓扑排序核心算法 模块 栈操作求顶点入度0 入度出栈，其余 顶点入度减 1 图图 3.1.4 拓扑排序核心算法模块图拓扑排序核心算法模块图 沈阳航空航天大学课程设计报告 5 第三章 详细设计 2.2 系统流程设计系统流程设计 图图 2.12.1 系统流程图系统流程图 否 开始 输入顶点及弧的信息 输入符合条件？ 根据输入信息建立邻接表，建立有 向图，并在图形界面上绘制出有向 图。 建立栈 在邻接表中寻找入度为 0 的顶点，将其顺序入 栈 进行拓扑排序，将栈顶元素出栈，并在图形界面当中演 示排序过程；将与栈顶元素邻接的顶点的入度减一 判断栈是否为空 结束 是 否 是 沈阳航空航天大学课程设计报告 6 3.2 数据结构数据结构 3.2.1 图图 typedef char vertextypemax_name; / 字符串类型 typedef struct arcnode int adjvex;/ 该弧所指向的顶点的位置 struct arcnode *nextarc; / 指向下一条弧的指针 arcnode; / 表结点 typedef struct vnode vertextype data;/ 顶点信息 arcnode *firstarc;/ 第一个表结点的地址,指向第一条依附该顶 点的弧的指针 vnode,adjlistmax_vertex_num;/ 头结点 typedef struct adjlist vertices; int vexnum,arcnum;/ 图的当前顶点数和弧数 int kind;/ 图的种类标志 algraph 3.2.2 栈栈 typedef int selemtype; / 栈类型 #define stack_init_size 10/ 存储空间初始分配量 #define stackincrement 2/ 存储空间分配增量 / 栈的顺序存储表示 typedef struct sqstack 沈阳航空航天大学课程设计报告 7 selemtype *base;/ 在栈构造之前和销毁之后，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 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；栈非空返回 0 沈阳航空航天大学课程设计报告 8 3) int push(sqstack *s, selemtype e) 功能：元素入栈 参数：*s 待操作的栈；插入元素 e 为新的栈顶元素 4) int pop(sqstack *s,selemtype *e) 功能：元素出栈 参数：*s 待操作的栈；若栈不空，则删除 s 的栈顶元素，用 e 返回其值， 并返回 1；否则返回 0 3.3.2 有向图有向图(dag)邻接表存储结构邻接表存储结构(alg)的操作的操作 1) int locatevex(algraph g,vertextype u) 功能：顶点在头结点数组中的定位 参数：g 待操作的图；u 要在图中定位的顶点 返回值：若 g 中存在顶点 u,则返回该顶点在图中位置;否则返回-1 2) int creategraph(algraph *g) 功能：建立图。函数内包含了由用户输入顶点数、弧数、顶点以及弧的操作 参数：*g 待操作的图 返回值：图建立成功返回 1；图建立失败返回 0 3) void display(algraph g) 功能：输出图的邻接表 g。用图形显示 参数：g 待输出的图 4) void findindegree(algraph g,int indegree) 功能：求顶点的入度 参数：g 待操作的图，indegree储存每个顶点的入度的数组 3.3.3 拓扑排序拓扑排序 1) int topologicalsort(algraph g) 功能：实现拓扑排序，并在图形界面上演示排序过程 参数：g 待进行拓扑排序的图 错误判断：包含有向图是否有环的判断 沈阳航空航天大学课程设计报告 9 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,int d4) 功能：从起点(a1,b2)到终点(c3,d4)画一条直线 参数：(a1,b2) 起点坐标，(c3,d4) 终点坐标 沈阳航空航天大学课程设计报告 10 第四章 调试分析 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) 有向图能实现拓扑排序 顶点数和弧数:5,5 顶点:a b c d e 边:a dd cc be ae c 结果：b 为一个拓扑排序序列 2) 有向图不能实现拓扑排序 顶点数和弧数:4,4 顶点:a b c d 沈阳航空航天大学课程设计报告 11 边:ab ba cd dc 结果：此有向图有回路，无法进行拓扑排序！ 4.2 遇到的困难、错误及修改遇到的困难、错误及修改 1.vc+6.0 环境下无法绘图。 解决办法：在 上找到绘图库 easyx，可以在 vc+6.0 上画图。 2. 在绘图界面里不好确定下一个顶点的位置。 解决方法：自定义 8 个点用作顶点的圆心位置，放在一个数组中，使用时按 顺序取用。缺点是扩展性不强。 3. 画线时，线画到了顶点圆内了。 解决方法：大致估算一下圆心与参考点的距离，在坐标上各加减适当的距离， 使线差不多与圆相切。 沈阳航空航天大学课程设计报告 12 第五章 用户使用说明与执行结果 以下 17 张图是本程序的运行截图，本程序使用方法一目了然。 图图 5.1 图图 5.2 沈阳航空航天大学课程设计报告 13 图图 5.3 图图 5.4 沈阳航空航天大学课程设计报告 14 图图 5.5 图图 5.6 沈阳航空航天大学课程设计报告 15 图图 5.7 图图 5.8 沈阳航空航天大学课程设计报告 16 图图 5.9 图图 5.10 沈阳航空航天大学课程设计报告 17 图图 5.11 图图 5.12 沈阳航空航天大学课程设计报告 18 图图 5.13 图图 5.14 沈阳航空航天大学课程设计报告 19 图图 5.15 图图 5.16 沈阳航空航天大学课程设计报告 20 . 图图 5.17 沈阳航空航天大学课程设计报告 21 参考文献 1 严蔚敏， 数据结构（ c 语言版） ，北京，清华大学出版社, 2007 2 谭浩强， c 语言程序设计 ，北京，清华大学出版社， 2003 3 4 沈阳航空航天大学课程设计报告 22 附 录（关键部分程序清单） /* 数据结构 c 语言实现版 拓扑排序 编译环境：vc+6.0 日期：2012 年 2 月 16 日 */ /程序所需头文件/ #include #include #include #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 arcnode int adjvex;/ 该弧所指向的顶点的位置 struct arcnode *nextarc; / 指向下一条弧的指针 arcnode; / 表结点 沈阳航空航天大学课程设计报告 23 typedef struct vnode vertextype data;/ 顶点信息 arcnode *firstarc;/ 第一个表结点的地址,指向第一条依附该顶 点的弧的指针 vnode,adjlistmax_vertex_num;/ 头结点 typedef struct adjlist vertices; int vexnum,arcnum;/ 图的当前顶点数和弧数 int kind;/ 图的种类标志 algraph; / 采用邻接表存储结构,构造图 g/ / 若 g 中存在顶点 u,则返回该顶点在图中位置;否则返回-1。 int locatevex(algraph g,vertextype u) int i; for(i=0;iadjvex = j; p-nextarc = (*g).verticesi.firstarc; / 插在表头 (*g).verticesi.firstarc = p; return 1; / 输出图的邻接表 g。用图形显示。/ void huayuan(int a,int b) /画圆函数 沈阳航空航天大学课程设计报告 25 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 画图/ initgraph(800, 600); / 初始化图形窗口 setbkcolor(hsltorgb(180,0.5,0.5);/设置背景色 cleardevice();/清屏函数 setcolor(red);/设置绘图线条的颜色 printf(“%d 个顶点：n“,g.vexnum);/先画顶点圆 for(i = 0; i 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;iadjvex+; p=p-nextarc; /.栈操作/ typedef int selemtype; / 栈类型 #define stack_init_size 10/ 存储空间初始分配量 #define stackincrement 2/ 存储空间分配增量 / 栈的顺序存储表示 typedef struct sqstack selemtype *base;/ 在栈构造之前和销毁之后，base 的值为 null selemtype *top;/ 栈顶指针 int stacksize;/ 当前已分配的存储空间，以元素为单位 sqstack;/ 顺序栈 /初始化栈。构造一个空栈 s。 int initstack(sqstack *s) / 为栈底分配一个指定大小的存储空间 (*s).base = (selemtype *)malloc(stack_init_size*sizeof(selemtype); if( !(*s).base ) / 存储分配失败 沈阳航空航天大学课程设计报告 28 printf(“存储空间分配失败,请按任意键退出本程序，清空内存后，再 运行本程序。n“); getch(); exit(0); (*s).top = (*s).base; / 栈底与栈顶相同表示一个空栈 (*s).stacksize = stack_init_size; return 1; /判断栈是否为空栈。若栈 s 为空栈（栈顶与栈底相同的） ，则返回 1，否则 返回 0。 int stackempty(sqstack s) if(s.top = s.base) return 1; else return 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); / 存储分配失败 (*s).top = (*s).base+(*s).stacksize; 沈阳航空航天大学课程设计报告 29 (*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 语言实现的。/ int 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); /对各顶点求入度 indegree0vernum-1 沈阳航空航天大学课程设计报告 30 initstack( /初始化栈 for(i=0;inextarc) k=p-adjvex; /对 i 号顶点的每一 个邻接点的入度减 1 if(!(-indegreek) /若入度减为 0，则入栈 push( 沈阳航空航天大学课程设计报告 31 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 /while getch(); setcolor(red); if(countg.vexnum) /该有向图有回路 outtextxy(200,550,“-此有向图有回路,无法进行拓扑