C++用链表实现大整数加减法操作: 用链表每个结点存储大整数的每一位的十进制数字。 要求: 1, 随机产生 2 个 1~50 位的数字串,并存储到 2 个链表中。 2, 进行加法或减法操作,结果存储到新的链表中。 3, 打印运算结果。
时间: 2023-05-26 20:05:14 浏览: 111
实现代码如下:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_LENGTH 50 // 最大位数
typedef struct Node {
int digit; // 当前结点存储的数字
struct Node* next; // 下一个结点指针
} Node;
/**
* 创建一个新的结点并返回其指针
*/
Node* new_node(int digit, Node* next) {
Node* node = (Node*) malloc(sizeof(Node));
node->digit = digit;
node->next = next;
return node;
}
/**
* 创建一个长度为 length 的随机大整数并返回其链表表示
*/
Node* random_integer(int length) {
Node* head = NULL;
for (int i = 0; i < length; i++) {
int digit = rand() % 10; // 生成 0~9 的随机数
head = new_node(digit, head);
}
return head;
}
/**
* 打印一个大整数的链表表示
*/
void print_integer(Node* head) {
if (head == NULL) {
printf("0");
return;
}
Node* current = head;
while (current != NULL) {
printf("%d", current->digit);
current = current->next;
}
}
/**
* 将两个正整数相加并返回结果链表
*/
Node* add_integer(Node* a, Node* b) {
Node* result = NULL; // 结果链表
int carry = 0; // 进位
while (a != NULL || b != NULL || carry > 0) {
int digit_a = a == NULL ? 0 : a->digit;
int digit_b = b == NULL ? 0 : b->digit;
int sum = digit_a + digit_b + carry;
int digit = sum % 10;
carry = sum / 10;
result = new_node(digit, result);
if (a != NULL) a = a->next;
if (b != NULL) b = b->next;
}
return result;
}
/**
* 将两个正整数相减并返回结果链表
*/
Node* subtract_integer(Node* a, Node* b) {
Node* result = NULL; // 结果链表
int borrow = 0; // 借位
while (a != NULL || b != NULL) {
int digit_a = a == NULL ? 0 : a->digit;
int digit_b = b == NULL ? 0 : b->digit;
int diff = digit_a - digit_b - borrow;
int digit = (diff + 10) % 10;
borrow = diff < 0 ? 1 : 0;
result = new_node(digit, result);
if (a != NULL) a = a->next;
if (b != NULL) b = b->next;
}
// 删除结果链表前导零
while (result != NULL && result->digit == 0) {
Node* temp = result;
result = result->next;
free(temp);
}
return result;
}
int main() {
srand((unsigned int) time(NULL)); // 初始化随机种子
Node* a = random_integer(rand() % MAX_LENGTH + 1); // 随机生成一个大整数 a
Node* b = random_integer(rand() % MAX_LENGTH + 1); // 随机生成一个大整数 b
printf("a = ");
print_integer(a);
printf("\n");
printf("b = ");
print_integer(b);
printf("\n");
Node* c = add_integer(a, b); // 将 a 和 b 相加
Node* d = subtract_integer(a, b); // 将 a 和 b 相减
printf("a + b = ");
print_integer(c);
printf("\n");
printf("a - b = ");
print_integer(d);
printf("\n");
free(a); // 释放 a 所占用的内存
free(b); // 释放 b 所占用的内存
free(c); // 释放 c 所占用的内存
free(d); // 释放 d 所占用的内存
return 0;
}