课程设计(论文)任务书
软件学院软件工程专业2011 - 2班
一、课程设计(论文)题目数据结构课程设计
二、课程设计(论文)工作自2012 年12月17日起至2012 年12月18 日止。
三、课程设计(论文) 地点: 软件工程实训中心
四、课程设计(论文)内容要求：
1．本课程设计的目的
（1）使学生熟练掌握抽象数据类型的组织和定义；
（2）使学生熟练掌握数据类型的定义和实现；
（3）培养学生组织和分析数据的能力；
（4）培养学生分析和应用基于不同数据结构的算法的能力；
（5）提高学生的科技论文写作能力。
2．基本要求：
每位同学在以下题目中任选一题（在方框中打勾），独立完成课程设计：
□稀疏矩阵运算：实现稀疏矩阵的输入、输出、加减乘的运算。
□关键路径：求出完成整项工程至少需要多少时间以及整项工程中的关键活动。
（1）能够输入并存储一个描述工程的AOE网；
（1）对输入的AOE网，应判断其是否能够顺利进行；
（2）若该工程能顺利进行，输出完成整项工程至少需要多少时间，以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。
□银行业务模拟：参见《数据结构》教材P68。
3．课程设计论文编写要求
（1）要按照书稿的规格打印誊写课设报告；
（2）报告分为封面、任务书（本文档）、正文、课程设计体会和参考文献四部分；
学生签名：
年月日
课程设计(论文)评审意见
（1）题目分析（20分）：优（）、良（）、中（）、一般（）、差（）；（2）流程分析（30分）：优（）、良（）、中（）、一般（）、差（）；（3）数据定义（30分）：优（）、良（）、中（）、一般（）、差（）；（4）代码编写（10分）：优（）、良（）、中（）、一般（）、差（）；（5）创新能力（10分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性、设计态度及考勤是否降等级：是（）、否（）
评阅人：职称：讲师
年月日
正文
一、数据结构定义
1.抽象数据类型
本设计中用到的数据结构ADT定义如下：
ADT Graph{
数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。
数据关系R：
R={VR}
VR={|v,w (- V且P(v,w),表示从v到w的弧，
谓词P(v,w)定义了弧的意义或信息} 基本操作P：
CreateGraph(* G ,V,VR)
初始条件：V是图的顶点集，VR是图中弧的集合。
操作结果：按V和VR的定义构造图G。
Thelongestkey_Way(* G ,V,VR ,T)
初始条件：图G存在，T表示完成此项工程至少需要的时间。
操作结果：利用V和VR计算出结果T。
ThekeyWay( )//关键活动函数
初始条件：图G存在，函数调用的程序函数。
操作结果：输入V和VR计算结果T。
}ADT Graph
2.存储结构定义
数据存储结构的C语言定义如下：
//邻接表类型
typedef struct ANode //弧的节点结构类型
{
int adjvex; //弧的终点位置（弧头）int dut; //弧的权值
struct ANode *nextarc; //指向下一条弧的指针}ArcNode;
typedef struct //头结点的类型
{
int projectname; //顶点域
int id; //顶点的入度信息ArcNode *firstarc; //指向第一条弧
}V exnode;
3.基本操作
数据结构的基本操作实现如下：
void CreateGraph(V exnode* G,int projectnum,int activenum)
初始条件：projectnum是图的顶点集，activenum是图中弧的集合即活动时间。
操作结果：输入顶点数和弧的值，构造图G。
int Thelongestkey_Way(V exnode* G,int projectnum,int activenum,int& totaltime)
初始条件：图G存在，totaltime是计算图中工程的时间。
操作结果：由存在的图G，利用顶点和弧的关系信息，计算出工程至少需要的时间。void ThekeyWay( )
初始条件：由上面两个函数存在。
操作结果：显示进入求关键活动的结果。
Int main( )
初始条件：由上面函数存在。
操作结果：显示最终结果。
二、解题过程
1.问题分解
该问题主要应实现以下功能：
（1）计算完成整个工程的至少需要的时间。
（2）确定关键路径，以找出哪些活动时影响工程进度的关键。
因此须计算以下几点：
a.事件的最早发生时间ve[k]；
b.事件最迟发生时间vl[k]；
c.活动最早开始时间ee[i]；
d.活动的最迟开始时间el[i]；
计算其过程必须分别在拓扑有序和逆拓扑有序的前提下进行。也就说，ve[k]必须在事件vk所有前驱的最早发生的时间求得之后才能确定。因此，可以在拓扑排序的基础上计算ve[k]和vl[k]。由此得到求解关键路径的方法：
首先输入e条有向边，建立AOE-网的邻接表存储结构；然后从始点出发，令事件的最早发生时间为0，按拓扑有序求其余各顶点时间的最早发生时间ve[k]；(代码如下)
while(p) {
k=p->adjvex ;
Graph[k].id --;
if(ve[j]+p->w >ve[k])
ve[k]=ve[j]+p->w ;
}
