问题描述

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

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

解决方案

#include <iostream>#include <fstream>#include <cstdlib>#include <iomanip>#include <string>#define MAX_VERTEX_NUM 99#define NULL 0int ij;using namespace std;typedef struct Arcnode{char adjvex;int number;struct Arcnode *nextarc;int time;}Acrnode;typedef struct VNode{char data;Acrnode *firstarc;}VNodeAdjlist[MAX_VERTEX_NUM];typedef struct{Adjlist vertices;int vexnumarcnum;}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 flagnumnumber=0;int mn;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(finb' '); 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(finb' '); 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 &Sint x){*S.top=x;S.top++;}void Pop(Sqstack &Sint &x){x=*--S.top;}void Topologicalsort(ALGraph Gint indegree[])//有向图G采用邻接表存储结构。//若G无回路，则输出G的顶点的一个拓扑序列否则返回ERROR。{ Findindegree(Gindegree); //对各个顶求入度indegree[0..vernum-1]Acrnode *p; int countk;Sqstack S;Initstack(S);for (i=0;i<G.vexnum;++i) //建零入度顶点栈Sif(!indegree[i]) Push(Si); //入度为0者入栈count=0; //对输出顶点计数while(!Stackempty(S)){Pop(Si); //cout << G.vertices[i].data; //输出i号顶点并计数++count; for(p=G.vertices[i].firstarc; p; p=p->nextarc){k=p->number; //对i号顶点的每个邻接点的入度减1if(!(--indegree[k])) Push(Sk); //若入度减为0，则入栈}}if(count<G.vexnum) cout << ""ERROR!该工程不能顺利完成！""; //该有向图有回路else cout << ""Ready!该工程可以顺利完成！"" << endl;}void Topologicalorder(ALGraph GSqstack &Tint indegree[]int ve[])//有向网G采用邻接表存储结构，求各顶点事件的最早发生时间ve//T为拓扑排序顶点栈，S为零入度顶点栈。//若G无回路，则用栈T返回G的一个拓扑序列，且函数值为OK，否则为ERROR。{Findindegree(Gindegree); //对各个顶求入度indegree[0..vernum-1]Acrnode *p; int countk;Sqstack S;Initstack(S);for (i=0;i<G.vexnum;++i) //建零入度顶点栈Sif(!indegree[i]) Push(Si); //入度为0者入栈count=0; //对输出顶点计数while(!Stackempty(S)){Pop(Sj); Push(Tj); ++count; //j号顶点入T栈并计数for(p=G.vertices[j].firstarc; p; p=p->nextarc){k=p->number; //对i号顶点的每个邻接点的入度减1if(!(--indegree[k])) Push(Sk); //若入度减为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 Gint 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 Gint indegree[]int ve[]int vl[]){int a[MAX_VERTEX_NUM]={0};int b[MAX_VERTEX_NUM]={0};Sqstack T;Initstack(T);Topologicalorder(GTindegreeve); Acrnode *p;int kduteeel;for(i=0;i<G.vexnum;++i)vl[i]=ve[G.vexnum-1]; //初始化顶点时间的最迟发生时间while(!Stackempty(T)) //按逆拓扑排序求各顶点的vl值{for(Pop(Tj)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<jk>}}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(abGvevl);}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(Gindegree);}break;case 3:Criticalpath(Gindegreevevl);break;case 4:{print();cout << endl;}break;case 0:cout << ""再见！"";break;}}while(ddy!=0);cin.get(bye);cin.get(bye);return 0;}data.txtABCDEFGHIB6 C4 D5 E1 E1 F2 G9 H7 H4 I2 I4 example.txtABCDEFGHI（事件代号）B6 C4 D5 （每个事件的后继事件及活动时间）E1 (每个数字后空格)E1 F2 G9 H 7 H4 I2 I4

解决方案二：
代码乱了，请直接参考：http://zhidao.baidu.com/question/572682269.html

解决方案三：

 #include <iostream>#include <fstream>#include <cstdlib>#include <iomanip>#include <string>#define MAX_VERTEX_NUM 99#define NULL 0int ij;using namespace std;typedef struct Arcnode{char adjvex;int number;struct Arcnode *nextarc;int time;}Acrnode;typedef struct VNode{char data;Acrnode *firstarc;}VNodeAdjlist[MAX_VERTEX_NUM];typedef struct{Adjlist vertices;int vexnumarcnum;}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 flagnumnumber=0;int mn;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(finb' '); 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(finb' '); 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 &Sint x){*S.top=x;S.top++;}void Pop(Sqstack &Sint &x){x=*--S.top;}void Topologicalsort(ALGraph Gint indegree[])//有向图G采用邻接表存储结构。//若G无回路，则输出G的顶点的一个拓扑序列否则返回ERROR。{ Findindegree(Gindegree); //对各个顶求入度indegree[0..vernum-1]Acrnode *p; int countk;Sqstack S;Initstack(S);for (i=0;i<G.vexnum;++i) //建零入度顶点栈Sif(!indegree[i]) Push(Si); //入度为0者入栈count=0; //对输出顶点计数while(!Stackempty(S)){Pop(Si); //cout << G.vertices[i].data; //输出i号顶点并计数++count; for(p=G.vertices[i].firstarc; p; p=p->nextarc){k=p->number; //对i号顶点的每个邻接点的入度减1if(!(--indegree[k])) Push(Sk); //若入度减为0，则入栈}}if(count<G.vexnum) cout << ""ERROR!该工程不能顺利完成！""; //该有向图有回路else cout << ""Ready!该工程可以顺利完成！"" << endl;}void Topologicalorder(ALGraph GSqstack &Tint indegree[]int ve[])//有向网G采用邻接表存储结构，求各顶点事件的最早发生时间ve//T为拓扑排序顶点栈，S为零入度顶点栈。//若G无回路，则用栈T返回G的一个拓扑序列，且函数值为OK，否则为ERROR。{Findindegree(Gindegree); //对各个顶求入度indegree[0..vernum-1]Acrnode *p; int countk;Sqstack S;Initstack(S);for (i=0;i<G.vexnum;++i) //建零入度顶点栈Sif(!indegree[i]) Push(Si); //入度为0者入栈count=0; //对输出顶点计数while(!Stackempty(S)){Pop(Sj); Push(Tj); ++count; //j号顶点入T栈并计数for(p=G.vertices[j].firstarc; p; p=p->nextarc){k=p->number; //对i号顶点的每个邻接点的入度减1if(!(--indegree[k])) Push(Sk); //若入度减为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 Gint 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 Gint indegree[]int ve[]int vl[]){int a[MAX_VERTEX_NUM]={0};int b[MAX_VERTEX_NUM]={0};Sqstack T;Initstack(T);Topologicalorder(GTindegreeve); Acrnode *p;int kduteeel;for(i=0;i<G.vexnum;++i)vl[i]=ve[G.vexnum-1]; //初始化顶点时间的最迟发生时间while(!Stackempty(T)) //按逆拓扑排序求各顶点的vl值{for(Pop(Tj)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<jk>}}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(abGvevl);}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(Gindegree);}break;case 3:Criticalpath(Gindegreevevl);break;case 4:{print();cout << endl;}break;case 0:cout << ""再见！"";break;}}while(ddy!=0);cin.get(bye);cin.get(bye);return 0;}data.txtABCDEFGHIB6 C4 D5 E1 E1 F2 G9 H7 H4 I2 I4 example.txtABCDEFGHI（事件代号）B6 C4 D5 （每个事件的后继事件及活动时间）E1 (每个数字后空格)E1 F2 G9 H 7 H4 I2 I4

解决方案四：
这个数据结构书上不是有么。。。

解决方案五：
这个数据结构书上不是有么。。。

解决方案六：
这个数据结构书上不是有么。。。