updatados2007.cpp

大数运算的设计与实现

         if(i!=0)
         p=big_numnodeinsert( p,1,1, i+'0');

        while(j==0)
	{
			 if(r2!=NULL)
			 {
	          c=r2->data;
	          
			 
			 q=big_numnodeinsert(q,1,1,  c);
          q=deletezero( q);//去掉头部多余零
		   
		  yushu=q;
		 
		  q->next=NULL; 
       
			 }
			 if(r2==NULL)
		  { 
		return p;
		  
		  }
	   
		   t=deletezero( t);//去掉头部多余零
	      
     	  j= big_numCOMPARE(q,t);//大数绝对值的比较

	}
         r3=r2;
       r2=r2->next;
        i=0;

}

	 return p;


}

  big_numnode *bignum_operation:: big_numDEVIDE(char  a[],char b[])//大数除法
{
   big_numnode *r,*t,*headr ,*headt,*p,*q,*r1,*r2;  //  存储创建的两个链表的尾结点
   int n=0; int i=0;//记录移位次数
   int j=0;
   int m=0;
   int point=0;
   int w=0;
   int k=0;
   char c;
   r=creatlinklist(a);// 创建双向链表
   t=creatlinklist(b);// 创建双向链
   headr=linklist_length( r);//返回r的头指针
   int n1=n_inter;//存储链表r整数部分位数
   int n2=n_small;//存储链表r小数部分位数
   headt= linklist_length( t);//返回t的头指针
   int n3=n_inter;//存储链表t整数部分位数
   int n4=n_small;//存储链表t小数部分位数
   if(n2!=0)
   r= deletpoint(r);//删除小数点操作
   if(n4!=0)
   t= deletpoint(t);//删除小数点操作
   r=deletezero( r);//去掉头部多余零
   t=deletezero( t);
   int zero=isZERO(r);
   if(zero==0)return r;
	 zero=isZERO(t);
	 if(zero==0)//合法性检查
	 {cout<<"除数不能为零"<<endl;
	 exit(0);
	 }
	 n=n3+n4;
	 m=n1+n2;
  
	 p=new  big_numnode;//用于存储商的头结点
		p->data='0';
		p->ahead=p->next=NULL;
	    j= big_numCOMPARE(r,t);//大数绝对值的比较
	 while(j==0)
	 {
	  r=big_numnodeinsert(r,1,1,  '0');//当被除数小于除数时被除数尾补零
	  p=big_numnodeinsert( p,1,1, '0');
	 w++;
	 if(w==1)
	 {p=big_numnodeinsert( p,1,1, '.');
	 
	  k++;
	 }
	  j= big_numCOMPARE(r,t);//大数绝对值的比较
	 
	 }
	
         r1=getlinknode(r,m-n);
		 r2=r1->next;
         q=r1;
         q->next=NULL;

while(point <=n_smallpoint)//控制总的循环次数
{

   j= big_numCOMPARE(q,t);//大数绝对值的比较
while(j==1){
	
		 q=big_numSUB(q,t);
		 q->next=NULL; 
		 q=deletezero( q);//去掉头部多余零
		 t=deletezero( t);//去掉头部
         j= big_numCOMPARE(q,t);//大数绝对值的比较
		 i++; 
}
         if(i!=0)
         p=big_numnodeinsert( p,1,1, i+'0');

        while(j==0)
	{
			 if(r2!=NULL)
			 {
	          c=r2->data;
	          r2=r2->next;
			 }
		  else 
		  { 
			c='0'; 
		    point++;
		  if(point ==1&&k!=1)
		   p=big_numnodeinsert( p,1,1, '.');
		  }
	      q=big_numnodeinsert(q,1,1,  c);
          q=deletezero( q);//去掉头部多余零
		  q->next=NULL; 
          zero=isZERO(q);//判断余数是否为零
		  if(zero==0&&r2==NULL)
		  {   p=big_numnodeinsert( p,1,1, '0');
			  return p;	
		  }
		  t=deletezero( t);//去掉头部多余零
	      
     	  j= big_numCOMPARE(q,t);//大数绝对值的比较
	      if(j==0){
	    	p=big_numnodeinsert( p,1,1, '0');
		  }

	}

        zero=isZERO(q);
	    if(zero==0&&r2==NULL)
		{
			p=big_numnodeinsert( p,1,1, '0');
			return p;	
        }
        i=0;

}

	 return p;
}

big_numnode *bignum_operation::addpoint(big_numnode *rear,int n)//乘除法增加小数点操作

{
	big_numnode *p1,*p2,*s;
	int i=0,j=0;

	p1=rear;

	linklist_length(rear);
 
	i=n_inter;//整数部分位数
 if(i>n&&n!=0)
 {
 
	 while(j<n)
 {
 
		 p2=p1;
 
		 p1=p1->ahead;

		 j++;
 
 }

	 s=new  big_numnode;//小数点节点插入
	  
	 s->data='.';
	 
	 s->ahead=s->next=NULL;
   
	 p1->next=s;
   
	 s->ahead=p1;
   
	 s->next=p2;
  
	 p2->ahead=s;
}

if(i<=n&&n!=0)
{

	int n1=n-i;

	j=0;

	while(j<i)
 {
 
		p2=p1;
 
		p1=p1->ahead;
 
		j++;
 
 }
j=0;

while(j<n1+2)
{//小数点节点插入,向前插入时的移位补0
s=new  big_numnode;
	  if(j==n1)
		  
		  s->data='.';
		 else
			 
			 s->data='0';
	  
		 s->ahead=s->next=NULL;
   
		 p1->next=s;
   
		 s->ahead=p1;
  
		 s->next=p2;
   
		 p2->ahead=s;

		 p2=p2->ahead;

		 j++;

}
}
return rear;
}

big_numnode *bignum_operation::deletpoint(big_numnode *p)//删除小数点操作
	 {    //p为尾指针,返回尾指针

		 big_numnode *rear,*q;
		
		 rear=p;
		
		 while(p->ahead!=NULL&&p->data!='.')
		 {
			 q=p;
			
			 p=p->ahead;

		 }
	 
		 if(p->data=='.')//小数点删除方便乘法运算
		 {
		 
			 p->ahead->next=q;
		 
			 q->ahead=p->ahead;
		 
			 free(p);
		 }
	 
	 return rear;
	 }
  big_numnode *bignum_operation::MULmoveleft(big_numnode *rear,int n,int f)//乘法移位操作
  {//rear 尾指针,n移位个数,f=0左移,f=1右移
      big_numnode *p,*q,*point;
	  
	  int j=0;
      
	  linklist_length( rear);
	  
	  int n1=n_inter;//存储链表r整数部分位数
	  
	  int n2=n_small;//存储链表r小数部分位数
   
	  q=rear;
	  
	  if(n2==0&&f==0){//整数左移位	  
	 
		  while(j++<n)
	  {
			  p=new  big_numnode;//头结点
	 
			  p->data='0';
	 
			  p->ahead=p->next=NULL;
	 
			  q->next=p;
	
			  p->ahead=q;
	   
			  q=p;     
	  
			  p=p->next;
	  }


		  return q;

	  }
if(n2==0&&f==1){//整数右移位
	  while(j++<n)//向前遍历寻找小数点位置
	  {
		  p=q;
		  q=q->ahead;
	  
	  }
	  
      point=new  big_numnode;//小数点插入操作
	  
	  point->data='.';
	  
	  point->ahead=point->next=NULL;
	  
	  q->next=point;
	 
	  point->ahead=q;
	  
	  point->next=p;
	 
	  p->ahead=point;
}
  return rear;
  
  }
big_numnode *  bignum_operation::big_numMUL1(big_numnode * r,char b)//大数乘法乘数位数字与被乘数相乘
 { //r传入参数是尾节点，返回值也是尾节点
	 big_numnode * p,*p1,*rear,*p2,*p3;
 
	 int c=0;int s=0;
 
	 p=r;
 
	 p2= rear=new  big_numnode;//尾结点	

	 rear->ahead=rear->next=NULL;
 while(p->ahead!=NULL)
 {
	 s=((p->data-'0')*(b-'0')+c)%10;
 
	 c=(p->data-'0')*(b-'0')/10;
 
	 p2->data=s+'0';						
 
	 p3=new  big_numnode;
 
	 p3->ahead=p3->next=NULL;
 
	 p3->data='0';//初始化
 
	 p3->next=p2;

	 p2->ahead=p3;
 
	 p2=p3;				      
	 
	 p=p->ahead;//
 }
 
 p1=rear;
if(c!=0)//表示最高位有进位位
{
	p1=big_numnodeinsert(rear,0,1 ,'0'+c);//结点插入操作p1为尾节点
   
}
 
return p1; //返回头节点
 }
 big_numnode *  bignum_operation::big_numMUL(char  a[],char b[])//大数乘法
 {
 
 
  big_numnode *r,*t,*p,*q,*p1,*p2;  //  存储创建的两个链表的尾结点
   int n=0;  
  
   r=creatlinklist(a);// 创建双向链表
     
   t=creatlinklist(b);// 创建双向链
	  
   linklist_length( r);
	  
   int n1=n_inter;//存储链表r整数部分位数
	  
   int n2=n_small;//存储链表r小数部分位数
	  
   linklist_length( t);
	  
   int n3=n_inter;//存储链表t整数部分位数
	  
   int n4=n_small;//存储链表t小数部分位数
      
   if(n2!=0)
      
	   r= deletpoint(r);//删除小数点操作
      if(n4!=0)
	 
		  t=deletpoint(t);//删除小数点操作
	  if((n1+n2)>=(n3+n4))//判断两个大数的位数大小大者做被乘数
	  {
		  p=r; q=t;
	  }
	  else{
	     
		  p=t;
		  q=r;
	  }
	  
	  int j=0;
	 
          n=n2+n4; 
		   
		   while(q->ahead!=NULL)//外层循环用来控制乘数次数循环次数由乘数位数决定
	  {
			   j++;//控制移位次数
	   if(j==1)
	   {
		   p1=  big_numMUL1(p,q->data);//生成第j趟乘法链
			 
		   q=q->ahead; 
	   
	   if(q->ahead==NULL)
		   
		   break;	   
	   
	   }
			
	   if(q!=NULL){
			 
		   p2=  big_numMUL1(p,q->data);//生成第j+1趟乘法链
		  
		   p2=	MULmoveleft(p2,j,0);//乘法移位操作,p3为尾节点
		 
		  p1= big_numADD(p1,p2 , 1);//大数加法具体操作
	
		  q=q->ahead;
			 }
		
	   }  
	   
	  addpoint(p1,n);//乘除法增加小数点操作
	  
	  return p1;

 }


 big_numnode *  bignum_operation::big_numMUL( big_numnode *r, big_numnode *t)//大数乘法
 {
 
 
  big_numnode *p,*q,*p1,*p2;  //  存储创建的两个链表的尾结点
   
  int n=0;  
	  
  linklist_length( r);
	  
  int n1=n_inter;//存储链表r整数部分位数
	  
  int n2=n_small;//存储链表r小数部分位数
	  
  linklist_length( t);
	 
  int n3=n_inter;//存储链表t整数部分位数
	 
  int n4=n_small;//存储链表t小数部分位数
      
  if(n2!=0)
     
	  r= deletpoint(r);//删除小数点操作
     
  if(n4!=0)
	 
	  t=   deletpoint(t);//删除小数点操作
	 
  if((n1+n2)>=(n3+n4))//判断两个大数的位数大小大者做被乘数
	  {
	  p=r; q=t;
	  }
	  
  else{
	     p=t;q=r;
	  }
	  
  int j=0;
	 
  n=n2+n4; 
		   
while(q->ahead!=NULL)//外层循环用来控制乘数次数循环次数由乘数位数决定
{
	j++;//控制移位次数
	   
	if(j==1)
{
		p1=  big_numMUL1(p,q->data);//生成第j趟乘法链
		
		q=q->ahead; 
	   
	   if(q->ahead==NULL)
		   
		   break;	   
	   
	   }
if(q!=NULL){
			 
	p2=  big_numMUL1(p,q->data);//生成第j+1趟乘法链
		  
	p2=	MULmoveleft(p2,j,0);//乘法移位操作,p3为尾节点
		 
	p1= big_numADD(p1,p2 , 1);//大数加法具体操作
	
	q=q->ahead;
			 }
		
	   }  
	    
	  addpoint(p1,n);//乘除法增加小数点操作
	   
	  return p1;

 }

big_numnode * bignum_operation::linklist_length(big_numnode * rear)//用于大数整数部分和小数部分长度 
{

	int  j=0;

	n_inter=0;n_small=0;

	big_numnode *q=rear;

while(q->ahead!=NULL)
 {
  
	n_inter++;
  
	if(q->data=='.')
  {
		n_small= n_inter-1;
   
		n_inter=0;
  }  
  
	q=q->ahead;
  
  }
return q;
}




bool  bignum_operation::bignum_check(char str)// 大数数字字符合法性检查
 {
      
	 if((str-'0')>=0&&(str-'0'<=9))
	 {	 
		 i++;
	     
		 return 1;
	 }
	 else  if(i==0&&(str=='+'||str=='-') )
     	 
		 return 1;
       else if (i!=0&&(str='E'||str=='e'))
           
		   return 1; 

        else  return 0;

 
 
 }

 big_numnode * bignum_operation:: creatlinklist( char a[])// 创建双向链表
{
	  
		big_numnode * head;
		
		int i=0;
        
		head=new  big_numnode;//头结点
		
		head->data='0';
		
		head->ahead=head->next=NULL;
		
		big_numnode * rear,*q,*p;  //  尾结点
        
        p=q=head;
	
				while(a[i]!='\0' )  
						{
								p=new  big_numnode;
								if(a[i]!=32)
								p->data=a[i];
								p->ahead=p->next=NULL;
								q->next=p;
								p->ahead=q;
								 q=p;
								p=p->next;
								i++;
						}
                rear=q;
        

return rear;//返回尾指针

}

 
 
 int bignum_operation::  big_numCOMPARE(big_numnode * rear1,big_numnode * rear2)//大数绝对值的比较
 { 
          //如果 rear1大于rear2,就反回1，否则返回0
  big_numnode *q,*p,*q1,*p1;  //  两个链表的尾结点
  
  int  i1=0;
  
  int  i2=0;
  
  q1=q= rear1;
  
  p1=p= rear2;
  
  rear1->next=NULL;

  rear2->next=NULL;
  
  while(q1->ahead)//
	  
	  q1=q1->ahead;
while(p1->ahead)//得到头节点
	  
p1=p1->ahead;

linklist_length(q);//用于计算大数整数部分和小数部分长度

i1=n_inter;

linklist_length( p);//用于计算大数整数部分和小数部分长度

i2=n_inter;
if(i1>i2)//rear1 链表的整数部分大于rear2上的整数部分位数

return 1;

else if(i1<i2)  return 0;

else if(i1==i2) {

	q1=q1->next;

	p1=p1->next;
while(q1!=NULL)
{

	if((q1->data-'0')>(p1->data-'0'))

		return 1;
else  if((q1->data-'0')<(p1->data-'0'))
        
 return 0;

else  {  
	q1=q1->next;
            
	p1=p1->next;

if(q1==NULL)//表示两个数相等

return 1;

}
}


}


}
 void bignum_operation:: linklist_print(big_numnode * head)//链表的输出函数，参数head为头部指针
 { 
	 big_numnode *p;
	 p=head;
	 while(p!=NULL)
	{  
		 cout<<p->data;
		p=p->next;
	}
	 
 
 }



 
big_numnode *bignum_operation::big_numnodeinsert(big_numnode * p,int i,int n, char c)//结点插入操作 
{
/*i=0,表示向前插入，i=1表示向后插入，n 控制插入的结点个数，p 是尾结点*/
//p传入参数是尾节点，返回值也是尾节点
	big_numnode  *rear,*p1,*h;
       rear=p; 
	  
	   
	   if(n>0&&i==1)//尾插
{
	for(int j=0;j<n;j++)
	{
	p1=new  big_numnode;
	p1->data=c;
     p1->ahead=p1->next=NULL;
	 p->next=p1;
	 p1->ahead=p;
	 p=p->next;
	} 
rear= p1;
}

if(n>0&&i==0)
{
	int j=0;
	while(p->ahead!=NULL)//向前搜索到头节点
	{p=p->ahead;
	}
     h=p->next;//h 记录头节点后的节点	
	while(j<n)
	{
	p1=new  big_numnode;
	p1->data=c;
     p1->ahead=p1->next=NULL;
	 p1->next=h;
     h->ahead=p1;
	 p->next=p1;
	 p1->ahead=p;
	 h=h->ahead;
	j++;
	}

}
return rear;

}


big_numnode *bignum_operation::big_numADD(big_numnode *rear1,big_numnode *rear2, int op)//大数加法具体操作
{//乘法时不考虑小数点，按位加,rear2 长度大于rear1
big_numnode *p1,*p2;
     int s=0;
	 int c=0;
    	p1=rear2;
    	 p2=rear1;//初始化
//if(op==1)//加法标志
//{
	
	while((p1->ahead!=NULL)&&(p2->ahead!=NULL))
	{
		
			s=   (p1->data-'0'+p2->data -'0'+c)%10;
		c=(p1->data -'0'+p2->data -'0'+c)/10;
		p1->data=s+'0'; //本位数值
		p2->data=s+'0';
		p1=p1->ahead;  p2=p2->ahead; //链表指针向前移动

		
		}


	if(c==0)
	{
	if(p1->ahead!=NULL)
	{		free(rear1);
			return  rear2;
	}
	if(p2->ahead!=NULL){