拓扑排序.txt

数据结构学习用到的一些程序！！里面有二叉树相关的几个

#include<stdio.h>
#include<cstdlib>
#define outmax 3//最大出度
#define inmax 2//最大入度
#define vex 9//顶点个数
#define max 10000//定义极大值
int linjie_0[vex][outmax]={{1,2,3},{4},{4},{5},{6,7},{7},{8},{8},{-1}};//出邻接顶点
int linjie_1[vex][inmax]={{-1},{0},{0},{0},{1,2},{3},{4},{4,5},{6,7}};//入邻接顶点
int label_1[vex][3]={{0,0,3},{0,1,1},{0,1,1},{0,1,1},{0,2,2},{0,1,1},{0,1,1},{0,2,1},{0,2,0}};//第0列是拓扑列标志位，第1列是入度，第2列是出度
int labevl[vex][3]={{0,0,3},{0,1,1},{0,1,1},{0,1,1},{0,2,2},{0,1,1},{0,1,1},{0,2,1},{0,2,0}};//第0列是拓扑列标志位，第1列是入度（在拓扑排序子程序中值要改变），第2列是出度
int juzhen[vex][vex];//邻接矩阵
int tuopu[vex],tuopu_k=0;//拓扑序列
int ve[vex],vl[vex];//顶点，事件的最早发生时间和最迟发生时间
int e[vex][vex],l[vex][vex];//边，活动的最早开始时间和最迟开始时间，两者相等的即为关键路径
void tuopupaixu();//拓扑排序子程序
void make_ve();//事件最早发生时间子程序
void make_vl();//事件最迟发生时间子程序
void critical_path();//关键路径子程序
int main()
{
    int i,j;
    for(i=0;i<vex;i++)
    for(j=0;j<vex;j++)
	{
        tuopu[i]=0;
        ve[i]=0;
        juzhen[i][j]=max;
        vl[i]=max;
	}
    juzhen[0][1]=6;
    juzhen[0][2]=4;
    juzhen[0][3]=5;
    juzhen[1][4]=1;
    juzhen[2][4]=1;
    juzhen[3][5]=2;
    juzhen[4][6]=9;
    juzhen[4][7]=7;
    juzhen[5][7]=4;
    juzhen[6][8]=2;
    juzhen[7][8]=4;//初始化
    tuopupaixu();
    make_ve();
    make_vl();
    critical_path();
    printf("\n");
    system("pause");
    return 0;
}


void tuopupaixu()
{
    int i,j;
    while(1)
	{
       for(i=0;i<vex;i++)
       if(labevl[i][0]==0)
       j=1;
       if(j==0)
       break;
       for(i=0;i<vex;i++)
      if(labevl[i][0]==0 && labevl[i][1]==0)
	  {
         labevl[i][0]=1;//删除已经排入拓扑序列的顶点
         tuopu[tuopu_k]=i;//拓扑编号
         tuopu_k++;
         for(j=0;j<labevl[i][2];j++)
         labevl[linjie_0[i][j]][1]--;//使和排入拓扑序列的顶点相邻的顶点的入度减1
	  }
	}
    printf("拓扑序列：");
    for(i=0;i<vex;i++)
    printf("%d",tuopu[i]);
}
void make_ve()
{
     printf("\n事件的最早开始时间：");
     int i,j;
     int a1,a2,a3;
     for(i=0;i<vex;i++)//按拓扑序列的顺序做
	 {
        a1=tuopu[i];
        for(j=0;j<label_1[a1][2];j++)//从源点到汇点推进
		{
            a2=linjie_0[a1][j];//向后邻接顶点
            a3=juzhen[a1][a2];//边的权值
            if(ve[a2]<ve[a1]+a3)
            ve[a2]=ve[a1]+a3;//ve(j)=Max { ve(i)+dut(<i,j>) }
		}
	 }
     for(i=0;i<vex;i++)
     printf("[%d]-%d",i,ve[i]);
}
void make_vl()
{
     printf("\n事件的最迟开始时间：");
     int i,j;
     int a1,a2,a3;
     vl[vex-1]=ve[vex-1];//汇点的vl值等于其ve值
     for(i=vex-1;i>0;i--)//按逆拓扑序列的顺序做
	 {
         a1=tuopu[i];
         for(j=0;j<label_1[a1][1];j++)//从汇点到源点推进
		 {
             a2=linjie_1[a1][j];//向前邻接顶点
             a3=juzhen[a2][a1];//边的权值
             if(vl[a2]>vl[a1]-a3)
             vl[a2]=vl[a1]-a3;//vl(i)=Min { vl(j)-dut(<i,j>) }
		 }
	 }
     for(i=0;i<vex;i++)
     printf("[%d]-%d",i,vl[i]);
}
void critical_path()
{
     printf("\n关键路径：");
     int i,j;
     for(i=0;i<vex;i++)
     for(j=0;j<vex;j++)
	 {
        if(juzhen[i][j]!=max)
		{
            e[i][j]=ve[i];//e(i)=ve(i)
            l[i][j]=vl[j]-juzhen[i][j];//l(i)=vl(j)-dut(<i,j>)
            if(e[i][j]==l[i][j] && e[i][j]!=max)//关键路径的判断
            printf("[%d]-->[%d] ",i,j);
		}
	 }
}