bn.cpp

数据结构书上的大数相乘的具体实现

/****************************************/

/*头函数*/
#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<string.h>

#define max 10000

char sum[max];
/****************************************/

/*子函数计算两个数的乘积*/
void fmul(char s1[],char s2[])
{
	int ls1,ls2;	/*用于存储长度，进位信息*/
	int i,j,p,q;
	int m;
	int k=0,flag;	//k-每位相乘的结果,flag-进位数
	char mid[max];	/*中间数组*/
	ls1=strlen(s1);
	ls2=strlen(s2);

/*********将整数在数组中逆序存放*********/
	i=0;
	j=ls1-1;
	while(j>=0)
	{
		mid[i++]=s1[j--];
	}
	mid[i]=s1[ls1];	//结束标志保存
	strcpy(s1,mid);

	i=0;
	j=ls2-1;
	while(j>=0)
	{
		mid[i++]=s2[j--];
	}
	mid[i]=s2[ls2];	//结束标志保存
	strcpy(s2,mid);
/****************************************/

//	cout<<s1<<endl<<s2<<endl;	//测试

	/*计算*/
	for(i=0;i<max;i++)	//结果数组清零
	{
		sum[i]='0';
	}
	i=j=k=0;	//k-每位相乘的结果
	flag=0;		//flag-进位数
	p=0;
	q=0;

	while(s2[i]!='\0')
	{
		flag=0;
		m=q;
		for(m=0;m<q;m++)		//?????????
		{
			mid[m]='0';
		}
		p=m;
//		p=q;
		while(s1[j]!='\0')
		{
			k=(s1[j]-'0')*(s2[i]-'0');
			mid[p]=(flag+k)%10+'0';	//取本位
			flag=(flag+k)/10;		//取进位
			j++;
			p++;
		}
		if(flag!=0)
		{
			mid[p++]=flag+'0';
		}
		mid[p]='\0';
		flag=0;
		p=0;
/****************************************/
		if(i==0)
		{
			while(mid[p]!='\0')
			{
				sum[p]=mid[p];
				p++;
			}
		}
		else
		{   
			while(mid[p]!='\0')
			{
				k=(sum[p]-'0')+(mid[p]-'0');
				sum[p]=(k+flag)%10+'0';
				flag=(k+flag)/10;
				p++; 
			}
			if(flag!=0)
			{
				sum[p++]=flag+'0';
				flag=0;
			}
		}

		j=0;
		i++;
		q++;
	}
/**************结果正序排列*************/
	sum[p]='\0';
	i=0;
	j=0;
	strcpy(mid,sum);
	p-=1;
	while(p>=0)
	{
		sum[j]=mid[p];
		p--;
		j++;
	}
	sum[j]='\0';
//	return 0;
}

/***************************************/
/*主函数*/

int main()
{
	char s1[]=("55");
	char s2[]=("33");
	fmul(s1,s2);
	cout<<sum<<endl;
	system("pause");
	return 0;
}