刷题 | 计算任意长度整数之和

• 2022 年 9 月 12 日
• 筆記
• 代码, 基础算法, 数据结构

问题：

试设计一种表示任意长的整数（非负）的数据结构，计算任意给定的两个整数之和的算法。

算法思路：

1. 利用数组（顺序表）对整数进行存储，数组中的每一个元素存放一个数字，数组A和B分别存储两个整数；
2. 执行整数相加操作：
   • A和B低位对齐；
   • 从低位到高位对应位相加，和为cur_sum，将cur_sum%10存储到当前位，将cur_sum/10存储到高位；
   • 处理最高位，若最高位求和结果产生进位，需要将结果的所有元素均后移一位。

代码实现：

SeqList* add_op(SeqList *LA, SeqList *LB){
    /*
        1.LA和LB末尾对齐；
        2.逐元素相加；
        3.判断首位是否产生进位，若进位则需要先将各位后移一位.
    */ 
   //1.LA和LB末尾对齐；
   SeqList *Long, *Short;
   int margin, i, cur_sum;
   if(LA->length > LB->length){
    Long = LA;
    Short = LB;
   }else{
    Long = LB;
    Short = LA;
   }
   margin = Long->length - Short->length;
   for(i=Short->length-1;i>=0;i--){
    Short->list[i+margin] = Short->list[i];
   }
   //2.逐元素相加；
   for(i=Long->length-1;i>0;i--){
    int l = Long->list[i];
    int s = Short->list[i];
    cur_sum = Long->list[i] + Short->list[i];
    Long->list[i] = cur_sum % 10;
    Long->list[i-1] += cur_sum / 10;
   }
   //3.判断首位是否产生进位.
   cur_sum = Long->list[0] + Short->list[0];
   if(cur_sum / 10 == 0){
    Long->list[0] = cur_sum % 10;
   }else{
    for(i=Long->length-1;i>0;i--){
        Long->list[i+1] = Long->list[i];
    }
    Long->list[1] = cur_sum % 10;
    Long->list[0] = cur_sum / 10;
    Long->length += 1;
   }
   return Long;
}

运行截图：