besttree.c

《数据结构》教材源程序,可以让你轻松的根据教材学习数据结构

/***********************************************/
/*              构造最佳二叉排序树             */
/*  文件名:BESTTREE.C   函数名：conbesttree()  */
/***********************************************/

#define n 20         /*n为内部结点最大个数*/
int p[n],q[n+1];     /* p、q分别存放内部结点与外部结点的查找概率 */
void conbesttree(int c[n+1][n+1],int w[n+1][n+1],int r[n+1][n+1],int n0)
{  int i,j,k0,k,d,m;
   for (i=0;i<=n0;i++)     /*初始化，三个矩阵下三角清0*/
      for (j=0;j<=i;j++)
           {  c[i][j]=0;
              r[i][j]=0;
              w[i][j]=0;
            }
   for (i=0;i<=n0;i++)     /*构造初始w[i,j]矩阵*/
       {  w[i][i]=q[i];
          for (j=i+1;j<=n0;j++)
	     w[i][j]=w[i][j-1]+p[j]+q[j];
       }
   for (j=1;j<=n0;j++)     /*构造一个内部结点的最佳二叉排序树*/
       {
         c[j-1][j]=w[j-1][j];
         r[j-1][j]=j;
        }
   for (d=2;d<=n0;d++)     /*构造包括d个内部结点的最佳二叉排序树*/
       for (j=d;j<=n0;j++)
         {i=j-d;
          m=c[i+1][j];     /*根为i+1，右子树花费为C[i+1,j]*/
          k0=i+1;
          for (k=i+2;k<=j;k++)
             if (c[i][k-1]+c[k][j]<m )
                   {
                      m=c[i][k-1]+c[k][j];
                      k0=k;
                    }
             c[i][j]=w[i][j]+m;
	     r[i][j]=k0;
          }
}
main()
{int n0,i,j;
 int c[n+1][n+1],w[n+1][n+1],r[n+1][n+1];
 printf("Please input n:");
 scanf("%d",&n0);
 for (i=1;i<=n0;i++)
    { printf("p[%d]=",i);scanf("%d",&p[i]);}   /*输入内部结点的查找概率*/
 for (i=0;i<=n0;i++)
    { printf("q[%d]=",i);scanf("%d",&q[i]);}   /*输入外部结点的查找概率*/
 conbesttree(c,w,r,n0);    /*求最佳二叉排序树*/
 printf("Cost is:\n");     /*输出构造过程中各子树的代价*/
 for (i=0;i<=n0;i++)
   { for (j=0;j<=n0;j++)
       if (j<i) printf("    "); else printf("%4d",c[i][j]);
     printf("\n");
   }
 printf("W[i,j] is:\n");   /*输出权值矩阵上三角部分*/
 for (i=0;i<=n0;i++)
   { for (j=0;j<=n0;j++)
	if (j<i) printf("    "); else printf("%4d",w[i][j]);
     printf("\n");
   }
 printf("r[i,j] is:\n");   /*输出构造过程中各子树的根*/
 for (i=0;i<=n0;i++)
   { for (j=0;j<=n0;j++)
       if (j<i) printf("    "); else  printf("%4d",r[i][j]);
     printf("\n");
   }
}