大整数类（链表实现）.md

tags	title	created	modified
Code	大整数类（链表实现）	2022-09-02T13:15:50.997Z	2022-09-02T13:16:12.400Z

大整数类（链表实现）

class BigInt
{
public:
    BigInt()
    {
        m_pHead = new Node;
        m_pHead->nxt = NULL;
    }
    ~BigInt()
    {
        while (m_pHead)
        {
            Node *p = m_pHead;
            m_pHead = p->nxt;
            delete p;
        }
    }
    BigInt &operator=(BigInt &rhs)
    {
        m_len = rhs.m_len;
        Node *p = rhs.m_pHead->nxt;
        Node *m = m_pHead;
        for (int i = 0; i < rhs.m_len; i++)
        {
            Node *q = new Node;
            q->data = p->data;
            m->nxt = q;
            q->pre = m;
            m = q;
            p = p->nxt;
        }
        m_pTail = m;
        return *this;
    }

    friend ostream &operator<<(ostream &os, BigInt &rhs)
    {
        Node *p = rhs.m_pHead->nxt;
        for (int i = 0; i < rhs.m_len; i++)
        {
            cout << p->data;
            p = p->nxt;
        }
        return os;
    }
    friend istream &operator>>(istream &is, BigInt &rhs)
    {
        string s;
        cin >> s;
        Node *p = rhs.m_pHead;
        int i = 0;
        while (s[i] != '\0')
        {
            Node *q = new Node;
            q->data = s[i] - '0';
            p->nxt = q;
            q->pre = p;
            p = q;
            i++;
        }
        rhs.m_pTail = p;
        rhs.m_len = i;
        return is;
    }
    friend BigInt &operator+(const BigInt &rhs1, const BigInt &rhs2)
    {
        BigInt *result = new BigInt;
        Node *front = new Node;
        Node *s = front; //为了和原来的链表具有一样的结构，最后释放这个空的尾结点；
        Node *p = rhs1.m_pTail;
        Node *q = rhs2.m_pTail;
        int jw = 0;
        for (int i = 0; i < min(rhs1.m_len, rhs2.m_len); i++)
        {
            Node *newnode = new Node;
            newnode->data = (p->data + q->data + jw) % 10;
            jw = (p->data + q->data + jw) / 10;
            newnode->nxt = front;
            front->pre = newnode;
            front = newnode;
            p = p->pre;
            q = q->pre;
        }
        if (rhs1.m_len > min(rhs1.m_len, rhs2.m_len))
        {
            for (int i = 0; i < rhs1.m_len - min(rhs1.m_len, rhs2.m_len); i++)
            {
                Node *newnode = new Node;
                newnode->data = (p->data + jw) % 10;
                jw = (p->data + jw) / 10;
                newnode->nxt = front;
                front->pre = newnode;
                front = newnode;
                p = p->pre;
            }
            if (jw > 0)
            {
                Node *newnode = new Node;
                newnode->data = jw;
                newnode->nxt = front;
                front->pre = newnode;
                front = newnode;
                result->m_pHead->nxt = front;
                front->pre = result->m_pHead;
                result->m_len = rhs1.m_len + 1;
            }
            else
            {
                result->m_pHead->nxt = front;
                front->pre = result->m_pHead;
                result->m_len = rhs1.m_len;
            }
        }
        else if (rhs2.m_len > min(rhs1.m_len, rhs2.m_len))
        {
            for (int i = 0; i < rhs2.m_len - min(rhs1.m_len, rhs2.m_len); i++)
            {
                Node *newnode = new Node;
                newnode->data = (q->data + jw) % 10;
                jw = (q->data + jw) / 10;
                newnode->nxt = front;
                front->pre = newnode;
                front = newnode;
                q = q->pre;
            }
            if (jw > 0)
            {
                Node *newnode = new Node;
                newnode->data = jw;
                newnode->nxt = front;
                front->pre = newnode;
                front = newnode;
                result->m_pHead->nxt = front;
                front->pre = result->m_pHead;
                result->m_len = rhs2.m_len + 1;
            }
            else
            {
                result->m_pHead->nxt = front;
                front->pre = result->m_pHead;
                result->m_len = rhs2.m_len;
            }
        }
        else
        {
            if (jw > 0)
            {
                Node *newnode = new Node;
                newnode->data = jw;
                newnode->nxt = front;
                front->pre = newnode;
                front = newnode;
                result->m_pHead->nxt = front;
                front->pre = result->m_pHead;
                result->m_len = rhs2.m_len + 1;
            }
            else
            {
                result->m_pHead->nxt = front;
                front->pre = result->m_pHead;
                result->m_len = rhs2.m_len;
            }
        }
        result->m_pTail = s->pre;
        s->pre->nxt = NULL;
        delete s;
        return *result;
    }

private:
    int m_len;
    struct Node
    {
        int data;
        struct Node *pre;
        struct Node *nxt;
    } * m_pHead, *m_pTail;
};