critical_path.c

本设计完成了要求的所有功能

#include<stdlib.h>
#include<stdio.h>
#define MAXVEX 200
#define FALSE 0
#define TRUE 1
#define MAXEDGE 80

typedef struct EdgeNode EdgeNode;
typedef struct EdgeNode * PEdgeNode;
typedef struct EdgeNode * EdgeList;
typedef float Adj;

struct EdgeNode {
    int endvex;			/* 相邻顶点 */
    Adj weight;
    PEdgeNode nextedge;	/* 指向下一个顶点 */
};						/* 边表中的结点 */

typedef struct {
    EdgeList edgelist;		/* 边表的头指针 */
} VexNode;				/* 顶点表中的结点 */


typedef struct {
    int vexs_no[MAXVEX];		/* 顶点在顶点表中的下标值 */
} Topo;

typedef struct {
    int n;				/* 图的顶点个数 */
    VexNode vexs[MAXVEX];
} GraphList;     /*图的定义*/




void Menu()
     //菜单函数

{
	printf("\n=============Critical_path==============\n");
	printf("\n Please choose a function:\n");
	printf("\n 1.The system establishes a diagram, the use that make to adjust to ");
	printf("\n   try.Beg an its Critical path also.");
	printf("\n 2.The customer establishes a diagram.Beg an its Critical ");
	printf("\n   path also.");
	
	printf("\n 0.Exit.\n\n");
	printf("========================================\n");
	printf("\nPlease input number:");
}//Menu();




main()
{
	void Insert_peak(GraphList* p,int a,int b,float weight);
    GraphList* Cre_GList();
	void Cre_AOV(EdgeList p, int* indegree, int* top);
	void Count_ee(GraphList* pe,Topo* t, Adj* ee);
	void Count_out(GraphList * pe,Adj* ee,Adj* le, Adj* e, Adj* l);
	void Count_le(GraphList * pe,Topo* t, Adj* ee, Adj* le) ;
	int Toposort(GraphList * v, Topo * t) ;
	int Critical_Path(GraphList * pe); 

    
	int i,j;
	char a[100];
	
	char Cre_sys[]={"The diagram that system establish is: "};
	char re_choose[]={"\nThe choice is invalid, please re- choose....\n"};
    
	GraphList* p;
	int aa[]={0,0,1,2,1,4,3};
	int bb[]={1,2,2,3,4,5,5};
	float ww[]={1,2,3,4,5,6,7};/*调试关键路径的数据*/


    

	while(1)
	{
		Menu();
		for(j=0;j<100;j++)
		{
			scanf("%c",&a[j]);
			if(a[j]=='\n') break;
		}   /*功能选择*/
		
        if(a[1]!='\n'){
			printf("\n%s",re_choose);
			system("pause");
			system("cls");
			continue;
		}
        else{
			if(a[0]=='0') break;
			
			switch(a[0])
			{
			case '1' :
				p = (GraphList*)malloc(sizeof(GraphList));
				p->n = 6;
				for (i = 0; i < p->n; i++)
					p->vexs[i].edgelist = NULL;
				printf("\n%s\n",Cre_sys);
				for (i = 0; i < 7; i++){
					printf("%d. %d,%d,%.0f\n",i+1,aa[i],bb[i],ww[i]);
					Insert_peak(p,aa[i],bb[i],ww[i]);
				}
				if (Critical_Path(p) == FALSE)
					printf("There is no critical path!\n");
				system("pause");
				system("cls");
				break;
            case '2' :
				p = Cre_GList();
				if (Critical_Path(p) == FALSE)
					printf("There is no critical path!\n");
    
				system("pause");
				system("cls");
				break;      
		    case '3' :
				
				system("pause");
				system("cls");
				break;
		     
		    default  :
				printf("\n%s",re_choose);
				system("pause");
				system("cls");
		
			}/*end switch*/
		}/*end else*/
	}/*end while*/
}


/*插入一个新点*/
void Insert_peak(GraphList* p,int a,int b,float weight)
{
    EdgeList pp;
    PEdgeNode temp;
    temp = (PEdgeNode)malloc(sizeof(EdgeNode));
    temp->endvex = b;
    temp->nextedge = NULL;
    temp->weight = weight;
    pp = p->vexs[a].edgelist;
    if (pp == NULL)
        p->vexs[a].edgelist = temp;
    else {
        while (pp->nextedge != NULL)
            pp = pp->nextedge;
        pp->nextedge = temp;
    }
}



/* 构造邻接表*/
GraphList* Cre_GList()
{
    GraphList* p;
    Adj w;
    int i,a,b,k;
    p = (GraphList*)malloc(sizeof(GraphList));
    printf("\nplease insert the number of the vex in yout graph : ");
    scanf("%d",&p->n);
	printf("\nplease insert the number of the edge:");
	scanf("%d",&k);
    for (i = 0; i < p->n; i++)
        p->vexs[i].edgelist = NULL;
    printf("please insert three number in this pattern a,b,w .and a，b stand for the peak，");
	printf("\nc stand for weigh 。\n");
    for (i = 0; i < k; i++){
	  printf("%d. ",i+1);
      scanf("%d,%d,%f",&a,&b,&w);
      Insert_peak(p,a,b,w);
    }
    return p;
}



/*建立AOV-网*/
void Cre_AOV(EdgeList p, int* indegree, int* top) 
{
    int k;

    while (p) {                       /* 删除以该顶点为起点的边 */
        k = p->endvex;
        indegree[k]--;
        if (indegree[k] == 0) {         /* 将入度为零的边入栈 */
            indegree[k] = *top;
            *top = k;
        }
        p = p->nextedge;
    }
}


 
/* 搜索整个邻接表 ,求出所有顶点的入度数 */
void Search_InDegree(GraphList* g, int *InDegree) 
{
    int i;
    PEdgeNode p;

    for (i = 0; i < g->n; i++)
        InDegree[i] = 0;

    for (i = 0; i < g->n; i++) {
        p = g->vexs[i].edgelist;
        while(p) {
            InDegree[p->endvex]++;
            p = p->nextedge;
        }
    }
}


/* 拓扑排序*/
int Toposort(GraphList * v, Topo * t) 
{
    void Search_InDegree(GraphList* g, int *InDegree);
	void Cre_AOV(EdgeList p, int* indegree, int* top) ;
	EdgeList p;
    int i, j, node_no = 0, top = -1;
    int Indegree[MAXVEX];
 
    Search_InDegree(v, Indegree); /*调用函数*/  
    for (i = 0; i < v->n; i++)
        if (Indegree[i] == 0) {        /* 将入度为零的顶点入栈 */
            Indegree[i] = top; top = i;
        }

    while (top != -1) {                /*栈不为空时 */
        j = top;
        top = Indegree[top];               /* 取出栈顶元素 */
        t->vexs_no[node_no++] = j;
        p = v->vexs[j].edgelist;    /* 取该元素边表中的第一个边结点 */
        /*删除该结点,构造新的AOV网*/
       
        Cre_AOV(p, Indegree, &top);
    }

    if (node_no < v->n) {       /* 判断AOV网中是否存在回路 */
        printf("The aov network has a cycle\n");
        return FALSE;
    }

    return TRUE;
}



/* 计算数组ee*/
void Count_ee(GraphList* pe,Topo* t, Adj* ee) 
{
    int i, j, k;
    EdgeList p;

    for (i = 0; i < pe->n; i++) ee[i] = 0;
    for (k = 0; k < pe->n; k++) {       /* 求事件vj可能的最早发生时间ee(j) */
        i = t->vexs_no[k];
        p = pe->vexs[i].edgelist;
        while (p != NULL) {
            j = p->endvex;
            if (ee[i] + p->weight > ee[j])
                ee[j] = ee[i] + p->weight;
            p = p->nextedge;
        }
    }
}




/* 计算数组le*/
void Count_le(GraphList * pe,Topo* t, Adj* ee, Adj* le) 
{
    int i, j, k;
    EdgeList p;
    for (i = 0; i < pe->n; i++)         /* 求事件vi允许的最迟发生时间le(i) */
        le[i] = ee[pe->n - 1];
    for (k = pe->n - 2; k >= 0; k--) {
        i = t->vexs_no[k];
        p = pe->vexs[i].edgelist;
        while (p != NULL) {
            j = p->endvex;
            if( le[j] - p->weight < le[i] )
                le[i] = le[j] - p->weight;
            p = p->nextedge;
        }
    }
}




/* 计算数组e,l并输出结果*/
void Count_out(GraphList * pe,Adj* ee,Adj* le, Adj* e, Adj* l) 
{
    int i, j, k = 0;
    EdgeList p;
    printf("\nThe Critical path that search come out is: \n");
    /* 求活动的最早开始时间e(k)及最晚开始时间l(k) */
    for (i = 0; i < pe->n; i++) {
        p = pe->vexs[i].edgelist;
        while (p != NULL) {
            j = p->endvex;
            e[k] = ee[i];
            l[k] = le[j] - p->weight;
            if (e[k] == l[k])
                printf("(%2d, %2d), ", i, j);
            k++;
            p = p->nextedge;
        }
    }
}



/* 关键路径算法*/
int Critical_Path(GraphList * pe) 
{
	void Count_ee(GraphList* pe,Topo* t, Adj* ee);
	void Count_out(GraphList * pe,Adj* ee,Adj* le, Adj* e, Adj* l);
	void Count_le(GraphList * pe,Topo* t, Adj* ee, Adj* le) ;
	int Toposort(GraphList * v, Topo * t) ;

    Adj ee[MAXVEX], le[MAXVEX], l[MAXEDGE], e[MAXEDGE];
    Topo topo;
    if (Toposort(pe, &topo) == FALSE)               /* 求AOE网的一个拓扑序列 */
        return FALSE;
    Count_ee(pe, &topo, ee); /*计算数组ee*/
    Count_le(pe, &topo, ee, le);/*计算数组le*/
    Count_out(pe, ee, le, e, l);/*计算数组e,l并输出结果*/
    printf("\n");
    return TRUE;
}