bigint.cpp

用C++实现的 用链表实现无限大整数的加减运算,

#include "BigInt.h"
#include "stdio.h"
#include "math.h"
//---------------------------
// 构造函数
//---------------------------
BigInteger::BigInteger()
{
	curNode=head=end=NULL;
	sign=0;
}

//---------------------------
// 拷贝构造函数
//---------------------------
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();
}

//---------------------------
// 输入数字
//---------------------------
void BigInteger::GetNum()
{
	char	c;
	int		p, num;

GetNum_begin:
	p=0;
	num=0;

	fflush(stdin);						//清空键盘缓冲区
	while( (c=getchar())!=10 )
	{
		if(c=='-' || c=='+')			//输入符号
			if(head==NULL && p==0 && sign==0)	//合法
			{
				if(c=='-')
					sign=-1;
				else
					sign=1;
				continue;
			}
			else								//非法
				goto GetNum_error;

		else if(c>='0' && c<='9')		//输入数字
			if(p==4)					//已满4个数字
				goto GetNum_error;
			else
			{
				if(!sign) sign=1;
				num=num*10+c-'0';
				p++;
			}
		
		else if(c==',')					//输入逗号
			if(p<4 && head!=NULL)
				goto GetNum_error;
			else
			{
				p=0;
				AddNodeAtEnd(num);
				num=0;
			}

		else							//非法字符
			goto GetNum_error;
	}
	
	if(p==4 || (p>0 && head==NULL))
	{
		AddNodeAtEnd(num);
		num=0;
		goto GetNum_end;
	}

GetNum_error:
	printf("格式错误，请检查一遍，然后重新输入: ");
	Reset();
	goto GetNum_begin;
GetNum_end:
	RemoveZeroOfHead();
}

//---------------------------
// 在链头增加一个结点
//---------------------------
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;
}

//---------------------------
// 操作符“=”的重载
//---------------------------
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()
{
	//符号
	if(sign==-1)
		printf("-");

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

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

//---------------------------
// 清除多余的零
//---------------------------
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;
}