hugeint.cpp

巨型整形实现,长度不受windows机器字长限制,实现了基本的加减乘除等运行.

#include <iostream.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include "Hugeint.h"

Hugeint::Hugeint()
{
	first = new Hugeintnode;
	result = 0;
}

Hugeint::Hugeint(const Hugeint & h)
{
	first = new Hugeintnode(h.getheaddata());
	Hugeintnode *p = h.first->privor;
	while(p != h.first)
	{
		insert(p->data);
		p = p->privor;
	}
	result = 0;
}

Hugeint::~Hugeint()
{
	makeempty();
	delete first;
}

int Hugeint::getheaddata()const
{
	return first->data;
}

void Hugeint::setheaddata(int x)
{
	first->data = x;
}

bool Hugeint::upfirstdata(int x)
{
	if(!isempty())
	{
		first->next->data = x;
		return true;
	}
	else
		cerr<<"The hugeint is empty!"<<endl;
	return false;
}

bool Hugeint::isempty()const
{
	return first->next == first;
}

void Hugeint::insert(int x)
{
	Hugeintnode *p = new Hugeintnode(x);
	p->next = first->next;
	first->next->privor = p;
	first->next = p;
	p->privor = first;
}

void Hugeint::insertfromback(int x)
{
	Hugeintnode *p = new Hugeintnode(x);
	p->next = first;
	p->privor = first ->privor;
	first->privor->next = p;
	first->privor = p;
}

void Hugeint::print()const
{
	Hugeintnode *p = first->privor;
	while(p != first)
	{
		cout<<p->data;
		p = p->privor;
	}
	cout<<endl;
}

ostream & operator << (ostream &out,  Hugeint &h)
{
	if(!h.isempty())
	{
	while(h.getfirstdata() == 0)
	{
		if(h.isempty())
			break;
		h.removefirst();
	}
	if(h.isempty())
	{
		h.insert(0);
	    h.setheaddata(1);
	}
		if(h.getheaddata() == 0)
			out<<'-';
			Hugeintnode *p = h.first->next;
		while(p != h.first)
		{
			out<<p->data;
			p = p->next;
		}
	}
	return out;
}

bool Hugeint::removefirst()
{
	if(isempty())
		return false;
	else
	{
		Hugeintnode *p;
		p = first->next;
		first->next = p->next;
		//p->privor->next = p->next;
		p->next->privor = p->privor;
		delete p;
	}
	return true;
}

void Hugeint::makeempty()
{
	if(isempty())
		return ;
	else
	{
		Hugeintnode *p ;
		while( first->next != first)
		{
			p = first->next;
			first->next = p->next;
			delete p;
		}
	}
}
		
istream & operator >> (istream &in, Hugeint &h)
{
	char ch[1000];
	cin>>ch;
	int len = strlen(ch);
	if(ch[0] == '-')
	{
		h.setheaddata(0);
		for(int i = len; i > 0; i--)
			if(isdigit(ch[i]))
				h.insert(ch[i]-'0');
	}
	else
		if(isdigit(ch[0]))
		{
			h.setheaddata(1);
			for(int i = len; i >= 0; i--)
			if(isdigit(ch[i]))
				h.insert(ch[i]-'0');
		}
 	return in;
}

Hugeint & Hugeint::operator = (const long & value)
{
	this->makeempty();
	long val = abs(value);
	if(value == 0)
		insert(0);
	if(value >= 0)
		setheaddata(1);
	else
		setheaddata(0);
	while(val != 0)
	{
		insert(val % 10);
		val /= 10;
	}
	return *this;
}

Hugeint & Hugeint::operator = (int value)
{
	this->makeempty();
	int val = abs(value);
	if(value == 0)
		insert(0);
	if(value >= 0)
		setheaddata(1);
	else
		setheaddata(0);
	while(val != 0)
	{
		insert(val % 10);
		val /= 10;
	}
	return *this;
}

Hugeint & Hugeint::operator = (const char * ch)
{
	this->makeempty();
	int len = strlen(ch);
	if(ch[0] == '-')
	{
		setheaddata(0);
		for(int i = len; i > 0; i--)
			if(isdigit(ch[i]))
				insert(ch[i]-'0');
	}
	else 
		if(isdigit(ch[0]))
		{
			setheaddata(1);
			for(int i = len; i >= 0; i--)
			if(isdigit(ch[i]))
				insert(ch[i]-'0');
		}
    return *this;
}

Hugeint & Hugeint::operator = (const Hugeint & h)
{
	makeempty();
	Hugeintnode *p = h.first->privor;
	while(p != h.first)
	{
		insert(p->data);
		p = p->privor;
	}
	setheaddata(h.getheaddata());
	return *this;
}



int Hugeint::getfirstdata()const
{
	if(!isempty())
		return first->next->data;
	return 0;
}

Hugeint  Hugeint::add(const Hugeint &h)
{
	Hugeint temp;
	Hugeintnode *p = first->privor;
	Hugeintnode *q = h.first->privor;

	int carry = 0;
	while(p != first && q != h.first)
	{
		temp.insert(p->data + q->data + carry);
		if(temp.getfirstdata() > 9)
		{
			temp.upfirstdata(temp.getfirstdata() % 10);
			carry = 1;
		}
		else
			carry = 0;
		q = q->privor;
		p = p->privor;
	}
	while(p != first)
	{
		temp.insert(p ->data + carry);
		if(temp.getfirstdata() > 9)
		{
			temp.upfirstdata(temp.getfirstdata() % 10);
			carry = 1;
		}
		else
			carry = 0;
		p = p->privor;
	}
	while(q != h.first)
	{
		temp.insert(q ->data + carry);
		if(temp.getfirstdata() > 9)
		{
			temp.upfirstdata(temp.getfirstdata() % 10);
			carry = 1;
		}
		else
			carry = 0;
		q = q->privor;
	}
	if(carry == 1)
		temp.insert(carry);
	temp.setheaddata(1);
	return Hugeint(temp);
}



Hugeint  Hugeint::div(const Hugeint & h)
{
	Hugeint tem;
	Hugeintnode *p = first->privor;
	Hugeintnode *q = h.first->privor;
	int carry = 0;
	while(p != first && q != h.first)
	{
		tem.insert(p->data - q->data - carry);
		if(tem.getfirstdata() < 0)
		{
			tem.upfirstdata(10 + tem.getfirstdata());
			carry = 1;
		}
		else
			carry = 0;
		p = p->privor;
		q = q->privor;
	}
	while(p != first)
	{
		tem.insert(p->data - carry);
		if(tem.getfirstdata() < 0)
		{
			tem.upfirstdata(10 + tem.getfirstdata());
			carry = 1;
		}
		else
			carry = 0;
		p = p->privor;
	}
	while(tem.getfirstdata() == 0)
	{
		if(tem.isempty())
			break;
		tem.removefirst();
	}
	if(tem.isempty())
	{
		tem.insert(0);
		tem.setheaddata(1);
	}
	return Hugeint(tem);
}



Hugeint  Hugeint::divv(const Hugeint & h)
{
	Hugeint te;
	Hugeintnode *q = first->privor;
	Hugeintnode *p = h.first->privor;
	int carry = 0;
	while(p != h.first && q != first)
	{
		te.insert(p->data - q->data - carry);
		if(te.getfirstdata() < 0)
		{
			te.upfirstdata(10 + te.getfirstdata());
			carry = 1;
		}
		else
			carry = 0;
		p = p->privor;
		q = q->privor;
	}
	while(p != h.first)
	{
		te.insert(p->data - carry);
		if(te.getfirstdata() < 0)
		{
			te.upfirstdata(10 + te.getfirstdata());
			carry = 1;
		}
		else
			carry = 0;
		p = p->privor;
	}
	while(te.getfirstdata() == 0)
	{
		if(te.isempty())
			break;
		te.removefirst();
	}
	if(te.isempty())
	{
		te.insert(0);
		te.setheaddata(1);
	}
	return Hugeint(te);
}



Hugeint  Hugeint::hugeabs(const Hugeint & h)
{
	Hugeint t;
	t = h;
	t.setheaddata(1);
	return Hugeint(t);
}

int Hugeint::length()const
{
	Hugeintnode *p = first->next;
	int i = 0;
	while(p != first)
	{
		i++;
		p = p->next;
	}
	return i;
}

bool Hugeint::operator >= (const Hugeint & h)
{
	if(getheaddata() > h.getheaddata())
		return true;
	else
		if(getheaddata() < h.getheaddata())
			return false;
	else if(getheaddata() == 1 && h.getheaddata() == 1)
	{
		if(length() > h.length())
			return true;
		else if(length() < h.length())
			return false;
		else
		{
			Hugeint t1 =hugeabs(*this);
			Hugeint t2 =hugeabs(h);
			Hugeintnode *p = t1.first->next;
			Hugeintnode *q = t2.first->next;
			while(p != t1.first && q != t2.first)
			{
				if(p->data > q->data)
					return true;
				else if(p->data < q->data)
					return false;
				p = p->next;
				q = q->next;
			}
			return true;
		}
	}
	else if(getheaddata() == 0 && h.getheaddata() == 0)
	{
		if(length() > h.length())
			return false;
		else if(length() < h.length())
			return true;
		else
		{
			Hugeint t1 =hugeabs(*this);
			Hugeint t2 =hugeabs(h);
			Hugeintnode *p = t1.first->next;
			Hugeintnode *q = t2.first->next;
			while(p != t1.first && q != t2.first)
			{
				if(p->data > q->data)
					return false;
				else if(p->data < q->data)
					return true;
				p = p->next;
				q = q->next;
			}
			return true;
		}
	}
	return true;
}

Hugeint  Hugeint::operator + (const Hugeint & h)
{
	Hugeint result;
	int condition;
	Hugeint h1 = hugeabs(*this);
	Hugeint h2 = hugeabs(h);
	if(getheaddata() == 1 && h.getheaddata() == 1)
		condition = 0;
	else if(getheaddata() == 0 && h.getheaddata() == 0)
		condition = 3;
	else if(getheaddata() == 1 && h.getheaddata() == 0)
	{
	   if(h1 >= h2 )
			condition = 1;
		else
			condition = 4;
	}
	else if(getheaddata() == 0 && h.getheaddata() == 1)
	{
		if( h1 >= h2)
			  condition = 2;
		else
			condition = 5;
	}

	switch(condition)
	{
	case 0:
		result = add(h);
		result.setheaddata(1);
		break;
	case 1:
		result = div(h);
		result.setheaddata(1);
		break;
	case 4:
		result = divv(h);
		result.setheaddata(0);
		break;
	case 2:
		result = div(h);
		result.setheaddata(0);
		break;
	case 5:
		result = divv(h);
		result.setheaddata(1);
		break;
	case 3:
		result = add(h);
		result.setheaddata(0);
		break;
	default:
		break;
	}
	return Hugeint(result);
}



Hugeint  Hugeint::operator + (const long & value)
{
	Hugeint re;
	Hugeint h ;
	h = value;
	re = *this + h;
	return Hugeint(re);
}



Hugeint Hugeint::operator - (const Hugeint & h)
{
	Hugeint divre;
	int condition;
	Hugeint h1 = hugeabs(*this);
	Hugeint h2 = hugeabs(h);
	if(getheaddata() == 1 && h.getheaddata()== 1)
	{
		if(h1 >= h2)
			condition = 0;
		else
			condition = 1;
	}
	else if(getheaddata() == 1 && h.getheaddata() == 0)
		condition = 2;
	else if(getheaddata() == 0 && h.getheaddata() == 1)
		condition = 3;
	else 
	{
		if(h1 >= h2)
			condition = 4;
		else 
			condition = 5;
	}

	switch(condition)
	{
	case 0:
		divre = div(h);
		divre.setheaddata(1);
		break;
	case 1:
		divre = divv(h);
		divre.setheaddata(0);
		break;
	case 2:
		divre = add(h);
		divre.setheaddata(1);
		break;
	case 3:
		divre = add(h);
		divre.setheaddata(0);
		break;
	case 4:
		divre = div(h);
		divre.setheaddata(0);
		break;
	case 5:
		divre = divv(h);
		divre.setheaddata(1);
		break;
	default:
		break;
	}
	return Hugeint(divre);
}

bool Hugeint::operator > (const Hugeint & h)
{
	if(getheaddata() > h.getheaddata())
		return true;
	else
		if(getheaddata() < h.getheaddata())
			return false;
	else if(getheaddata() == 1 && h.getheaddata() == 1)
	{
		if(length() > h.length())
			return true;
		else if(length() < h.length())
			return false;
		else
		{
			Hugeint t1 =hugeabs(*this);
			Hugeint t2 =hugeabs(h);
			Hugeintnode *p = t1.first->next;
			Hugeintnode *q = t2.first->next;
			while(p != t1.first && q != t2.first)
			{
				if(p->data > q->data)
					return true;
				else if(p->data < q->data)
					return false;
				p = p->next;
				q = q->next;
			}
			return false;
		}
	}
	else if(getheaddata() == 0 && h.getheaddata() == 0)
	{
		if(length() > h.length())
			return false;
		else if(length() < h.length())
			return true;
		else
		{
			Hugeint t1 =hugeabs(*this);
			Hugeint t2 =hugeabs(h);
			Hugeintnode *p = t1.first->next;
			Hugeintnode *q = t2.first->next;
			while(p != t1.first && q != t2.first)
			{
				if(p->data > q->data)
					return false;
				else if(p->data < q->data)
					return true;
				p = p->next;
				q = q->next;
			}
			return false;
		}