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

目 录

（自动生成）

1介绍 2 需求分析 3 总体设计（概要设计）

4详细设计 5调试（测试） 6课程设计总结 参考文献

1 课程设计介绍 ............................................................................................................ 1 1.1 课程设计目的 ....................................................................................................... 1 1.2 课程设计内容 ....................................................................................................... 1 1.2 课程设计要求 ....................................................................................................... 1 2 需求设计 .................................................................................................................... 3 2.1 课设题目粗略分析 ............................................................................................... 3 2.2 原理图介绍 ........................................................................................................... 4 2.2.1 功能模块图 ................................................................................................... 4 2.2.2 流程图分析 ................................................................................................... 4 3 需求分析 .................................................................................................................... 6 3.1 存储结构 ............................................................................................................... 6 3.2 算法描述 ............................................................................................................... 6 4.调试与分析 ................................................................................................................ 10 （1）调试过程 ........................................................................................................... 10 （2） 程序执行过程 ................................................................................................. 10 参考文献 ........................................................................................................................ 12 总结 ................................................................................................................................ 13 附 录（关键部分程序清单） .................................................................................. 14

I

湖南工学院课程设计报告

1 课程设计介绍

1.1 课程设计目的

（1）熟悉使用c语言编码程序，解决实际问题；

（2）了解数据结构与算法的设计方法，具备初步的分析和设计能力。

（3）初步掌握软件开发过程的分析能力，系统设计，程序编码，测试等基本能力。 （4）提高综合运用的能力，运用所学理论知识与分析能力。

1.2 课程设计内容

编写算法，编写函数实现图的拓扑排序：

1. 求所有顶点的入度 2. 实现进栈与处栈 3. 找相邻的顶点

1.2 课程设计要求

上交的成果的内容必须由以下四个部分组成，缺一不可

1． 上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）；

2． 上交程序的说明文件：（保存在.doc中）在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明；

3． 课程设计报告：（保存在word 文档中，文件名要求 按照\"姓名-学号-课程设计报告\"起名，如文件名为\"张三-001-课程设计报告\".doc ）按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成；

其中包括: a)概要设计

在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。

b）详细设计

各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）

1

湖南工学院课程设计报告

源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。

c）调试分析

测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。

4. 课设总结： （保存在word 文档中）总结可以包括 : 课程设计 过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容

2

湖南工学院课程设计报告

2 需求设计

2.1 课设题目粗略分析

本课设题目要求编写算法能够建立有向无环图，有向无环图，顾名思义，即一个无环的有向图，是一类较有向图更一般的特殊有向图。 其功能要求及个人在写程序时对该功能的实现作如下分析：

1. 将图以合适的方式存储起来。图有多种存储方式，其中最常用的存储方式有图的邻接矩阵和邻接表。本人在构思时使用邻接表来建立有向无环图，将其存储起来；

2. 求解该有向无环图的拓扑排序，并将其输出出来。若通过构造，建立了一个有向无环图，那么一定可以求出其拓扑排序，其原理比较简单。即统计每个节点的入度，将入度为0的结点提取出来，然后再统计剩下的结点的入度，再次将入度为零的结点提取出来，以此类推，这样就形成了一个序列，这样的序列就是该图的拓扑排序序列；

3. 拓扑排序算法应能够处理出现环的情况。个人在写程序时，考虑到构造图时，会有构造成有向有环图的情况，应该在运行程序时，提醒出来，然后重新输入有向无环图，知道输入正确为止。这样就有多次构造邻接表的问题，每一次构造邻接表时，都应该将原来错误的（不是无环图的）邻接表空间释放掉，否则，会变得混乱；

4. 输出除拓扑排序外，还要求输出邻接表数据。由于图是用邻接表存储的，所以很容易将其邻接表输出出来。

3

湖南工学院课程设计报告

2.2 原理图介绍

2.2.1 功能模块图

拓扑排序算法

图的存储

图的遍历

拓扑排序

邻接矩阵邻接表有环图遍历全部

无环图无法遍历入度为零入队列 输出队列

图2.1 功能模块图

2.2.2 流程图分析

根据程序的总的步骤，拟将整个流程分为三个模块。三个模块既相互又相互联系。具体分析如下：

1. 图像输入，根据题目要求，要能够建立一个有向无环图，这就要我们在程序中去建立。考虑到输入方式要尽量方便全面，采用输入弧的方式，输入每条弧的链接的两个结点，当输入-1时结束输入。这样再输入的时候，与相邻的两个结点的邻接矩阵对应的位置也做相应改变。

2. 判断图是不是有向无环图。当图为有向无环图时，则挑选完毕后，队列应该是满的，进行后续步骤。对于结点入队列的顺序，需要借助于visited数组。选取入度为零的结点，入队列，调整visited数组，循环进行。若队列不满，则输入的图不符合要求，应该重新输入。在程序中应做适当提醒，然后自动转模块1.，进行图的重新编辑。

4

湖南工学院课程设计报告

3. 拓扑排序。此时，所输入的弧应该是有向无环图了，下面进行拓扑排序。在判断它是否为无环图的过程中已经形成了一个满队列。接下来所要做的事情就是循环出队列，按照队列固有的顺序进行输出即可，排序完成。

是 循环出队列 结束 图2.2 程序流程图

否 满队列 无环图 图形输入 开始 否构造邻接表，并将其输出 是 入度为零入队列 调整visited 5

湖南工学院课程设计报告

3 需求分析

3.1 存储结构

一个无环的有向图叫做有向无环图，简称DAG图。本算法首先要建立一个有向五环图，即通过输入各边的数据，搭建图的结构。 对于图的存储，用到邻接表，是一种链式存储结构。

typedef struct Node {

int data;

struct Node *next;

}GraphNode;

GraphNode vexs[maximum];

对于用来排序的队列Queue，则用到了顺序存储结构的队列，用数组表示。 int Queue[maximum];

3.2 算法描述

1. 邻接表的构造：

本算法借用图的邻接矩阵构造邻接表，其形式如下：

int Graph[maximum][maximum];

对于相邻的结点i和j，Graph[i][j]=1，若不相邻，则Graph[i][j]=0；对于邻接表的存储结构，上面已作说明，定义一个GraphNode类型的数组变量vexs[maximum]和一个GraphNode类型的指针变量*newnode。若两个结点i和j相邻（由i指向j，Graph[i][j]=1），则在vexs[maximum]第i行添加以j为值的newnode数据，即vexs[i-1]->next=*newnode。其中newnode->data=j，newnode->next=NULL。直到遍历完整个邻接矩阵，邻接表随即建立完成。简单算法说明如下：

for(i=0;ifor(j=0;j6

湖南工学院课程设计报告

{

if(Graph[i][j])

CreateAdjacentTable(i,j); //当邻接矩阵Graph[i][j]有值时，则构

造邻接表

}

2. 队列初始化（入队操作）及出队操作

在本算法中队列主要用来，构造拓扑排序序列。由于队列具有先入先出的特点，所以，将每次选择入度为零的结点入队，这样当结点都入队的时候，再依次出队，这样，排序序列显而易见。它将图这样的非线性结构转化为队列这样的线性结构。

（1） 队列初始化：

void addqueue(int *queue,int x)//入队操作 { }

（2） 出队操作：

int delqueue(int *queue)//出队操作 {

int e; if(rear==front) {

return -2; if(rear==l-1) { } rear++; queue[rear]=x; return;

printf(\"队列已满\\n\"); return;

7

湖南工学院课程设计报告

}

front++; }

3. 拓扑排序

本程序的拓扑排序，必须在图的邻接表已知的情况下。它还有另外一个功能：判断一个图是不是无环图。确切的说，不能单纯的叫拓扑排序，但考虑它主要的作用，在不引起误解的情况下就叫拓扑排序算法。

判断一个图是否为有向无环图并进行拓扑排序，判定方法有很多种，检查一个有向图是否存在环要比无向图复杂。对于无向图来说，若深度优先遍历过程中遇到回边（即指向已访问过的顶点的边），则必存在环；而对于有向图来说，这条回边有可能指向深度优先森林中另一棵生成树上顶点的弧。但是，如果从有向图上某个顶点v出发的遍历，在dfs(v)结束之前出现一条从顶点u到顶点v的回边，由于u在生成树上是v的子孙，则有向图中必定存在包含顶点v和u的环。

另一种判断是否有环的方法则显得简单的多，尤其是对于本题目来说，由于本题要求是对有向无环图进行拓扑排序，其主要方法是将入度为零的结点依次输出出来，知道图的所有定点全部输出为止。那么若图为有环图，在环上的结点在其他结点都选择出来后，入度都不为零，即无法被输出出来。那么就可以认为按照拓扑排序的方法输出结点后，若不是将节点全部输出出来的，则此图为有环图。

判断好图是否为有向图后，考虑到题目要求，要能够处理出现环的情况，若构造的图为有环图，则折回开始重新输入图的数据，重新构造图，直到该图为无环图为止。若图已经是无环图，则进行拓扑排序，排序方法前面已经讲过，在此主要诉说用到的辅助存储。数组visited[]存储各结点的入度，对入度为零的结点，依次入队列Queue，调整visited[]数组，结点全部入队列后，然后依次出队列，拓扑排序完成。

void TopoSort(int *visited,int *Queue)

8

e=queue[front]; queue[front]=0; return e;

湖南工学院课程设计报告

{ }

int i; rear=-1; front=-1; int topnum=0,ml[maximum],n=0; GraphNode *p; for(i=0;inext; while(p!=NULL) {visited[(p->data)-1]++; p=p->next;}} while(topnum!=l) { for(i=0;inext; while(p!=NULL) {visited[(p->data)-1]--; p=p->next;} visited[i]=-1; } } topnum++; }

for(i=0;iif(n==l) {

printf(\"拓扑排序为：\\n\"); for(i=0;i\");} jj=1; }

printf(\"\\n\");

9

湖南工学院课程设计报告

4.调试与分析

（1）调试过程

在调试程序是主要遇到以下几类问题：

1. 数组的数据容易出现混乱，比如结点用数字标识，数组结点的位置是从0开始，而标识符往往从1开始，这在程序的开始就应该注意到；

2. 各函数的形参，实参的区别，全局变量，局部变量的区别，特别是在做大型程序的时候，如果多个函数都要用到一个变量，那么就应把该变量定义为全局变量，若错误的定义为局部变量，很容易出现错误；

3. 对于一个程序，对于出现不同情况应能够正确处理，比如对本题而言，是对有向无环图进行拓扑排序。若经过错误的构造，该图是有环图，则应该提示该图是有环图，并自动重新输入该图，开始的时候由于缺乏考虑，会导致有环图也像无环图一样进行“拓扑排序”。

4. 程序应该条例清晰，结构明朗，各个函数代表各个模块，起到不同的作用，并协调运作，形成含有不同功能的程序。开始时因为程序的结构混乱而导致很难调试，无法找到错误的根源。

（2） 程序执行过程

1. 对于有向无环图，以图4.2.1为例进行拓扑排序：

2 3 1 6 4 图4.1 有向无环图

5 程序运行结果如图4.2.2所示：

10

湖南工学院课程设计报告

图4.2 有向无环图拓扑排序

2. 对于有向有环图，以图4.2.3为例：

2

1 4

图4.3 有向有环图

3 6 5 程序运行结果如图4.2.4所示：

图4.4 有向有环图程序运行结果

11

湖南工学院课程设计报告

参考文献

[1] 数据结构教材 [2] www.baidu.com

[3] 谭浩强.C程序设计[M].北京：清华大学出版社，2005.

12

湖南工学院课程设计报告

总结

课程设计总结： 每一次课设都是对自己综合能力的提高，这次也不例外。数据结构是一门应用性很高的基础课程。通过课设，我收到到了一下几个方面 1. 通过此次课设，我恢复了基础的C语言编程能力，并在此基础上，利用数据结构，能够变出更具有实用性，也具有更复杂功能的程序。很多以前想象不到的功能，通过数据结构巧妙的安排，也可以轻松实现。 2. 通过此次课设，我锻炼了自己思考的能力。以前总是不相信自己，能够把一个问题思考的有多深。现在，通过的思考，哪怕是一段漫长的时间得到的是对知识更为深刻的理解。 3. 通过此次课设，我能够借阅资料。通过更为广泛的寻找来为自己获得启发。通过请教他人，运用合作意识，让自己的做事效率更高。为自己增添信心。 4. 它让我学到很多。虽然课设时间很短，但收获却是别的方式无法拥有的，因为它让我把只是运用于实践，把思考当做一种享受，其乐趣是无穷的，它对我的影响很深远。 指导教师评语： 指导教师(签字)： 年 月 日 课程设计成绩 13

湖南工学院课程设计报告

附 录（关键部分程序清单）

程序代码

#include \"stdafx.h\" #include \"stdio.h\" #include \"stdlib.h\" #define maximum 20

int Graph[maximum][maximum];

int dist[maximum]; // 表示当前点到源点的最短路径长度 int visited[maximum]; int Queue[maximum]; int l; int jj=0;

typedef struct Node { int data; struct Node *next; }GraphNode;

GraphNode vexs[maximum]; //顶点数组 int rear=-1; int front=-1;

int queue[maximum];

void addqueue(int *queue,int x)//入队操作 { if(rear==l-1) { printf(\"队列已满\\n\"); return; } rear++; queue[rear]=x; return; }

int delqueue(int *queue)//出队操作 { int e; if(rear==front) {

14

湖南工学院课程设计报告

return -2; }

front++; e=queue[front]; queue[front]=0; return e; }

void CreateAdjacentTable(int v1,int v2) { GraphNode *newnode; newnode=(GraphNode *)malloc(sizeof(GraphNode)); newnode->data=v2+1;newnode->next=NULL; GraphNode *p; p=&vexs[v1]; while(p->next!=NULL) p=p->next; p->next=newnode; }

void TopoSort(int *visited,int *Queue) { int i; rear=-1; front=-1; int topnum=0; int ml[maximum]; int n=0; GraphNode *p; for(i=0;inext; while(p!=NULL) { visited[(p->data)-1]++; p=p->next; } } while(topnum!=l) { for(i=0;i15

湖南工学院课程设计报告

p=(&vexs[i])->next; while(p!=NULL) { visited[(p->data)-1]--; p=p->next; } visited[i]=-1; } } topnum++; } for(i=0;i\");} jj=1; } printf(\"\\n\"); }

void main() { int Graph[maximum][maximum]; GraphNode *kk,*dd; int source,destination; int i,j;

printf(\"输入图的顶点个数：\"); scanf(\"%d\ while(jj==0)

16

湖南工学院课程设计报告

{ for(i=0;il) { printf(\"超出范围请重新输入：\"); scanf(\"%d\ } printf(\"输入边的第二个顶点：\"); scanf(\"%d\ printf(\"\\n\"); if(destination==source) { printf(\"出现循环请重新输入：\"); scanf(\"%d\ } if(destination>l) { printf(\"顶点超出范围，重新输入：\"); scanf(\"%d\ } Graph[source-1][destination-1]=1; printf(\"输入边的第一个顶点：\"); scanf(\"%d\ printf(\"\\n\"); } for(i=0;inext!=NULL) { dd=kk->next; kk->next=dd->next; free(dd); } visited[i]=0; Queue[i]=0; }

17

湖南工学院课程设计报告

for(i=0;inext!=NULL) { kk=kk->next; printf(\"%d\ } printf(\"\\n\"); }

TopoSort(visited,Queue); } }

18