数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究用链表表示的两个数字的加法？
这里，我们来看看如何将存储在不同链表中的两个数字相加。在链表中，数字的每个数字都已存储。如果数字是 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){
//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
更新于： 31-07-2019
295 查看
广告