设计—个实现任意长的整数进行四则运算和幂次运算的演示程序。利用双向循环链表实现大数的存储,每个结点含一个整型变量。
时间: 2024-03-12 15:48:16 浏览: 72
基于链表实现的大数四则运算,支持小数,外附带幂运算,理论上长度不限
5星 · 资源好评率100%
好的,我可以为您提供一个基于双向循环链表的大数计算演示程序。以下是实现的步骤:
1. 定义一个双向循环链表节点结构体,其中包含一个整型变量用于保存每个数字,以及两个指针用于链接前驱节点和后继节点。
```c++
struct Node {
int data; // 存储的数字
Node* prev; // 前驱节点指针
Node* next; // 后继节点指针
};
```
2. 定义一个双向循环链表结构体,其中包含头节点和尾节点指针,以及表示链表长度的整型变量。
```c++
struct DoubleLinkedList {
Node* head; // 头节点指针
Node* tail; // 尾节点指针
int length; // 链表长度
};
```
3. 实现大数的输入和输出函数,这里以字符串形式输入和输出大数。
```c++
void input(DoubleLinkedList& num, string str) {
// 将字符串逆序存储到链表中
for (int i = str.length() - 1; i >= 0; i--) {
Node* node = new Node;
node->data = str[i] - '0';
node->prev = num.tail;
node->next = NULL;
if (num.length == 0) {
num.head = node;
num.tail = node;
} else {
num.tail->next = node;
num.tail = node;
}
num.length++;
}
}
string output(DoubleLinkedList num) {
// 将链表逆序输出到字符串中
string str = "";
Node* p = num.tail;
while (p != NULL) {
str += to_string(p->data);
p = p->prev;
}
return str;
}
```
4. 实现大数的加法、减法、乘法和除法运算函数。
```c++
// 大数加法
void add(DoubleLinkedList& num1, DoubleLinkedList& num2, DoubleLinkedList& result) {
int carry = 0; // 进位
Node* p1 = num1.head;
Node* p2 = num2.head;
while (p1 != NULL || p2 != NULL) {
int x = p1 == NULL ? 0 : p1->data;
int y = p2 == NULL ? 0 : p2->data;
int sum = x + y + carry;
Node* node = new Node;
node->data = sum % 10;
node->prev = result.tail;
node->next = NULL;
if (result.length == 0) {
result.head = node;
result.tail = node;
} else {
result.tail->next = node;
result.tail = node;
}
carry = sum / 10;
if (p1 != NULL) p1 = p1->next;
if (p2 != NULL) p2 = p2->next;
result.length++;
}
if (carry > 0) {
Node* node = new Node;
node->data = carry;
node->prev = result.tail;
node->next = NULL;
result.tail->next = node;
result.tail = node;
result.length++;
}
}
// 大数减法
void subtract(DoubleLinkedList& num1, DoubleLinkedList& num2, DoubleLinkedList& result) {
int borrow = 0; // 借位
Node* p1 = num1.head;
Node* p2 = num2.head;
while (p1 != NULL || p2 != NULL) {
int x = p1 == NULL ? 0 : p1->data;
int y = p2 == NULL ? 0 : p2->data;
int diff = x - y - borrow;
if (diff < 0) {
diff += 10;
borrow = 1;
} else {
borrow = 0;
}
Node* node = new Node;
node->data = diff;
node->prev = result.tail;
node->next = NULL;
if (result.length == 0) {
result.head = node;
result.tail = node;
} else {
result.tail->next = node;
result.tail = node;
}
if (p1 != NULL) p1 = p1->next;
if (p2 != NULL) p2 = p2->next;
result.length++;
}
while (result.length > 1 && result.tail->data == 0) {
result.tail = result.tail->prev;
delete result.tail->next;
result.tail->next = NULL;
result.length--;
}
}
// 大数乘法
void multiply(DoubleLinkedList& num1, DoubleLinkedList& num2, DoubleLinkedList& result) {
int len1 = num1.length;
int len2 = num2.length;
int len = len1 + len2;
int carry = 0;
for (int i = 0; i < len; i++) {
Node* node = new Node;
node->data = 0;
node->prev = result.tail;
node->next = NULL;
if (result.length == 0) {
result.head = node;
result.tail = node;
} else {
result.tail->next = node;
result.tail = node;
}
}
Node* p1 = num1.head;
Node* p2 = num2.head;
Node* p = result.head;
for (int i = 0; i < len1; i++) {
p2 = num2.head;
p = result.head;
carry = 0;
for (int j = 0; j < len2; j++) {
int x = p1->data;
int y = p2->data;
int prod = x * y + carry + p->data;
p->data = prod % 10;
carry = prod / 10;
p = p->next;
p2 = p2->next;
}
while (carry > 0) {
int sum = carry + p->data;
p->data = sum % 10;
carry = sum / 10;
p = p->next;
}
p1 = p1->next;
}
while (result.length > 1 && result.tail->data == 0) {
result.tail = result.tail->prev;
delete result.tail->next;
result.tail->next = NULL;
result.length--;
}
}
// 大数除法
void divide(DoubleLinkedList& num1, DoubleLinkedList& num2, DoubleLinkedList& result) {
DoubleLinkedList dividend, divisor, quotient;
dividend = num1;
divisor = num2;
quotient.head = new Node;
quotient.head->data = 0;
quotient.head->prev = NULL;
quotient.head->next = NULL;
quotient.tail = quotient.head;
quotient.length = 1;
while (compare(dividend, divisor) >= 0) {
int k = 0;
DoubleLinkedList tmp;
tmp.head = new Node;
tmp.head->data = 0;
tmp.head->prev = NULL;
tmp.head->next = NULL;
tmp.tail = tmp.head;
tmp.length = 1;
while (compare(dividend, multiply(divisor, power(10, k))) >= 0) {
k++;
}
k--;
tmp = multiply(divisor, power(10, k));
while (compare(dividend, tmp) >= 0) {
subtract(dividend, tmp, dividend);
add(quotient, power(10, k), quotient);
}
}
result = quotient;
}
```
5. 实现大数的幂次运算函数。
```c++
// 大数幂次运算
void power(DoubleLinkedList& num, int n, DoubleLinkedList& result) {
result.head = new Node;
result.head->data = 1;
result.head->prev = NULL;
result.head->next = NULL;
result.tail = result.head;
result.length = 1;
while (n > 0) {
if (n % 2 == 1) {
result = multiply(result, num);
}
num = multiply(num, num);
n /= 2;
}
}
```
6. 最后,可以编写一个主函数来测试以上函数的正确性。
```c++
int main() {
DoubleLinkedList num1, num2, result;
input(num1, "123456789012345678901234567890");
input(num2, "987654321098765432109876543210");
add(num1, num2, result);
cout << output(result) << endl;
subtract(num1, num2, result);
cout << output(result) << endl;
multiply(num1, num2, result);
cout << output(result) << endl;
divide(num1, num2, result);
cout << output(result) << endl;
power(num1, 10, result);
cout << output(result) << endl;
return 0;
}
```
以上就是基于双向循环链表的大数计算演示程序。
阅读全文