bignum.h

大数运算的设计与实现

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include <conio.h>
#include <math.h>
#include "time.h"
#include <iomanip.h>
#include <fstream.h>
#define maxlength 99999
ofstream out_stream;
ifstream in_stream;
double duration;
clock_t start, finish;//用于计算时间

 typedef struct Node    // 定义一个双向链表用来存贮结果
{
char data;     // 数据定义为字符的原因：要显示负号
Node *next;    // 尾指针
Node *ahead;   // 首指针
}big_numnode;

 class bignum_operation{
 
 private:         
				       int i;//变量用于合法性检查时的标识数位 
				       int n_inter,n_small;//用于求大数整数位数和小数位数
	                   int sign;//在大数比较时标志大数的大小
			           int  n_smallpoint;//当不能整除时设置保留小数点后的尾数
                       big_numnode *yushu;
 public:	char *pa;
 			int k;

 public:  
	        
	 big_numnode *  creatlinklist( char a[]);// 创建双向链表用来存储大数
          	   
	 big_numnode *  big_numADD(char a[],char b[]);//大数加法
	 
	 big_numnode * big_numADD(big_numnode *rear1,big_numnode *rear2, int n1,int n2,int n3,int n4,int op);//大数加法具体操作 
           
	 big_numnode *big_numADD(big_numnode *rear1,big_numnode *rear2, int op);//大数加法具体操作
			  
	 big_numnode * big_numSUB(char  str[],char str2[]);//大数减法
	 
	 big_numnode *big_numSUB(big_numnode *r ,big_numnode *t );//大数减法
	 
	 big_numnode * big_numMUL(char  str[],char str2[]);//大数乘法
      	 
	 big_numnode *  big_numMUL( big_numnode *r, big_numnode *t);//大数乘法
	
	 big_numnode *  bignum_operation::big_numMUL1(big_numnode * r,char b);//大数乘法数
	 
	 big_numnode * big_numDEVIDE(char  str[],char str2[]);//大数除法
	 
	 big_numnode * linklist_length(big_numnode * rear);//用于求连表长度 
			  
	 int isZERO(big_numnode *r);//用于除法运算时除数是否为零判断
		
	 big_numnode *MULmoveleft(big_numnode *rear,int n,int f);//乘法移位操作
		
	 big_numnode *bignum_operation::big_numnodeinsert(big_numnode * p,int i,int n, char c );//结点插入操作 

	 int big_numCOMPARE(big_numnode * rear1,big_numnode * rear2);//大数绝对值的比较
              	  
	 big_numnode *deletpoint(big_numnode *p);//删除小数点操作
			
	 big_numnode *addpoint(big_numnode *r,int i);//乘除法增加小数点操作

	 big_numnode * getlinknode( big_numnode * r,int n);//得到链表某个节点
			  
	 big_numnode * deletezero(  big_numnode * r);//删除链表头节点到第一个非零节点间的零


	 big_numnode * big_numENCHANGE(char a[],char f );//大数进制转换函数
     
	 big_numnode * big_numDEVIDE( big_numnode *rear1, big_numnode *rear2);//大数除法

	 big_numnode *functionchoice(char a[],char b[],char f);//根据操作符号选择运算函数

	 big_numnode *big_numPOWER(char a[],char b[]);//大数乘方运算
	 
		 bignum_operation();//构造函数
               
	 ~bignum_operation();//析构函数
 
 } bignum_operation ;




   /**///////////////////////////////////////////////////////////////////////////
      
     //factorial类
  //  Purpose:         计算n!的值
  /**///////////////////////////////////////////////////////////////////////////
  
   
   
 class factorial{
                 public:

                   int GetNumber(char a[]);                                   //输入 n 
                   int GetBitLength(int n);                           //求n!的位数
                   char* Initialize(int);                             //初始化存储结果的值
                   void PrintValue(char *a,int size,char* fileName);  //打印值到文件
                   char* GetValue(int val);                           //计算
                   char* SubGetValue(char* ,int);                      
				    factorial();
                    ~factorial();
				   char * factorialcomputer(char a[],int i);
				   void readFILE(char filename[],char *a3);//文件读取函数
				 public: 
						  int value;
					      int size;
						  char *pp;
						  char *pa;
						  char factorial_out[maxlength];
                     	  char fileName1[20];

 }factorial;

factorial::factorial()
{
size=0;
pp=NULL;
value=0;

}
factorial::~factorial()
{
delete []pp;
}
 
 


 //函数GetValue
 // 求得计算结果
 //返回结果
 
 //  参数:val 计算阶乘的值
 char* factorial::GetValue(int val)
 {
     //定义一个数组存储阶乘的值
    
     int VALUE=val; 
     int length=GetBitLength(VALUE);
     char *arrValue = new char[length]; 
    if(!arrValue) {
         cout <<"申请内存失败!" << endl; 
         exit(1); 
     } 
     arrValue[0] = 1; 
     for(int i=1; i<length; i++) 
         arrValue[i] = 0; 
     arrValue=SubGetValue(arrValue,VALUE);
     return arrValue;
 }
 
 char* factorial::SubGetValue(char* arrValue,int n)
 {
     int index=0;
     long carrier=0;
     double bitCount = 1; 
     int begin = 0; 
  
     for(index=2; index<=n; ++index) 
     { 
         long multiValue = 0;   
         bitCount += log10((long double)index); 
         if(arrValue[begin] == 0) 
             begin++; 
  
         for(int j=begin; j<int(bitCount); ++j) 
         { 
             multiValue += (index*arrValue[j]); 
             arrValue[j] = char(multiValue % 10); 
             multiValue /= 10; 
         } 
     } 
   return arrValue;
 }
 
 //得到计算阶乘的值,此函数为新增
int factorial::GetNumber(char a[]) 
 { 
	 
	 char ch=a[0];
  int i=0;
  int tokenval=0;
	while(-1<(ch-'0')&&(ch-'0')<10)
			{
				tokenval=tokenval*10+ch-'0';
					i++;
				ch=a[i];
		
	}
	 
    if(tokenval == 0)         exit(1); 
    return tokenval; 
} 

//函数GetBitLength
// 求得计算结果的位数,本函数为新增加
//参数
//     n 需要计算的阶乘的数
//返回结果的位数
int factorial::GetBitLength(int n) 
{ 
    double sum = 1.0; 
    for(int i=1; i<=n; i++) 
        sum += log10((long double)i);
  
	return int(sum); 
} 
//-----------
//函数:Initialize
//   初始化存储结果的数组
//参数:
//     size      数组的长度  
//返回值
//    初始化后的数组
//-------------
char * factorial::Initialize(int size) 
{ 
    char *arrValue = new char[size];
    if(!arrValue) {
        cout << size<<"太大,申请内存失败!" << endl; 
        exit(1); 
    } 
    arrValue[0] = 1; 
    for(int i=1; i<size; i++) 
        arrValue[i] = 0; 
    return arrValue; 
} 
  

//-----------
//函数:PrintValue
//   将结果输入到一个文件中
//参数:
//     buff      存储结果的数组
//   buffLen   数组的长度
//   fileName  文件名         
//-------------

void factorial::PrintValue(char *buff,int buffLen,char *fileName)
{
     FILE *fp=NULL;
    //-----------------------------

    if (fileName==NULL)        return ;
    fp=fopen(fileName,"wt");
   
	if (fp==NULL)
    {
        printf("不能创建文件%s",fileName);
        return ;
   }

   for(int i=buffLen-1; i>=0; i--)
    {
       fprintf(fp,"%d",int(buff[i]));
          
    }
    fprintf(fp,"\n");
    fclose(fp);
}

char* factorial::factorialcomputer(char a[],int i)
{// i=1 标志不用读到DOS界面直接存文件，i=0，读出并存文件
    
		value=GetNumber(a);
	
		char fileName[16];
		 
		size=GetBitLength(value);
		
		pa = Initialize(size);

		pa=GetValue(value);
 	
    	sprintf(fileName,"%d!.txt",value);	
	
		strcpy(fileName1,fileName);
		
		PrintValue(pa,size,fileName);
        
	readFILE( fileName1,factorial_out);//文件读取函数	
	//	factorial.factorial_out[i];函数输出接口
		return pa;


}
void factorial::readFILE(char filename[],char *a3)//文件读取函数	
{
	char  filenum;
	int j=0;
	
	in_stream.open( filename);
	
	if(in_stream.fail())
	 {
		cout<<filename<<" file open faild.\n";
  
	 }

	in_stream>>filenum;
while(!in_stream.eof())
{	
	a3[j]=filenum;
	j++;
	in_stream>>filenum;

}
	a3[j]='\0';
 
	in_stream.close();

}


class  arrange{
 public:    
            
	big_numnode *arrangecomputer(char a[],char b[]);
	readFILE(char filename[],char*);		
	arrange();	
	~arrange();	
 private:
	
  char h1[maxlength];
  char h2[maxlength];
  char h3[maxlength];
 }arrange;
 arrange::arrange()//构造函数
	{

	}
 arrange::~arrange()//析构函数
	{
	
	}

 arrange::readFILE(char filename[],char *a3)//文件读取函数	
{
	char  filenum;
	int j=0;
	
	in_stream.open( filename);
	
	if(in_stream.fail())
	 {
		cout<<filename<<" file open faild.\n";
  
	 }

	in_stream>>filenum;
while(!in_stream.eof())
{	
	a3[j]=filenum;
	j++;
	in_stream>>filenum;

}
	a3[j]='\0';
 
	in_stream.close();

}

big_numnode *arrange:: arrangecomputer(char a[],char b[])//排列组合的实现
 {
	char c[100];//存减数

	big_numnode *p;

	big_numnode *s=bignum_operation.big_numSUB( a, b);//大数减法	

	int k=0;
	if(s->data=='0'&&s->next!=NULL)
		s=s->next;
	
while(s){
		    c[k]=s->data;
			p=s;
			s=s->next;
		
			k++;
			free(p);
	}
		
		c[k]='\0';//得到排列组合计算时的做分母的减数
    

		
		char* a1=factorial.factorialcomputer(a,1);   //得到a的阶乘

	
	readFILE(factorial.fileName1,h1);

	char*b1=factorial.factorialcomputer(b,1);//得到b的阶乘

	readFILE(factorial.fileName1,h2);

	char*c1=factorial.factorialcomputer(c,1);//得到减数的阶乘
	


	readFILE(factorial.fileName1,h3);

	big_numnode *t=bignum_operation.big_numDEVIDE(h1,h2);//大数除法
	while(t->ahead->ahead)//找到头节点 
	t=t->ahead;
	k=0;
	while(t&&t->data!='.'){
		 
	h1[k]=t->data;//a2 此时用于存储第一次除得的商
		p=t;
		t=t->next;
		k++;
		
		free(p) ;
	}
	h1[k]='\0';

	t=bignum_operation.big_numDEVIDE(h1,h3);//大数除法

	return t;
 }






 bignum_operation:: bignum_operation()//构造函数
 {
		i=0;
		sign=0;
		n_inter=0;
		n_small=0;
   		 k=2;	
		 n_smallpoint=5;

 }
bignum_operation:: ~bignum_operation()//析构函数
 {


 } 
big_numnode *  bignum_operation::big_numMUL( big_numnode *r, big_numnode *t)//大数乘法
 {
 
 
  big_numnode *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);//大数加法具体操作
		//	free(p2);

		  q=q->ahead;
			 }
		
	   }  
	  addpoint(p1,n);//乘除法增加小数点操作
	  
	  return p1;
}


	big_numnode *bignum_operation::big_numPOWER(char a[],char b[])//大数乘方运算
    {
	
	big_numnode *r,*p;  //  存储创建的两个链表的尾结点
    int j=0; 
	p=r=creatlinklist(a);// 创建双向链表
  char ch=b[0];
  int i=0;
  int tokenval=0;
	while((ch-'0'>-1)&&(ch-'0')<10)
			{
				tokenval=tokenval*10+ch-'0';
					i++;
				ch=b[i];
		
			}
if(tokenval==0)
{p=creatlinklist("1");// 创建双向链表

return p;
}
	
	
	while(j<tokenval-1)
	{ p=big_numMUL(p,r);//大数乘法
	  j++;
	}
return p;
	
	}

big_numnode *bignum_operation::  big_numENCHANGE(char a[],char f)
{//进制转换函数，实现十进制到二，八，十六 进制的转换
	//a[n]是传入大数，f 是转换类型标志，b,o,x
           
		big_numnode *p,*q,*r;
		char c[5];
		int j=0;
		int k=0;
		if(f=='b'||f=='B')
		{
		strcpy(c,"2");
		}
		else if(f=='o'||f=='O')
		{
	    strcpy(c,"8");
		}
		else if(f=='X'||f=='x')
		{
		strcpy(c,"16");
		}
		else {
		cout<<"输入字符非法！！"<<endl;
			exit(0);
		
		}
          p=creatlinklist(a);// 创建双向链表
          r=creatlinklist(c);// 创建双向链表
		   q=new  big_numnode;//用于存储商的头结点
		  q->data='0';
		  q->ahead=q->next=NULL;
		  j=big_numCOMPARE(p,r);//大数绝对值的比较
          while(j==1)
		  { 
 	        p=big_numDEVIDE(  p, r);//大数除法取得整数部分商 
		 
			if(f=='x')
			if(yushu->ahead->ahead!=NULL)	
			{
			if(yushu->data=='0')
				yushu->data='A';
            if(yushu->data=='1')
				yushu->data='B';
            if(yushu->data=='2')
				yushu->data='c';
            if(yushu->data=='3')
				yushu->data='D';
			if(yushu->data=='4')
				yushu->data='E';
            if(yushu->data=='5')
				yushu->data='F';
			}	
            q=big_numnodeinsert(q,1,1, yushu->data);//从节点插入
		//	p=deletezero( p);//去掉头部多余零
		 //  r=deletezero(r);//去掉头部
           j=big_numCOMPARE(p,r);//大数绝对值的比较
		  
		  }
		   
	       q=big_numnodeinsert(q,1,1,p->data);//结点插入操作 
	       q=big_numnodeinsert(q,0,1,f);//结点插入操作 
	       return q;
}