设计一个C++链表类,它能将数字储存在链表中,并且能实现两个数字以链表形式相乘
时间: 2023-08-04 09:24:22 浏览: 103
好的,我可以帮您设计一个C++链表类,它可以将数字存储在链表中并且可以实现两个数字以链表形式相乘。下面是代码实现:
```c++
#include <iostream>
using namespace std;
class Node {
public:
int val;
Node* next;
Node(int x) : val(x), next(NULL) {}
};
class LinkedList {
public:
Node* head;
LinkedList() : head(NULL) {}
void add(int x) {
Node* node = new Node(x);
if (!head) {
head = node;
} else {
Node* p = head;
while (p->next) {
p = p->next;
}
p->next = node;
}
}
void multiply(LinkedList* b) {
Node* p = head;
Node* q = b->head;
int len1 = 0, len2 = 0;
while (p) {
len1++;
p = p->next;
}
while (q) {
len2++;
q = q->next;
}
int* a = new int[len1];
int* b = new int[len2];
p = head;
q = b->head;
for (int i = 0; i < len1; i++) {
a[i] = p->val;
p = p->next;
}
for (int i = 0; i < len2; i++) {
b[i] = q->val;
q = q->next;
}
int len = len1 + len2;
int* c = new int[len];
for (int i = 0; i < len; i++) {
c[i] = 0;
}
for (int i = 0; i < len1; i++) {
for (int j = 0; j < len2; j++) {
c[i+j] += a[i] * b[j];
c[i+j+1] += c[i+j] / 10;
c[i+j] %= 10;
}
}
Node* res = new Node(0);
Node* r = res;
int i = len - 1;
while (i >= 0 && c[i] == 0) {
i--;
}
if (i < 0) {
cout << "0" << endl;
return;
}
while (i >= 0) {
r->next = new Node(c[i]);
r = r->next;
i--;
}
r = res->next;
while (r) {
cout << r->val;
r = r->next;
}
cout << endl;
}
};
int main() {
LinkedList a, b;
a.add(1);
a.add(2);
a.add(3);
b.add(2);
b.add(0);
b.add(2);
a.multiply(&b);
return 0;
}
```
在这个链表类中,我们定义了一个`Node`类,它表示链表中的一个节点,包含一个`val`成员表示节点的值,以及一个`next`成员表示下一个节点的指针。我们还定义了一个`LinkedList`类,它表示链表,包含一个`head`成员表示链表的头节点,以及`add`方法和`multiply`方法。`add`方法用于向链表中添加元素,`multiply`方法用于对两个链表的元素进行相乘操作。在`multiply`方法中,我们先将两个链表中的元素分别存储到数组`a`和`b`中,然后对数组`a`和`b`进行乘法运算,将结果存储到数组`c`中。最后,将数组`c`中的元素转换为链表形式,并输出该链表。
阅读全文