big.cpp

大家一定写过计算器程序吧！但如果让你写一个用来计算成千上万位数的程序

#include <iostream.h>
#include <malloc.h>
#include <string.h>
#include <conio.h>
#include "big.h"


/*---------------------------------*/
big::big()
{

}

/*---------------------------------*/
big::big(int i)
{

}

/*---------------------------------*/
big::~big()
{

}

/*---------------------------------*/
void big::FreeNode(struct node **h)
{
 struct node *p;
 while((*h) != NULL){
	 p = *h;
	 *h = (*h)->next;
	 free(p);
 }
}

/*---------------------------------*/
Node* big::BuildNode(char *ch)
{int num=0, i, j, k, n, first=1;
 char *pch;
 struct node *h,*tail,*p;
 h = NULL;
 if(*ch == '\0') return h;
 while(*(ch+num) != '\0') num++;
 

while(num > 0)
{
 p=(struct node*)malloc(sizeof(struct node));
 p->data = 0;
 p->next = NULL;
 if(first) {first = 0; h = tail = p; }
 else { tail->next = p; tail = tail->next; } 
 pch = ch+num-1;
 i = 0;
 while(i < 4 && num > 0){// && *pch != '\0'
     k = *pch - '0';
     n = 1;
	 for(j=0;j<i;j++) n = n*10;
	 p->data += k*n;
     i++;
	 num--;
	 pch--;
 }
}
/* h->next = NULL;
 tail = h;
 num -= 4;
 while((num > 0) && *(ch+num-1) != '\0'){
     if((*ch < '0') || (*ch > '9')) {FreeNode(&h); return h;}
	 p=(struct node*)malloc(sizeof(struct node));
	 p->data = *(ch+num-1) - '0';
	 tail->next = p;
     tail = tail->next;
	 tail->next = NULL;
	 num--;
 }*/
 return h;
}

/*---------------------------------*/
void big::CopyNode(struct node **dest, struct node *src)
{struct node *p,*pdest,*temp;
int first=1;
p = src;
while(p != NULL){
	temp = (struct node*)malloc(sizeof(struct node));
    temp->data = p->data;
	temp->next = NULL;
	if(first) {first = 0; (*dest) = temp; pdest = *dest;}
	else {pdest->next = temp; pdest = pdest->next;}
	p = p->next;
}
}

/*---------------------------------*/
struct node* big::SubNode(struct node *h1, struct node *h2) //h1 must greater than h2
{
 struct node *p1,*p2,*rlt,*prlt,*temp;
 
 p1 = h1; p2 = h2; prlt = rlt = NULL;
 while(p1 != NULL)
 {
	 if(rlt == NULL){
		 rlt = (struct node*)malloc(sizeof(struct node));
		 rlt->data = 0;
		 rlt->next =NULL;
		 prlt = rlt;
	 }
	 if(p2 != NULL) prlt->data = p1->data - p2->data;
	 else prlt->data = p1->data;
	 if(p1->next != NULL){
		 temp = (struct node*)malloc(sizeof(struct node));
	     temp->data = 0;
	     temp->next = NULL;
		 prlt->next = temp;
		 prlt = prlt->next;
	 }
	 p1 = p1->next;
	 if(p2 != NULL) p2 = p2->next;
 }

 RuleNode(&rlt);
 return rlt;
}

/*---------------------------------*/
struct node* big::MulNode(struct node *h1, struct node *h2)
{
 struct node *p1,*p2,*prlt,*rlt,*bak,*bak1;
 int first=1;

 CopyNode(&bak1,h1);
 CopyNode(&bak, h1);
 p1 = bak; p2 = h2;
 prlt = rlt = NULL;
 while(p2 != NULL){
	 if((p2->data == 0) && (prlt != NULL && prlt->next != NULL)) {
		 prlt = prlt->next; 
		 p2 = p2->next;
		 continue;
	 }
    // if(p2->data == 0) 此情况下的效率还可以改进
	 while(p1 != NULL) {p1->data *= p2->data; p1 = p1->next;}

	 if(first) {first = 0; rlt = prlt = bak; RuleNode(&rlt);}
	 else{
		 if(prlt->next != NULL) {
			 prlt = prlt->next;
		     BindNode(&prlt, bak); 
		 } 
         else {
			 BindNode(&prlt->next, bak); 
			 prlt = prlt->next;
		 }
	     FreeNode(&bak);  //free the bak node.
	 }
     CopyNode(&bak,bak1);
	 p1 = bak;
	 p2 = p2->next;
 } 

 RuleNode(&rlt);
 FreeNode(&bak);
 FreeNode(&bak1);
 return rlt;
}

/*---------------------------------*/
void big::BindNode(struct node **dest, struct node *src) //*dest += src
{
 struct node *p1,*p2;
 p1 = *dest; p2 = src;
 if(p1 == NULL) {CopyNode(dest, src); return;}
 while((p1 != NULL)&&(p2 != NULL)){
    p1->data += p2->data;
    if(p1->next == NULL || p2->next == NULL) break;
	p1 = p1->next; 
	p2 = p2->next;
 }
 if(p1->next == NULL) {p1->next = p2->next; p2->next = NULL;}
 RuleNode(dest);  
 //FreeNode(&src);
}

/*---------------------------------*/
void big::DecNode(struct node **dest)
{
 int len;
 struct node *p;
  if(*dest == NULL) return;
  p = *dest;
  len = 0;
  while(p != NULL) {len++; p = p->next;}
  if((len == 1)&&(*dest)->data == 0) return;

  (*dest)->data -= 1;
  RuleNode(dest);
}

/*---------------------------------*/
int big::CmpNode(struct node *h1, struct node *h2)
{
int len1,len2,i;
struct node *p1,*p2;
len1 = len2 = 0;
p1 = h1; p2 = h2;
while(p1 != NULL) {len1++; p1 = p1->next;}
while(p2 != NULL) {len2++; p2 = p2->next;}
if(len1 > len2) return 1;
else if(len1 < len2) return -1;
else{
    if(len1 == 0) return 0;
    while(len1 > 0){
	  p1 = h1; p2 = h2; i = 1;  
	  while(i < len1) {p1 = p1->next; p2 = p2->next; i++;}
      
	  if(p1->data > p2->data) return 1;
	  else if(p1->data < p2->data) return -1;
      len1--;
	}
	return 0;
}
}

/*---------------------------------*/
int  big::CheckZero(struct node **h)
{
  int num=0;
  struct node *p;
  while(((*h) != NULL)&&((*h)->data == 0)) {
	  num+=4; 
	  p = *h;
	  (*h) = (*h)->next;
	  free(p);
  }
  return num;
}

/*---------------------------------*/
void big::RuleNode(struct node **h)
{ struct node *hd,*p;
  int flag;
  hd = *h;
  if(hd == NULL) return;
	while(hd != NULL){
		if(hd->data > 9999) {//'+'
			while(hd->data>9999) {
			  if(hd->next == NULL) {p=(struct node*)malloc(sizeof(struct node));
			             p->data  = 0;
					     p->next  = NULL;
					     hd->next = p;
			  }
              hd->next->data += hd->data/10000;
			  hd->data %= 10000;
			}
		}
		else if(hd->data < 0){//'-'
			  while(hd->data < 0){
				hd->data += 10000;  	
		        if(hd->next == NULL) {p=(struct node*)malloc(sizeof(struct node));
			             p->data  = 10000;
					     p->next  = NULL;
					     hd->next = p;
				}
			    hd->next->data--;
			  }
		}
		hd = hd->next;
	}
	flag = 0;
	while(!flag){
		hd = *h;
		p = hd->next;
		if(p == NULL) {p = hd;}
		while(p->next != NULL) {hd = hd->next; p = p->next;}
		if(p->data == 0){
			if(p == hd) {free(p); p = hd = *h = NULL; flag = 1;}
			else {hd->next = NULL; free(p);}			
            	
		}
		else if(p->data > 0) flag = 1;
	}
}

/*---------------------------------*/
char* big::NodeToString(struct node *h)
{
 char *p;
 struct node *hd;
 int num,i;
 num = 0;
 hd = h;
 while(hd != NULL) {num++; hd = hd->next;}
 hd = h;
 p = (char *)malloc(num*4 + 1);
 for(i=num-1;i>=0;i--)
 {
   *(p+i*4+0) = '0' + hd->data/1000;
   *(p+i*4+1) = '0' + (hd->data/100)%10;
   *(p+i*4+2) = '0' + (hd->data%100)/10;
   *(p+i*4+3) = '0' + hd->data%10;
   hd = hd->next;
 }
 *(p+num*4) = '\0';
 while(*p == '0') p++;
 return p; 		
}

/*---------------------------------*/
char* big::Addin(struct node **h1, struct node *h2)
{
 struct node *p1,*p2;
 char *ch;
 p1 = *h1; p2 = h2;
 if(p1 == NULL) return NodeToString(h2);
 if(p2 == NULL) return NodeToString(*h1);
 while((p1->next != NULL)&&(p2->next != NULL)){
    p1->data += p2->data;
	p1 = p1->next; 
	p2 = p2->next;
 }
 p1->data += p2->data;
 if(p1->next == NULL) {p1->next = p2->next; p2->next = NULL;}
 RuleNode(h1);
 ch = NodeToString(*h1);
 return ch;
}

/*---------------------------------*/
char* big::Step(char *s)
{int f,cnt=0;
 long NumOfZero=0;
 char *ch,*rt;
 struct node *h1,*h2,*bak,*rlt;

 if(*s == '0') {
	 rt = (char*)malloc(2);
     *rt = '1';
     *(rt+1) = '\0'; 
	 return rt; 
 }
 h1 = BuildNode(s);
 h2 = (struct node*)malloc(sizeof(struct node));
 h2->data = 1;
 h2->next = NULL;
 
 CopyNode(&rlt,h1);
 DecNode(&h1);
 f = CmpNode(h1,h2);
 while(f > 0){
       NumOfZero += CheckZero(&rlt);
	   CopyNode(&bak,rlt);
	   FreeNode(&rlt);
	   rlt = MulNode(bak,h1);
       FreeNode(&bak);

   cnt++;
   if(cnt>=100){ 
	   cnt = 0;
       rt = NodeToString(h1);
       cout<<"Now process : "<<rt<<endl;
   }

   DecNode(&h1);
   f = CmpNode(h1,h2);
 }

 ch = NodeToString(rlt);
 if(NumOfZero != 0){
   char *pch = (char*)malloc(NumOfZero+1);
   memset(pch,(int)'0',NumOfZero);
   *(pch+NumOfZero) = '\0';
   ch = strcat(ch, pch);
 }
 FreeNode(&rlt);
 FreeNode(&h1);
 FreeNode(&h2);
 return ch;
}

/*---------------------------------*/
char* big::Add(char *s1, char *s2)
{
  char *p;
  struct node *h1,*h2;
  h1 = h2 = NULL;
  h1 = BuildNode(s1);
  h2 = BuildNode(s2);
  p = Addin(&h1, h2);
  FreeNode(&h1);
  FreeNode(&h2);
  return p;
}

/*---------------------------------*/
char* big::Sub(char* s1, char* s2)
{char *ch,*pchar,c='0';
 struct node *h1, *h2;
 struct node *p1,*p2;
 int len1,len2,i;
 int flag=0;
 len1 = strlen(s1);
 len2 = strlen(s2);
 if(len1 == 0 && len2 != 0) {
	 pchar = (char*)malloc(strlen(s2)+2);
	 *pchar = '-';
	 strcpy(pchar+1,s2);
	 return pchar; 
 }
 if(len2 == 0) return s1;
 if(len1 < len2) {ch = s1; s1 = s2; s2 = ch; flag = 1;}
 else if(len1 == len2) { 
	 i = 0;
	 while(*(s2+i) == *(s1+i) && len1 > i) i++;
	 if(i == len1) {
		 ch = (char*)malloc(2); 
	     *ch = '0';
		 *(ch+1) = '\0';
		 return ch;
	 }
	 if(*(s2+i)-*(s1+i) > 0) {ch = s1; s1 = s2; s2 = ch; flag = 1;}  
 }
 h1 = BuildNode(s1);
 h2 = BuildNode(s2);
 p1 = h1; p2 = h2;
 while((p1->next != NULL)&&(p2->next != NULL)){
    p1->data -= p2->data;
	p1 = p1->next; 
	p2 = p2->next;
 } 
 p1->data -= p2->data;
 if(p1->next == NULL) {
    p1->next = p2->next;
	p2 = p2->next;
    while(p2 != NULL) {p2->data = 0 - p2->data; p2 = p2->next;}	
 }
 RuleNode(&h1);
 ch = NodeToString(h1);
 if(flag) { 
     pchar = (char*)malloc(strlen(ch)+2);
	 *pchar = '-';
	 strcpy(pchar+1,ch);
	 return pchar;
 }
 return ch; 
}

/*---------------------------------*/
char* big::Mul(char* s1, char* s2)
{struct node *h1,*h2;
 struct node *p1,*p2;
 struct node *rlt;
 char *ch,*pchar;
 int len1,len2,NumOfZero=0;
 
 len1 = strlen(s1);
 len2 = strlen(s2);
 if(len1 == 0 || len2 == 0) {
	 pchar = (char*)malloc(2);
	 *pchar = ' '; 
	 *(pchar+1) = '\0';
	 return pchar; 
 }
	
 h1 = BuildNode(s1);
 h2 = BuildNode(s2);
 p1 = h1; p2 = h2;
 NumOfZero += CheckZero(&h1);
 NumOfZero += CheckZero(&h2);

 rlt = MulNode(h1, h2);

 ch = NodeToString(rlt);
 if(NumOfZero != 0){
   char *pch = (char*)malloc(NumOfZero+1);
   memset(pch,(int)'0',NumOfZero);
   *(pch+NumOfZero) = '\0';
   ch = strcat(ch, pch);
 }
 FreeNode(&h1);
 FreeNode(&h2);
 FreeNode(&rlt);
 return ch;
}

/*---------------------------------*/
char* big::Div(char* s1, char* s2)
{
 char *ch;
 struct node *h1,*h2,*p1,*p2,*p;
 struct node *rlt;
 int len1,len2;
 len1 = strlen(s1);
 len2 = strlen(s2);
 if((len1 < len2) || ((len1 == len2)&&(strcmp(s1,s2) < 0)))
 {
	 ch = (char*)malloc(2);
	 *ch = '0';
	 *(ch+1) = '\0';
	 return ch;
 }
 
 h1 = BuildNode(s1);
 h2 = BuildNode(s2);
 p1 = h1; p2 = h2; rlt = NULL;
 while(CmpNode(p1,p2) >= 0)
 {
  p = SubNode(p1,p2);
  p1 = p;

  if(rlt == NULL) {
	  rlt = (struct node*)malloc(sizeof(struct node));
      rlt->data = 0;
	  rlt->next = NULL;
  }
  rlt->data++;
  if(rlt->data > 9) RuleNode(&rlt);
 }
 
 RuleNode(&rlt);
 ch = NodeToString(rlt);
 FreeNode(&h1);
 FreeNode(&h2);
 FreeNode(&rlt);
 return ch;
}

/*---------------------------------*/
void main()
{
 cout<<"hello"<<endl;
 big a;
 char *p1="34344534543534534556536560000000000", 
	  *p2="25543534543555504545545454300000000",
	  *p3="2005",
      *p4="2",*p5,*tmp,*p;
 cout<<a.Add(p1, p2)<<endl;
 cout<<a.Sub(p1, p2)<<endl;
 cout<<a.Mul(p1, p2)<<endl;
 cout<<a.Div(p1, p2)<<endl;

//2^1000
 int num,first = 1;
 tmp = p4;
 for(num=1;num<1000;num++)
 {
   p5 = a.Mul(tmp,p4);
   tmp = p5;
 }
 cout<<"Length: "<<strlen(tmp)<<endl;
 cout<<"2^1000 = "<<tmp<<endl;
//此处的tmp不知该如何释放

//2005!
 p = a.Step(p3);
 cout<<"Length: "<<strlen(p)<<endl;
 cout<<p<<endl;

 cout<<"any key to exit..."<<endl;
 getch();
}