超大数乘法程序

#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://com.8s8s.com/it/it25165.htm