超大数乘法程序

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

#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;

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航