chugeinteger.cpp

利用Linklist实现超大整数之加减乘除

#include <iostream>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cctype>

using namespace std;

#include "CHugeInteger.h"

HugeInteger::HugeInteger()
{
	flag = true;
	sig = 1;
	NUM = NULL;
}

HugeInteger::~HugeInteger()
{
	DestoryList(NUM);
}

void HugeInteger::input(string A,string B)
{
	a = A;
	b = B;
	string::iterator it = a.begin();

	for(;it != a.end();it++)
	{
		if(!isdigit(*it))
		{
			flag = false;
			return;
		}
	}

	it = b.begin();

	for(;it != b.end();it++)
	{
		if(!isdigit(*it))
		{
			flag = false;
			return;
		}
	}

	flag = true;
}

void HugeInteger::output()
{
	if(!flag) return;

	if(sig < 0)
		cout << '\n' << "Result=-";
	else
		cout << '\n' << "Result=";
	
	NODEH it  = NUM->head;
	NODEH end = NUM->end;

	if(it == NULL) return;
	
	for(;it != end;it = it->n)
		putchar(it->data + '0');
	
	putchar(it->data + '0');
	putchar('\n');
}

void HugeInteger::output(char *A)
{
	if(!flag) return;
	
	NODEH it  = NUM->head;
	NODEH end = NUM->end;

	if(it == NULL) return;
	
	for(;it != end;it = it->n,A++)
		*A = it->data + '0';

	*(A++) = it->data + '0';
	*(A++) = '\0';
}

void HugeInteger::add()
{
	if(!flag) return;
	
	LISTH CS = NULL;
	LISTH BCS = NULL;

	const char* a_cstr = a.c_str();
	const char* b_cstr = b.c_str();

	if(!(a_cstr && b_cstr)			   ) return;
	if(!InitList(NUM)				   ) return;
	if(!(InitList(CS) && InitList(BCS))) return;
	
	if(strcmp(a_cstr, b_cstr) > 0)
	{
		const char *pa = a_cstr,*pb = b_cstr;

		for(;'\0' != *pa;++pa)
			EndAdd(BCS, *pa - '0');
		
		for(;'\0' != *pb;++pb)
			EndAdd(CS, *pb - '0');
	}
    else
	{
        const char *pa = a_cstr,*pb = b_cstr;

        for(;'\0' != *pa;++pa)
			EndAdd(CS, *pa - '0');
        
		for(;'\0' != *pb;++pb)
			EndAdd(BCS, *pb - '0');
	}

	NUM = BCS;
	ADD(CS, NUM);
	DestoryList(CS);
}

void HugeInteger::subtract()
{
	if(!flag) return;
	
	LISTH CS = NULL;
	LISTH BCS = NULL;

	const char* a_cstr = a.c_str();
	const char* b_cstr = b.c_str();

	if(!(a_cstr && b_cstr)			   ) return;
	if(!InitList(NUM)				   ) return;
	if(!(InitList(CS) && InitList(BCS))) return;
	
	if(isGreaterThan())
	{
		const char *pa = a_cstr,*pb = b_cstr;
		
		for(;'\0' != *pa;++pa)
			EndAdd(CS, *pa - '0');
		
		for(;'\0' != *pb;++pb)
			EndAdd(BCS, *pb - '0');
	}
    else
	{
		const char *pa = a_cstr,*pb = b_cstr;

		for(;'\0' != *pa;++pa)
			EndAdd(BCS, *pa - '0');
		
		for(;'\0' != *pb;++pb)
			EndAdd(CS, *pb - '0');
	}
	
	NUM = BCS;
	SUB(CS, NUM);
	DestoryList(CS);
}

void HugeInteger::multiply()
{
	if(!flag) return;

	LISTH CS = NULL;
	LISTH BCS = NULL;

	const char* a_cstr = a.c_str();
	const char* b_cstr = b.c_str();

	if(!(a_cstr && b_cstr)			   ) return;
	if(!InitList(NUM)				   ) return;
	if(!(InitList(CS) && InitList(BCS))) return;
	
	if('-' == *a_cstr)
	{
		++a_cstr;
		sig *= -1;
	}
    else if('+' == *a_cstr)
		++a_cstr;
		
	if('-' == *b_cstr)
	{
		++b_cstr;
		sig *= -1;
    }
	else if('+' == *b_cstr)
		++b_cstr;
	
	if(strcmp(a_cstr, b_cstr) > 0)
	{
		const char *pa = a_cstr,*pb = b_cstr;

		for(;'\0' != *pa;++pa)
			EndAdd(BCS, *pa - '0');
		
		for(;'\0' != *pb;++pb)
			EndAdd(CS, *pb - '0');
    }
    else
	{
        const char *pa = a_cstr,*pb = b_cstr;

        for(;'\0' != *pa;++pa)
			EndAdd(CS, *pa - '0');

		for(;'\0' != *pb;++pb)
			EndAdd(BCS, *pb - '0');
    }
	
	NODEH cs_p = CS->end;
	UINT bit = 0;
	LISTH TEMP;
	
	for(;cs_p != CS->head;cs_p = cs_p->p)
	{
		InitList(TEMP);
		BitMul(BCS, cs_p->data, TEMP);
/*#ifdef _DEBUG
		puts("===============================================================\n");
		PrintList(BCS);
		printf(" X %d=", cs_p->data);
		PrintList(TEMP);
#endif*/
		AddZero(TEMP, bit);
		ADD(TEMP, NUM);
/*#ifdef _DEBUG
		puts("\nNUM:");
		PrintList(NUM);
		printf("\nbit:%d\n", bit);
#endif*/
		++bit;
		DestoryList(TEMP);
	}

	InitList(TEMP);
	BitMul(BCS, cs_p->data, TEMP);
/*#ifdef _DEBUG
	puts("===============================================================\n");
	PrintList(BCS);
	printf(" X %d=", cs_p->data);
	PrintList(TEMP);
#endif*/
	AddZero(TEMP, bit);
	ADD(TEMP, NUM);
/*#ifdef _DEBUG
	puts("\nNUM:");
	PrintList(NUM);
	printf("\nbit:%d\n", bit);
#endif*/
	DestoryList(CS);
	DestoryList(BCS);
	DestoryList(TEMP);
}

void HugeInteger::divide()
{
	if(!flag) return;

	UINT  tmplen;
	LISTH CS	 = NULL;
	LISTH BCS	 = NULL;
	LISTH TMPCS  = NULL;
	LISTH TSTPDT = NULL;

	const char* a_cstr = a.c_str();
	const char* b_cstr = b.c_str();
	
	if(!(a_cstr && b_cstr)			   ) return;
	if(!InitList(NUM)				   ) return;
	if(!(InitList(CS) && InitList(BCS) && 
		 InitList(TMPCS))) return;
	
	if(isGreaterThan())
	{
		const char *pa = a_cstr,*pb = b_cstr;
		
		for(;'\0' != *pa;++pa)
			EndAdd(CS, *pa - '0');
		
		for(;'\0' != *pb;++pb)
			EndAdd(BCS, *pb - '0');
	}
    else
	{
		const char *pa = a_cstr,*pb = b_cstr;

		for(;'\0' != *pa;++pa)
			EndAdd(BCS, *pa - '0');
		
		for(;'\0' != *pb;++pb)
			EndAdd(CS, *pb - '0');
	}

	if(CmpHGInt(BCS, CS, BCS->length))
		tmplen = BCS->length + 1;
	else
		tmplen = BCS->length;
	
	NODEH it_cs = CS->head;
	UINT i = 0;

	while(i < tmplen)
	{
		it_cs = it_cs->n;
		i++;
	}

	CopyLIST(CS, TMPCS, tmplen);
	TestDIV(BCS, TMPCS, NUM, TSTPDT);

	while(tmplen < CS->length)
	{
		SUB(TMPCS, TSTPDT);
		EndAdd(TSTPDT, it_cs->data);

		if(TMPCS) DestoryList(TMPCS);

		InitList(TMPCS);
		CopyLIST(TSTPDT, TMPCS, TSTPDT->length);
		TestDIV(BCS, TMPCS, NUM, TSTPDT);
		it_cs = it_cs->n;
		tmplen++;
	}

	DestoryList(BCS);
	DestoryList(CS);
	DestoryList(TMPCS);
	DestoryList(TSTPDT);
}

void HugeInteger::modulus()
{
	if(!flag) return;

	LISTH CS	= NULL;
	LISTH BCS	= NULL;
	LISTH TMPCS = NULL;

	const char* a_cstr = a.c_str();
	const char* b_cstr = b.c_str();
	
	if(!(a_cstr && b_cstr)			   ) return;
	if(!InitList(NUM)				   ) return;
	if(!(InitList(CS) && InitList(BCS) && 
		 InitList(TMPCS))) return;
	
	if(isGreaterThan())
	{
		const char *pa = a_cstr,*pb = b_cstr;
		
		for(;'\0' != *pa;++pa)
			EndAdd(CS, *pa - '0');
		
		for(;'\0' != *pb;++pb)
			EndAdd(BCS, *pb - '0');
	}
    else
	{
		const char *pa = a_cstr,*pb = b_cstr;

		for(;'\0' != *pa;++pa)
			EndAdd(BCS, *pa - '0');
		
		for(;'\0' != *pb;++pb)
			EndAdd(CS, *pb - '0');
	}

	divide();

	NODEH num_p = NUM->end;
	UINT bit = 0;
	LISTH TEMP;
	
	for(;num_p != NUM->head;num_p = num_p->p)
	{
		InitList(TEMP);
		BitMul(BCS, num_p->data, TEMP);
		AddZero(TEMP, bit);
		ADD(TEMP, TMPCS);
		++bit;
		DestoryList(TEMP);
	}

	InitList(TEMP);
	BitMul(BCS, num_p->data, TEMP);
	AddZero(TEMP, bit);
	ADD(TEMP, TMPCS);
	SUB(CS, TMPCS);

	if(NUM) DestoryList(NUM);
	InitList(NUM);
	CopyLIST(TMPCS, NUM, TMPCS->length);

	DestoryList(CS);
	DestoryList(BCS);
	DestoryList(TMPCS);
}

bool HugeInteger::isGreaterThan()
{
	const char *pa = a.c_str(),*pb = b.c_str();

	if(a.length() > b.length()) 
		return true;
	else if(a.length() < b.length())
		return false;
	else if(a.length() == b.length())
	{
		for(;'\0' != *pa;++pa,++pb)
		{
			if(*pa - '0' > *pb - '0') return true;
			if(*pa - '0' < *pb - '0') return false;
		}
	}
	
	return false;
}

bool HugeInteger::isLessThan()
{
	return !isGreaterThan();
}

bool HugeInteger::isEqualTo()
{
	const char *pa = a.c_str(),*pb = b.c_str();

	if(a.length() != b.length()) 
		return false;
	else if(a.length() == b.length())
	{
		for(;'\0' != *pa;++pa,++pb)
			if(*pa - '0' != *pb - '0') return false;
	}
	
	return true;
}

bool HugeInteger::isNotEqualTo()
{
	return !isEqualTo();
}

bool HugeInteger::isGreaterThanOrEqualTo()
{
	if(isGreaterThan() || isEqualTo()) return true;
	return false;
}

bool HugeInteger::isLessThanOrEqualTo()
{
	if(isLessThan() || isEqualTo()) return true;
	return false;
}

bool HugeInteger::isZero(string str_num)
{
	const char *pa = str_num.c_str();
	bool check_zero = 1;

	for(;'\0' != *pa;++pa)
		check_zero &= (*pa - '0' == 0) ? 1 : 0;

	return check_zero == 1 ? true : false;
}