拓扑排序课程设计论文.doc

课程设计成果 学院:_计算机工程学院_ _ 班 级: XXXX 学生姓名: XXXX 学 号: XXXXX 设计地点（单位）_XXX_ _设计题目:_拓扑排序_ 完成日期： 2014 年 12 月 28 日 成绩(五级记分制):_ _ _ 教师签名:_ _课程设计任务书设计题目：拓扑排序学生姓名XXX课程名称数据结构程序设计专业班级XXX地 点XX起止时间2014.12.25-2015.1.9设计内容及要求问题描述：编写函数实现图的拓扑排序。设计参数 进度要求两个星期内完成。参考资料1 李素若,陈万华等编著.数据结构.北京：中国水利水电出版社,2014.7.2 李素若，琚辉，严永松编著.数据结构习题解答及上机指导.北京：中国水利水电出版社,2014.9.3 谭浩强. C+面向对象程序设计.北京：清华大学出版社，2006.其它说明1.本表应在每次实施前一周由负责教师填写二份，教研室审批后交学院院备案，一份由负责教师留用。2.若填写内容较多可另纸附后。3.一题多名学生共用的，在设计内容、参数、要求等方面应有所区别。教研室主任： 指导教师： 2015 年 1 月 9 日目 录1 问题描述12 基本要求13算法思想14数据结构24.1链式队列的存储类型为24.2图的类型（邻接表存储结构）为25模块划分25.1链式队列操作25.2有向图(DAG)邻接表存储结构(ALG)的操作35.3拓扑排序及拓扑检测算法35.4主函数46测试数据46.1对“建立有向图并输出”的测试46.2对“建立有向图并求一个拓扑排序序列”的测试46.3对“检测用户输入的课程安排”的测试47测试情况57.1对“建立有向图并输出”的测试57.2对“建立有向图并求一个拓扑排序序列”的测试77.3对“检测用户输入的课程安排”的测试88系统开发所用到的技术11参考文献13附录 全部代码141 问题描述 在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。拓扑排序可以应用于教学计划的安排，根据课程之间的依赖关系，制定课程安排计划。按照用户输入的课程数，课程间的先后关系数目以及课程间两两间的先后关系，程序执行后会给出符合拓扑排序的课程安排计划。2 基本要求1、选择合适的存储结构，建立有向无环图，并输出该图； 2、实现拓扑排序算法； 3、运用拓扑排序实现对教学计划安排的检验。3 算法思想1、采用邻接表存储结构实现有向图；有向图需通过顶点数、弧数、顶点以及弧等信息建立。 2、拓扑排序算法void TopologicalSort(ALGraph G) 中，先输出入度为零的顶点，而后输出新的入度为零的顶点，此操作可利用栈或队列实现。考虑到教学计划安排的实际情况，一般先学基础课（入度为零），再学专业课（入度不为零），与队列先进先出的特点相符，故采用队列实现。 3、拓扑排序算法void TopologicalSort(ALGraph G)，大体思想为： 1)遍历有向图各顶点的入度，将所有入度为零的顶点入队列； 2)队列非空时，输出一个顶点，并对输出的顶点数计数； 3)该顶点的所有邻接点入度减一，若减一后入度为零则入队列； 4)重复2)、3)，直到队列为空，若输出的顶点数与图的顶点数相等则该图可拓扑排序，否则图中有环。 4、要对教学计划安排进行检验，因此编写了检测用户输入的课程序列是否是拓扑序列的算法void TopSortCheck(ALGraph G)，大体思想为： 1)用户输入待检测的课程序列，将其存入数组； 2)检查课程序列下一个元素是否是图中的顶点（课程），是则执行3)，否则输出“课程XX不存在”并跳出； 3)判断该顶点的入度是否为零，是则执行4)，否则输出“入度不为零”并跳出； 4)该顶点的所有邻接点入度减一；5)重复2)、3)、4)直到课程序列中所有元素均被遍历，则该序列是拓扑序列，否则不是拓扑序列。4 数据结构 4.1链式队列的存储类型为typedef int ElemType;typedef struct QNodeElemType data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue; 4.2图的类型（邻接表存储结构）为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 structAdjList vexhead;/邻接表头结点数组int vexnum,arcnum;/图的顶点数和弧数ALGraph;5 模块划分5.1链式队列操作1) void InitQueue(LinkQueue *Q)功能：初始化链式队列参数：*Q 待初始化的队列2) int QueueEmpty(LinkQueue Q)功能：判断空队列参数：Q 待判断的队列返回值：队列为空返回 1；队列非空返回 03) void EnQueue(LinkQueue *Q, ElemType e)功能：元素入队列参数：*Q 待操作的队列；e 要入队列的元素4) void DeQueue(LinkQueue *Q, ElemType *e)功能：元素出队列参数：*Q 待操作的队列；*e 记录出队列元素的变量5.2有向图(DAG)邻接表存储结构(ALG)的操作1) int LocateVex(ALGraph G,VertexType v)功能：顶点在头结点数组中的定位参数：G 待操作的图；v 要在图中定位的顶点返回值：顶点存在则返回在头结点数组中的下标；否则返回图的顶点数2) int CreateGraph(ALGraph *G)功能：建立图函数内包含了由用户输入顶点数、弧数、顶点以及弧的操作参数：*G 待操作的图返回值：图建立成功返回1；图建立失败返回0错误判断：包含顶点数、弧数是否正确的判断；包含用户输入的弧的顶点是否存在的判断3) void PrintGraph(ALGraph G)功能：输出有向图参数：G 待输出的图4) int CreateGraph2(ALGraph *G)功能：建立预置课程图（输出函数内预置课程信息，并自动建立有向图）参数：*G 待操作的图返回值：图建立成功返回1；图建立失败返回0错误判断：包含顶点数、弧数是否正确的判断包含弧的顶点是否存在的判断5) void PrintGraph2(ALGraph G)功能：输出预置课程图参数：G 待输出的图5.3拓扑排序及拓扑检测算法1) void TopologicalSort(ALGraph G)功能：实现拓扑排序参数：G 待进行拓扑排序的图错误判断：包含有向图是否有环的判断2) void TopSortCheck(ALGraph G)功能：运用拓扑排序的思想检测教学计划函数内包含了由用户输入待检测的课程序列的操作参数：G 待操作的图错误判断：包含用户输入的课程是否存在的判断包含不是拓扑序列的原因（该课程有多少个先决课程未学）5.4主函数void main()功能：主函数利用while语句和switch语句实现菜单化调用函数6 测试数据 6.1对“建立有向图并输出”的测试 1) 正确的有向图信息 顶点数和弧数:4,3 顶点:A B C D 边: A BB CC D 2) 错误的边 顶点数和弧数:4,3 顶点:A B C D 边: A BB CC E 3) 错误的顶点数或弧数 顶点数和弧数:3,7 6.2对“建立有向图并求一个拓扑排序序列”的测试 1) 有向图能实现拓扑排序 顶点数和弧数:5,5 顶点:A B C D E 边:A DD CC BE AE C 2) 有向图不能实现拓扑排序 顶点数和弧数:5,5 顶点:A B C D E 边:A DD CC BE AB A 6.3对“检测用户输入的课程安排”的测试 1) 课程序列符合拓扑序列 课程序列:C9 C10 C11 C6 C1 C12 C4 C2 C3 C5 C7 C8 2) 课程序列中有课程不存在 课程序列:C9 C10 C11 C6 C1 C12 C4 C2 C13 C5 C7 C8 3) 课程序列不是拓扑序列 课程序列:C9 C10 C11 C1 C8 C6 C12 C4 C2 C3 C5 C77 测试情况程序初始执行界面（以下测试编号与本文第七节测试数据编号一一对应） 7.1对“建立有向图并输出”的测试 1) 正确的有向图信息 有向图信息正确的情况下，程序显示“有向图建立成功”，并输出有向图。 2) 错误的边 本测试中，第三条边(C E)的一个顶点E不是有向图中的顶点，程序能判断本错误并显示相应的提示信息。 3) 错误的顶点数或弧数 本测试中，顶点数和弧数分别为3,7。若有向图共有n个顶点，两顶点间最多有2条有向边，则有向图最多有n*(n-1)条边。而3*(3-1)=6<7,故程序提示“顶点数或弧数不正确，有向图建立失败”；程序还能判断负的顶点数和弧数。 7.2对“建立有向图并求一个拓扑排序序列”的测试 1) 有向图能实现拓扑排序 有向图能实现拓扑排序的情况下，程序输出其中一个拓扑排序序列。 2) 有向图不能实现拓扑排序 本测试中，有向图其中四条边(A D)、(D C)、(C B)、(B A)构成环，程序能判断有向图有回路并提示相应信息。 7.3对“检测用户输入的课程安排”的测试 程序首先输出预置的课程信息和据此建立的有向图。 1) 课程序列符合拓扑序列 在用户输入的课程序列符合拓扑序列的情况下，程序提示“本课程序列符合拓扑序列”，并显示如图菜单。 2) 课程序列中有课程不存在 本程序预置了C1-C12共12门课程，若用户输入的课程序列中有不属于预置课程的课程，程序会提示“课程XX不存在！”，并显示如图菜单。 3) 课程序列不是拓扑序列 若用户输入的课程序列不是拓扑序列，程序会输出原因，即“学习课程XX时，还有X门先决课程未学！” ，并显示如图菜单。8 系统开发所用到的技术操作系统： Windows XP开发软件: Visual C+ 6.0技术：功能模块（函数）；指针；结构；链表；文件保存及读取。模块与函数:功能模块：求解较小问题的算法与程序称作“功能模块”，各功能模块可以先单独设计，然后将求解所有的子问题的模块组合成求解原问题的程序。将一个大问题分解成多个解决小问题的模块的设计思想。由功能模块组成程序的结构：主控模块和模块组成。模块还可细分。自顶向下，逐步分解的设计思想函数：完成相对独立功能和程序。模块独立：功能独立的子功能模块之间的关系简单，使用独立变量，模块规模适当：分解模块要注意层次： (1)对问题抽象化 (2)设计时细化设计原则：高内聚，低耦合指针就是指向变量和对象的地址。 指针的用途非常广泛，比如如果你想通过函数改变一个变量的值，就得用指针而不能用值传递。还有在很多时候变量，特别是对象的数据量实在太大，程序员就会用指针来做形参，只需要传递一个地址就行，大大提高了效率。指针就是指向变量和对象的地址。指针的用途非常广泛，比如如果你想通过函数改变一个变量的值，就得用指针而不能用值传递。还有在很多时候变量，特别是对象的数据量实在太大，程序员就会用指针来做形参，只需要传递一个地址就行，大大提高了效率。c语言之所以强大，以及其自由性，很大部分体现在其灵活的指针运用上。因此，说指针是c语言的灵魂，一点都不为过。链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，链表比较方便插入和删除操作。参考文献1 李素若,陈万华等编著.数据结构.北京：中国水利水电出版社,2014.72 李素若，琚辉，严永松编著.数据结构习题解答及上机指导.北京：中国水利水电出版社,2014.93 谭浩强. C+面向对象程序设计.北京：清华大学出版社，2006.附录 全部代码#include "stdlib.h"#include "stdio.h"#include "string.h"/*/* 以下为链式队列操作 */*/* 定义链式队列类型 */typedef int ElemType;typedef struct QNodeElemType data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;/* 1.初始化链式队列 */void InitQueue(LinkQueue *Q)Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode);if (!(Q->front) exit(0);Q->front->next=NULL; /* 2.判断空队列 */int QueueEmpty(LinkQueue Q)if(Q.front=Q.rear)return 1;else return 0; /* 3.入队列 */void EnQueue(LinkQueue *Q, ElemType e)QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if (!p) exit(0);p->data=e; p->next=NULL;Q->rear->next=p;Q->rear=p; /* 4.出队列 */void DeQueue(LinkQueue *Q, ElemType *e)QueuePtr p;if(Q->front!=Q->rear)p=Q->front->next;*e=p->data;Q->front->next=p->next;if (Q->rear=p) Q->rear=Q->front;free(p); /*/* 以下为有向图(DAG)邻接表存储结构(ALG)的操作 */*/#define MAX_VERTEX_NUM 20 /最大顶点个数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 structAdjList vexhead; /邻接表头结点数组int vexnum,arcnum; /图的顶点数和弧数ALGraph;/* 5.顶点在头结点数组中的定位 */int LocateVex(ALGraph G,VertexType v)int i;for(i=0;i<G.vexnum;i+)if(strcmp(v,G.vexheadi.name)=0) break;return i; /* 6.建立图（邻接表） */int CreateGraph(ALGraph *G) /成功建立返回1，不成功则返回0int i,j,k; VertexType v1,v2;ArcNode *newarc;printf("n输入有向图顶点数和弧数vexnum,arcnum:"); /输入顶点数和弧数scanf("%d,%d",&(*G).vexnum,&(*G).arcnum); /输入并判断顶点数和弧数是否正确if(*G).vexnum<0|(*G).arcnum<0|(*G).arcnum>(*G).vexnum*(*G).vexnum-1)printf("n顶点数或弧数不正确，有向图建立失败！n");return 0; printf("n输入 %d 个顶点:",(*G).vexnum); /输入顶点名称for(i=0;i<(*G).vexnum;i+)scanf("%s",(*G).vexheadi.name); printf("n顶点列表:n共有%d个顶点: ",(*G).vexnum);/输出顶点名称for(i=0;i<(*G).vexnum;i+)printf("%s ",(*G).vexheadi.name);for(i=0;i<(*G).vexnum;i+) /邻接表初始化(*G).vexheadi.firstarc=NULL;(*G).vexheadi.indegree=0;printf("nn输入 %d 条边:vi vjn",(*G).arcnum); /输入有向图的边for(k=0;k<(*G).arcnum;k+)scanf("%s%s",v1,v2); /v1是弧的起点（先决条件），v2是弧的终点i=LocateVex(*G,v1);j=LocateVex(*G,v2); /定位顶点并判断顶点是否存在if(i>=(*G).vexnum)printf("顶点%s不存在，有向图建立失败！n",v1);return 0; if(j>=(*G).vexnum)printf("顶点%s不存在，有向图建立失败！n",v2);return 0; newarc=(ArcNode*)malloc(sizeof(ArcNode); /前插法建顶点链表newarc->vexpos=j;if(*G).vexheadi.firstarc=NULL)newarc->next=NULL;(*G).vexheadi.firstarc=newarc; elsenewarc->next=(*G).vexheadi.firstarc->next;(*G).vexheadi.firstarc->next=newarc; (*G).vexheadj.indegree+; /对应顶点入度计数加1printf("n有向图建立成功！n");return 1;/* 7.按邻接表方式输出有向图 */void PrintGraph(ALGraph G)int i;ArcNode *p;printf("n输出有向图:n");for(i=0; i<G.vexnum; i+)printf("n顶点:%s ",G.vexheadi.name);printf("入度:%3dn",G.vexheadi.indegree);p=G.vexheadi.firstarc;printf("邻接点:");while(p!=NULL)printf("%s ",G.vexheadp->vexpos.name);p=p->next; printf("n");/为避免演示时要输入过多数据，以下函数将课程编号、课程间的先后关系通过数组预置/* 8.建立预置课程图（邻接表） */int CreateGraph2(ALGraph *G) /成功建立返回1，不成功则返回0int i,j,k;VertexType v1,v2;ArcNode *newarc;VertexTypeSubjectName12="C1","C2","C3","C4", /课程名称"C5","C6","C7","C8","C9","C10","C11","C12" ,RelationV116="C1","C1","C2","C1", /基础课"C3","C4","C11","C5","C3","C3","C6","C9","C9","C9","C10","C11",RelationV216="C2","C3","C3","C4", /以上面课程为基础的课"C5","C5","C6","C7","C7","C8","C8","C10","C11","C12","C12","C12",;/* 输出本程序使用的课程及先后关系表 */printf("n本程序预置了如下课程及先后关系:n");printf("n课程编号 课程名称 先决条件n C1 程序设计基础 无n C2 离散数学 C1n C3 数据结构 C1,C2n C4 汇编语言 C1n C5 语言的设计和分析 C3,C4n C6 计算机原理 C11n C7 编译原理 C5,C3n C8 操作系统 C3,C6n C9 高等数学 无n C10 线性代数 C9n C11 普通物理 C9n C12 数值分析 C9,C10,C1n");system("PAUSE");(*G).vexnum=12;(*G).arcnum=16;if(*G).vexnum<0|(*G).arcnum<0|(*G).arcnum>(*G).vexnum*(*G).vexnum-1)printf("n课程数或先后关系不正确，有向图建立失败！n");return 0; /判断课程数和弧数是否正确for(i=0;i<(*G).vexnum;i+)strcpy(*G).vexheadi.name,SubjectNamei); for(i=0;i<(*G).vexnum;i+) /邻接表初始化(*G).vexheadi.firstarc=NULL;(*G).vexheadi.indegree=0; for(k=0;k<(*G).arcnum;k+)strcpy(v1,RelationV1k);strcpy(v2,RelationV2k);i=LocateVex(*G,v1);j=LocateVex(*G,v2); /定位课程并判断课程是否存在if(i>=(*G).vexnum)printf("课程%s不存在，有向图建立失败！n",v1);return 0; if(j>=(*G).vexnum)printf("课程%s不存在，有向图建立失败！n",v2);return 0; newarc=(ArcNode*)malloc(sizeof(ArcNode); /前插法建课程链表newarc->vexpos=j;if(*G).vexheadi.firstarc=NULL)newarc->next=NULL;(*G).vexheadi.firstarc=newarc; elsenewarc->next=(*G).vexheadi.firstarc->next;(*G).vexheadi.firstarc->next=newarc; (*G).vexheadj.indegree+; /对应课程入度计数加1printf("n有向图建立成功！n");return 1;/* 9.按邻接表方式输出预置课程图 */void PrintGraph2(ALGraph G)int i;ArcNode *p;printf("n输出有向图:n");for(i=0; i<G.vexnum; i+)printf("n课程:%s ",G.vexheadi.name);printf("入度:%3dn",G.vexheadi.indegree);p=G.vexheadi.firstarc;printf("以本课程为基础的课程:");while(p!=NULL)printf("%s ",G.vexheadp->vexpos.name);p=p->next;printf("n");/*/* 以下为拓扑排序算法 */*/* 10.拓扑排序 */void TopologicalSort(ALGraph G)int i,k,count;ElemType e;ArcNode *p;LinkQueue Q; /*定义队列*/InitQueue(&Q);for(i=0; i<G.vexnum; i+) /零入度课程入队列if(!G.vexheadi.indegree) EnQueue(&Q,i);count=0; /对输出课程计数变量初始化printf("nnn以上课程的一个拓扑排序序列为:n");while(!QueueEmpty(Q)DeQueue(&Q,&e); /先将入度为零的课程输出printf("%s ",G.vexheade.name);count+; /对输出的顶点计数for(p=G.vexheade.firstarc;p;p=p->next) /遍历当前课程的邻接点k=p->vexpos; /邻接点位置if(!(-G.vexheadk.indegree) /每个邻接点入度减1后若为零则入队列EnQueue(&Q,k);printf("n");if(count<G.vexnum)printf("n该有向图有回路，无法完成拓扑排序！n"); /*/* 以下为拓扑检测算法 */*/* 11.运用拓扑排序的思想检测教学计划 */void TopSortCheck(ALGraph G)int i,k; ArcNode *p; VertexType v,CheckList12;/待检测序列TopologicalSort(G);printf("n输入待检测的课程序列:n");for(i=0; i<G.vexnum; i+) /输入待检测序列scanf("%s",CheckListi);for(i=0; i<G.vexnum; i+) strcpy(v,CheckListi); k=LocateVex(G,v); if(k>=G.vexnum) /判断课程是否存在 printf("课程%s不存在！n",v);return; if(G.vexheadk.indegree!=0) /判断课程入度是否为零 printf("学习课程%s时,还有%d门先决课程未学！n",v,G.vexheadk.indegree); printf("本课程序列不是拓扑序列nn");return; else for(p=G.vexheadLocateVex(G,v).firstarc;p;p=p->next)/遍历此课程邻接点k=p->vexpos; /邻接点位置G.vexheadk.indegree-; /每个邻接点入度减1 printf("本课程序列符合拓扑序列nn");/*/* 12.主函数 */*/int main()ALGraph G;int menu,menu2;while(1)printf("n*n");printf("*1.建立有向图并输出 *n");printf("*2.建立有向图并求一个拓扑排序序列 *n");printf("*3.检测用户输入的课程安排 *n");printf("*4.清屏 *n");printf("*5.退出 *n");printf("*n");printf("请输入你的选择:");scanf("%d",&menu);switch(menu)case 1:if(CreateGraph(&G)system("PAUSE");PrintGraph(G);/有向图建成则执操作break;case 2:if(CreateGraph(&G) /有向图建成则执操作system("PAUSE");PrintGraph(G);system("PAUSE");TopologicalSort(G); break;case 3:if(CreateGraph2(&G) /有向图建成则执操作system("PAUSE");PrintGraph2(G); system("PAUSE