main.cpp

动态规划实现的字典排序

#include "OBSTNode.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <ostream>
#include <string>
#include <math.h>
#include<iomanip>

#define MAXSIZE 10
#define A 2
using namespace std;
vector<OBSTNode> obsn_var;
vector<float> float_q_var;
bool analysefile(int &sum)
{
	ifstream inFile(".\\test.txt");
	if(inFile.fail())
	{
		cerr<<"Unable to open file for reading...."<<endl;
		exit(1);
	}
    int i=0;
	string nextToken;
	OBSTNode obstnode;
	while(inFile>>nextToken)
	{
		if(i%2==0)	
		{
			obstnode.setvalue(atoi(nextToken.c_str()));
			sum=sum+atoi(nextToken.c_str());
		}
		if(i%2==1)
		{
			obstnode.setcontent(nextToken);
			obsn_var.push_back(obstnode);
		}
		i++;
	}
	inFile.close();
	return true;
}

bool setprobility(int sum)
{
	for(int i=0;i<obsn_var.size();i++)
	{
		obsn_var[i].setpro(sum);
	}
	return true;
}


int commonprefix(int i_first,int i_next)
{
	int i=0;
	int i_tmp1=obsn_var[i_first].returncontent().size();
	int i_tmp2=obsn_var[i_next].returncontent().size();
	const char * pch_tmp1=obsn_var[i_first].returncontent().c_str();
	const char * pch_tmp2=obsn_var[i_next].returncontent().c_str();
	int i_ch1=0,i_ch2=1;
    for(int k=0;k<i_tmp1/2&&k<i_tmp2/2;k++)
	{
		if(pch_tmp1[i_ch1]==pch_tmp2[i_ch1]&&pch_tmp1[i_ch2]==pch_tmp2[i_ch2])
		{
			i++;
			i_ch1=i_ch1+2;
			i_ch2=i_ch2+2;
		}
		else
			break;
	}
	return i;
}

void getQsum(float &i_q_sum)
{
	int i_total_obsn_var=obsn_var.size();
	float_q_var.push_back(1);
	for(int k=0;k<i_total_obsn_var-1;k++)
	{
		float i_q_number=(float)1/(pow(A,commonprefix(k,k+1)));
		i_q_sum=i_q_sum+(float)1/(pow(A,commonprefix(k,k+1)));
		float_q_var.push_back(i_q_number);
	}
	float_q_var.push_back(1);
	i_q_sum=i_q_sum+2;
}

void setQ(float i_q_sum)
{
	for(int m=0;m<float_q_var.size();m++)
		float_q_var[m]=(float_q_var[m]/(float)i_q_sum)*0.01;                   

}

void height(vector<vector<int> > &root,int i_left,int i_right,int i_height)
{
	if(i_left<=i_right)
	{
		int i_root=root[i_left][i_right];
		obsn_var[i_root].sethight(i_height);
		i_height=i_height+1;
		height(root,i_left,i_root-1,i_height);
		height(root,i_root+1,i_right,i_height);
	}
}
void OPTIMAL_BST()
{
   cout<<"正在申请e，w，root的空间，请耐心等待......"<<endl;
   vector<vector<float> > e(MAXSIZE+1, vector<float>(MAXSIZE+1)); 
   vector<vector<float> > w(MAXSIZE+1, vector<float>(MAXSIZE+1));
   vector<vector<int> > root(MAXSIZE,vector<int>(MAXSIZE));

	for(int i=0;i<MAXSIZE+1;i++)
	{
		e[i][i]=float_q_var[i];
		w[i][i]=float_q_var[i];
	}

 	for(int l=0;l<=MAXSIZE;l++)
 	{
 		int i=0;
 		for(;i<MAXSIZE-l;i++)
 		{
 			int j=i+l+1;
 			e[i][j]=10;
			w[i][j]=w[i][j-1]+obsn_var[j-1].returnprobility()+float_q_var[j];	
			int r=i;
		    for(;r<=j&&r<10;r++)
			{
				float t=e[i][r]+e[r+1][j]+w[i][j];
                if(t<e[i][j])
				{
					e[i][j]=t;				
					root[i][j-1]=r;
				}

			}
 		}

	}
	cout<<"正在运行optimal BST，请耐心等待......"<<endl;
	int i_root=root[0][MAXSIZE-1];
	cout<<"根节点的位置:"<<i_root<<endl;
	cout<<"根节点处的权值:"<<w[0][MAXSIZE]<<endl;
	cout<<"OBST的平均搜索代价:"<<e[0][MAXSIZE]<<endl;
	height(root,0,MAXSIZE-1,0);
	cout<<"正在释放申请的e，w，root的空间!!!"<<endl;
}

void main()
{
    obsn_var.reserve(MAXSIZE);
	int i_sum=0;
	if(analysefile(i_sum)==true)
	{
//	for(int i=0;i<10;i++)
//		cout<<obsn_var[i].returnvalue()<<obsn_var[i].returncontent()<<endl;
	setprobility(i_sum);
//	for(int j=0;j<10;j++)
//		cout<<obsn_var[j].returnprobility()<<obsn_var[j].returncontent()<<endl;
//	cout<<i_sum<<endl;
    float i_q_sum=0;
	getQsum(i_q_sum);
//	cout<<i_q_sum<<endl;
	setQ(i_q_sum);
//	for(int k=0;k<=10;k++)
//		cout<<float_q_var[k]<<endl;
//	for(int i=0;i<MAXSIZE;i++)
//		cout<<obsn_var[i].returnvalue()<<obsn_var[i].returncontent()<<" "<<obsn_var[i].returnheight()<<endl;
	OPTIMAL_BST();
//	for(int i=0;i<MAXSIZE;i++)
//		cout<<obsn_var[i].returnvalue()<<obsn_var[i].returncontent()<<" "<<obsn_var[i].returnheight()<<endl;
	}
	else 
		cout<<"打开文件失败!"<<endl;
}