在c++中使用双链表实现两个任意长的整数求和

### C++ 双向链表实现大整数相加 为了实现两个任意长度整数的加法操作，可以采用双向循环链表来存储这些大整数。以下是具体实现方法： #### 结构定义 首先定义双向链表节点结构 `Node` 和双向循环链表类 `BigInt`。 ```cpp // 定义链表节点结构 struct Node { int data; Node* next; Node* prev; Node(int val = 0, Node* n = nullptr, Node* p = nullptr) : data(val), next(n), prev(p) {} }; // 定义双向循环链表类 BigInt class BigInt { private: Node *head, *tail; public: BigInt(); ~BigInt(); void add(const BigInt& other); friend std::ostream &operator<<(std::ostream &os, const BigInt &bigint); static BigInt fromString(const std::string &numStr); }; ``` #### 构造函数与析构函数 初始化和清理工作由构造器及析构器完成。 ```cpp BigInt::BigInt() : head(nullptr), tail(nullptr) {} BigInt::~BigInt() { while (head != nullptr) { auto temp = head->next; delete head; head = temp; } } ``` #### 字符串转换为BigInt对象的方法 提供静态成员函数用于将字符串形式的大整数转化为 `BigInt` 对象实例。 ```cpp BigInt BigInt::fromString(const std::string &numStr) { BigInt result; for (auto it = numStr.rbegin(); it != numStr.rend(); ++it) { if (*it >= '0' && *it <= '9') { append(result.head, new Node(*it - '0')); } else throw "Invalid character"; } return result; } void append(Node*& h, Node* newNode){ if (!h) { h = newNode; newNode->prev = newNode; newNode->next = newNode; } else { Node* last = h->prev; last->next = newNode; newNode->prev = last; newNode->next = h; h->prev = newNode; } } ``` #### 加法逻辑实现 核心部分在于处理每一位上的数值累加以及进位情况。 ```cpp void BigInt::add(const BigInt &other) { Node *pThis = this->head ? this->head->prev : nullptr, *pOther = other.head ? other.head->prev : nullptr; int carry = 0; while (pThis || pOther || carry) { int sum = carry + (pThis ? pThis->data : 0) + (pOther ? pOther->data : 0); carry = sum / 10; sum %= 10; if (pThis) { pThis->data = sum; pThis = pThis->prev; } else { insertFront(this->head, new Node(sum)); } if (pOther) pOther = pOther->prev; } } void insertFront(Node *&h, Node *newNode) { if (!h) { h = newNode; newNode->prev = newNode; newNode->next = newNode; } else { Node *last = h->prev; last->next = newNode; newNode->prev = last; newNode->next = h; h->prev = newNode; h = newNode; } } ``` #### 输出重载 方便打印查看计算后的结果。 ```cpp std::ostream &operator<<(std::ostream &os, const BigInt &bigint) { if(bigint.head == nullptr) os << "Empty List"; else{ Node *current = bigint.head; do { os << current->data; current = current->next; }while(current != bigint.head); } return os; } ``` 通过上述代码片段展示了如何利用C++中的双向链表来进行两个任意长度整数间的加法运算[^1]。