C++实现高精度加法：解决大数相加问题

在计算机科学中，处理超出基本数据类型限制的大数是一个常见的挑战。高精度算法，也称为大数算法，为我们提供了克服这些限制的有效方法。本文将探讨如何使用C++实现高精度加法，并提供一个完整的代码示例来演示其工作原理。

问题描述

当需要进行超出 int 或 long long int 等基本数据类型表示范围的加法运算时，就会出现大数相加问题。例如，如果要计算两个100位数的和，则无法使用标准数据类型直接存储或操作这些数字。

解决方案：链表

解决此问题的常用方法是使用链表来表示大数。链表提供了一种灵活的方式来存储数字的每一位，而无需预先定义数组的大小。

代码实现cpp#include using namespace std;

struct Node { int data; Node* next;};

Node* createLinkedList() { Node* head = new Node; head->next = nullptr; return head;}

void insertNode(Node* head, int data) { Node* newNode = new Node; newNode->data = data; newNode->next = nullptr;

Node* p = head;    while (p->next != nullptr) {        p = p->next;    }    p->next = newNode;}

Node* addTwoNumbers(Node* l1, Node* l2) { Node* p1 = l1->next; Node* p2 = l2->next; Node* result = createLinkedList(); Node* p = result;

int carry = 0;    while (p1 != nullptr || p2 != nullptr || carry != 0) {        int sum = carry + (p1 != nullptr ? p1->data : 0) + (p2 != nullptr ? p2->data : 0);        int digit = sum % 10;        carry = sum / 10;

    insertNode(p, digit);        p = p->next;

    if (p1 != nullptr) p1 = p1->next;        if (p2 != nullptr) p2 = p2->next;    }

return result;}

void printLinkedList(Node* head) { Node* p = head->next; while (p != nullptr) { cout << p->data << ' '; p = p->next; } cout << endl;}

void deleteLinkedList(Node* head) { Node* p = head; while (p != nullptr) { Node* temp = p; p = p->next; delete temp; }}

int main() { Node* l1 = createLinkedList(); Node* l2 = createLinkedList();

int num;    cout << '请输入第一个大数（以-1结尾）：' << endl;    while (cin >> num && num != -1) {        insertNode(l1, num);    }

cout << '请输入第二个大数（以-1结尾）：' << endl;    while (cin >> num && num != -1) {        insertNode(l2, num);    }

Node* result = addTwoNumbers(l1, l2);

cout << '计算结果为：' << endl;    printLinkedList(result);

deleteLinkedList(l1);    deleteLinkedList(l2);    deleteLinkedList(result);

return 0;}

代码解释

创建链表: createLinkedList() 函数创建一个新的链表，并返回其头节点。2. 插入节点: insertNode() 函数将一个新的节点插入到链表的末尾。3. 高精度加法: addTwoNumbers() 函数接受两个链表作为输入，分别表示要相加的两个大数。它创建第三个链表来存储结果，并逐位执行加法运算，同时处理进位。4. 打印链表: printLinkedList() 函数遍历链表并打印每个节点的数据。5. 删除链表: deleteLinkedList() 函数释放链表占用的内存。

测试代码

在 main() 函数中，我们创建两个链表 l1 和 l2，并从用户输入中读取数字来填充它们。然后，我们调用 addTwoNumbers() 函数来计算它们的和，并将结果存储在 result 链表中。最后，我们打印 result 链表的内容。

总结

高精度算法是处理超出基本数据类型限制的大数的强大工具。通过使用链表来表示大数，我们可以轻松执行加法、减法、乘法和除法等算术运算。