用双向链表实现超长含小数的整数加减法
时间: 2024-03-26 22:36:40 浏览: 94
链表实现长整数相加减
好的,基于您的需求,我可以为您提供一种用双向链表实现超长含小数的整数加减法的方法。
我们可以将整数和小数部分分别用两个双向链表来存储。对于加法操作,我们可以先将两个数的小数部分对齐,然后从小数点后一位开始向前遍历双向链表,同时将整数部分的链表也从尾部开始遍历,依次相加,处理进位即可。对于减法操作,我们需要先将两个数的小数部分对齐,然后从小数点后一位开始向前遍历双向链表,同时将整数部分的链表也从尾部开始遍历,依次相减,处理借位即可。
下面是一个示例代码,可以实现超长含小数的整数加减法:
```c++
struct Node {
Node *prev, *next;
char val;
};
class Decimal {
public:
Decimal(): decimal_point(0) {
head1 = new Node;
head2 = new Node;
tail1 = head1;
tail2 = head2;
head1->prev = NULL;
head2->prev = NULL;
head1->next = tail1;
head2->next = tail2;
tail1->prev = head1;
tail2->prev = head2;
tail1->next = NULL;
tail2->next = NULL;
}
void add(int x) {
Node *node = new Node;
node->val = x + '0';
node->prev = tail1;
node->next = tail1->next;
tail1->next = node;
tail1 = node;
}
void sub(int x) {
Node *node = new Node;
node->val = x + '0';
node->prev = tail2;
node->next = tail2->next;
tail2->next = node;
tail2 = node;
}
void set_decimal_point(int pos) {
decimal_point = pos;
}
Decimal operator+(const Decimal& other) const {
Decimal res;
Node *p = tail1->prev;
Node *q = other.tail1->prev;
int carry = 0;
int decimal_count = 0;
while (p != head1->prev || q != other.head1->prev || carry != 0) {
char x = (p != head1->prev ? p->val : '0');
char y = (q != other.head1->prev ? q->val : '0');
if (x == '.') {
res.add('.');
decimal_count = 0;
if (p != head1->prev) p = p->prev;
if (q != other.head1->prev) q = q->prev;
continue;
}
int sum = (x - '0') + (y - '0') + carry;
carry = sum / 10;
sum %= 10;
res.add(sum);
if (++decimal_count == decimal_point) {
res.add('.');
}
if (p != head1->prev) p = p->prev;
if (q != other.head1->prev) q = q->prev;
}
return res;
}
Decimal operator-(const Decimal& other) const {
Decimal res;
Node *p = tail1->prev;
Node *q = other.tail1->prev;
bool borrow = false;
int decimal_count = 0;
if (compare(other) < 0) {
borrow = true;
std::swap(p, q);
}
while (p != head1->prev || q != other.head1->prev) {
char x = (p != head1->prev ? p->val : '0');
char y = (q != other.head1->prev ? q->val : '0');
if (x == '.') {
res.add('.');
decimal_count = 0;
if (p != head1->prev) p = p->prev;
if (q != other.head1->prev) q = q->prev;
continue;
}
if (borrow) {
x--;
borrow = false;
}
if (x < y) {
x += 10;
borrow = true;
}
int diff = x - y;
res.sub(diff);
if (++decimal_count == decimal_point) {
res.add('.');
}
if (p != head1->prev) p = p->prev;
if (q != other.head1->prev) q = q->prev;
}
return res;
}
int compare(const Decimal& other) const {
Node *p = tail1->prev;
Node *q = other.tail1->prev;
while (p != head1->prev || q != other.head1->prev) {
char x = (p != head1->prev ? p->val : '0');
char y = (q != other.head1->prev ? q->val : '0');
if (x < y) {
return -1;
} else if (x > y) {
return 1;
}
if (p != head1->prev) p = p->prev;
if (q != other.head1->prev) q = q->prev;
}
return 0;
}
private:
Node *head1, *head2, *tail1, *tail2;
int decimal_point;
};
```
使用示例:
```c++
Decimal a, b;
a.add(1);
a.add(2);
a.add(3);
a.set_decimal_point(2);
b.add(4);
b.add(5);
b.add(6);
b.set_decimal_point(1);
Decimal c = a + b;
Decimal d = a - b;
```
在这个示例中,我们创建了两个超长含小数的整数 a 和 b,然后分别添加了 123.00 和 45.6 两个数字。接着,我们通过重载运算符实现了加法和减法操作,并将结果存储在变量 c 和 d 中。
阅读全文