bignum.h

大数运算的设计与实现

		
		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);//乘除法增加小数点操作
	  
	 while(p1->ahead->ahead)
		  
		 p1=p1->ahead;
	  
	 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;
}



 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'>=0)&&( a[i]-'0'<=9)&&( a[i]!='/0')|| a[i]=='.')  
		{
			p=new  big_numnode;
			
			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;


  }



 }
 

 
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){
	
			free(rear2); return rear1;
			}
}
if(c!=0)
{

	if(p1->ahead!=NULL)
{
		s=   (p1->data-'0'+c)%10;
	
		c=(p1->data -'0'+c)/10;

		p1->data=s+'0';
  
		if(c!=0)
	
			p1=big_numnodeinsert(rear2,0,1 ,'0'+c);//结点插入操作p1为接收到的尾结点
	
		free(rear1);
		return rear2;
}

else if(p2->ahead!=NULL)
{
	s=(p2->data-'0'+c)%10;
	
	c=(p2->data -'0'+c)/10;
    
	p2->data=s+'0';
	
	if(c!=0)
		
		p1=big_numnodeinsert(rear1,0,1 ,'0'+c);//结点插入操作p1为接收到的尾结点
	
	free(rear2);
    
	return rear1;
}

else 
{
	p1=big_numnodeinsert(p1,0,1 ,'0'+c);//结点插入操作p1为接收到的尾结点

	free(rear1);

	return rear2;
}

}

}


}


 big_numnode *bignum_operation::big_numADD(big_numnode *rear1,big_numnode *rear2, int n1,int n2,int n3,int n4,int op)//大数加法具体操作 
 {/*i=0,表示向前插入，i=1表示向后插入，n 控制插入的结点个数, op 标志是加法还是减法:0 减法，1是加法*/
	big_numnode *p,*p1,*p2;
     
	int s=0;
	 
	int c=0;
	 
	p1=rear1;
	 
	p2=rear2;//初始化
	 sign=	big_numCOMPARE(rear1, rear2);//大数绝对值的比较
	  
	 if(n1<n3)
	 {
		  p=rear1;
	 
		  p1=big_numnodeinsert(p,0,n3-n1,'0');//结点插入操作p1为接收到的尾结点
	 } 
	if(n1>n3)
		 {	
		p=rear2;

		p1=big_numnodeinsert(p,0,n1-n3,'0');//结点插入操作p1为接收到的尾结点
	
		p2=rear1;
	
	}


	 if(n2<n4)
	 {


		 p=rear1;


		 p2=big_numnodeinsert(p,1,n4-n2 ,'0');//结点插入操作p1为接收到的尾结点
	 }
if(n2>n4)
{
	p=rear2;
	 
	p1=big_numnodeinsert(p,1,n2-n4,'0');//结点插入操作p1为接收到的尾结点

	p2=rear1;	 
}
if(op==1)//加法标志
{
	
	while((p1->ahead!=NULL)&&(p2->ahead!=NULL))
	{
		if(p1->data!='.'&&p2->data!='.')
		{	
			s=   (p1->data-'0'+p2->data -'0'+c)%10;
		
			c=(p1->data -'0'+p2->data -'0'+c)/10;
		
			p1->data=s+'0'; //本位数值
		}
		
		p1=p1->ahead;  
		p2=p2->ahead; //链表指针向前移动

		
		}

if(c!=0)//表示最高位有进位位
{
	p1=big_numnodeinsert(p,0,1 ,'0'+c);//结点插入操作p1为接收到的尾结点
}
}
if(op==0)
{// 减法标志
   c=0;
   s=0;
if(sign==1)
	 {p1=rear1;
	 p2=rear2;//初始化
	 }
   if(sign==0)
	 {p2=rear1;
	 p1=rear2;//初始化
   }
while((p1->ahead!=NULL)&&(p2->ahead!=NULL))
	{
		if(p1->data!='.'&&p2->data!='.')
		{	
		      if(p1->data>=p2->data)	
			  {
			s=   p1->data-p2->data ;
	
		p1->data=s+'0'; //本位数值
			  c=0;
			  }
		
			  else {
				 
			  s=   p1->data+10 -p2->data ;
              c=-1;
	
		p1->data=s+'0'; //本位数值
			  
			  }
	
	  
	}

         p1=p1->ahead;  p2=p2->ahead; //链表指针向前移动
	     if(c!=0)
			
			 p1->data=p1->data-1;}
	

}

if(sign==0&&op==0)
{
 p1->data='-';//判断是否是负数,若是则符号存储在头节点	
return p1;
}
else
return p1->next;


/////////////////////////////


}
 
   big_numnode * bignum_operation::big_numADD(char a[],char b[])//大数加法
{
      big_numnode *r,*t;  //  存储创建的两个链表的尾结点
     
	  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小数部分位数
	  
	  r= big_numADD(r,t,  n1, n2, n3, n4 ,1);//大数加函数 返回链表头部指针
	
	  return r;
}
big_numnode *bignum_operation::big_numSUB(big_numnode *r ,big_numnode *t )//大数减法
 {
      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小数部分位数  
   
	  sign=	big_numCOMPARE(r, t);//大数绝对值的比较

r= big_numADD(r,t,  n1, n2, n3, n4 ,0);//大数减法函数 返回链表指针

 while(r->next!=NULL)
	{ r=r->next;
	}

return r;
 
 }








big_numnode *bignum_operation::big_numSUB(char a[],char b[])//大数减法
 {
   big_numnode *r,*t;  //  存储创建的两个链表的尾结点
      
   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小数部分位数  
      
   sign=	big_numCOMPARE(r, t);//大数绝对值的比较


   r= big_numADD(r,t,  n1, n2, n3, n4 ,0);//大数加函数 返回链表指针

	return r;
 
 }