关键路径-数据结构课程设计任务书

由天下分享时间：2024/9/9 1:09:19 加入收藏我要投稿点赞

课程设计(论文)任务书

软件学院软件工程专业 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; //指向第一条弧

}Vexnode;

3. 基本操作

数据结构的基本操作实现如下：

void CreateGraph(Vexnode* G,int projectnum,int activenum)

初始条件：projectnum是图的顶点集，activenum是图中弧的集合即活动时间。操作结果：输入顶点数和弧的值，构造图G。

int Thelongestkey_Way(Vexnode* 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 ; }

接着从终点出发，令事件最迟发生时间等于其最早发生时间，按逆拓扑排序求其余各顶点事件最迟发生时间 vl[k]；最后根据各顶点事件的ve和vl值，求所有活动最早开始时间ee和最迟开始时间el。如果某活动满足条件ee＝el，则为关键活动。(代码如下)

if(ee==el) //关键活动 printf(\是\）；

同时，为计算各顶点事件的ve值是在拓扑排序的过程中进行的，因此需一个队列来记录拓扑排序，如果顶点的入度为0，则该顶点从队尾进入队列，拓扑排序时，从队头出队列。 (代码如下)

if(G[k].id ==0)//如果入度为0，则入队 TopoQueue[++rear]=k;

p=p->nextarc ; // 指向下一个结点

2. 模块结构

系统主要由 4 个模块组成，分别是：（1）创建图

（2）求完成此项工程至少要多少时间（3）求关键活动函数（4）主函数

模块之间的结构如下：

3. 解题思路

各模块的实现步骤为（1）首先主函数main( );

（2）调用实现求关键活动的函数ThekeyWay();

（3）再调用CreateGraph(Vexnode* G,int projectnum,int activenum);创建图；（4）再调用

Thelongestkey_Way(Vexnode* G,int projectnum,int activenum,int& totaltime)；求完成此项工程至少要多少时间

三、实现

#include

#include //malloc(); free(); exit(); #include //I/O控制头文件

#include //控制过程函数 system(\//邻接表类型

typedef struct ANode //弧的节点结构类型 {

int adjvex; //弧的终点位置（弧头） int dut;

//弧的权值

struct ANode *nextarc; //指向下一条弧的指针 }ArcNode;

typedef struct //头结点的类型 {

int projectname; //顶点域

int id;

//顶点的入度信息

ArcNode *firstarc; //指向第一条弧

}Vexnode;

void CreateGraph(Vexnode* G,int projectnum,int activenum)//创建图{

int begin,end,duttem; // 弧的前结点，尾结点，活动时间 ArcNode *p;// 弧指针 for(int i=0;i

{

G[i].projectname=i;//顶点命名

G[i].id =0;//顶点信息的度数均赋值为零 G[i].firstarc =NULL; //顶点指针为空 }

printf(\

printf(\请输入活动工程的信息，温馨提示：（请用int型格式输入：弧尾，弧头，活动时间）\\n\

printf(\例如：输入 1,2,3 即代表弧<1,2>的活动时间为3。\\n\ printf(\

for(int k=0;k

scanf(\输入弧的前结点，尾结点，活动时间

p=(ArcNode*)malloc(sizeof(ArcNode));//开辟弧的存储空间p

p->adjvex =end-1;//数组下标从0开始记录，故减一，将弧头插入邻接表内 p->dut =duttem; //此弧的活动时间为duttem G[end-1].id ++; //弧头指向，入度+1

p->nextarc=G[begin-1].firstarc ;//插入弧p，使得下一结点作为下一条弧的弧尾（前结点）

G[begin-1].firstarc =p; } }

int Thelongestkey_Way(Vexnode* G,int projectnum,int activenum,int& totaltime) // 求完成此项工程至少要多少时间 {

int i,j,k,m=0; int front=-1,rear=-1;

int* TopoQueue=(int*)malloc(projectnum*sizeof(int));// 用拓扑序列保存数据 int* vl=(int*)malloc(projectnum*sizeof(int));//vl表示最迟发生时间 int* ve=(int*)malloc(projectnum*sizeof(int));//ve表示最早发生时间 int* l=(int*)malloc(activenum*sizeof(int));//l表示活动最迟开始时间 int* e=(int*)malloc(activenum*sizeof(int));//e表示活动最早开始时间 ArcNode *p;

totaltime=0; //完成此工程至少需要的时间 for(i=0;i

ve[i]=0;//活动的最早发生时间均赋值为0

for(i=0;i

if(G[i].id==0) //入度为0，即为头结点 {

TopoQueue[++rear]=i;//所有头结点队尾插入，且队尾指针+1 m++; //记录入队列的顶点个数 } }

while(front!=rear) //队列不为“空” {

front++; // 出队列，队头指针+1 j=TopoQueue[front]; // 结点依次出队列 m++; // 记录结点数

p=G[j].firstarc ; // 指向其下一个顶点

while(p) {

k=p->adjvex ; // 弧头

G[k].id --;// 删除一个入度为0的前结点和其弧，入度减一 if(ve[j]+p->dut >ve[k])// 将最长路径赋值给ve[k] ve[k]=ve[j]+p->dut ;

if(G[k].id ==0)//如果入度为0，则入队 TopoQueue[++rear]=k;

p=p->nextarc ; // 指向下一个结点 } }

if(m

printf(\工程建立的图有环，不能计算关键路径！\\n\ printf(\即将退出工程！谢谢使用！\\n\ return 0; }

totaltime=ve[projectnum-1];//完成的至少时间为所有结点累加的时间和 for(i=0;i

for(i=projectnum-2;i>=0;i--)// 逆拓扑排序，求vl {

j=TopoQueue[i]; p=G[j].firstarc ;

while(p) {

k=p->adjvex ; //指向弧头 if((vl[k]-p->dut )dut ; p=p->nextarc ; } } i=0; printf(\

for(j=0;j

p=G[j].firstarc; while(p) {

k=p->adjvex ; e[++i]=ve[j]; l[i]=vl[k]-p->dut;

printf(\d | d | d | d | ? |\+1,G[k].projectname +1,e[i],l[i],l[i]-e[i]); if(l[i]==e[i]) //关键活动 printf(\是\

G[j].projectname +1,G[k].projectname +1); printf(\

p=p->nextarc ; } } return 1; }

void ThekeyWay()//关键活动函数 {

int projectnum,activenum,totaltime=0; printf(\

printf(\ printf(\欢迎进入求关键活动系统！\\n\ printf(\

printf(\请输入项目中AOE-网的结点数：\ scanf(\

printf(\请输入项目中AOE-网的活动数：\ scanf(\

Vexnode* G=(Vexnode*)malloc(projectnum*sizeof(Vexnode)); CreateGraph(G,projectnum,activenum);

Thelongestkey_Way(G,projectnum,activenum,totaltime); printf(\

printf(\工程所需至少活动时间为：%d \\n\ system(\ }

int main() {

printf(\

printf(\ 亲！欢迎进入本应用程序 \\n\

printf(\ printf(\退出本程序\\n\

printf(\开始输入工程相关数据并求关键活动\\n\ int a; system(\

printf(\

printf(\请输入选择 0 or 1:\ scanf(\ }

switch(a) { case 1:

ThekeyWay(); break;

case 0:

printf(\谢谢使用本程序！再见！\\n\

printf(\作者：柯晔-11级2班19号！谢谢使用！\\n\

default:printf(\无效的选项\\n\}

四、实验结果

1. 实验数据 1,2,6 1,3,4 1,4,5 2,5,1 3,5,1 4,6,2 5,7,9 5,8,7 6,8,4 7,9,2 8,9,4

2. 实验结果

（1）开始界面

（2）测试正确数据

① 输入选择1进入程序

② 输入顶点数和弧数

③ 输入活动时间

④ 打印出关键活动和完成整项工程至少需要多少时间

（3）测试错误数据

注意：应输入的数为整型数据，若输入非整形的数据，则程序遇到问题关闭。如图所示

（4）测试环

（5）退出程序

五、实验小结

1. 数据结构使用小结

本次程序使用的思想是拓扑排序和逆拓扑排序，其中用到队列来存放数据，是其巧妙之处。用到了邻接表，先建立邻接表的存储单元，为建立邻接表做准备。为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对于有向图是以vi为尾的弧）。每个结点由3个域组成，其中邻接域（adjvex）指示与顶点vi邻接的点在图中的位置，链域(nextarc)指示下一条边或弧的结点，权值域（W）存储边或弧的权值大小。在表头结点除了设有链域（firstarc指向链表中第一个结点之外，还设有存储顶点v或其他有关的数据域（dut）和存储顶点入度的域（id）。

2. 需完善之处

(1)界面不够美观；

(2)算法单一化，可以采用栈的思想去改进； (3)打印出结果的图，需完善；

(4)进入本程序简单明了，增加其严谨性

课程设计体会

通过此次课程设计，我在这其中准备了一个星期多，首先通过对所选的实验去了解，一遍一遍的翻看教材知识，从基础入手，把第七章图，去掌握。一开始理论知识都懂，但是看到代码很茫然，不知从何下手。不懂，就查阅了网上的资料，细嚼慢咽，我把资料代码打印出来，慢慢的去理解，一有不懂就翻书，查阅百度和相关知识。在这个过程，培养了我自学能力，和遇到困难问题而不是马上去问，先自己独立解决。有时候电脑前一坐就是一整天，也提升了自己的耐力，从中学到了很多。

另外，这次实验中，我感受到，要做一件事情，并不是想我们想的那样简单和容易。只有扎扎时时的学习知识打好基本功底，才能解决实际生活中的实际问题。从这次课设中也让我明白以后要多了解相关专业知识,从课本例题研究，从课外借阅书籍或从网上查找资料，俗话说：“多看不如多读，多读不如多写”，“好记性不如烂笔头”，所以我们更多的是要上机操作，将知识运用到实际问题中。同时，增加自己的动手能力，这样才能便于我们更好的解决问题。为今后打好坚实的基础。

参考文献

[1] 严蔚敏编.数据结构（C语言版）.北京: 清华大学出版社，2007 [2] 谭浩强著.C语言程序设计（第二版）.北京: 清华大学出版社，2008.11 [3] 彭勃.数据结构.北京: 电子工业出版社，2007.6 [4]网上资料