开发者社区> 问答> 正文

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

大神们,求解啊,跪求了,课程设计啥也不会,有没有大神能够教一下

展开
收起
a123456678 2016-03-05 11:52:26 2982 0
1 条回答
写回答
取消 提交回答
  •  #include <iostream>
    #include <fstream>
    #include <cstdlib>
    #include <iomanip>
    #include <string>
    #define MAX_VERTEX_NUM 99
    #define NULL 0
    int i,j;
    using namespace std;typedef struct Arcnode
    {
    char adjvex;
    int number;
    struct Arcnode *nextarc;
    int time;
    }Acrnode;typedef struct VNode
    {
    char data;
    Acrnode *firstarc;
    }VNode,Adjlist[MAX_VERTEX_NUM];typedef struct
    {
    Adjlist vertices;
    int vexnum,arcnum;
    }ALGraph;typedef struct
    {
    int *base;
    int *top;
    int stacksize;
    }Sqstack;void exampleout()
    {
    ifstream fin;
    ofstream fout;fin.open("example.txt");
    if(fin.fail())
    {
    cout << "Input file opening failed.\n";
    exit(1);
    }
    char a;
    fin.get(a);
    while(!fin.eof())
    {
    cout << a;
    fin.get(a);
    }
    fin.close();
    }void print()
    {
    ifstream fin;
    ofstream fout;fin.open("result.txt");
    if(fin.fail())
    {
    cout << "Input file opening failed.\n";
    exit(1);
    }
    char a;
    fin.get(a);
    while(!fin.eof())
    {
    cout << a;
    fin.get(a);
    }
    fin.close();
    }int number(string b)//将数字字符串转化为对应的数字
    {
    int flag,num,number=0;
    int m,n;
    flag=b.length();
    for(m=0;m<flag;m++)
    { 
    num=b[m]-48;
    for(n=0;n<flag-m-1;n++)
    num=num*10;
    number=number+num;
    }
    return number;
    }void datain(ALGraph *G)
    {
    Acrnode *p,*q;
    i=0; j=0;
    char a; string b;ifstream fin;
    ofstream fout;fin.open("data.txt");
    if(fin.fail())
    {
    cout << "Input file opening failed.\n";
    exit(1);
    }fin.get(a);
    while(a!='\n')
    {
    G->vertices[i].data=a;
    //cout << G->vertices[i].data;
    fin.get(a);
    i++;
    G->vexnum=i;
    }G->arcnum=0;for(j=0;j<G->vexnum;j++)
    {
    fin.get(a);
    if(a!='\n')
    {
    G->vertices[j].firstarc=(Acrnode *)malloc(sizeof(Acrnode));
    G->vertices[j].firstarc->adjvex=a;
    G->vertices[j].firstarc->nextarc=NULL;
    //cout << G->vertices[j].data << G->vertices[j].firstarc->adjvex;
    getline(fin,b,' '); 
    G->vertices[j].firstarc->time=number(b);
    G->arcnum++;
    //cout << G->vertices[j].firstarc->time;
    q=G->vertices[j].firstarc;
    fin.get(a);
    while(a!='\n')
    {
    p=(Acrnode *)malloc(sizeof(Acrnode));
    p->adjvex=a;
    //cout << p->adjvex;
    p->nextarc=NULL;
    q->nextarc=p;
    q=p;
    getline(fin,b,' '); 
    p->time=number(b);
    G->arcnum++;
    //cout << p->time;
    fin.get(a);
    }
    }
    }
    //cout << G->arcnum;
    fin.close();
    }void Findindegree(ALGraph G, int indegree[])
    {
    char x; Acrnode *r;
    for(i=0;i<G.vexnum;i++)
    {
    x=G.vertices[i].data;
    for(j=0;j<G.vexnum;j++)
    {
    r=G.vertices[j].firstarc;
    while(r!=NULL)
    {
    if(r->adjvex==x) {indegree[i]++;r->number=i;r=NULL;}
    else r=r->nextarc;
    }
    } 
    //cout << indegree[i];
    }
    }void Initstack(Sqstack &S)
    {
    S.base=(int *)malloc(MAX_VERTEX_NUM * sizeof(int));
    S.top=S.base;
    S.stacksize=MAX_VERTEX_NUM;
    }int Stackempty(Sqstack S)
    {
    if(S.top==S.base) return 1;
    else return 0;
    }void Push(Sqstack &S,int x)
    {
    *S.top=x;
    S.top++;
    }
    void Pop(Sqstack &S,int &x)
    {
    x=*--S.top;
    }void Topologicalsort(ALGraph G,int indegree[])
    //有向图G采用邻接表存储结构。
    //若G无回路,则输出G的顶点的一个拓扑序列,否则返回ERROR。
    { 
    Findindegree(G,indegree); //对各个顶求入度indegree[0..vernum-1]
    Acrnode *p; int count,k;
    Sqstack S;
    Initstack(S);
    for (i=0;i<G.vexnum;++i) //建零入度顶点栈S
    if(!indegree[i]) Push(S,i); //入度为0者入栈
    count=0; //对输出顶点计数
    while(!Stackempty(S))
    {
    Pop(S,i); 
    //cout << G.vertices[i].data; //输出i号顶点并计数
    ++count; 
    for(p=G.vertices[i].firstarc; p; p=p->nextarc)
    {
    k=p->number; //对i号顶点的每个邻接点的入度减1
    if(!(--indegree[k])) Push(S,k); //若入度减为0,则入栈
    }
    }
    if(count<G.vexnum) cout << "ERROR!该工程不能顺利完成!"; //该有向图有回路
    else cout << "Ready!该工程可以顺利完成!" << endl;
    }void Topologicalorder(ALGraph G,Sqstack &T,int indegree[],int ve[])
    //有向网G采用邻接表存储结构,求各顶点事件的最早发生时间ve
    //T为拓扑排序顶点栈,S为零入度顶点栈。
    //若G无回路,则用栈T返回G的一个拓扑序列,且函数值为OK,否则为ERROR。
    {
    Findindegree(G,indegree); //对各个顶求入度indegree[0..vernum-1]
    Acrnode *p; int count,k;
    Sqstack S;
    Initstack(S);
    for (i=0;i<G.vexnum;++i) //建零入度顶点栈S
    if(!indegree[i]) Push(S,i); //入度为0者入栈
    count=0; //对输出顶点计数
    
    while(!Stackempty(S))
    {
    Pop(S,j); 
    Push(T,j); 
    ++count; //j号顶点入T栈并计数
    for(p=G.vertices[j].firstarc; p; p=p->nextarc)
    {
    k=p->number; //对i号顶点的每个邻接点的入度减1
    if(!(--indegree[k])) Push(S,k); //若入度减为0,则入栈
    if(ve[j]+p->time>ve[k]) ve[k]=ve[j]+p->time;
    } 
    }
    //for (i=0;i<G.vexnum;++i)
    //cout << ve[i];
    ofstream fout;
    fout.open("result.txt");
    
    fout.close();if(count<G.vexnum) cout << "ERROR"; //该有向图有回路
    }void result(int a[],int b[],ALGraph G,int ve[],int vl[])
    {
    ofstream fout;
    fout.open("result.txt");
    fout << "工程的最短耗时为: " << ve[G.vexnum-1] << endl;
    fout << "关键活动 最早开始时间 最晚开始时间" << endl;
    for(j=0;j<i;j++)
    {
    fout << " <" << G.vertices[a[j]].data << "," << G.vertices[b[j]].data << "> ";
    fout << ve[a[j]] << " " << ve[b[j]] << " ";
    fout << vl[a[j]] << " " << vl[b[j]] << " " << endl;
    }
    fout.close();
    }void Criticalpath(ALGraph G,int indegree[],int ve[],int vl[])
    {
    int a[MAX_VERTEX_NUM]={0};
    int b[MAX_VERTEX_NUM]={0};
    Sqstack T;
    Initstack(T);
    Topologicalorder(G,T,indegree,ve); 
    Acrnode *p;int k,dut,ee,el;
    for(i=0;i<G.vexnum;++i)
    vl[i]=ve[G.vexnum-1]; //初始化顶点时间的最迟发生时间
    while(!Stackempty(T)) //按逆拓扑排序求各顶点的vl值
    {
    for(Pop(T,j),p=G.vertices[j].firstarc; p; p=p->nextarc)
    {
    k=p->number; dut=p->time; 
    if(vl[k]-dut<vl[j]) vl[j]=vl[k]-dut; //dut<j,k>
    }
    }
    i=0;
    for(j=0;j<G.vexnum;++j) //求ee,el和关键活动
    for(p=G.vertices[j].firstarc;p;p=p->nextarc)
    {
    k=p->number; dut=p->time;
    ee=ve[j]; el=vl[k]-dut;
    if(ee == el)
    {a[i]=j;b[i]=k;i++;} //输出关键活动
    }
    result(a,b,G,ve,vl);
    }int main()
    {ALGraph G; int ddy; char bye;
    
    for(j=0;j<MAX_VERTEX_NUM;j++) {G.vertices[j].data=0;G.vertices[j].firstarc=NULL;}
    
    int indegree[MAX_VERTEX_NUM]={0};
    int ve[MAX_VERTEX_NUM]={0};
    int vl[MAX_VERTEX_NUM]={0};
    
    cout << "WELLCOME!本程序将计算工程的最短耗时和关键路径" << endl;
    do
    {
    cout << endl << "请选择:" << endl;
    cout << "1.查看数据文件示例文本" << endl;
    cout << "2.检查输入的工程能否顺利完成" << endl;
    cout << "3.计算工程的最短耗时和关键路径并生成文本文件" << endl;
    cout << "4.显示计算结果" << endl;
    cout << "0.退出" << endl << endl;
    cin >> ddy;
    switch(ddy)
    {
    case 1:exampleout();break;
    case 2:{datain(&G); Topologicalsort(G,indegree);}break;
    case 3:Criticalpath(G,indegree,ve,vl);break;
    case 4:{print();cout << endl;}break;
    case 0:cout << "再见!";break;
    }
    }while(ddy!=0);
    cin.get(bye);
    cin.get(bye);
    return 0;
    }data.txtABCDEFGHI
    B6 C4 D5 
    E1 
    E1 
    F2 
    G9 H7 
    H4 
    I2 
    I4 
    example.txtABCDEFGHI(事件代号)
    B6 C4 D5 (每个事件的后继事件及活动时间)
    E1 (每个数字后空格)
    E1 
    F2 
    G9 H 7 
    H4 
    I2 
    I4
    2019-07-17 18:53:09
    赞同 展开评论 打赏
问答分类:
C++
问答标签:
问答地址:
问答排行榜
最热
最新

相关电子书

更多
使用C++11开发PHP7扩展 立即下载
GPON Class C++ SFP O;T Transce 立即下载
GPON Class C++ SFP OLT Transce 立即下载