Question

高分: C语言 数据结构之长整数四则运算,要求用链表...

长整数四则运算
【问题描述】
设计一个实现任意长的整数进行加法运算的演示程序。
【基本要求】
利用双向循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范 围是－(215-l)~(215-1) 。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。
【测试数据】
(1) 0；0； 应输出 "0" 。
(2)－2345，6789； －7654，3211； 应输出 "－1，0000，0000" 。
(3)－9999，9999；1，0000，0000，0000； 应输出 "9999，0000，0001" 。
(4) 1，0001，0001；－1，0001，0001； 应输出 "0" 。
(5) 1，0001，0001；－1，0001，0000； 应输出 "1" 。
(6) -9999，9999，9999；－9999，9999，9999；应输出 "－1，9999，9999，9998" 。 (7) 1，0000，9999，9999；1； 应输出 "1，0001，0000，0000 " 。
【实现提示】
(1) 每个结点中可以存放的最大整数为 215-1=32767， 才能保证两数相加不会溢出。但若这样存放，即相当于按32768进制数存放，在十进制数与32768进制数之间的转换十分不方便。故可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表表示为万进制数。
(2) 可以利用头结点数据域的符号代表长整数的符号。相加过程中不要破坏两个操作数链表。不能给长整数位数规定上限。
【选作内容】
(1) 实现长整数的四则运算；
(2) 实现长整数的乘方和阶乘运算；
(3) 整型量范围是－ (2n－1) ~ (2n－1)， 其中，n是由程序读人的参量。输入数据的分
组方法可以另行规定。

Answer 1

#include <iostream>
#include <list>
#include <string>
#include <stdexcept>
#include <sstream>
#include <iomanip>
using namespace std;

struct long_int_t {
    // arg_value只能包含正负号和数字
    long_int_t(string const &arg_value) : m_positive(true) {
        string::size_type rest = arg_value.size();
        if (rest) {
            string::size_type pos = 0;
            // 处理符号位，如果有的话
            if (arg_value[pos] == '-') {
                m_positive = false;
                ++pos;
                --rest;
            }
            else if (arg_value[pos] == '+') {
                ++pos;
                --rest;
            }
            // 读取数据，每次to_read位
            while (rest) {
                string::size_type to_read = rest % 4;
                to_read = to_read ? to_read : 4;
                string four_digits = arg_value.substr(pos, to_read);
                istringstream tmp_stream(four_digits);
                unsigned short tmp;
                if (!(tmp_stream >> tmp)) {// 读取失败
                    throw invalid_argument(four_digits + " cannot be converted to unsigned short");
                }
                m_data.push_back(tmp);
                pos += to_read;
                rest -= to_read;
            }
        }
        normalize();
    }
    long_int_t operator-() const {
        long_int_t result(*this);
        result.m_positive = !result.m_positive;
        return result;
    }
    bool positive() const {
        return m_positive;
    }

private:
    bool m_positive;
    typedef list<unsigned short> data_t;
    data_t m_data;
    static unsigned short const modulus = 10000;

    long_int_t() {}
    void normalize() {
        while (!m_data.empty() && !m_data.front()) m_data.pop_front();
        if (m_data.empty()) {
            m_data.push_back(0);
        }
    }
    friend ostream& operator<<(ostream &arg_ostream, long_int_t const &arg_value) {
        if (!arg_value.positive()) arg_ostream << "-";
        data_t::const_iterator it = arg_value.m_data.begin();
        if (it != arg_value.m_data.end()) {
            arg_ostream << *it;
            for (;++it != arg_value.m_data.end(); ) {
                arg_ostream << "," << setw(4) << setfill('0') << *it;
            }
        }
        return arg_ostream;
    }
    friend long_int_t operator+(long_int_t const& arg_a, long_int_t const &arg_b) {
        if (arg_a.m_positive == arg_b.m_positive) {// 同号
            if (arg_a.m_data.size() < arg_b.m_data.size()) {
                return arg_b + arg_a;
            }
            // now: arg_a.m_data.size() >= arg_b.m_data.size()
            long_int_t result;
            result.m_positive = arg_a.m_positive;
            unsigned short carry = 0;
            data_t::const_reverse_iterator it_a = arg_a.m_data.rbegin(), it_b = arg_b.m_data.rbegin();
            for (;it_b != arg_b.m_data.rend(); ++it_a, ++it_b) {
                unsigned short sum = *it_a + *it_b + carry;
                carry = sum / modulus;
                sum %= modulus;
                result.m_data.push_front(sum);
            }
            for (;it_a != arg_a.m_data.rend(); ++it_a) {
                unsigned short sum = *it_a + carry;
                carry = sum / modulus;
                sum %= modulus;
                result.m_data.push_front(sum);
            }
            if(carry) result.m_data.push_front(carry);
            return result;
        }
        if (arg_a.m_positive) {// arg_a >= 0, arg_b < 0
            return arg_a - (-arg_b);
        }
        else {// arg_a < 0, arg_b >= 0
            return arg_b - (-arg_a);
        }
    }

    friend long_int_t operator-(long_int_t const& arg_a, long_int_t const &arg_b) {
        if (arg_a.m_positive == arg_b.m_positive) {// 同号
            if (arg_a.m_data.size() < arg_b.m_data.size() || 
                (arg_a.m_data.size() == arg_b.m_data.size() && arg_a.m_data.front() < arg_b.m_data.front())) {
                // |arg_a| < |arg_b|
                return -(arg_b - arg_a);
            }
            // now: |arg_a| >= |arg_b|
            long_int_t result;
            result.m_positive = arg_a.m_positive;
            unsigned short borrow = 0;
            data_t::const_reverse_iterator it_a = arg_a.m_data.rbegin(), it_b = arg_b.m_data.rbegin();
            for (;it_b != arg_b.m_data.rend(); ++it_a, ++it_b) {
                unsigned short diff = *it_a + modulus - *it_b - borrow;
                borrow = 1 - diff / modulus;
                diff %= modulus;
                result.m_data.push_front(diff);
            }
            for (;it_a != arg_a.m_data.rend(); ++it_a) {
                unsigned short diff = *it_a + modulus - borrow;
                borrow = 1 - diff / modulus;
                diff %= modulus;
                result.m_data.push_front(diff);
            }
            result.normalize();
            return result;
        }
        if (arg_a.m_positive) {// arg_a >= 0, arg_b < 0
            return arg_a + (-arg_b);
        }
        else {// arg_a < 0, arg_b >= 0
            return  -((-arg_a) + arg_b);
        }
    }
};

int main() {
    string line;
    while (getline(cin, line)) {// 读取一行
        // 识别两个参数
        string a, b, *current = &a;
        for (string::size_type i = 0; i != line.size(); ++i) {
            char const c = line[i];
            if (c != ',') {// 逗号忽略
                if (c == ';') current = &b;// 开始读取下一个数
                else if (c == '-' || isdigit(c)) current->push_back(c);
                // else 不知道是什么东西，忽略
            }
        }
        long_int_t const int_a(a), int_b(b);
        cout << int_a << " + " << int_b << " = " << (int_a + int_b) << "\n";
    }

    return 0;
}

追问

厉害，但这是c++，能否用c语言实现呢？