数据结构_关键路径实验报告.pdf

数据结构关键路径实验报告.pdf 一、实验目的 本实验的主要目的是巩固和加深对数据结构课程基本知识的理解，综合数据结构课程里学的理论知识，完成对关键路径程序的设计。通过本实验，学生可以理解和掌握图的各种基本数据结构的定义、存储结构和相应的算法，并能够用 C 语言实现。 二、实验内容 本实验的主要内容是编写能够找出给定工程施工图的关键路径的程序。该程序需要读取用户输入的图的顶点个数和边的个数，并将其存储在内存中，然后输出该AOE网的关键路径。 三、实验环境 本实验的硬件配置为 Pentium(R) Dual-Core CPU E6500 @2.93GHz，内存为 1.96GB。软件环境为 Microsoft Windows XP Professional Service Pack 3，Microsoft Visual C++ 6.0。 四、需求分析 本实验的需求分析可以分为三个部分：输入、输出和程序所能达到的功能。 * 输入：输入的形式和输入值的范围是根据题目要求与提示输入所建图的顶点个数和边的个数，用空格间隔，并且所输入的顶点和边的数目不超过定义好的 VEX_NUM 和 ARC_NUM，然后输入顶点的信息和入度以空格为间隔，最后输入每 2 个顶点以及边的权值。 * 输出：输出的形式是输出 AOE 网的关键路径。 * 程序所能达到的功能：对于给定的一个工程施工图，该图以边为单位从键盘输入，该程序能够输出该 AO 网的关键路径。 五、概要设计 为了实现上述操作，抽象数据图的定义如下： * 结构体 arcnode 用于声明边表中结点结构，包括邻接顶点、边上的权值和指向下一个边表节点的指针。 * 结构体 node 用于声明头结点结构，包括顶点的信息、入度和指向第一个边表节点的指针。 六、详细设计 本实验的详细设计可以分为两个模块：主程序模块和建立 AOE 网的邻接表函数模块。 * 主程序模块：main 函数的主要功能是读取用户输入的图的顶点个数和边的个数，并调用 create_ALgraph 函数建立 AOE 网的邻接表，然后调用 oupe_ALgraph 函数输出 AOE 网的邻接表，最后调用 Criticalpath 函数求 AOE 网的关键路径。 * 建立 AOE 网的邻接表函数模块：create_ALgraph 函数的主要功能是建立 AOE 网的邻接表，e 为弧的数目，n 为顶点数。该函数的实现过程是首先初始化头结点结构，然后依次读取用户输入的边的信息，并将其存储在邻接表中。