tu.cpp

几个常用的数据结构算法：堆栈、链表、二叉树、图等。

#include<stdio.h> 

#include<stdlib.h> 

#include<iomanip.h> 

#include <process.h> 

//#define PROJECTNUMBER 9//10 

//#define PLANNUMBER 11//13 

typedef struct node 

{ 

    int adjvex; 

    int dut; 

    struct node *next; 

}edgenode; 

typedef struct 

{ 

    int projectname; 

    int id; 

    edgenode *link; 

}vexnode; 

//vexnode Graphicmap[PROJECTNUMBER]; 

void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber) 

{ 

    int begin,end,duttem; 

    edgenode *p; 

    for(int i=0;i<projectnumber;i++) 

    { 

    Graphicmap[i].projectname=i; 

       Graphicmap[i].id =0; 

       Graphicmap[i].link =NULL; 

    }   

    printf("某项目的开始到结束在图中的节点输入<vi,vj,dut>\n"); 

    printf("如：3,4,9 回车表示第三节点到第四节点之间的活动用了9个单位时间\n"); 

    for(int k=0;k<activenumber;k++) 

    { 

       scanf("%d,%d,%d",&begin,&end,&duttem); 

       p=(edgenode*)malloc(sizeof(edgenode)); 

       p->adjvex =end-1; 

       p->dut =duttem; 

       Graphicmap[end-1].id ++; 

       p->next =Graphicmap[begin-1].link ; 

       Graphicmap[begin-1].link =p; 

    } 

} 

int SearchMapPath(vexnode* Graphicmap,int projectnumber,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<projectnumber;i++) ve[i]=0; 

    for(i=0;i<projectnumber;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[j]+p->dut ; 

           if(Graphicmap[k].id ==0) 

              topologystack[++rear]=k; 

           p=p->next ; 

       } 

    } 

    if(m<projectnumber) 

    { 

       printf("\n本程序所建立的图有回路不可计算出关键路径\n"); 

       printf("将退出本程序\n"); 

       return 0; 

    } 

    totaltime=ve[projectnumber-1]; 

    for(i=0;i<projectnumber;i++) 

       vl[i]=totaltime; 

    for(i=projectnumber-2;i>=0;i--) 

    { 

       j=topologystack[i]; 

       p=Graphicmap[j].link ; 

       while(p) 

       { 

           k=p->adjvex ; 

           if((vl[k]-p->dut )<vl[j]) 

              vl[j]=vl[k]-p->dut ; 

           p=p->next ; 

       } 

    } 

    i=0; 

    printf("| 起点 | 终点 |  最早开始时间  |  最迟完成时间  | 差值 |  备注  |\n"); 

    for(j=0;j<projectnumber;j++) 

    { 

       p=Graphicmap[j].link; 

       while(p) 

       { 

           k=p->adjvex ; 

           e[++i]=ve[j]; 

           l[i]=vl[k]-p->dut; 

           printf("| %4d | %4d |    %4d    |    %4d    | %4d |",Graphicmap[j].projectname +1,Graphicmap[k].projectname +1,e[i],l[i],l[i]-e[i]); 

           if(l[i]==e[i]) 

              printf(" 关键活动 |"); 

           printf("\n"); 

           p=p->next ; 

       } 

    } 

 return 1; 

} 

void seekkeyroot() 

{ 

    int projectnumber,activenumber,totaltime=0; 

    system("cls"); 

    printf("请输入这个工程的化成图形的节点数:"); 

    scanf("%d",&projectnumber); 

  printf("请输入这个工程的活动个数:"); 

  scanf("%d",&activenumber); 

  vexnode* Graphicmap=(vexnode*)malloc(projectnumber*sizeof(vexnode)); 

  CreateGraphic(Graphicmap,projectnumber,activenumber); 

  SearchMapPath(Graphicmap,projectnumber,activenumber,totaltime); 

  printf("整个工程所用的最短时间为：%d个单位时间\n",totaltime); 

  system("pause"); 

} 

int main() 

{ 



    char ch; 

    for(;;) 

    { 

       do 

       { 

           system("cls"); 

           printf("|             欢迎进入求关键路径算法程序              |"); 

      for(int i=0;i<80;i++)printf("*"); 

           printf("%s","(S)tart开始输入工程的节点数据并求出关键路径\n"); 

           printf("%s","(E)xit退出\n"); 

           printf("%s","请输入选择:"); 

           scanf("%c",&ch); 

           ch=toupper(ch); 

       }while(ch!='S'&&ch!='E'); 

     switch(ch) 

     { 

      case'S': 

      seekkeyroot(); 

           break; 

       case'E': 

           return 1; 

     } 

    } 

}