08.cpp

一般来说用int型变量超过2^31的数就会溢出。此程序是利用数组对长度很长的整形字符串进行加减操作

/*	传的参数char const *a，需要在_Add和_Minus中用栈分配数组
	可以保证原来的两数不被改写，但似乎太浪费了，并且效率低下
	不知道有没有什么好的方法。
*/

#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define TRUE 1
#define FALSE 0

#define FADD 1
#define FMINUS 2

#define MaxLength 10000
int getLen(char *array)
{
	int len=0;
	char *p=array;
	while('\0'!=*p++)
		len++;
	return len;
}

//除去开头多余的0
void omitZero(char num[])
{
	char *p=num;
	if ('-'==*num) p++;
	int l=getLen(num);
	int z=0;
	while('0'==*p++)
		z++;
	if(z==l) { num[0]='0'; num[1]='\0'; }	//除去000000000的情况
	else if ((z==(l-1)) && ('-'==*num)) { num[0]='0'; num[1]='\0'; }	//除去-000000000的情况
	else		//一般情况，除去00000124535等
	{
		for(int i=('-'==*num)?z+1:z; i<l; i++)
			num[i-z]=num[i];
		num[l-z]='\0';
	}
}

//	检查两个正数，看那个更大
int isAbigger(char *a, char *b)
{
	int lenA=getLen(a);
	int lenB=getLen(b);
	
	if(lenA>lenB) return TRUE;
	else if(lenA==lenB)
	{
		char *tempA=a;
		char *tempB=b;
		while ((*tempA++==*tempB++)&&(*tempA!='\0'))
			NULL;
		tempA--; tempB--;
		if(*tempA>=*tempB) return TRUE;
		else return FALSE;
	}
	else return FALSE;
}

//保证被减数a大于减数b
void _Minus(char const *aBig, char const *bBig, char c[])
{
	char a[MaxLength];
	char b[MaxLength];
	strcpy(a, aBig);
	strcpy(b, bBig);
	
	int lenA=getLen(a);
	int lenB=getLen(b);
	char *headA=a, *headB=b, *headC=c;
	char *tempA=a+lenA-1, *tempB=b+lenB-1, *tempC=c+lenA-1;
	*(tempC+1)='\0';
	if(!isAbigger(a+lenA-lenB, b))
	{
		headA+=lenA-lenB;
		while('0'==*--headA)
			*headA='9';
		(*headA)-=1;
	}
	headA=a;
	for(int i=0; i<lenA-lenB; i++)
	{
		*headC++=*headA++;
	}
	while((tempB+1)!=b)
	{
		if(*tempA>=*tempB) *tempC=char(*tempA-*tempB)+'0';
		else { *(tempA-1)-=1; *tempC=char(*tempA-*tempB+10)+'0'; }
		tempA--; tempB--; tempC--;
	}
}
//保证被加数a大于加数b
void _Add(char const *aBig, char const *bBig, char c[])
{
	char a[MaxLength];
	char b[MaxLength];
	strcpy(a, aBig);
	strcpy(b, bBig);
	
	int lenA=getLen(a);
	int lenB=getLen(b);
	char *headA=a, *headB=b, *headC=c;
	char *tempA=a+lenA-1, *tempB=b+lenB-1, *tempC=c+lenA;
	*(tempC+1)='\0';
	*tempC='0';
	while((tempA+1)!=a)
	{
		if((*tempA-'0'+*tempB-'0'+*tempC-'0')>9)
		{
			*tempC+=*tempA-'0'+*tempB-'0'-10;
			*(tempC-1)='1';
		}
		else { 
			*tempC+=*tempA-'0'+*tempB-'0';
			*(tempC-1)='0'; }
		tempA--; tempC--;
		if((tempB)!=b) tempB--;
		else 
			*tempB='0';
	}
}

void Minus(char a[],char b[], char c[])
{
	omitZero(a);
	omitZero(b);
	if(getLen(a)>MaxLength || getLen(a)>MaxLength) 
	{
		cout<<"the number is too long."<<endl;
		return;
	}

	if(('-'==*a) && ('-')==*b) //如果被减数、减数均是负数
	{
		if(isAbigger(a+1, b+1)) { *c++='-'; _Minus(++a, ++b, c); c--;}
		else { _Minus(++b, ++a, c); }
	}
	else if(('-'==*a) && ('-')!=*b) //如果被减数是正数、减数是负数
	{
		*c++='-'; 
		if(isAbigger(a+1, b)) _Add(++a, b, c);
		else _Add(b, ++a, c);
	}
	else if(('-'!=*a) && ('-')==*b) //如果被减数是负数、减数是正数
	{
		if(isAbigger(a, b+1)) _Add(a, ++b, c);
		else _Add(++b, a, c);
	}
	else if(('-'!=*a) && ('-')!=*b) //如果被减数、减数均是正数
	{
		if(isAbigger(a, b)) { _Minus(a, b, c); }
		else { *c++='-'; _Minus(b, a, c); c--;}
	}
	omitZero(c);
}

void Add(char a[], char b[], char c[])
{
	omitZero(a);
	omitZero(b);
	if(getLen(a)>MaxLength || getLen(a)>MaxLength) 
	{
		cout<<"the number is too long."<<endl;
		return;
	}

	if(('-'==*a) && ('-')==*b) //都是是负数
	{
		Minus(a, ++b, c);
	}
	else if(('-'==*a) && ('-')!=*b) //一个负数一个正数
	{
		Minus(b, ++a, c);
	}
	else if(('-'!=*a) && ('-')==*b) //一个负数一个正数
	{
		Minus(a, ++b, c);
	}
	else if(('-'!=*a) && ('-')!=*b) //都是正数
	{
		if(isAbigger(a, b)) _Add(a, b, c);
		else _Add(b, a, c);
	}
	omitZero(c);
}

//Test应用库函数测试
int Test(int a, int b, int flag)
{
	char bufferA[MaxLength];
	char bufferB[MaxLength];
	char bufferC[MaxLength];
	char myResult[MaxLength];

	_itoa(a, bufferA, 10);
	_itoa(b, bufferB, 10);
	
	if(flag==FADD)
	{
		_itoa(a+b, bufferC, 10);
		Add(bufferA, bufferB, myResult);
	}
	else
	{
		_itoa(a-b, bufferC, 10);
		Minus(bufferA, bufferB, myResult);
	}

	int r=strcmp(myResult, bufferC);
	if(0!=r) cout<<"A="<<a<<endl<<"B="<<b<<endl<<endl;
	return !r;
}

void Test(char const *aBig, char const *bBig, char *c)
{
	char a[MaxLength+1];
	char b[MaxLength+1];
	strcpy(a, aBig); strcpy(b, bBig);
	Add(a, b, c);
	cout<<a<<"+"<<b<<"="<<c<<endl;
	Minus(a, b, c);
	cout<<a<<"-"<<b<<"="<<c<<endl;
	Minus(b, a, c);
	cout<<b<<"-"<<a<<"="<<c<<endl;
}

void TestBond()
{
	char c[MaxLength+1];

	Test("0", "0", c);
	Test("1", "0", c);
	Test("-1", "0", c);
	Test("-0", "0", c);
	Test("-0000000123", "-42345", c);
	Test("00000000123", "124512", c);
	Test("99999999999999999999999", "1", c);
	Test("-011111", "1234567890", c);
	cout<<endl;
}

const int MAXNUM=10000;
const int TESTTIME=100000;

void main()
{
	char a[MaxLength+1]="124";
	char b[MaxLength+1]="12536";
	char c[MaxLength+1]="0";
	
	//Add(a, b, c);
	//Minus(a, b, c);
	//cout<<c<<endl;
	TestBond();
		
	int i, isOK=1;
	srand( (unsigned)time(NULL));
	for(i=0; i<TESTTIME; i++) 
	{ 
		isOK=Test(rand()%MAXNUM-MAXNUM/2, rand()%MAXNUM-MAXNUM/2, FADD);
		if(0==isOK) break;
	
		isOK=Test(rand()%MAXNUM-MAXNUM/2, rand()%MAXNUM-MAXNUM/2, FMINUS);
		if(0==isOK) break;
	}
	if (isOK) cout<<"all the "<<TESTTIME<<" times random test passed"<<endl;
}