algorithm_10_3_opt.cpp

从输入文件中读取数据,构造最优二叉树,输入文件格式如下: 节点的值 出现概率 例如: A 0.001 B 0.25

// Algorithm_10_3_OPT.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <fstream>
#include <iostream>
#include <stdio.h>
#include <time.h>
#include <string>
	using namespace std;

int StringToNumber(char *s)
{	
	long long int sum=0;
	for(int i=0;s[i]!='\0';i++)
		sum=sum*10+s[i]-'0';
	return sum;
}


void inputNodeSum(int &NodeCount)
{
	char tmpChar;
	char input[1000];
	char num[5];
	int i = 0;

	while((tmpChar=getchar())!='\n')
	{
		if(((tmpChar>='0')&&(tmpChar<='9'))&&(i <= 4))
		{
			num[i++] = tmpChar;
		}
		else
			break;
	}
	num[i] = '\0';
	while(tmpChar != '\n')
	{
		tmpChar = getchar();
	}
	NodeCount = StringToNumber(num);
}

float StringToFloat(char *s)
{	
	int i = 0;
	float sum=0;
	while(s[i] != '\0')
		i++;
	i -= 1;
	for(;s[i] != '.';i--)
		sum=sum*0.1+s[i]-'0';
	sum *= 0.1;
	return (sum);
}

void inputProb(float &prob)
{
	int i = 0;
	int DianCount = 0;
	char tmpChar;
	char input[6];
	bool CheckValid = true;
	while((tmpChar=getchar())!='\n')
	{
		if((((tmpChar>='0')&&(tmpChar<='9'))||(tmpChar == '.'))&&(i <= 5))
		{
			if(tmpChar == '.')
			{
				DianCount++;
				if(((DianCount == 1)&&(i != 1))||(DianCount > 1))
				{
					CheckValid = false;
					break;
				}
			}
			input[i++] = tmpChar;
		}
		else
			break;
	}
	input[i] = '\0';
	while(tmpChar != '\n')
	{
		tmpChar = getchar();
	}
	if(i==0)
		prob = -1;
	else
	{
		if(CheckValid == false)
			prob =  -1;
		else
			prob = StringToFloat(input);
	}
	
}

void inputNodeProb(float* prob,int NodeCount)
{
	int i=0;
	float sumProb = 0;
	for(i=0;i<NodeCount;i++)
	{
		cout<<"\t\t请输入第"<<i<<"个节点的Prob:"<<endl;
		cout<<"\t\t如果你的输入大于1,将只取小数部分"<<endl;
		cout<<"\t\t"<<endl;
		inputProb(prob[i]);
		//cout<<prob[i]<<endl;
		sumProb += prob[i];
		if((prob[i] == -1)||(prob[i] > 1)||(sumProb > 1)||((sumProb > 1)&&(i < NodeCount)))
		{
			cout<<"\t\t你的输入不正确,是因为:";
			if(prob[i] == -1)
				cout<<"输入不合规范"<<endl;
			else
				cout<<"使PROB总和大于1"<<endl;
			cout<<"\t\t请重新输入"<<endl;
			i-= 1;
		}
	}
	
}

void bestChoice(float* prob,float** cost,int** root,int low,int high)
{
	int r = 0;
	int i = 0;
	float p = 0.0;
	float rCost = 0.0;
	float bestCost;
	int bestRoot;

	for(i = low;i <= high;i++)
		p += prob[i-1];//////////////////////////////////////test
	if(high < low)
	{
		bestCost = 0;//空树
		bestRoot = -1;
	}
	else
		bestCost = 65535;
	for(r=low;r<=high;r++)
	{
		rCost = p + cost[low][r-1] + cost[r+1][high];
		if(rCost < bestCost)
		{
			bestCost = rCost;
			bestRoot = r;
		}
	}
	cost[low][high] = bestCost;
	root[low][high] = bestRoot;
}

void optimalBST(float* prob,int n,float** cost,int** root)
{
	int low,high;
	for(low = n+1;low >= 1;low--)
	{
		for(high = low - 1;high <= n;high++)
			bestChoice(prob,cost,root,low,high);
	}
}

void BuiltTree(int low,int high,int** root,int depeth,int father,int* cmpNum)
{
	if(low>high)
		return;
	//if(low == high)
	//{
		//cout<<"当前节点为"<<root[low][high]<<" 其深度为"<<depeth<<"\t\t其父节点为"<<father<<endl;
	//	return;
	//}
	if(depeth != 1)
	{
		int tmpRoot = root[low][high];
		//cout<<"当前节点为"<<root[low][high]<<" 其深度为"<<depeth<<"\t\t其父节点为"<<father<<endl;
		cmpNum[tmpRoot - 1] = depeth;
	}
	//cout<<root[low][high];
	int k = root[low][high];
	BuiltTree(low,k-1,root,depeth+1,k,cmpNum);
	BuiltTree(k+1,high,root,depeth+1,k,cmpNum);
}

void DrawBST(int NodeCount,int** root,int father,int* cmpNum)// 其中father为整棵树的根节点，主要是为了输出方便
//cmpNum为统计比较次数的数组，我们在每次递归时会将查找次数加一
{
	cout<<"当前节点为"<<father<<" 为根节点"<<"其深度为0"<<endl;
	cmpNum[father-1] = 1;
	BuiltTree(1,NodeCount,root,1,father,cmpNum);
}

#define MAXNODECOUNT 1500;

int _tmain(int argc, _TCHAR* argv[])
{
	int NodeCount = 0;
	int i = 0;
	int j = 0;
	char tmpInput[100];//临时存储读入的数据
	int lengthInput = 0;
	
	FILE * stream;
	char* filePath=new char[100];
	cout<<"\t\t请输入包含要处理数据的文件名：";
	cin>>filePath;
	getchar();
	if( (stream=fopen(filePath, "r" )) == NULL )
	{
		 printf( "\t\t文件打开失败，请检查您的输入...\n" );
		 getchar();
		 return 0;
	}
	

	char** key = new char*[1500];
	float* prob = new float[1500];
	int k=0;
	int m=0;
	int inputType = 0;
	float tmpProb = 0.0;
	int inputCount=0;
	
	while (!feof(stream))
	{
		if(inputType == 0)
		{
			fscanf( stream, "%s", tmpInput );
			lengthInput = strlen(tmpInput);
			key[k] = new char[lengthInput+1];
			strcpy(key[k],tmpInput);
			k++;
			inputType = 1;
		}
		else if(inputType == 1)
		{
			fscanf( stream, "%s", tmpInput );
			tmpProb = StringToFloat(tmpInput);
			prob[m] = tmpProb;
			m++;
			inputType = 0;
		}
	}
	inputCount = m;
	key[k] = NULL;
	prob[m] = '\0';
	/*for(i=0;i<k;i++)
	{
		cout<<"值："<<key[i]<<"     概率："<<prob[i]<<endl;
	}*/
	
	float probCount = 0.0;
	for(i=0;i<m;i++)
		probCount += prob[i];

	//cout<<probCount<<endl;
	/*if(probCount > 1.1)
	{
		cout<<"您的输入不合法，请校正后再输入！"<<endl;
		return 0;
	}
	cout<<"efef"<<endl;*/
/*	for(int i=0;i<NodeCount;i++)//测试输入情况
	{
		cout<<i<<endl;
		cout<<prob[i]<<endl;;
	}*/

	int* cmpNum=new int[inputCount+1];  //比较次数数组

	float** cost=new float*[inputCount+2];
	for(i=0;i<inputCount+2;i++)
		cost[i] = new float[inputCount+1];

	for(i=1;i<inputCount+2;i++)
		cost[i][i] = prob[i-1];

	//for(i=1;i<NodeCount+2;i++)
		//cost[i][i-1] = 0;

	int** root=new int*[inputCount+2];
	for(i=0;i<inputCount+2;i++)
		root[i] = new int[inputCount+1];
	time_t c_start, c_end;
	c_start = clock();
	optimalBST(prob,inputCount,cost,root);
	c_end = clock();
	printf("\t\t用掉的时间为:%f毫秒\n",difftime(c_end,c_start)) ; 
	//cout<<"cost矩阵"<<endl;
/*	for(i=1;i<NodeCount+2;i++)//测试输出情况
	{
		for(j=0;j<i;j++)
			cout<<0<<"\t";
		for(j=i;((j<NodeCount+1)&&(j>=i));j++)
		{
			//cout<<"cost["<<i<<"]["<<j<<"] = "<<cost[i][j]<<endl;
			cout<<cost[i][j]<<"\t";
		}
		cout<<endl;
	}*/
//			cout<<"root["<<i<<"]["<<j<<"] = "<<root[i][j]<<endl;
	getchar();
	system("cls");
	//cout<<"\n\n\n\n\t\t最后结果为："<<endl;
	//cout<<"\t\t根为："<<root[1][inputCount]<<endl;
	//cout<<"\t\t耗费为："<<cost[1][inputCount]<<endl;
	//int ttttt = root[1][inputCount];
	//cout<<key[ttttt-1]<<endl;
	//getchar();

	DrawBST(inputCount,root,root[1][inputCount],cmpNum);
	system("cls");

	cout<<"\n____________________________________________________________________________"<<endl;
	cout<<"Key\t       Probability(Pi)\tComparisons(Ci)\tPiCi"<<endl;
	cout<<"----------------------------------------------------------------------------"<<endl;
	for(i=0;i<inputCount;i++)
	{
		int lengthofKey = strlen(key[i]);
		cout<<key[i];
		for(int j=0;j<15-lengthofKey;j++)
			cout<<" ";
		cout<<prob[i]<<"    \t"<<cmpNum[i];
		float tmpPC = (prob[i])*(cmpNum[i]);
		cout<<"\t\t"<<tmpPC<<endl;

		if((i%19 == 0)&&(i != 0))
		{
			cout<<"按回车键继续显示下一页"<<endl;
			getchar();
			system("cls");
			cout<<"_____________________________________________________________________________"<<endl;
			cout<<"Key\t       Probability(Pi)\tComparisons(Ci)\tPiCi"<<endl;
			cout<<"-----------------------------------------------------------------------------"<<endl;
		}
	}
	cout<<"_____________________________________________________________________________"<<endl;
	cout<<"\t\t\t\t\t    Total="<<cost[1][inputCount]<<endl;
	cout<<"-----------------------------------------------------------------------------"<<endl;
	getchar();

	
	return 0;
}