超大数乘法程序的详细介绍

#include <iostream>
#include <cstring>
#include <string>
#include <cassert>
#include <cstdlib>
typedef int ET;
typedef struct NODE{
ET data;
struct NODE * p;
struct NODE * n;
}NODE,*NODEH;
typedef struct LIST{
NODEH head;
NODEH end;
int length;
}LIST,*LISTH;
////////////////////////
////////////////////////
inline bool InitList(LISTH& L)
{
//将头结点L处理一下
L=(LISTH)malloc(sizeof(LIST));
assert(L);
L->head = L->end = NULL;
L->length=0;
return true;
}
inline NODEH NMalloc(const ET& elem)
{
//返回一个新结点，其数据为elem
NODEH temp=(NODEH)malloc(sizeof(NODE));
assert(temp);
temp->data=elem;
return temp;
}
inline bool PreAdd(LISTH& L,const ET& elem)
{
//在头部加入新结点elem
NODEH temp=NMalloc(elem);
++(L->length);
if(NULL==L->head&&NULL==L->end){
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;
}
inline bool EndAdd(LISTH& L,const ET& elem)
{
//在尾部加入新结点elem
NODEH temp=NMalloc(elem);
++(L->length);
if(NULL==L->head&&NULL==L->end){
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;
}
inline bool DestoryList(LISTH& L)
{
//将表L 释放
NODEH temp=L->head,it;
if(temp==NULL){
free(L);
return true;
}
while(temp!=L->end){
it=temp;
temp=temp->n;
free(it);
}
free(temp);
free(L);
return true;
}
inline void PrintList(LISTH& L)
{
//print
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');
}
inline bool AddZero(LISTH& L,int count)
{
//在L的尾部加上count个0
while(count--)EndAdd(L,0);
return true;
}
inline bool BitMul(LISTH& L,const int number,LISTH& NUM)
{
//将L与数number相乘 后的结果存入NUM中去
//NUM应当为空表结构！！！！！！！！！
NODEH L_end=L->end;
int 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;
}
inline bool ADD(const LISTH& La,LISTH& Lb)
{
// Lb= La+Lb
NODEH pa=La->end,pb=Lb->end;
int status=0;
for(;pa!= La->head;pa=pa->p,pb=pb->p){
if(pb==NULL){
PreAdd(Lb,0);
pb=Lb->head;
}
int 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;
}
int 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;
}
///////////////////////////////////////////////////////////////////////////////
inline void MUL(const char * a,const char *b)
{
//init
LISTH CS=NULL; //乘数
LISTH BCS=NULL; //被乘数
LISTH NUM=NULL; //结果
assert(a&&b);
assert(InitList(NUM));
assert(InitList(CS)&&InitList(BCS));
{
//符号处理
int sig=1;
if('-'==*a){
++a;
sig*=-1;
}
else if('+'==*a) ++a;
if('-'==*b){
++b;
sig*=-1;
}
else if('+'==*b)++b;
if(sig<0)putchar('-');
}
if(strcmp(a,b)>0){
const char *pa= a,*pb=b;
for(;'/0'!=*pa;++pa){
int temp= *pa-'0';
assert(EndAdd(BCS,temp) );
}
for(;'/0'!=*pb;++pb){
int temp= *pb-'0';
assert(EndAdd(CS,temp) );
}
}
else {
const char *pa= a,*pb=b;
for(;'/0'!=*pa;++pa){
int temp= *pa-'0';
assert(EndAdd(CS,temp) );
}
for(;'/0'!=*pb;++pb){
int temp= *pb-'0';
assert(EndAdd(BCS,temp) );
}
}
// init end!!!!
NODEH cs_p= CS->end;
int bit = 0;//位数
for(; cs_p !=CS->head ; cs_p=cs_p->p){
LISTH TEMP;
InitList(TEMP);
BitMul(BCS,cs_p->data,TEMP);
///////////////////////////////////////////////////////////////////////
puts("===============================================================/n");
PrintList(BCS);///////////////////////////////////////////////
printf(" X %d=",cs_p->data);
PrintList(TEMP);
///////////////////////////////////////////////////////////////////////
//<============================== here!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
AddZero(TEMP,bit);
ADD(TEMP,NUM);
/////////////////
puts("/nNUM:");
PrintList(NUM);
printf("/nbit:%d/n",bit);
////////////////////////////////////////////////////////////////////
++bit;
DestoryList(TEMP);
}
LISTH TEMP;
InitList(TEMP);
BitMul(BCS,cs_p->data,TEMP);
///////////////////////////////////////////////////////////////////////
puts("===============================================================/n");
PrintList(BCS);///////////////////////////////////////////////
printf(" X %d=",cs_p->data);
PrintList(TEMP);
///////////////////////////////////////////////////////////////////////
//<============================== here!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
AddZero(TEMP,bit);
ADD(TEMP,NUM);
/////////////////
puts("/nNUM:");
PrintList(NUM);
printf("/nbit:%d/n",bit);
////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////
std::cout<<'/n'<<"结果=";
PrintList(NUM);
putchar('/n');
///////////清理工作
DestoryList(TEMP);
DestoryList(BCS);
DestoryList(CS);
DestoryList(NUM);
}
int main(void)
{
std::string a,b;
std::cin>>a;
std::cin>>b;
MUL(a.c_str(),b.c_str());

system("pause");
return 0;
}

本文地址：http://www.45fan.com/a/luyou/70766.html