obst.cpp

最优二分检索树的实现

//
//		OBST	最小成本的二分检索树算法
//		kingwind
//		2003.11.30
////////////////////////////////////////////////////

#include "OBST.h"

OBST::OBST(int n)
{
	this->m_n = n;

	this->m_p = new double[this->m_n + 1];
	this->m_q = new double[this->m_n + 1];
	this->m_c = new double[(this->m_n + 1)*(this->m_n + 1)];
	this->m_w = new double[(this->m_n + 1)*(this->m_n + 1)];
	this->m_r = new int[(this->m_n + 1)*(this->m_n + 1)];

	for(int i=0;i<(this->m_n + 1)*(this->m_n + 1);i++)
		this->m_r[i] = 0;
}

OBST::~OBST()
{
	delete[] this->m_c;
	delete[] this->m_p;
	delete[] this->m_q;
	delete[] this->m_w;
	delete[] this->m_r;
}

void OBST::readData()
{
	//just for test
	double t[5] = {0,3,3,1,1};
	double t2[5] = {2,3,1,1,1};

	for(int i =0;i<5;i++)
	{
		this->m_p[i] = t[i]; 
		this->m_q[i] = t2[i];
	}
}

void OBST::handle()
{
	for(int i=0;i<this->m_n;i++)
	{
		this->m_w[i*(this->m_n+1)+i] = this->m_q[i];
		this->m_r[i*(this->m_n+1)+i] = 0;
		this->m_c[i*(this->m_n+1)+i] = 0;

		this->m_w[i*(this->m_n+1)+i+1] = this->m_q[i] + this->m_q[i+1] + this->m_p[i+1];
		this->m_r[i*(this->m_n+1)+i+1] = i+1;
		this->m_c[i*(this->m_n+1)+i+1] = this->m_q[i] + this->m_q[i+1] + this->m_p[i+1];
	}

	this->m_w[(this->m_n+1)*(this->m_n+1)-1] = this->m_q[m_n];
	this->m_r[(this->m_n+1)*(this->m_n+1)-1] = 0;
	this->m_c[(this->m_n+1)*(this->m_n+1)-1] = 0;

	for(int m=2;m<m_n+1;m++)
	{
		for(int i=0;i<m_n-m+1;i++)
		{
			int j= i+m;
			this->m_w[i*(m_n+1)+j] = this->m_w[i*(m_n+1)+j-1] + this->m_p[j] + this->m_q[j];
			double temp = 9999;//设置为一个较大的数值
			int k = 0;
			for(int l=this->m_r[i*(m_n+1)+j-1];
			l<this->m_r[(i+1)*(m_n+1)+j]+1;
			l++)
			{
				if(temp > (this->m_c[i*(m_n+1)+l-1]+this->m_c[l*(m_n)+j]))
				{
					temp = (this->m_c[i*(m_n+1)+l-1]+this->m_c[l*(m_n)+j]);
					k = l;
				}
			}

			this->m_c[i*(m_n+1)+j] = this->m_w[i*(m_n+1)+j] + this->m_c[i*(m_n+1)+k-1] + this->m_c[k*(m_n+1)+j];
			this->m_r[i*(m_n+1)+j] = k;
		}
	}
}

void OBST::printResult()
{
	cout<<"每颗树Tij的树根如下所示:\n";
	for(int i=0;i<=m_n;i++)
	{
		for(int j=0;j<=m_n;j++)
		{
			if((this->m_r[i*(m_n+1)+j]) == 0 && i!=j)
				cout<<"  \t";
			else
				cout<<(this->m_r[i*(m_n+1)+j])<<"\t";
		}
		cout<<endl;
	}
	cout<<endl;
}