设计一个C++链表类,它能将数字存入链表中,并且可以重载*以实现两个百位数相乘
时间: 2024-02-28 16:56:07 浏览: 86
用类的方式实现C++链表功能
好的,我可以帮你设计一个C++链表类,使其能够存储任意长度的数字,并且重载*运算符以实现两个百位数的相乘。
首先,我们需要定义一个节点类,用于表示链表中的每个节点:
```cpp
class Node {
public:
int val;
Node* next;
Node(int val): val(val), next(NULL) {}
};
```
然后,我们可以定义链表类,其中包含了一些常用的链表操作,例如插入节点、删除节点和遍历链表:
```cpp
class LinkedList {
private:
Node* head;
public:
LinkedList(): head(NULL) {}
~LinkedList() {
Node* cur = head;
while (cur != NULL) {
Node* next = cur->next;
delete cur;
cur = next;
}
}
void insert(int val) {
Node* node = new Node(val);
if (head == NULL) {
head = node;
} else {
Node* cur = head;
while (cur->next != NULL) {
cur = cur->next;
}
cur->next = node;
}
}
void remove(int val) {
if (head == NULL) {
return;
}
if (head->val == val) {
Node* tmp = head;
head = head->next;
delete tmp;
return;
}
Node* cur = head;
while (cur->next != NULL && cur->next->val != val) {
cur = cur->next;
}
if (cur->next != NULL) {
Node* tmp = cur->next;
cur->next = tmp->next;
delete tmp;
}
}
void print() {
Node* cur = head;
while (cur != NULL) {
cout << cur->val;
cur = cur->next;
}
cout << endl;
}
int size() {
int cnt = 0;
Node* cur = head;
while (cur != NULL) {
cnt++;
cur = cur->next;
}
return cnt;
}
friend LinkedList operator*(const LinkedList& a, const LinkedList& b) {
LinkedList res;
Node* cur_a = a.head;
while (cur_a != NULL) {
Node* cur_b = b.head;
int carry = 0;
LinkedList tmp;
for (int i = 0; i < cur_a->val; i++) {
tmp.insert(0);
}
while (cur_b != NULL) {
int mul = cur_a->val * cur_b->val + carry;
carry = mul / 10;
tmp.insert(mul % 10);
cur_b = cur_b->next;
}
if (carry != 0) {
tmp.insert(carry);
}
res = res + tmp;
cur_a = cur_a->next;
}
return res;
}
friend LinkedList operator+(const LinkedList& a, const LinkedList& b) {
LinkedList res;
Node* cur_a = a.head;
Node* cur_b = b.head;
int carry = 0;
while (cur_a != NULL || cur_b != NULL) {
int sum = carry;
if (cur_a != NULL) {
sum += cur_a->val;
cur_a = cur_a->next;
}
if (cur_b != NULL) {
sum += cur_b->val;
cur_b = cur_b->next;
}
carry = sum / 10;
res.insert(sum % 10);
}
if (carry != 0) {
res.insert(carry);
}
return res;
}
};
```
在链表类中,我们重载了*运算符和+运算符,用于实现两个百位数的相乘和相加。其中,*运算符中采用了竖式相乘的方法,将结果存储在一个临时链表中,最后将所有临时链表相加即可得到最终结果。
现在,我们可以使用该链表类来存储任意长度的数字,并且进行相乘操作了。例如,以下代码将创建两个链表,分别存储数字123和456,并计算它们的乘积:
```cpp
int main() {
LinkedList a, b;
string str_a = "123";
string str_b = "456";
for (int i = str_a.size() - 1; i >= 0; i--) {
a.insert(str_a[i] - '0');
}
for (int i = str_b.size() - 1; i >= 0; i--) {
b.insert(str_b[i] - '0');
}
LinkedList c = a * b;
c.print(); // 输出结果为:56088
return 0;
}
```
希望这个链表类能够对你有所帮助!
阅读全文