只用鏈表且不用algorithm實現支持負數的實數高精度運算(包括高精度乘高精度)
时间: 2023-08-21 15:19:55 浏览: 89
好的,我来为您解答。
首先,我们需要定义一个链表节点结构体,来存储每个数字:
```c++
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
```
接着,我们定义一个链表类,来实现高精度的加减乘除运算:
```c++
class LinkedList {
private:
ListNode *head;
public:
LinkedList(): head(NULL) {}
void insert(int val) {
ListNode *node = new ListNode(val);
node->next = head;
head = node;
}
void add(LinkedList &b) {
ListNode *a_node = head, *b_node = b.head;
int carry = 0;
while (a_node || b_node || carry) {
int sum = (a_node ? a_node->val : 0) + (b_node ? b_node->val : 0) + carry;
carry = sum / 10;
sum %= 10;
insert(sum);
a_node = a_node ? a_node->next : NULL;
b_node = b_node ? b_node->next : NULL;
}
}
void subtract(LinkedList &b) {
ListNode *a_node = head, *b_node = b.head;
int borrow = 0;
while (a_node) {
int diff = a_node->val - (b_node ? b_node->val : 0) - borrow;
borrow = diff < 0 ? 1 : 0;
diff = diff < 0 ? diff + 10 : diff;
insert(diff);
a_node = a_node->next;
b_node = b_node ? b_node->next : NULL;
}
while (head && head->val == 0) {
ListNode *node = head;
head = head->next;
delete node;
}
}
void multiply(LinkedList &b) {
LinkedList result;
int offset = 0;
for (ListNode *a_node = head; a_node; a_node = a_node->next) {
LinkedList tmp;
int carry = 0;
for (int i = 0; i < offset; i++) {
tmp.insert(0);
}
for (ListNode *b_node = b.head; b_node || carry; b_node = b_node ? b_node->next : NULL) {
int product = (a_node ? a_node->val : 0) * (b_node ? b_node->val : 0) + carry;
carry = product / 10;
product %= 10;
tmp.insert(product);
}
result.add(tmp);
offset++;
}
head = result.head;
}
void print() {
if (!head) {
printf("0");
return;
}
ListNode *node = head;
while (node) {
printf("%d", node->val);
node = node->next;
}
}
};
```
在链表类中,我们实现了加法、减法、乘法三种运算,并且支持负数的处理。
接下来,我们可以利用这个链表类来实现高精度浮点数的加减乘除运算。假设我们要实现的是两个浮点数的乘法运算,可以按照以下步骤进行:
1. 将两个浮点数分别拆分成小数点前后两个整数部分;
2. 分别将两个整数部分转化为链表表示,然后调用链表类的乘法运算;
3. 将链表表示的结果转化为浮点数表示。
具体代码实现如下:
```c++
double multiply(double a, double b) {
int a_int = (int)a, b_int = (int)b;
double a_frac = a - a_int, b_frac = b - b_int;
LinkedList int_part_a, int_part_b, frac_part_a, frac_part_b;
while (a_int) {
int_part_a.insert(a_int % 10);
a_int /= 10;
}
while (b_int) {
int_part_b.insert(b_int % 10);
b_int /= 10;
}
while (a_frac > 1e-10) {
a_frac *= 10;
frac_part_a.insert((int)a_frac);
a_frac -= (int)a_frac;
}
while (b_frac > 1e-10) {
b_frac *= 10;
frac_part_b.insert((int)b_frac);
b_frac -= (int)b_frac;
}
LinkedList int_part_res, frac_part_res;
int_part_a.multiply(int_part_b);
frac_part_a.multiply(frac_part_b);
frac_part_res.add(frac_part_a);
while (frac_part_res.head && frac_part_res.head->val >= 10) {
frac_part_res.head->val %= 10;
if (frac_part_res.head->next) {
frac_part_res.head->next->val++;
} else {
frac_part_res.insert(1);
}
frac_part_res.head = frac_part_res.head->next;
}
int_part_res.add(frac_part_res);
double res = 0, factor = 1;
ListNode *node = int_part_res.head;
while (node) {
res += node->val * factor;
factor *= 10;
node = node->next;
}
return res;
}
```
这样,我们就实现了一个支持负数的高精度浮点数运算。当然,这个实现可能还不够完善,还需要根据实际需求进行调整和优化。
阅读全文