リンクリストで表される 2 つの数値を加算します

ここでは、別々のリンク リストに格納されている 2 つの数値を加算する方法を見ていきます。リンクリストには、数値の各桁が格納されます。数値が 512 の場合、次のように保存されます -

512 = (5)-->(1)-->(2)-->NULL

このタイプのリストが 2 つ提供されており、私たちのタスクはそれらを追加し、合計を計算した結果を取得することです。ここではC STLリンクリストを使用します。賭けのためのより良いアイデアを得るためにアルゴリズムを見てみましょう。

アルゴリズム

addListNumbers(l1, l2)

Begin
   Adjust the l1 and l2 lengths by adding leading 0s with the smaller one
   carry := 0
   res := an empty list
   for each node n from l1, scan from last to first, do
      item := (l1.item + l2.item + carry) mod 10
      insert item at the beginning of res
      carry := (l1.item + l2.item + carry) / 10
   done
   if carry is not 0, then
      add carry at the beginning of res
   end if
   return res
End

例

#include<iostream>
#include<list>
using namespace std;
list addListNumbers(list<int> l1, list<int> l2){
   //add leading 0s to the shortest number to make them equal length
   if(l1.size() > l2.size()){
      for(int i = l2.size(); i != l1.size(); i++){
         l2.push_front(0);
      }
   }else if(l1.size() < l2.size()){
      for(int i = l1.size(); i != l2.size(); i++){
         l1.push_front(0);
      }
   }
   list<int>::reverse_iterator it1 = l1.rbegin();
   list<int>::reverse_iterator it2 = l2.rbegin();
   list<int> result;
   int carry = 0;
   while(it1 != l1.rend()){
      result.push_front((*it1 + *it2 + carry) % 10);
      carry = (*it1 + *it2 + carry) / 10;
      it1++; it2++;
   }
   if(carry != 0){
      result.push_front(carry);
   }
   return result;
}
list<int> numToList(int n){
   list<int> numList;
   while(n != 0){
      numList.push_front(n % 10);
      n /= 10;
   }
   return numList;
}
void displayListNum(list<int> numList){
   for(list<int>::iterator it = numList.begin(); it != numList.end();
   it++){
      cout<<*it;
   }
   cout << endl;
}
int main() {
   int n1 = 512;
   int n2 = 14578;
   list<int> n1_list = numToList(n1);
   list<int> n2_list = numToList(n2);
   list<int> res = addListNumbers(n1_list, n2_list);
   cout << "First number: "; displayListNum(n1_list);
   cout << "Second number: "; displayListNum(n2_list);
   cout << "Result: "; displayListNum(res);
}

出力

First number: 512
Second number: 14578
Result: 15090

以上がリンクリストで表される 2 つの数値を加算しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。