拓扑排序课程设计报告

1、.软件技术基础课程设计拓扑排序一 目的通过课程设计，加深对程序设计语言和软件技术基础课程所学知识的理解，熟练掌握和巩固C语言的基本知识和语法规范，包括：数据类型（整形、实型、字符型、指针、数组、结构等）；运算类型（算术运算、逻辑运算、自增自减运算、赋值运算等）；程序结构（顺序结构、判断选择结构、循环结构）；库函数应用等；复杂任务功能分解方法（自顶向下逐步求精、模块化设计、信息隐藏等），熟练掌握和巩固三种基本图形结构的逻辑结构、存储结构以及相关运算和应用。学会编制结构清晰、风格良好、数据结构适当的C语言程序，从而具备利用计算机编程分析解决综合性实际问题的初步能力。二 需求分析题目描述：判断一个有

2、向图是否存在回路，并求出有向无环图的拓扑序列。1、输入数据在工程文件中保存输入2个字符串数TXT文件。第一个为图按次序排列的所有边的前顶点，第二个为相对应的第二个顶点。2、输出数据图的定点数，边数，每个顶点的信息及入度，构造的邻接表，图的拓扑排序。3、程序功能已将AOV网存入文件中，运行时从文件读取数据；对一个AOV网，应判断其是否是有向无环图，若是则输出其任意一个拓扑排序序列，不是则进行相关的说明；构造图的邻接表；输出所有顶点的入度。三 概要设计1、全局变量或类型说明/*结构体定义*/typedef struct A_Node /定义表结点结构 int adjvex; /与vi相邻接的顶点编

3、号 struct A_Node *nextarc; /指向下一条弧(边)的指针 A_Node;typedef struct V_Node /定义表头结点结构 int data; A_Node *firstarc; /指向第一条弧（边）的指针 V_Node, AdjListMAX_NUM;typedef struct /定义邻接表结构 AdjList vertices; /表头结点数组 int vex_num, arc_num; /顶点和弧（边）的个数 ALGraph;typedef struct /构件栈 Elem_T *base; Elem_T *top; int stacksize; Sq

4、;2、模块功能1) void Init(Sq *S); 功能：初始化栈。构造一个空栈S参数：*S 待初始化的栈2) int Stack(Sq *S)功能：判断空栈参数：S 待判断的栈返回值：栈为空返回 1；栈非空返回 03) Void Int(Sq *S, Elem_T e)功能：元素入栈参数：*S 待操作的栈；插入元素e为新的栈顶元素4) void Out(Sq *S, Elem_T e);功能：元素出栈参数：*S 待操作的栈；若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回05) void Creat_Graph(ALGraph *G)功能：建立图。函数内包含了由用户输入顶点

5、数、弧数、顶点以及弧的操作参数：*G 待操作的图返回值：图建立成功返回1；图建立失败返回06) void Find_InDegree(ALGraph G, int indegree)功能：求顶点的入度参数：G 待操作的图，indegree储存每个顶点的入度的数组7) void TuoPu(ALGraph G);功能：实现拓扑排序，并在图形界面上演示排序过程参数：G 待进行拓扑排序的图错误判断：包含有向图是否有环的判断四 详细设计源代码详情如下：/*拓扑排序*/*张雪涛*/*2013.12.27*/*函数头文件、宏定义、变量声明*/#include<STDIO.H>#include&

6、lt;STDLIB.H>#define MAX_NUM 15 #define STACK_SIZE 100#define STACK_MENT 10#define OK 1#define M 20#define ERROR 0#define NUM 15typedef int Elem_T;char number1NUM;char number2NUM;/*结构体定义*/typedef struct A_Node /定义表结点结构 int adjvex; /与vi相邻接的顶点编号 struct A_Node *nextarc; /指向下一条弧(边)的指针 A_Node;typedef s

7、truct V_Node /定义表头结点结构 int data; A_Node *firstarc; /指向第一条弧（边）的指针 V_Node, AdjListMAX_NUM;typedef struct /定义邻接表结构 AdjList vertices; /表头结点数组 int vex_num, arc_num; /顶点和弧（边）的个数 ALGraph;typedef struct /构件栈 Elem_T *base; Elem_T *top; int stacksize; Sq;/*函数声明*/void Init(Sq *);int Stack(Sq *); void TuoPu(ALG

8、raph);int Out(Sq *, Elem_T);int Int(Sq *, Elem_T *);void Creat_Graph(ALGraph *);void Find_InDegree(ALGraph, int *);/*主函数*/int main(void) char num='Y'FILE *fp;fp=fopen("num1.txt","r"); /打开num1文件if(fp!=NULL)for(int i=1;i<=NUM;i+)fscanf(fp,"%d",&number1i);/将

9、文件的内容读入number1数组中fclose(fp); /关闭文件fp=fopen("num2.txt","r"); /打开文件num2if(fp!=NULL)for(int i=1;i<=NUM;i+)fscanf(fp,"%d",&number2i);/读取文件的内容到number2中fclose(fp); /关闭文件 while(1) printf("n欢迎您继续使用，请选择 Y or N :"); /判断是否为Y，若是则继续运行，若是N则退出 scanf("%c",&am

10、p;num); if(num='N')exit(0);ALGraph G; Creat_Graph(&G); /调用函数创建有向图 TuoPu(G); /进行拓扑排序 return 0;void Init(Sq *S) /初始化栈 S->base = (Elem_T *) malloc(STACK_SIZE * sizeof (Elem_T);/构建空指针 if (!S->base) printf("memory allocation failed, goodbye");/判断是否建立成功 exit(1); S->top = S-&

11、gt;base; S->stacksize = STACK_SIZE;int Out(Sq *S, Elem_T *e)/出栈操作 if (S->top = S->base) return ERROR; *e = *-S->top; return 0;void Int(Sq *S, Elem_T e)/进栈操作 if (S->top - S->base >= S->stacksize) S->base = (Elem_T *) realloc(S->base, (S->stacksize + STACK_MENT) * size

12、of (Elem_T); if (!S->base) printf("memory allocation failed, goodbye"); exit(1); S->top = S->base + S->stacksize; S->stacksize += STACK_MENT; *S->top+ = e;int Stack(Sq *S)/判断栈是否为空 if (S->top = S->base) return OK; else return ERROR;void Creat_Graph(ALGraph *G)/构建图 in

13、t m, n, i,j; A_Node *p; printf("n*n"); printf("* 欢迎您使用拓扑排序 *n"); printf("* 制作者：张雪涛 *n");printf("* 学号：10056041 *n"); printf("*n"); printf("请输入顶点数和边数:10 15"); G->vex_num=10 ;/要构建的顶点个数 G->arc_num=15;/要构建的边数 for (i = 1; i <= G->vex_

14、num; i+) G->verticesi.data = i;/构建顶点 G->verticesi.firstarc = NULL; j=1; for (i = 1; i <= G->arc_num; i+) /输入存在边的点集合 if(j>15) j=1;n=number1j;/起点数组m=number2j;/终点数组printf("n 第");printf("%d ",i);if(i>=10)printf("条边的两顶点序号分别为为:");elseprintf(" 条边的两顶点序号分别

15、为为:");printf("%d ",n);/打印构建的边printf("%d",m);j+; /scanf("%d%d", &n, &m); while (n < 0 | n > G->vex_num | m < 0 | m > G->vex_num) printf("n 输入的顶点序号不正确 请重新输入!");printf("n 第");printf("%d ",i);if(i>=10)printf(&q

16、uot;条边的两顶点序号分别为为:");elseprintf(" 条边的两顶点序号分别为为:"); scanf("%d%d", &n, &m); p = (A_Node*) malloc(sizeof (A_Node);/构建空链表 if (p = NULL) printf("memory allocation failed,goodbey"); exit(1); p->adjvex = m;/表头指向终点 p->nextarc = G->verticesn.firstarc; G->

17、verticesn.firstarc = p; void Find_InDegree(ALGraph G, int indegree)/找入度为零的节点 int i; for (i = 1; i <= G.vex_num; i+) indegreei = 0; for (i = 1; i <= G.vex_num; i+) while (G.verticesi.firstarc) indegreeG.verticesi.firstarc->adjvex+; G.verticesi.firstarc = G.verticesi.firstarc->nextarc; voi

18、d TuoPu(ALGraph G) /进行拓扑排序 int indegreeM; int i, k, n; int count = 0; /用来统计顶点的个数 A_Node *p; /定义一个栈，用来保存入度为0的顶点 Sq S; Find_InDegree(G, indegree);/查找深度 Init(&S);/初始化栈 for (i = 1; i <= G.vex_num; i+) if (!indegreei)/如果深度为0则入栈Int(&S, i); if (count < G.vex_num) printf("nn该有向图有回路!n"

19、;);else printf("n进行拓扑排序输出顺序为:n"); /输出结果 while (!Stack(&S) Out(&S, &n);/出栈 printf("%4d", G.verticesn.data);/打印结果 count+; for (p = G.verticesn.firstarc; p != NULL; p = p->nextarc) k = p->adjvex; if (!(-indegreek) /自减若深度为0则入栈 Int(&S, k);/入栈 printf("n"

20、);printf("排序成功n");五 调试分析1、测试数据图的拓扑排序：1424444567893102、存在过的问题以及分析解决（1）本课程设计采用先把主体结构写好后在网结构中添加具体的分布功能。采用的是主分式的形式以保证一个功能不能实现并不影响其他的功能。（2）课程设计有较好的容错能力，能够让一般用户也不出错，能正确的输入信息和统计，保证了正确性。（3）修改的时候采用一边调试一边修改，并不断尝试错误输入和验证。六 测试结果测试结果如下图所示：正常使用： 继续选择是否使用：错误的输入如下：有回路的操作如下：七 用户使用说明运行程序前在工程文件中输入所构造图的边顶点并保存