homework.cpp

能实现任意两个超大整数的乘法。经本人实验

#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::cout<<"please enter  a ";
    std::cin>>a;
	
    std::cin>>b;
    MUL(a.c_str(),b.c_str());
    
    system("pause");
    return 0;
}