问题抽还 设计一个程序实现两个任意长的整数求和运算。 基本要求 利用双向循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是 -(21*-1)~(21*-1)。 输入和输出形式:每4位- -组， 组间用逗号隔开。 测试数据 (1)0和0，应输出“0”。 (2) -2345,6789，-7654,3211, 应输出“-10000,0000”。 (3) 9999.9999，,000000000， 应输出9999,000,0001”。 录 (4) 1,001,000，-1,001,0001, 应输出“0”。 (5) 1,00,0001, -1 ,00,0000，应输出“1”。 实现提示 (1)每个结点中可以存放的最大整数为219-1=32767,这样才能保证两数相加不会溢出。但若按 32 768进制数存放，在+进制数与32768进制数之间的转换十分不方便，故可以在每个结点中仅存放十 进制数的4位，即不超过9 999的非负整数，整个链表视为万进制数。 (2)可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程 中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一一种方法。 不能给 长整数位数规定上限。

以下是一个基于双向循环链表实现长整数求和的示例程序。程序的实现思路如下：

1. 定义一个双向循环链表结构体，每个节点存储4位十进制数，头结点的符号位表示长整数的符号，链表长度存储在头结点的绝对值中。

2. 读入两个长整数，并将它们存储到两个双向循环链表中。

3. 将两个链表从低位到高位逐位相加，将结果存储到一个新的链表中。

4. 对于新链表中每个节点的值，如果大于等于10000，则需要向高位进位，并将当前节点的值减去10000；如果小于0，则需要向高位借位，并将当前节点的值加上10000。

5. 最后输出新链表表示的长整数。

#include <iostream>
#include <string>
using namespace std;

const int BASE = 10000; // 每个节点存储的数值的最大值
const int DIGITS = 4; // 每个节点存储的数值的位数

// 定义双向循环链表节点结构体
struct ListNode {
    int val; // 当前节点存储的数值
    ListNode* prev; // 前驱指针
    ListNode* next; // 后继指针
    ListNode(int x = 0) : val(x), prev(nullptr), next(nullptr) {}
};

// 定义双向循环链表结构体
struct LinkedList {
    ListNode* head; // 头结点
    LinkedList() : head(new ListNode()) { head->prev = head->next = head; }
    ~LinkedList() { // 销毁链表
        ListNode* cur = head->next;
        while (cur != head) {
            ListNode* next = cur->next;
            delete cur;
            cur = next;
        }
        delete head;
    }
    void insert(int x) { // 在链表末尾插入一个节点
        ListNode* node = new ListNode(x);
        node->prev = head->prev;
        node->next = head;
        head->prev->next = node;
        head->prev = node;
        ++(head->val); // 链表长度加1
    }
    void print() { // 输出链表表示的长整数
        if (head->val == 0) { // 长整数为0
            cout << "0" << endl;
            return;
        }
        if (head->val < 0) { // 长整数为负数
            cout << "-";
        }
        ListNode* cur = head->prev;
        while (cur != head) {
            cout.width(DIGITS);
            cout.fill('0');
            cout << abs(cur->val);
            cur = cur->prev;
            if (cur != head) {
                cout << ",";
            }
        }
        cout << endl;
    }
};

// 将一个字符串转换为长整数的双向循环链表表示
LinkedList stringToList(const string& s) {
    LinkedList list;
    int sign = 1;
    int start = 0;
    if (s[0] == '-') { // 字符串表示的长整数为负数
        sign = -1;
        start = 1;
    }
    int num = 0;
    int len = 0;
    for (int i = s.length() - 1; i >= start; --i) {
        num += (s[i] - '0') * pow(10, len++);
        if (len == DIGITS || i == start) { // 每4位一组，转换为一个节点存储
            list.insert(sign * num);
            num = 0;
            len = 0;
        }
    }
    return list;
}

// 两个双向循环链表相加
LinkedList add(const LinkedList& a, const LinkedList& b) {
    LinkedList sum;
    ListNode* curA = a.head->next;
    ListNode* curB = b.head->next;
    int carry = 0; // 进位
    while (curA != a.head || curB != b.head) {
        int valA = curA != a.head ? curA->val : 0;
        int valB = curB != b.head ? curB->val : 0;
        int val = valA + valB + carry;
        sum.insert(val % BASE);
        carry = val / BASE;
        if (curA != a.head) {
            curA = curA->next;
        }
        if (curB != b.head) {
            curB = curB->next;
        }
    }
    if (carry != 0) { // 如果最高位有进位
        sum.insert(carry);
    }
    return sum;
}

// 对链表表示的长整数求相反数
LinkedList negate(const LinkedList& list) {
    LinkedList neg;
    neg.head->val = -list.head->val;
    ListNode* cur = list.head->next;
    while (cur != list.head) {
        neg.insert(-cur->val);
        cur = cur->next;
    }
    return neg;
}

// 比较两个链表表示的长整数的大小（绝对值）
int compare(const LinkedList& a, const LinkedList& b) {
    if (a.head->val != b.head->val) {
        return a.head->val > b.head->val ? 1 : -1;
    }
    ListNode* curA = a.head->prev;
    ListNode* curB = b.head->prev;
    while (curA != a.head && curB != b.head) {
        if (curA->val != curB->val) {
            return curA->val > curB->val ? 1 : -1;
        }
        curA = curA->prev;
        curB = curB->prev;
    }
    return 0;
}

// 计算两个链表表示的长整数的差（假设a>=b）
LinkedList subtract(const LinkedList& a, const LinkedList& b) {
    LinkedList diff;
    ListNode* curA = a.head->next;
    ListNode* curB = b.head->next;
    int borrow = 0; // 借位
    while (curA != a.head || curB != b.head) {
        int valA = curA != a.head ? curA->val : 0;
        int valB = curB != b.head ? curB->val : 0;
        int val = valA - valB - borrow;
        if (val < 0) {
            borrow = 1;
            val += BASE;
        }
        else {
            borrow = 0;
        }
        diff.insert(val);
        if (curA != a.head) {
            curA = curA->next;
        }
        if (curB != b.head) {
            curB = curB->next;
        }
    }
    while (diff.head->prev != diff.head && diff.head->prev->val == 0) { // 去掉高位的0
        ListNode* node = diff.head->prev;
        node->prev->next = diff.head;
        diff.head->prev = node->prev;
        delete node;
        --(diff.head->val);
    }
    return diff;
}

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    LinkedList a = stringToList(s1);
    LinkedList b = stringToList(s2);
    LinkedList sum;
    if (a.head->val >= 0 && b.head->val >= 0) { // 两个长整数都为非负数
        sum = add(a, b);
    }
    else if (a.head->val < 0 && b.head->val < 0) { // 两个长整数都为负数
        sum = add(negate(a), negate(b));
        sum.head->val = -sum.head->val;
    }
    else { // 两个长整数符号不同
        if (compare(a, b) >= 0) { // |a| >= |b|
            sum = subtract(a, b);
        }
        else {
            sum = subtract(b, a);
            sum.head->val = -sum.head->val;
        }
    }
    sum.print();
    return 0;
}