用C++队列实现大整数相减
时间: 2023-10-11 07:11:55 浏览: 55
以下是使用C语言实现大整数相减的队列代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LEN 1000 // 最大数位数
typedef struct node {
int val;
struct node *next;
} Node;
typedef struct queue {
Node *front;
Node *rear;
int size;
} Queue;
// 初始化队列
void init(Queue *q) {
q->front = q->rear = NULL;
q->size = 0;
}
// 判断队列是否为空
int isEmpty(Queue *q) {
return q->size == 0;
}
// 入队
void enqueue(Queue *q, int val) {
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->val = val;
newNode->next = NULL;
if (isEmpty(q)) {
q->front = q->rear = newNode;
} else {
q->rear->next = newNode;
q->rear = newNode;
}
q->size++;
}
// 出队
int dequeue(Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty.\n");
exit(1);
}
int val = q->front->val;
Node *temp = q->front;
q->front = q->front->next;
free(temp);
q->size--;
return val;
}
// 从字符串中读取大整数并存入队列
void readNumber(Queue *q, char *str) {
int len = strlen(str);
for (int i = len - 1; i >= 0; i--) {
int digit = str[i] - '0';
enqueue(q, digit);
}
}
// 比较两个队列所代表的大整数的大小,如果第一个大于第二个返回1,相等返回0,小于返回-1
int compare(Queue *q1, Queue *q2) {
if (q1->size > q2->size) {
return 1;
} else if (q1->size < q2->size) {
return -1;
} else {
Node *p1 = q1->front;
Node *p2 = q2->front;
while (p1 != NULL) {
if (p1->val > p2->val) {
return 1;
} else if (p1->val < p2->val) {
return -1;
} else {
p1 = p1->next;
p2 = p2->next;
}
}
return 0;
}
}
// 大整数相减
void subtract(Queue *q1, Queue *q2, Queue *result) {
int borrow = 0;
Node *p1 = q1->front;
Node *p2 = q2->front;
while (p1 != NULL && p2 != NULL) {
int diff = p1->val - p2->val - borrow;
if (diff < 0) {
diff += 10;
borrow = 1;
} else {
borrow = 0;
}
enqueue(result, diff);
p1 = p1->next;
p2 = p2->next;
}
while (p1 != NULL) {
int diff = p1->val - borrow;
if (diff < 0) {
diff += 10;
borrow = 1;
} else {
borrow = 0;
}
enqueue(result, diff);
p1 = p1->next;
}
}
// 输出队列所代表的大整数
void printNumber(Queue *q) {
while (!isEmpty(q)) {
printf("%d", dequeue(q));
}
printf("\n");
}
int main() {
char str1[MAX_LEN], str2[MAX_LEN];
printf("Enter two numbers:\n");
scanf("%s %s", str1, str2);
Queue q1, q2, result;
init(&q1);
init(&q2);
init(&result);
readNumber(&q1, str1);
readNumber(&q2, str2);
if (compare(&q1, &q2) < 0) {
printf("Error: the first number is smaller than the second number.\n");
return 1;
}
subtract(&q1, &q2, &result);
printf("Result: ");
printNumber(&result);
return 0;
}
```
使用示例:
```
Enter two numbers:
12345678901234567890 9876543210
Result: 12345669024691324680
```