用鏈表不用類實現高精度運算
时间: 2024-03-04 09:48:16 浏览: 16
高精度运算指的是对于超过计算机所能表示的数进行运算,需要使用链表来进行存储和计算。下面是一个简单的链表实现高精度加法的代码示例:
```c++
#include <iostream>
#include <string>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
int carry = 0;
while (l1 || l2 || carry) {
int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
cur->next = new ListNode(sum % 10);
carry = sum / 10;
cur = cur->next;
l1 = l1 ? l1->next : l1;
l2 = l2 ? l2->next : l2;
}
return dummy->next;
}
ListNode* constructList(string s) {
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
for (int i = s.size() - 1; i >= 0; i--) {
cur->next = new ListNode(s[i] - '0');
cur = cur->next;
}
return dummy->next;
}
int main() {
string s1 = "123456789";
string s2 = "987654321";
ListNode* l1 = constructList(s1);
ListNode* l2 = constructList(s2);
ListNode* res = addTwoNumbers(l1, l2);
while (res) {
cout << res->val;
res = res->next;
}
return 0;
}
```
在这个例子中,我们定义了一个 `ListNode` 结构体,其中 `val` 代表该节点的值,`next` 指向下一个节点。我们使用 `constructList` 函数将一个字符串构造成链表,每个字符代表链表中的一个节点。`addTwoNumbers` 函数接收两个链表作为输入,返回它们的和的链表表示。最后,我们在 `main` 函数中将两个字符串转化为链表,计算它们的和,并输出结果。
需要注意的是,在计算过程中我们需要考虑到进位的情况。每次计算两个节点的和时,将进位值 `carry` 加入到下一次的计算中。当两个链表都遍历完并且没有进位时,计算结束。
这只是一个简单的例子,实际使用中可能需要考虑更多的情况,比如减法、乘法、除法等运算。但是通过链表的实现方式,我们可以轻松地处理超过计算机所能表示的数的运算。