bignum.h

大数运算的设计与实现

big_numnode *bignum_operation::functionchoice(char a[],char b[],char f)
{
		big_numnode * t=NULL;
		
		big_numnode *r;
		
	

switch(f){
           if(f=='O'||f=='B'||f=='X'||f=='C')//大小写转换
				f=f-'32';

	case '+':
	          t=big_numADD( a, b);//大数加法
			  
			  break;
	case '-':
			
				t=big_numSUB( a, b);//大数减法

		
				break;
	case '*':
		
				t=big_numMUL( a, b);//大数乘法
				while(t->ahead->ahead)t=t->ahead;
		
				break;	
	case '/':
		
				t=big_numDEVIDE( a, b);//大数除法
				while(t->ahead->ahead){t=t->ahead;}
		
  				break;	
	case '!':
				pa= factorial.factorialcomputer(a,1);
				//阶乘运算函数
				
				break;	
	case 'b'://二进制转换
		
	t=	big_numENCHANGE( a, f );
	
	break;

case 'x'://十六进制转换
	
	t=	big_numENCHANGE( a, f );
	
	break;

case 'o'://八进制转换
		
	
	t=	big_numENCHANGE( a, f );
	
	break;
	    
case '^':
		
		t=big_numPOWER( a, b);//大数乘方
		while(t->ahead->ahead)t=t->ahead;
			
		break;
case 'c'://排列组合
	
	t=arrange.arrangecomputer(a, b);//排列组合的实现
	while(t->ahead){
			t=t->ahead;
		if(t->next->data=='.')t->next=NULL;

		
		}
       
		
		t=t->next;
       
		break;
case '&'://比较大小
		
	
      //  存储创建的两个链表的尾结点
      r=creatlinklist(a);// 创建双向链表
      t=creatlinklist(b);// 创建双向链
   k=big_numCOMPARE(r,t);//大数绝对值的比较
        if(k==1)
       
			AfxMessageBox("操作数1大于操作数2");	
			
		
		else 
		AfxMessageBox("操作数1小于操作数2");	
			
		
		break;
	    


default:
		
	AfxMessageBox("！输入表达式错误！");
	exit(0);

;




}


return t;

}
 

 big_numnode * bignum_operation::deletezero(  big_numnode * r)
{//删除链表头节点到第一个非零节点间的零，i=0 时r是尾指针,i=1时r 是头节点
   big_numnode * p,*q,*s;
   p=r;
   
   while(p->ahead!=NULL){
       q=p;
	   p=p->ahead;
     }//找到头节点
  
   
   while(q->data=='0'&&q->next!=NULL){
   p->next=q->next;
   q->next->ahead=p;
   s=q;
   q=q->next;
   free(s);
   }
   
   
   
   
   return r;

 }
 big_numnode * bignum_operation:: getlinknode( big_numnode * r,int n)
 {//得到链表某个节点，r 是尾指针，从后向前遍历，n 是走的节点数
 big_numnode * p;
 p=r;
 int i=0;
 while(i<n){
	 p=p->ahead;
	 i++;
 }
 
 return p;
}
int bignum_operation::isZERO(big_numnode *r)//用于除法运算时除数是否为零判断
 {//r 是尾指针，是零返回 0，否则返回 非零
big_numnode *p;
int i=0;
p=r;
while(p->ahead!=NULL){
	if(p->data=='0'||p->data=='.')p=p->ahead;
	else {
		i++;
		return  i ;}


}
return  i ;
}

big_numnode *bignum_operation:: big_numDEVIDE(big_numnode *r,big_numnode *t)//大数除法
{
big_numnode *p,*q,*r1,*r2,*r3;  //  存储创建的两个链表的尾结点
   int n=0; int i=0;//记录移位次数
   int j=0;
   int m=0;
   
   char c;
   linklist_length( r);//返回r的头指针
   int n1=n_inter;//存储链表r整数部分位数
   int n2=n_small;//存储链表r小数部分位数
   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);//大数绝对值的比较
	 
         r1=getlinknode(r,m-n);
		 r2=r1->next;
         q=r1;
         q->next=NULL;
while(r3!=NULL)//控制总的循环次数
{
 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++; 

          yushu=q;

}
         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;