刷題 | 計算任意長度整數之和

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

運行截圖：