optimal.cpp

最优二分检索树,欢迎下载 呵呵 大家多支持

#include <iostream>
#include <stdlib.h>
using namespace std;

#define max 1000000
#define m   10
#define n   10

void optimal(float *p,float *q,float (*&root)[n+1],float (*&e)[n+2])  //void optimal(float *p,float *q,int n,float* &root[n])

{
	float (*w)[n+2];
	w=new float[n+2][n+2];

	for(int i=1;i<=n+1;i++)
	{
		e[i][i-1]=q[i-1];
		w[i][i-1]=q[i-1];
	}

	for(int l=1;l<=n;l++)
	{
		for(i=1;i<=n-l+1;i++)
		{
			int j=i+l-1;
			e[i][j]=max;
			w[i][j]=w[i][j-1]+p[j]+q[j];
			for(int r=i;r<=j;r++)
			{
				float t;
				t=e[i][r-1]+e[r+1][j]+w[i][j];
				if(t<e[i][j])
				{
					e[i][j]=t;
					root[i][j]=r;
				}
			}
		}
	}
	//return root;//in book return root and e
}

void print(float (*root)[n+1],int i,int j)
{
		if(i==j)
			cout<<root[i][j];

		cout<<"( ";
		print(root,i,root[i][j]-1);
		print(root,root[i][j]+1,j);
		cout<<")";
		

}



void main()
{
//********************intialize******************************
	float*p,*q;
	p=new float[n+1];
	q=new float[n+1];

	float (*root)[n+1];
	root=new float[n+1][n+1];
	float (*e)[n+2];
	e=new float[n+2][n+2];

	for(int i=1;i<=n;i++)                             //initialize  root[][]  and e[][]
	{
		
		for(int j=1;j<=n;j++)
		{
			root[i][j]=0;
		}
	}	
	for(i=0;i<=n+1;i++)                             //initialize  e[][]
	{
		for(int j=0;j<=n+1;j++)
		{
			e[i][j]=0;
		}
	}
   


	
//********************produce p and q randomly**************************
	float temp=0;  //used for below p and q
	for(i=0;i<=n;i++)              
	{
		float t1,t2;
		if(i!=0)						//p[0]不用
		{
		
				t1=((float)(rand()%m)/100);
				if(temp+t1<1&&t1!=0)
					p[i]=t1;
				else
					while(temp+t1>=1||t1==0)
					{
						t1=((float)(rand()%m)/100);
						p[i]=t1;
					}
				temp+=t1;
		}
		
		if(i!=n)
		{
			t2=((float)(rand()%m)/100);
			if(temp+t2<1&&t2!=0)
				q[i]=t2;
			else
				while(temp+t2>=1||t2==0)
				{
					t2=((float)(rand()%m)/100);
					q[i]=t2;
				}
					temp+=t2;
		}
	
		
	}
	q[n]=1-temp;
	
//****************make it optimal binary search tree *********************	
	optimal(p,q,root,e);
//**********************output*********************
	cout<<"q :\n";
	for(i=0;i<=n;i++)
		cout<<q[i]<<"  ";
	
	cout<<endl<<endl;

	cout<<"p :\n";
	for(i=1;i<=n;i++)
		cout<<p[i]<<"  ";

	cout<<endl<<endl<<"root:\n";

	for(i=1;i<=n;i++)
	{	
		for(int j=1;j<=n;j++)
			cout<<root[i][j]<<"  ";
		cout<<endl;
	}

	cout<<endl<<endl<<"e:\n";

	for(i=1;i<=n+1;i++)
	{	
		for(int j=0;j<=n+1;j++)
			cout<<e[i][j]<<"\t";
		cout<<endl;
	}

	print(root,1,n);

	delete p;
	delete q;
	delete []root;
	delete []e;
}