最优二叉查找树
【源程序】
//本程序测试用例为课本例题
#include <stdio.h>
#define INF 1000000000
//将这两个二维数组定义为全局变量，从而可以避免在函数之间进行参数的传递double C[100][100];
int R[100][100];
double OptimalBST(double p[], int n)
{
int i, j, k, d;
int mink;
//注意这里min 和sum一定要定义成double类型，否则赋不上值！！
double min,sum;
for(i=1; i<=n; i++)
{
C[i][i-1]=0;
C[i][i]=p[i-1];
R[i][i]=i;
}
C[n+1][n]=0;
for(d=1; d<n; d++)
for(i=1; i<=n-d; i++)
{
j=i+d;
min=INF;
mink=i;
sum=0;
for(k=i; k<=j; k++)
{
sum+=p[k-1];
if (C[i][k-1]+C[k+1][j]<min)
{
min=C[i][k-1]+C[k+1][j];
mink=k;
}
}
C[i][j]=min+sum;
R[i][j]=mink;
}
return C[1][n];
}
int main()
{
int n;
double p[100];
printf("请输入字符个数：");
scanf("%d",&n);
printf("\n");
printf("请输入每个字符的查找概率：");
for(int i=0; i<n; i++)
{
scanf("%lf",&p[i]);
}
printf("\n");
printf("最少平均比较次数: %.2f",OptimalBST(p,n));
printf("\n");
printf("\n二维表C：\n");
for(int i=1; i<=n+1; i++)
{
for(int j=0; j<=n; j++)
printf("%.1f ",C[i][j]);
printf("\n");
}
printf("\n二维表R：\n");
for(int i=1; i<=n+1; i++)
{
for(int j=0; j<=n; j++)
printf("%d ",R[i][j]);
printf("\n");
}
return 0;
}
【运行结果】。