高分: 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是由程序读人的参量。输入数据的分
组方法可以另行规定。
#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语言实现呢？
温馨提示：答案为网友推荐，仅供参考
相似回答