《数据结构》课程设计指导书(2)

注意：该AOE网为仅有一个起始顶点且仅有一个终止顶点的有向无环网。 提示：该AOE网的弧代表活动，顶点代表事件。事件发生，以该顶点为弧尾的所

有活动即可开始；只有指向某顶点的所有弧（活动）都完成，该顶点代表的事件才会发生。每个事件都有最早发生时刻和最晚发生时刻；每个活动都有相应的最早开始时间、最晚开始时间、最早完成时间和最晚完成时间。弧的富余时间即为该弧在不影响整个工程工期的前提下允许其拖延的最大时间，富余时间为零的所有弧即构成关键路径。

3．设计要求

? 利用C、C++、C#或Java等语言实现该程序，程序应上机调试通过并运行正确。 ? 如果程序采用C#或Java等语言实现，则酌情加分；如果主要函数采用动态链接库形式实现，则酌情加分。

? 该网的存储方法要求采用十字链表存储法。

? 输入数据，构造AOE网的十字链表存储结构，求其关键路径并输出。 ? 撰写课程设计报告，报告格式按规范设置。

? 课程设计报告中应给出算法过程的具体分析、程序数据所采用的存储结构图、程序流程图、测试数据及其结果分析、算法的时间和空间复杂度等，另外还可以提出算法的进一步改进方法。 课题A2：求有向图的极大强连通分量并输出

1．设计目的

? 了解图的非线性特点、递归特点和动态特性。 ? 掌握图或网的十字链表存储结构及其遍历方法。 ? 掌握有向图极大强连通分量的求法。 2．主要内容

（1）输入有向图的顶点总数和所有顶点标志（每个顶点均用一个大写英文字母

作为标志）；

（2）输入图的弧数，并依次输入各条弧的信息，建立该图的十字链表存储结构； （3）输入一个顶点，求出图中该顶点所在的极大强连通分量，并输出。

图A2-1 有向网

将图A2-1存入十字链表中，若输入A，则输出顶点A所在的极大强连通分

6

量A,B,C；若输入F，则输出F,G。 3．设计要求

? 利用C、C++、C#或Java等语言实现该程序，程序应上机调试通过并运行正确。 ? 如果程序采用C#或Java等语言实现，则酌情加分；如果主要函数采用动态链接库形式实现，则酌情加分。

? 该图要求采用邻接表或十字链表作为存储结构。 ? 撰写课程设计报告，报告格式按规范设置。

? 课程设计报告中应给出算法过程的具体分析、程序数据所采用的存储结构图、程序流程图、测试数据及其结果分析、算法的时间和空间复杂度等，另外还可以提出算法的进一步改进方法。 课题A3：哈希查找的实现与分析 1．设计目的

? 掌握哈希函数的构造原则及哈希表的生成方法，并能在解决实际问题时灵活应用。

? 掌握哈希查找的基本过程及其适用场合。

? 巩固在散列查找时解决冲突的方法及各种方法的特点。 2．主要内容

（1）以某班所有同学的学号为关键字构造一个合适的哈希函数。

（2）所有同学信息均从文本文件Hash.txt中读取（文本文件中的各字段用跳格

键分隔）后插入到哈希表。 （3）用拉链法解决冲突。

图 Hash表中需要从文件读取的数据

7

3．设计要求

? 利用C、C++、C#或Java等语言实现该程序，程序应上机调试通过并运行正确。 ? 如果程序采用C#或Java等语言实现，则酌情加分；如果主要函数采用动态链接库形式实现，则酌情加分。

? 所有数据从文本文件Hash.txt中读取。

? 根据实际问题自行构造合理的哈希函数，要求采用拉链法解决Hash表的冲突。 ? 撰写课程设计报告，报告格式按规范设置。

? 课程设计报告中应给出算法过程的具体分析、程序数据所采用的存储结构图、程序流程图、测试数据及其结果分析、算法的时间和空间复杂度等，另外还可以提出算法的进一步改进方法。