2 qq 24516525 qq_24516525 于 2014.12.16 09:42 提问

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

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

6个回答

devmiao
devmiao   Ds   Rxr 2014.12.16 09:57

#include <iostream>#include <fstream>#include <cstdlib>#include <iomanip>#include <string>#define MAX_VERTEX_NUM 99#define NULL 0int 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) //建零入度顶点栈Sif(!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号顶点的每个邻接点的入度减1if(!(--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) //建零入度顶点栈Sif(!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号顶点的每个邻接点的入度减1if(!(--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.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

devmiao
devmiao   Ds   Rxr 2014.12.16 09:58

代码乱了,请直接参考:http://zhidao.baidu.com/question/572682269.html

hjkNet
hjkNet   Ds   Rxr 2014.12.16 10:16
 #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
qq_40865152
qq_40865152 回复柔软的胖纸: 这个代码里面287行出现的那个error c2143怎么解决
27 天之前 回复
hjkNet
hjkNet 回复devmiao: 好咯 3Q!
大约 3 年之前 回复
devmiao
devmiao 回复hjkNet: 谢谢你!听说你生病了啊~~现在好点了摸?
大约 3 年之前 回复
hjkNet
hjkNet 楼下的代码
大约 3 年之前 回复
wangyaninglm
wangyaninglm   Ds   Rxr 2014.12.16 21:03

这个数据结构书上不是有么。。。

wangyaninglm
wangyaninglm   Ds   Rxr 2014.12.16 21:03

这个数据结构书上不是有么。。。

wangyaninglm
wangyaninglm   Ds   Rxr 2014.12.16 21:04

这个数据结构书上不是有么。。。

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!