C++编写一个用单链表实现非负大整数的加法运算的程序。测试输入,每两行表示一个大整数,第一行是整数位数,第二行是整数各个数位:
时间: 2024-11-22 21:43:02 浏览: 27
在C++中,我们可以使用动态内存分配以及链表的方式来实现非负大整数的加法运算。下面是一个简单的示例程序,它首先定义了一个Node结构体存储每一位数字,并实现了加法操作:
```cpp
#include <iostream>
#include <string>
// 定义Node结构体用于存储一位数
struct Node {
int val; // 存储数值
Node* next; // 指向下一个节点
};
class BigInt {
private:
Node* head;
public:
BigInt() : head(nullptr) {}
void add(int num) {
Node* newNode = new Node{num};
if (head == nullptr) {
head = newNode;
} else {
Node* current = head;
while (current->next != nullptr && num > 0) {
current = current->next;
num--;
}
if (num > 0) {
newNode->next = head;
head = newNode;
} else {
newNode->next = current->next;
current->next = newNode;
}
}
}
void print() {
std::string result;
Node* temp = head;
while (temp != nullptr) {
result += std::to_string(temp->val);
temp = temp->next;
}
std::cout << result << std::endl;
}
};
int main() {
int size1, size2;
std::cin >> size1 >> size2; // 输入两个大数的位数
BigInt num1, num2;
for (int i = 0; i < size1; ++i) {
int digit1;
std::cin >> digit1;
num1.add(digit1); // 读入并添加第一位
}
for (int i = 0; i < size2; ++i) {
int digit2;
std::cin >> digit2;
num2.add(digit2); // 同理,对第二个数做同样的处理
}
num1.print(); // 输出第一个数
num2.print(); // 输出第二个数
// 现在将两个数相加
num1.add(num2.head->val); // 将第二个数的第一个位加到第一个数上
num2.head = num2.head->next;
num1.print(); // 再次输出结果
return 0;
}
```
在这个程序中,我们首先定义了两个BigInt对象num1和num2,然后分别读取每个数的每一位并加入对应的大整数链表。最后,我们将num2的第一个数位加到num1上,完成加法运算。
注意,这个例子假设输入的两个大整数不会导致溢出,如果需要处理更复杂的情况,例如进位等,还需要进一步完善代码。运行此程序时,请提供两个大整数的位数及其每一位作为输入。
阅读全文