霜之哀伤

最近在公司闲得无聊,正好一朋友叫我帮他写个大数相加,大数相乘函数,说是某公司程序员初试题,个人对C熟悉点,所以用C写这两个函数,考虑过许多算法,如算大数相加可把大数拆成若干个整型数用链表连起来,然后从后向前相加进位,但我感觉这样运算效率并不会提高多少,相反写起程序来更麻烦,所以我用人们笔算的方法写.
大数相加就是从个位开始一位位往前加.
大数相乘就是把其中一个大数一位位和另一个数相乘累加.
就是我们在草稿纸上笔算的方法了,注释我写的很多了,具体实现处法请看下面代码.

#include "stdio.h"
#include "string.h"
#include "stdlib.h"

/*判断字符串是否全是数字(返回是否合法)*/
char IsLegalData(char *strData)
{
   int i;
   int lenData;
   char ret = 1;    /*默认参数合法*/
   
   lenData = strlen(strData);
   if ( lenData < 1 )
   {
       ret = 0;    /*空字符串*/
   }

   if ( ret == 1 )
   {
       for (i=0; i<lenData-2; i++)
       {
           if ( (strData < 0x30) || (strData > 0x39) )
           {
               ret = 0;    /*字符串中有的不是数字，不合法*/
               break;
           }
       }
   }

   return ret;
}

/*给字符数组赋值*/
void SetChaArr(char *arr, char x, int lenArr)
{
   int i;
   
   for (i=0; i<lenArr; i++)
   {
       arr = x;
   }
}

/*去掉字符串大数前面的0*/
void RemovePreZero(char *strData)
{
   int i, j;
   int lenData;

   lenData = strlen(strData);    /*长度*/
   j = 0;
   for (i=0; i<lenData; i++)
   {
       if ( strData == 0x30 )
       {
           j += 1;    /*累计0的个数*/
       }
       else
       {
           break;    /*非零则跳出*/
       }
   }
   
   /*向前移位*/
   if ( j == lenData )
   {
       /*全0,则只给一个0*/
       strData[0] = 0x30;
       strData[1] = '\0';
   }
   else
   {
       if ( j > 0 )
       {
           /*前面有0移位*/
           for (i=0; i<lenData-j; i++)
           {
               strData = strData[i+j];
           }
           strData = '\0';
       }
   }
}

/*两个字符数字相加(返回是否进位)*/
int AddBigDataSub(char cx, char cy, int isCarry, char *sum)
{
   int ret = 0;

   *sum = cx + cy + isCarry - 0x30;    /*相加*/
   if ( *sum > 0x39 )
   {
       *sum -= 10;        /*大于9则进位减10*/
       ret = 1;        /*有进位*/
   }

   return ret;
}

/*从字符串中取字符*/
char GetChaFromStr(char *strData, int index)
{
   char ret;

   if ( index < 0 )
   {
       ret = 0x30;
   }
   else
   {
       ret = strData[index];
   }

   return ret;
}

/*两大数相加函数*/
char* AddBigData(char *strA, char *strB)
{
   int lenA, lenB, lenMax;
   int i, j, k;
   char legalFlag = 0;        /*默认参数不合法*/
   char *ret = NULL;

   /*参数合法性判断*/
   if ( IsLegalData(strA) )
   {
       legalFlag = IsLegalData(strB);
   }

   if ( legalFlag )
   {
       /********参数合法*******/
       /*去掉大数前面多余的0,减少程序运算次数*/
       RemovePreZero(strA);
       RemovePreZero(strB);

       /*两字符串长度*/
       lenA = strlen(strA);
       lenB = strlen(strB);
       
       /*分配空间*/
       lenMax = (lenA>lenB)?(lenA + 2):(lenB + 2);
       ret = (char *)malloc(lenMax*sizeof(char));
       SetChaArr(ret, 0x30, lenMax);    /*全部给字符'0'*/
       ret[lenMax-1] = '\0';    /*最后一位给结束符*/
       
       /*从个位开始往高位相加*/
       k = lenMax - 2;
       lenA -= 1;
       lenB -= 1;
       i = (lenA>lenB)?lenA:lenB;
       j = 0;
       for (; i>=0; i--)
       {
           j = AddBigDataSub(GetChaFromStr(strA, lenA--), GetChaFromStr(strB, lenB--), j, &ret[k--]);
       }
       if ( j == 1 )
       {
           ret[k] += 1;    /*处理最高位相加后还进位*/
       }
       else
       {
           /*不进位则前移字符串*/
           for (i=0; i<lenMax-1; i++)
           {
               ret = ret[i+1];
           }
       }
   }
   else
   {
       /*参数不合法,返回空字符串*/
       ret = NULL;
   }

   return ret;
}

/*两个字符数字相乘*/
int MultiTwoCha(char cx, char cy, int carry, char *multi)
{
   int ret = 0;

   *multi = (cx - 0x30) * (cy - 0x30) + carry;    /*相乘结果*/
   if ( *multi > 9 )
   {
       ret = *multi / 10;    /*十位数为进位*/
       *multi = (*multi % 10) + 0x30;    /*个位数为此位结果*/
   }
   else
   {
       *multi += 0x30;
   }

   return ret;
}

/*大数相乘子过程(返回大数与另一个大数中一个字符相乘后生成的字符串)*/
/*index从乘数个位起到高位从0计数(如:个位=0,十位=1,百位=2....)*/
char *MultiBigDataSub(char *strData, char cy, int index)
{
   char *ret = NULL;
   int lenMax = 0;
   int i, j, k;

   /*依次相乘组合字符串*/
   if ( cy == 0x30 )
   {
       ret = NULL;        /*乘0返回空*/
   }
   else
   {
       /*相乘后最大长度*/
       i = strlen(strData);
       lenMax = i + 2 + index;

       /*分配空间*/
       ret = (char *)malloc(lenMax*sizeof(char));
       SetChaArr(ret, 0x30, lenMax);    /*全部给字符'0'*/
       ret[lenMax-1] = '\0';    /*最后一位给结束符*/

       /*依次相乘组合字符串*/
       j = 0;
       k = lenMax - 2 - index;
       for (i=i-1; i>=0; i--)
       {
           j = MultiTwoCha(strData, cy, j, &ret[k--]);
       }
       if ( j > 0 )
       {
           ret[k] = j + 0x30;    /*处理最前面字节相乘有进位*/
       }
       else
       {
           for (i=0; i<lenMax-1; i++)
           {
               ret = ret[i+1];
           }
       }
   }

   return ret;
}

/*两大数相乘函数*/
char* MultiBigData(char *strA, char *strB)
{
   int lenA, lenB, lenMax;
   int i, j, k;
   char legalFlag = 0;        /*默认参数不合法*/
   char *ret = NULL;
   char *strTmp = NULL;
   char init[] = "0";

   /*参数合法性判断*/
   if ( IsLegalData(strA) )
   {
       legalFlag = IsLegalData(strB);
   }

   if ( legalFlag )
   {
       /********参数合法*******/
       /*去掉大数前面多余的0,减少程序运算次数*/
       RemovePreZero(strA);
       RemovePreZero(strB);

       /*两字符串长度*/
       lenA = strlen(strA);
       lenB = strlen(strB);
       
       ret = init;
       if ( lenA > lenB )    /*减少运算次数，加个判断*/
       {
           for (i=lenB-1; i>=0; i--)
           {
               strTmp = MultiBigDataSub(strA, strB, lenB-1-i);
               if ( strTmp != NULL )
               {
                   ret = AddBigData(ret, strTmp);    /*每次累加*/
                   free(strTmp);    /*释放中间分配的空间*/
               }
           }
       }
       else
       {
           for (i=lenA-1; i>=0; i--)
           {
               strTmp = MultiBigDataSub(strB, strA, lenA-1-i);
               if ( strTmp != NULL)
               {
                   ret = AddBigData(ret, strTmp);
                   free(strTmp);
               }
           }
       }
   }
   else
   {
       /*参数不合法,返回空字符串*/
       printf("参数不合法！\n");
       ret = NULL;
   }

   return ret;
}


void main()
{
   char a[] = "4312505034431493253543514231423140903293414";
   char b[] = "3214321432535343124321423143243534534321441";
   char *sum = NULL;
   char *mul = NULL;

   sum = AddBigData(a, b);
   printf("\n************************************************\n");
   printf("%s\n\t+\n%s\n", a, b);
   printf("= %s\n", sum);
   printf("\n************************************************\n");
   free(sum);

   printf("\n\n");

   mul = MultiBigData(a, b);
   printf("\n************************************************\n");
   printf("%s\n\t*\n%s\n", a, b);
   printf("=%s\n", mul);
   printf("\n************************************************\n");
   free(mul);
}


我在vc6.0下调试成功,调试时间不长,如还存在BUG,请留言或通知本人
QQ: 136314890 MSN: sxwz2007@hotmail.com