utilities.cpp

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

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

using namespace std;

#include "CHugeInteger.h"

bool InitList(LISTH& L)
{
	L = new LIST;
	
	if(!L) return false;	// Failed to allocate memory blocks.
	
	L->head = L->end = NULL;
	L->length = 0;
	return true;
}

NODEH NMalloc(const BYTE& elem)
{
	NODEH temp = new NODE;   

	if(!temp) return NULL;	// Failed to allocate memory blocks.
	
	temp->data = elem;
	return temp;
}
 
bool ADD(const LISTH& La,LISTH& Lb)
{
	NODEH pa = La->end,pb = Lb->end;
    BYTE status = 0;

    for(;pa != La->head;pa = pa->p,pb = pb->p)
	{
        if(pb == NULL)
		{
            PreAdd(Lb, 0);
            pb = Lb->head;
        }

        BYTE sum = pa->data + pb->data + status;
        
		if(sum >= 10)
		{
            pb->data = sum % 10;
            status = 1;
        }
        else
		{
            pb->data = sum;
            status = 0;
        }
	}

    if(pb == NULL)
	{
        PreAdd(Lb, 0);
        pb = Lb->head;
    }
	
	UINT sum = pa->data + pb->data + status;
    
	if(sum >= 10)
	{
		pb->data = sum % 10;
        if(pb->p == NULL)
		{
			PreAdd(Lb, 0);
			pb = Lb->head;
			pb->data = sum / 10;
			return true;
		}

		pb = pb->p;
		if(pb == NULL)
		{
			PreAdd(Lb, 0);
			pb = Lb->head;
		}
		
		pb->data = sum / 10;
		return true;
	}
	else	// sum < 10
		pb->data = sum;

    return true;
}

bool SUB(const LISTH& La,LISTH& Lb)
{
	NODEH pa = La->end,pb = Lb->end;
    BYTE status = 0;

    for(;pa != La->head;pa = pa->p,pb = pb->p)
	{
		if(pb == NULL)
		{
			PreAdd(Lb, 0);
			pb = Lb->head;
		}
		
		if(pa->data < pb->data)
		{
			pb->data = 10 + pa->data - pb->data - status;
			status = 1;
		}
		else if(pa->data == pb->data && status == 1)
		{
			pb->data = 10 + pa->data - pb->data - status;
			status = 1;		
		}
		else
		{
			pb->data = pa->data - pb->data - status;
			status = 0;
		}
	}

    if(pb == NULL)
	{
		PreAdd(Lb, 0);
		pb = Lb->head;
	}

	pb->data = pa->data - pb->data - status;
	return true;
}

bool PreAdd(LISTH& L,const BYTE& elem)
{
	NODEH temp = NMalloc(elem);
    ++(L->length);

	if(L->head == NULL && L->end == NULL)
	{
		temp->n = temp->p = NULL;
		L->head = L->end = temp;
        return true;
    }

	temp->p = NULL;   
    temp->n = L->head;
    L->head->p = temp;   
    L->head = temp;    
    return true;
}

bool EndAdd(LISTH& L,const BYTE& elem)
{
	NODEH temp = NMalloc(elem);
	++(L->length);

	if(L->head == NULL && L->end == NULL)
	{
		temp->n = temp->p = NULL;
		L->head = L->end = temp;
        return true;
    }
	
	temp->n = NULL;   
	temp->p = L->end;
	L->end->n = temp;   
	L->end = temp;    
    return true;
}

bool DestoryList(LISTH& L)
{
    NODEH temp = L->head,it;

    if(temp == NULL)
	{
        delete L;
        return true;
    }
	
    while(temp != L->end)
	{
        it = temp;
        temp = temp->n;
        delete it;
    }

    delete temp;
    delete L;  
	return true;
}
    
void PrintList(LISTH& L)
{
    NODEH it = L->head,end = L->end;

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

    putchar(it->data + '0');  
}

bool AddZero(LISTH& L,UINT count)
{
    while(count--) EndAdd(L, 0);
    return true;
}
 
bool BitMul(const LISTH& L,const UINT number,LISTH& NUM)
{
    NODEH L_end = L->end;
    BYTE  status = 0,temp;
    
	for(;L_end != L->head;L_end = L_end->p)
	{
		temp = L_end->data * number + status;
        PreAdd(NUM, temp % 10);
        status = temp / 10;
    }

	temp = L->head->data * number + status;

	if(temp >= 10)
	{
        PreAdd(NUM, temp % 10);
        PreAdd(NUM, temp / 10);
    }
    else 
		PreAdd(NUM, temp);
	
    return true;
}

void TestDIV(const LISTH& BCS,LISTH& TMPCS,LISTH& NUM,LISTH& TSTPDT)
{
	LISTH TMPNUM;
	
	if(TSTPDT != NULL) DestoryList(TSTPDT);
	InitList(TSTPDT);

	for(BYTE i = 9;i > -1;i--)
	{
		InitList(TMPNUM);
		BitMul(BCS, i, TMPNUM);

		if(TMPNUM->length < TMPCS->length)
		{
			UINT tmplen = TMPCS->length - TMPNUM->length;

			for(UINT j = 0;j < tmplen;j++) PreAdd(TMPNUM, 0);
		}

		if(!DivCmp(TMPNUM, TMPCS))
		{
			EndAdd(NUM, i);
			CopyLIST(TMPNUM, TSTPDT, TMPNUM->length);
			return;
		}

		DestoryList(TMPNUM);
	}
}

bool CmpHGInt(LISTH& L1,LISTH& L2,UINT Len)
{
	NODEH it_l1 = L1->head;
	NODEH it_l2 = L2->head;
	
	for(UINT i = 0;i < Len;i++)
	{
		if(it_l1->data > it_l2->data) return true;
		if(it_l1->data < it_l2->data) return false;
		
		it_l1 = it_l1->n;
		it_l2 = it_l2->n;
	}

	return false;
}

bool DivCmp(LISTH& L1,LISTH& L2)
{
	if(L1->length > L2->length)	return true;
	if(L1->length < L2->length)	PreAdd(L1, 0);

	NODEH it_l1 = L1->head;
	NODEH it_l2 = L2->head;
	
	while(it_l1 != NULL)
	{
		if(it_l1->data > it_l2->data) return true;
		if(it_l1->data < it_l2->data) return false;

		it_l1 = it_l1->n;
		it_l2 = it_l2->n;
	}

	return false;
}

void CopyLIST(LISTH& Src,LISTH& Des,UINT Len)
{
	NODEH it_src = Src->head;

	for(int i = 0;i < Len;i++)
	{
		EndAdd(Des, it_src->data);
		it_src = it_src->n;
	}
}