C语言数据结构--相对路径设计
|
#include #include #include #include typedef struct node//边表结点 { int adjvex; //邻接点编号 int dut; //弧的信息 struct node *next; //下一条弧指针 }edgenode; typedef struct //顶点表结点 { int projectname;//顶点域 int id;//顶点的入度信息 edgenode *link; //边表头指针 }vexnode; void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber)//创建图 { int begin,end,duttem; //分别代表弧的前节点，尾节点，活动时间 edgenode *p;// 边表头指针 for(int i=0;i { Graphicmap[i].projectname=i;//顶点的命名按0，1，2，3...... Graphicmap[i].id =0;//顶点的信息的度数均赋为零 Graphicmap[i].link =NULL; } printf("n"); printf("请输入某项目的信息，并请用整形数字表示（格式：弧头，弧尾，权值）：n"); printf("例如:输入1,2,4 即代表结点1与4之间的活动需要4个时间单位。n"); printf("n"); for(int k=0;k { scanf("%d,%d,%d",&begin,&end,&duttem); //请输入第%d条的起点、终点和权值 p=(edgenode*)malloc(sizeof(edgenode));//临时分配存储空间 p->adjvex =end-1;//因为是从零开始记的，姑要减一，就是让终点插入到邻接表内 p->dut =duttem; //该弧的活动时间为duttem Graphicmap[end-1].id ++; //入度加一 p->next =Graphicmap[begin-1].link ; Graphicmap[begin-1].link =p;//让下一个节点作为下一插入节点的前驱节点 } } int SearchMapPath(vexnode* Graphicmap,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));//用来表示在不推迟整个工程的前提下，VJ允许最迟发生的时间 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[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--)// 用逆拓扑排序来求活动Ai最迟完成开始时间，即从最后一个节点减去最短的时间 { 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"); 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 | %11d | %11d | %3d |",Graphicmap[j].projectname +1,Graphicmap[k].projectname +1,e[i],l[i],l[i]-e[i]); if(l[i]==e[i]) //当差值为零时，则为关键路径 printf(" 关键活动 <%2d,%4d>", Graphicmap[j].projectname +1,Graphicmap[k].projectname +1); printf("n"); p=p->next ; } } return 1; } void seekkeyroot()//求关键路径的主函数 { int projectnumber,activenumber,totaltime=0; printf("n"); printf("输入符合标准，欢迎进入求关键路径的系统!n"); printf("n"); printf("请输入这个项目的AOE-网的节点数: "); scanf("%d",&projectnumber); printf("请输入这个项目的AOE-网的活动个数: "); scanf("%d",&activenumber); vexnode* Graphicmap=(vexnode*)malloc(projectnumber*sizeof(vexnode)); CreateGraphic(Graphicmap,projectnumber,activenumber);//创建邻接图 SearchMapPath(Graphicmap,totaltime);//求出最大路径，并打印出关键路径 printf("n"); printf("整个工程所用的最短时间为：%d个单位时间n",totaltime); system("pause"); } int main() { char ch; for(;;) { do { system("cls"); printf("☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★ n"); printf(" 欢迎进入求关键路径算法程序 n"); printf("☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★ n"); printf("%s","ns(start)开始输入工程的节点数据并求出关键路径n"); printf("n"); printf("%s","e(exit)退出n"); printf("n"); printf("%s","请输入选择:"); scanf("%c",&ch); ch=toupper(ch); }while(ch!='S'&&ch!='E'); switch(ch) { case'S': seekkeyroot(); break; case'E': return 1; } } } （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |