清华大学：《数据结构》课程教学资源（习题讲义实验）试验五

试验五 实验题目:建筑工程拓扑排序问题 建造一座办公楼,需要进行选择设计单位、楼房总体设计等活动(参见下表) 选择地点需要在建造地基之前完成,打地基必须在建造楼房、楼房封顶和内部装 修之前完成 如下表所示,是一系列活动之间的关系。 活动代号 活动名称 先需活动 选择设计单位 无 楼房总体设计 AO,A3.A4 选择施工企业 选择建造地点 无 A4 资金筹措 购买建筑材料 A2.A4 A6 建造地基 建造楼房 A6 房屋封顶 A7 购买装修材料 A4 A10 外部装修 A8,A9 A11 内部装修 A12 工程验收 A10,A11 下图是建造一座办公楼的AOV网示意图 5 11 9 10 12 4 设计算法判断该工程是否有回落,如无给出该工程AOⅤ网的拓扑排序, 试验要求: 1、设计邻接表作为存储结构,可用队列或者栈作为拓扑排序辅助存储 结构。 2、设计创建图算法,拓扑排序算法,算法要有较好的性能 创建存储上图中建造工程AOV网信息,并实现该图的拓扑排序,设 计驱动程序、其他测试用例,并得出正确结果

试验五 实验题目：建筑工程拓扑排序问题 建造一座办公楼，需要进行选择设计单位、楼房总体设计等活动（参见下表）。 选择地点需要在建造地基之前完成，打地基必须在建造楼房、楼房封顶和内部装 修之前完成。 如下表所示，是一系列活动之间的关系。 活动代号 活动名称 先需活动 A0 选择设计单位 无 A1 楼房总体设计 A0,A3,A4 A2 选择施工企业 A1 A3 选择建造地点 无 A4 资金筹措 无 A5 购买建筑材料 A2,A4 A6 建造地基 A5 A7 建造楼房 A6 A8 房屋封顶 A7 A9 购买装修材料 A4 A10 外部装修 A8,A9 A11 内部装修 A10 A12 工程验收 A10,A11 下图是建造一座办公楼的 AOV 网示意图。 设计算法判断该工程是否有回落，如无给出该工程 AOV 网的拓扑排序。 试验要求： 1、 设计邻接表作为存储结构，可用队列或者栈作为拓扑排序辅助存储 结构。 2、 设计创建图算法，拓扑排序算法，算法要有较好的性能。 3、 创建存储上图中建造工程 AOV 网信息，并实现该图的拓扑排序，设 计驱动程序、其他测试用例，并得出正确结果

试验目的: 1、掌握图的存储结构及其基本操作,学会定义图的邻接表存储结构, 并能在实际问题中灵活运用。 2、掌握拓扑排序算法 3、通过本试验的具体应用实例,灵活运用拓扑排序并进一步巩固队列/ 栈的运用。 提示: 在一个有向图中进行拓扑排序要进行如下步骤 1、在一个有向图中选择一个没有入度的顶点,将其输出。 2、在图中删除该顶点和所有以它为出边的弧。 重复步骤1和2,知道全部顶点都被输出,或者当前图中存在环

试验目的： 1、 掌握图的存储结构及其基本操作，学会定义图的邻接表存储结构， 并能在实际问题中灵活运用。 2、 掌握拓扑排序算法。 3、 通过本试验的具体应用实例，灵活运用拓扑排序并进一步巩固队列/ 栈的运用。 提示： 在一个有向图中进行拓扑排序要进行如下步骤： 1、 在一个有向图中选择一个没有入度的顶点，将其输出。 2、 在图中删除该顶点和所有以它为出边的弧。 3、 重复步骤 1 和 2，知道全部顶点都被输出，或者当前图中存在环