中北大学

数据结构

课程设计说明书

 20##年12月20日

设计内容：

设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。

1、对一个描述工程的AOE网，应判断其是否能够顺利进行。

2、若该工程能顺利进行，输出完成整项工程至少需要多少时间，以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。  

设计要求：

(1) 符合课题要求，实现相应功能；

(2) 要求界面友好美观，操作方便易行；

(3) 注意程序的实用性、安全性；

1.       本设计所采用的数据结构（图）

程序流程图

2.       功能模块详细设计

2.1 详细设计思想

主函数switch()对条件进行选择判断，进入关键路径的程序，然后对结点数的接收，分配相应的存储空间，构建AOE-网，逐个对图结点信息（包括俩邻接点，权值）输入接收，并与分配存储空间。寻找关键路径：构建栈用与存储拓扑排序序列，求得每个接点的相应最早发生时间，最迟完成时间，关键事件的求取，并输出关键路径。

2.2 核心代码

#include "stdafx.h"

#include

#include

#include

#include

#include

using namespace std;

//#define PROJECTUNMBER 9//10

//#define PLANNUMBER 11//13

typedef struct node

{

    int adjvex;

    int dut;

    struct node *next;

}edgenode;

typedef struct

{

    int projectname;

    int id;

    edgenode *link;

}vexnode;

//vexnode Graphicmap[PROJECTNUMBER];

void GreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber)

{

    int begin,end,duttem;

    edgenode *p;

    for(int i=0;i

    { 

       Graphicmap[i].projectname=i;

       Graphicmap[i].id=0;

       Graphicmap[i].link=NULL;

    }

    printf("某项目的开始到结束在图中的节点输入\n");

    printf("如：3，4，9回车表示第三节点到第四节点之间的活动用了9个单位时间\n");

    printf("*********************************************\n");

    for(int k=0;k

    {

       scanf("%d,%d,%d",&begin,&end,&duttem);

       p=(edgenode*)malloc(sizeof(edgenode));

       p-＞adjvex=end-1;

       p-＞dut=duttem;

       Graphicmap[end-1].id++;

       p-＞next=Graphicmap[begin-1].link;

       Graphicmap[begin-1].link=p;

    }

}

int SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int& totaltime)

{

    int i,j,k,m=0;

    int front=-1,rear=-1;

    int* topologystack=(int*)malloc(projectnumber*sizeof(int));          //用来保存拓扑排列

    int* vl=(int*)malloc(projectnumber*sizeof(int));               //用来表示在不推迟整个工程的前提下，vl允许最迟发生时间

    int* ve=(int*)malloc(projectnumber*sizeof(int));                  //用来表示vj最早发生时间

    int* l=(int*)malloc(activenumber*sizeof(int));                    //用来表示活动Ai最迟完成开始时间

    int* e=(int*)malloc(activenumber*sizeof(int));                        //表示活动最早开始时间

    edgenode *p;

    totaltime=0;

    for(i=0;i

    for(i=0;i

    {

       if(Graphicmap[i].id==0)

       {

           topologystack[++rear]=i;

           m++;

       }

    }

    while(front!=rear)

    {

       front++;

       j=topologystack[front];

       m++;

       p=Graphicmap[j].link;

       while(p)

       {

           k=p-＞adjvex;

           Graphicmap[k].id--;

           if(ve[j]+p-＞dut＞ve[k])

              ve[k]=ve[j]+p-＞dut;

           if(Graphicmap[k].id==0)

              topologystack[++rear]=k;

           p=p-＞next;

       }

    }

    if(m

    {

       printf("\n本程序说建立的图有回路不可计算出关键路径\n");

       printf("将退出本程序\n");

       return 0;

    }

    totaltime=ve[projectnumber-1];

    for(i=0;i

       vl[i]=totaltime;

    for(i=projectnumber-2;i＞=0;i--)

    {

       j=topologystack[i];

       p=Graphicmap[j].link;

       while(p)

       {

           k=p-＞adjvex;

           if((vl[k]-p-＞dut)

              vl[j]=vl[k]-p-＞dut;

           p=p-＞next;

       }

    }

    i=0;  

    printf("|起点 |终点|最早开始时间 |最迟完成时间 |差值| 备注    |\n");

    for(j=0;j

    {

       p=Graphicmap[j].link;

       while(p)

       {

           k=p-＞adjvex;

           e[++i]=ve[j];

           l[i]=vl[k]-p-＞dut;

           printf("|  %4d  |  %4d  |  %4d  |   %4d  |   %4d  |",

              Graphicmap[j].projectname+1,Graphicmap[k].projectname

              +1,e[i],l[i],l[i]-e[i]);

           if(l[i]==e[i])

              printf("关键活动  |");

           printf("\n");

           p=p-＞next;

       }

    }

    return 1;

}

void seekkeyroot()

{

    int projectnumber,activenumber,totaltime=0;

    system("cls");

    printf("请输出这个工程的化成图形的节点数：");

    scanf("%d",&projectnumber);

    printf("\n");

    printf("请输入这个工程的活动个数:");

    scanf("%d",&activenumber);

    printf("\n");

    vexnode* Graphicmap=(vexnode*)malloc(projectnumber*sizeof(vexnode));

    GreateGraphic(Graphicmap,projectnumber,activenumber);

    SearchMapPath(Graphicmap,projectnumber,activenumber,totaltime);

    printf("整个工程所用的最短时间为：%d个单位时间\n",totaltime);

    system("pause");

}  

int main()

{

   

   

    char ch;

    for(;;)

    {

       do

       {

           system("cls");

           printf("|          欢迎进入求关键路径算法程序     |");

           for(int i=0;i＜80;i++)printf("*");

           printf("\n");

           printf("%s","(S)tart  开始输入工程的节点数据并求出关键路径\n");

           printf("\n");

           printf("%s","(E)xit   退出\n");

           printf("\n");

           printf("%s","请输入选择:");

           scanf("%c",&ch);

           ch=toupper(ch);

           if(ch!='S'&&ch!='E')

              printf("请输入正确的字符！\n");

           system("pause");

       }while(ch!='S'&&ch!='E');

       switch(ch)

       {

       case'S':

           seekkeyroot();

           break;

       case'E':

           return 1;

       }  

    }

}

2.3程序运行结果

输入S开始程序（如图）

输入节点数和活动个数（如图）

 

输入E，退出程序

3.       课程设计心得

这次的课程设计主要是对基础知识的灵活使用，这就让我进一步提高了对数据结构知识的巩固。这次设计的完成，有很多难题让我都曾不知所措，但通过努力最终解决它们让我体会到成就感，更重要的是我的能力在无形中得到了提升和优化。

今后我会更加的努力，去充分的提升自己。