bigint.cpp

本算法实现2-10集合划分问题,采用动态规划法和大整数方法

#include "BigInt.h"
#include <math.h>

//---------------------------
// 构造函数
//---------------------------
BigInteger::BigInteger()
{
	curNode=head=end=NULL;
	sign=0;
}

//---------------------------
// 构造函数
//---------------------------
BigInteger::BigInteger(const int i)
{
}

//---------------------------
// 拷贝构造函数
//---------------------------
BigInteger::BigInteger(const BigInteger &bi)
{
	IntNode		*pNode;

	curNode=head=end=NULL;
	sign=bi.sign;
	pNode=bi.head;
	while(pNode)
	{
		AddNodeAtEnd(pNode->Data);
		pNode=pNode->Next;
	}
}

//---------------------------
// 释构函数
//---------------------------
BigInteger::~BigInteger()
{
	Reset();
}

//---------------------------
// 输入数字
//---------------------------
bool BigInteger::GetNum( char* input )
{
	if( !input )
		return false;

	char	c;
	int		p = 1, num = 0;

	char* ptr = input;
	while( *(++ptr) != '\0' );
	
	sign = 1;
	while( ptr >= input )
	{
		c = *(--ptr);

		if( c=='-' || c=='+' )			//输入符号
		{
			if( ptr == input )			//合法
			{
				sign = ( c=='-' ) ? (-1):1;
				break;
			}
			else						//非法
				goto GetNum_error;
		}

		else if( c>='0' && c<='9' )		//输入数字
		{
			num += (int)( c - '0' ) * p;
			p *= 10;

			if( p == 10000 )			//已满4个数字
			{
				AddNodeAtHead(num);
				p=1;
				num=0;
			}
		}

		else							//非法字符
			goto GetNum_error;
	}
	
	if( p > 1 )
	{
		AddNodeAtHead(num);
		num=0;
		goto GetNum_end;
	}

GetNum_error:
	Reset();
	return false;
GetNum_end:
	RemoveZeroOfHead();
	return true;
}

//---------------------------
// 在链头增加一个结点
//---------------------------
void BigInteger::AddNodeAtHead(int dat)
{
	curNode=new IntNode;
	curNode->Data=dat;
	curNode->Prev=NULL;
	if(!head)
	{
		head=end=curNode;
		curNode->Next=NULL;
	}
	else
	{
		curNode->Next=head;
		head->Prev=curNode;
		head=curNode;
	}
}

//---------------------------
// 在链尾增加一个结点
//---------------------------
void BigInteger::AddNodeAtEnd(int dat)
{
	curNode=new IntNode;
	curNode->Data=dat;
	curNode->Next=NULL;
	if(!head)
	{
		head=end=curNode;
		curNode->Prev=NULL;
	}
	else
	{
		curNode->Prev=end;
		end->Next=curNode;
		end=curNode;
	}
}

//---------------------------
// 复位
//---------------------------
void BigInteger::Reset()
{
	IntNode		*nextNode;

	if(head==NULL)
		return;

	curNode=head;
	while(curNode)
	{
		nextNode=curNode->Next;
		delete curNode;
		curNode=nextNode;
	}
	head=NULL;
	end=NULL;
	curNode=NULL;
}

//---------------------------
// 操作符“+”的重载
//---------------------------
BigInteger BigInteger::operator +(const BigInteger &bi2)
{
	BigInteger	&bi1=*this, result;
	IntNode		*in1, *in2;
	int			new_num, rest=0;

	if(!bi1.head)
		return bi2;
	if(!bi2.head)
		return bi1;

	in1=bi1.end;
	in2=bi2.end;

	//两操作数同号
	if(bi1.sign==bi2.sign)
	{
		result.sign=bi1.sign;
		while(in1 && in2)
		{
			new_num=in1->Data + in2->Data + rest;
			if(new_num>9999)
			{
				new_num=new_num-10000;
				rest=1;
			}
			else
				rest=0;
			result.AddNodeAtHead(new_num);

			in1=in1->Prev;
			in2=in2->Prev;
		}

		if(in2) in1=in2;
		while(in1)
		{
			new_num=in1->Data+rest;
			if(new_num>9999)
			{
				new_num=new_num-10000;
				rest=1;
			}
			else
				rest=0;
			result.AddNodeAtHead(new_num);
			in1=in1->Prev;
		}
		if(rest)
			result.AddNodeAtHead(rest);
	}

	//两操作数异号
	else
	{
		IntNode		*tin;
		switch(AbsCompare(bi1, bi2))
		{
		case 1:
			result.sign=bi1.sign;
			break;
		case -1:
			tin=in1;
			in1=in2;
			in2=tin;
			result.sign=bi2.sign;
			break;
		case 0:
			result.sign=1;
			result.AddNodeAtEnd(0);
			return result;
		}		

		while(in1 && in2)
		{
			new_num=in1->Data - in2->Data + rest;
			if(new_num<0)
			{
				if(in1->Prev)
				{
					new_num=new_num+10000;
					rest=-1;
				}
				else
				{
					rest=0;
					result.sign=-1;
					new_num=-new_num;
				}
			}
			else
				rest=0;
			result.AddNodeAtHead(new_num);

			in1=in1->Prev;
			in2=in2->Prev;
		}

		while(in1)
		{
			new_num=in1->Data+rest;
			if(new_num<0)
			{
				new_num+=10000;
				rest=-1;
			}
			else
				rest=0;
			result.AddNodeAtHead(new_num);
			in1=in1->Prev;
		}
	}

	result.RemoveZeroOfHead();
	return result;
}

//---------------------------
// 操作符“*”的重载，完成与int的乘法
//---------------------------
BigInteger BigInteger::operator *(const int i)
{
	int j;
	BigInteger result;
	result.sign = ( sign*i > 0 ) ? sign:(-sign);
	
	int abs_i = abs(i);

	for(j = 0; j < abs_i; j++ )
		result = result + *this;

	return result;
}

//---------------------------
// 操作符“=”的重载
//---------------------------
BigInteger & BigInteger::operator =(const BigInteger &bi)
{
	//检查自赋值
	if(this==&bi)
		return *this;

	//释放资源
	Reset();

	//复制内容
	IntNode		*pNode;

	curNode=head=end=NULL;
	sign=bi.sign;
	pNode=bi.head;
	while(pNode)
	{
		AddNodeAtEnd(pNode->Data);
		pNode=pNode->Next;
	}

	//返回本对象的引用
	return *this;
}

//---------------------------
// 输出数值
//---------------------------
void BigInteger::Print( FILE* stream )
{
	//符号
	if(sign==-1)
		fprintf(stream, "-");

	//第一段数字
	if(head)
	{
		fprintf(stream, "%d", head->Data);
		curNode=head->Next;
	}
	else
		return;

	//后面的数字
	while(curNode)
	{
		fprintf(stream, "%04d", curNode->Data);
		curNode=curNode->Next;
	}
}

//---------------------------
// 清除多余的零
//---------------------------
void BigInteger::RemoveZeroOfHead()
{
	curNode=head;
	while(curNode && !curNode->Data)
	{
		head=head->Next;
		head->Prev=NULL;
		delete curNode;
		curNode=head;
	}
}

//---------------------------
// 比较绝对值的大小
//---------------------------
int BigInteger::AbsCompare(const BigInteger &bi1, const BigInteger &bi2)
{
	IntNode		*in1, *in2;

	in1=bi1.head;
	in2=bi2.head;

	while(in1 && in2)
	{
		in1=in1->Next;
		in2=in2->Next;
	}

	if(in1) return 1;
	if(in2) return -1;

	in1=bi1.head;
	in2=bi2.head;

	while(in1 && in1->Data==in2->Data)
	{
		in1=in1->Next;
		in2=in2->Next;
	}

	if(!in1)
		return 0;
	else if(in1->Data > in2->Data)
		return 1;
	else
		return -1;
}