拓扑排序(算法与数据结构课程设计)
16页1、拓扑排序一、问题描述 在AOV网中为了更好地完成工程,必须满足活动之间先后关系,需要将各活动排一个先后次序即为拓扑排序。拓扑排序可以应用于教学计划的安排,根据课程之间的依赖关系,制定课程安排计划。按照用户输入的课程数,课程间的先后关系数目以及课程间两两间的先后关系,程序执行后会给出符合拓扑排序的课程安排计划。二、基本要求 1、选择合适的存储结构,建立有向无环图,并输出该图; 2、实现拓扑排序算法; 3、运用拓扑排序实现对教学计划安排的检验。三、算法思想 1、采用邻接表存储结构实现有向图;有向图需通过顶点数、弧数、顶点以及弧等信息建立。 2、拓扑排序算法void TopologicalSort(ALGraph G) 中,先输出入度为零的顶点,而后输出新的入度为零的顶点,此操作可利用栈或队列实现。考虑到教学计划安排的实际情况,一般先学基础课(入度为零),再学专业课(入度不为零),与队列先进先出的特点相符,故采用队列实现。 3、拓扑排序算法void TopologicalSort(ALGraph G),大体思想为: 1)遍历有向图各顶点的入度,将所有入度为零的顶点入队列; 2)队列非空时,输
2、出一个顶点,并对输出的顶点数计数; 3)该顶点的所有邻接点入度减一,若减一后入度为零则入队列; 4)重复2)、3),直到队列为空,若输出的顶点数与图的顶点数相等则该图可拓扑排序,否则图中有环。 4、要对教学计划安排进行检验,因此编写了检测用户输入的课程序列是否是拓扑序列的算法void TopSortCheck(ALGraph G),大体思想为: 1)用户输入待检测的课程序列,将其存入数组; 2)检查课程序列下一个元素是否是图中的顶点(课程),是则执行3),否则输出“课程XX不存在”并跳出; 3)判断该顶点的入度是否为零,是则执行4),否则输出“入度不为零”并跳出; 4)该顶点的所有邻接点入度减一;5)重复2)、3)、4)直到课程序列中所有元素均被遍历,则该序列是拓扑序列,否则不是拓扑序列。四、数据结构 1、链式队列的存储类型为:typedef int ElemType;typedef struct QNodeElemType data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rea
3、r;LinkQueue; 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;五、模块划分1、链式队列操作1) void InitQueue(LinkQueue *Q)功能:初始化链式队列参数:*Q 待初始化的队列2) int QueueEmpty(LinkQueue Q)功能:判断空队列参数:Q 待判断的队列返回值:队列为空返回 1;队列非空返
4、回 03) void EnQueue(LinkQueue *Q, ElemType e)功能:元素入队列参数:*Q 待操作的队列;e 要入队列的元素4) void DeQueue(LinkQueue *Q, ElemType *e)功能:元素出队列参数:*Q 待操作的队列;*e 记录出队列元素的变量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)功能:建立预
《拓扑排序(算法与数据结构课程设计)》由会员cl****1分享,可在线阅读,更多相关《拓扑排序(算法与数据结构课程设计)》请在金锄头文库上搜索。
个人房屋买卖合作协议书范本(十一篇)
常用表面活性剂的HLB值精编版
生产运营管理岗位职责
医流巴巴团队建设活动感言
2022年校长开学典礼上的讲话稿
专题二课题1果酒和果醋的制作教学设计优质课比赛教案
生产车间员工2023年终工作总结(4篇).doc
运行值长岗位风险控制卡
玉米病虫害防治技术
学生会竞选的演讲稿范文
基于PLC的锅炉加热温度控制系统设计技术相关
教师师徒结对协议书
主题活动策划三篇3
1月浙江省普通高中学业水平考试语文试题j及答案
东北农业大学21秋《中级会计实务》在线作业二答案参考97
蔡阳小学“优教通”资源应用二次培训方案
什么是细节描写
完形填空专练 (16)
二年级下册语文《阿德的梦》教学设计
2021销售顾问年终总结(原创)
2022-07-29 9页
2023-03-07 17页
2023-09-08 13页
2023-10-29 14页
2023-04-15 4页
2024-01-16 103页
2023-12-04 6页
2023-09-27 70页
2023-12-21 6页
2023-08-14 8页