c++长整数、高精度运算双向循环链表

实现高精度运算的双向循环链表可以分为三个部分：节点结构体、链表结构体和高精度运算函数。

首先是节点结构体，可以定义如下：

struct Node {
    int val; // 当前节点的值
    Node* next; // 指向下一个节点的指针
    Node* prev; // 指向上一个节点的指针
    // 构造函数
    Node(int v = 0, Node* n = nullptr, Node* p = nullptr) : val(v), next(n), prev(p) {}
};

接下来是链表结构体，可以定义如下：

struct LinkedList {
    Node* head; // 头指针
    Node* tail; // 尾指针
    // 构造函数
    LinkedList() : head(nullptr), tail(nullptr) {}
    // 复制构造函数
    LinkedList(const LinkedList& lst) {
        head = tail = nullptr;
        Node* p = lst.head;
        while (p != nullptr) {
            push_back(p->val);
            p = p->next;
        }
    }
    // 析构函数
    ~LinkedList() {
        while (head != nullptr) {
            Node* p = head;
            head = head->next;
            delete p;
        }
    }
    // 在链表尾部插入一个节点
    void push_back(int v) {
        Node* p = new Node(v, nullptr, tail);
        if (tail != nullptr) {
            tail->next = p;
        } else {
            head = p;
        }
        tail = p;
    }
    // 在链表头部插入一个节点
    void push_front(int v) {
        Node* p = new Node(v, head, nullptr);
        if (head != nullptr) {
            head->prev = p;
        } else {
            tail = p;
        }
        head = p;
    }
};

最后是高精度运算函数，可以实现加法、减法和乘法等运算：

// 高精度加法
LinkedList add(const LinkedList& a, const LinkedList& b) {
    LinkedList res;
    int carry = 0; // 进位
    Node* p = a.tail;
    Node* q = b.tail;
    while (p != nullptr || q != nullptr) {
        int x = (p != nullptr) ? p->val : 0;
        int y = (q != nullptr) ? q->val : 0;
        int sum = x + y + carry;
        res.push_front(sum % 10);
        carry = sum / 10;
        if (p != nullptr) {
            p = p->prev;
        }
        if (q != nullptr) {
            q = q->prev;
        }
    }
    if (carry > 0) {
        res.push_front(carry);
    }
    return res;
}

// 高精度减法
LinkedList sub(const LinkedList& a, const LinkedList& b) {
    LinkedList res;
    int borrow = 0; // 借位
    Node* p = a.tail;
    Node* q = b.tail;
    while (p != nullptr || q != nullptr) {
        int x = (p != nullptr) ? p->val : 0;
        int y = (q != nullptr) ? q->val : 0;
        int diff = x - y - borrow;
        if (diff < 0) {
            diff += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        res.push_front(diff);
        if (p != nullptr) {
            p = p->prev;
        }
        if (q != nullptr) {
            q = q->prev;
        }
    }
    // 去除前导零
    while (res.head->next != nullptr && res.head->val == 0) {
        Node* p = res.head;
        res.head = res.head->next;
        res.head->prev = nullptr;
        delete p;
    }
    return res;
}

// 高精度乘法
LinkedList mul(const LinkedList& a, const LinkedList& b) {
    LinkedList res;
    int n = a.tail != nullptr ? 1 : 0;
    int m = b.tail != nullptr ? 1 : 0;
    if (n == 0 || m == 0) {
        return res;
    }
    int len = n + m - 1;
    int* c = new int[len];
    memset(c, 0, len * sizeof(int));
    Node* p = a.tail;
    for (int i = 0; p != nullptr; i++, p = p->prev) {
        Node* q = b.tail;
        for (int j = 0; q != nullptr; j++, q = q->prev) {
            c[i + j] += p->val * q->val;
            c[i + j + 1] += c[i + j] / 10;
            c[i + j] %= 10;
        }
    }
    while (len > 0 && c[len - 1] == 0) {
        len--;
    }
    for (int i = len - 1; i >= 0; i--) {
        res.push_back(c[i]);
    }
    delete[] c;
    return res;
}

这样，我们就实现了一个可以进行高精度运算的双向循环链表。