最优二叉查找树_动态规划

最优二叉查找树

【源程序】

//本程序测试用例为课本例题

#include

#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

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=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

{

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;

}

【运行结果】