添加两个数字,以链接列表表示?

在这里,我们将看到如何将存储在单独链表中的两个数字相加。在链接列表中,存储了数字的每一位。如果数字是512,那么它将如下存储:

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

我们提供了两个这种类型的列表,我们的任务是将它们加起来并在计算总和后得到结果。在这里,我们使用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){

   //在最短的数字上添加前导0,以使其长度相等

   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

以上是 添加两个数字,以链接列表表示? 的全部内容, 来源链接: utcz.com/z/317007.html

回到顶部