超大整数运算库含除法优化CC++

#include<string.h> #include <malloc.h> //将一个字符串改造成superInt char* superInt(char*a) { char *p; if(a[0]!='+'&&a[0]!='-')//如果字符串没有自带的符号 { p=(char*)malloc(strlen(a)+2); p[0]='+'; strcpy(p+1,a);//将a字符串拷贝到p+1 } else { p=(char*)malloc(strlen(a)+1); strcpy(p,a); } return p; } //求a的绝对值 //返回+a的数值 char* superIntabs(char*a) { char*p; if(a[0]=='+') { p=(char*)malloc(strlen(a)+1); strcpy(p,a); } else { p=(char*)malloc(strlen(a)+2); p[0]='+'; strcpy(p+1,a); } return p; } //比较两个整数的大小 //a>b 返回1；a=b返回0；a<b返回-1 int superIntcmp(char* a,char* b) { //首先比较正负 ：正数 >负数 if(a[0]<b[0])//'+'号的ASCII值为43，'-'的为45 { return 1; } else if(a[0]>b[0]) { return -1; } else//符号相同 { int aLen=strlen(a),bLen=strlen(b); if(a[0]=='+')//正数情况 { if(aLen>bLen)return 1; else if(aLen<bLen) return -1; else return strcmp(a+1,b+1); } else { if(aLen>bLen)return -1; else if(aLen<bLen)return 1; else return -1*strcmp(a+1,b+1); } } } //不带符号的正整数的比较 int superPosiIntcmp(char*a,char*b) { int aLen=strlen(a),bLen=strlen(b); if(aLen>bLen)return 1; else if(aLen<bLen) return -1; else return strcmp(a,b); } //超级大整数的加法 char* superIntadd(char*a,char*b) { char* p;//存放两数的和 char* temptr;//临时指针 if((a[0]=='+'&&b[0]=='+')||(a[0]=='-'&&b[0]=='-'))//两个树的符号相同 { temptr=superPosiIntadd(a+1,b+1); p=(char*)malloc(strlen(temptr)+2); if(a[0]=='+'&&b[0]=='+')//都为+ { p[0]='+'; } else//都为负数 { p[0]='-'; } strcpy(p+1,temptr); } else //两数的符号不相同 { if(b[0]=='+')//若b为正，交换。这样做是节省代码的方法 { char* ap=a;a=b;b=ap; } //若a为正数b为负数意味着a-(-b) if(a[0]=='+') { //得到b的绝对值babs char* babs=superIntabs(b); int abigflag=superIntcmp(a,babs); if(abigflag) { temptr=superPosiIntsub(a+1,babs+1); p=(char*)malloc(strlen(temptr)+2); if(abigflag>0) p[0]='+'; else p[0]='-'; strcpy(p+1,temptr); } else//a和babs相等，则返回0 { p=(char*)malloc(3); p[0]='+'; p[1]='0'; p[2]='\0'; } } } return p; } //不带符号的正整数的加法 char* superPosiIntadd(char*a,char*b) { char*p;//存放两数的和 int pLen=0; if(superPosiIntcmp(a,b)<0)//如果b>a，则交换， { char*temp=a;a=b;b=temp; } int aLen=strlen(a),bLen=strlen(b); p=(char*)malloc(aLen+2); char c=0;//进位 char h=0;//暂存 int i; for( i=0;i<bLen;i++)//for1 { h=a[aLen-i-1]-'0'+b[bLen-i-1]-'0'+c; if(h>9)//和大于9时进位处理 { h=h-10;c=1; } else c=0;//没有进位 p[aLen-i]=h+'0';//还原为字符存入p中 }//for1 //处理a的高位部分 for(i=bLen;i<aLen;i++)//for2 { h=a[aLen-i-1]-'0'+c; if(h>9) { h=h-10;c=1; } else c=0; p[aLen-i]=h+'0'; } if(c>0)//如果还有进位 { p[0]=c+'0'; p[aLen+1]='\0'; return p; } else { p[aLen+1]='\0'; return p+1; } } //超级大整数减法 char* superIntsub(char*a,char*b) { char* p=NULL;//结果指针 char* temptr=NULL;//临时 if ((a[0]=='+'&&b[0]=='+')||(a[0]=='-'&&b[0]=='-'))//两数的符号相同 1 { temptr=superPosiIntsub(a+1,b+1);//数值部分先做减法 p=(char*)malloc(strlen(temptr+2)); if (superIntcmp(a,b)>=0)//a>b { p[0]='+'; } else//a<b { p[0]='-'; } } //1 else//ab的符号不相同 { temptr=superPosiIntadd(a+1,b+1); p=(char*)malloc(strlen(temptr)+2); if (a[0]=='+') { p[0]='+'; } else { p[0]='-'; } } /////////// strcpy(p+1,temptr);//拼接数值部分 return p; } //不带符号的正整数减法 char* superPosiIntsub(char*a,char*b) { char*p;//存储结果的 int pLen=0; if(superPosiIntcmp(a,b)==0)//a,b相等 { p=(char*)malloc(2); p[0]='0'; p[1]='\0'; } else//1 { if(superPosiIntcmp(a,b)<0)//如果b>a，则交换， { char*temp=a;a=b;b=temp; } //保证a>=b int aLen=strlen(a),bLen=strlen(b); p=(char*)malloc(aLen+1); char c=0;//c是借位 char h=0;//临时存放 int i; for(i=0;i<bLen;i++) { h=a[aLen-i-1]-b[bLen-i-1]-c; if(h<0)//小于0，向高位借位 { h=h+10;c=1; } else { c=0; } p[aLen-i-1]=h+'0'; } //拼接a的剩余部分 for(i=bLen;i<aLen;i++) { h=a[aLen-i-1]-'0'-c; if(h<0) { h=h+10; c=1; } else { c=0; } p[aLen-i-1]=h+'0'; } p[aLen]='\0'; }//1 if(p[0]=='0')++p; return p; } //带符号的整数乘法 char* superIntmut(char*a,char*b) { char*p;//存放结果 char*temptr; temptr=superPosiIntmut(a+1,b+1);//数值乘法 p=(char*)malloc(strlen(temptr)+2); if(a[0]==b[0]) { p[0]='+'; } else { p[0]='-'; } strcpy(p+1,temptr); //拼接 return p; } /////不带符号的正整数乘法 char* superPosiIntmut(char*a,char*b) { char *p; int pLen=0; int aLen=strlen(a); int bLen=strlen(b); p=(char*)malloc(aLen+bLen); int i,j; //先初始化p为0000000000..... for (i=0;i<aLen+bLen-1;i++) { p[i]='0'; } p[i]='\0'; int c=0;//进位 char h=0; for(i=aLen-1;i>=0;i--) { c=0; for(j=bLen-1;j>=0;j--) { pLen=i+j; h=(a[i]-'0')*(b[j]-'0')+p[pLen]-'0'+c; c=h/10; h=h%10; p[pLen]=h+'0'; } if(c>0)p[i+j]=c+'0'; } return p; } //除法 char* superIntdiv(char*a,char*b) { char*p;// char*temptr; temptr=superPosiIntdiv(a+1,b+1); p=(char*)malloc(strlen(temptr)+2); if(a[0]==b[0]) { p[0]='+'; } else { p[0]='-'; } strcpy(p+1,temptr); //拼接 return p; } char* superPosiIntdiv(char*a,char*b) {/*两个超大整数不能直接相除，但可以用减法来实现除法运算， 具体做法是用除数去减被除数，每减一次，商加1，判别被除数是否小于除数， 如果小于除数，则算法终止，被除数中存放的就是两数