大神们,求解啊,跪求了,课程设计啥也不会,有没有大神能够教一下
3条回答 默认 最新
- 柔软的胖纸 2014-12-16 02: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
解决 2无用
悬赏问题
- ¥15 如何实验stm32主通道和互补通道独立输出
- ¥30 这是哪个作者做的宝宝起名网站
- ¥60 版本过低apk如何修改可以兼容新的安卓系统
- ¥25 由IPR导致的DRIVER_POWER_STATE_FAILURE蓝屏
- ¥50 有数据,怎么建立模型求影响全要素生产率的因素
- ¥50 有数据,怎么用matlab求全要素生产率
- ¥15 TI的insta-spin例程
- ¥15 完成下列问题完成下列问题
- ¥15 C#算法问题, 不知道怎么处理这个数据的转换
- ¥15 YoloV5 第三方库的版本对照问题