Question

数据结构。用链表实现两个长整数相加。

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;            }        }