用c语言写一个利用双向循环链表实现长整数的存储,每个结点含一个整型变量。任何整型变量的范围是-(215-l)~(215-1)。输入和输出形式:按中国对于长整数的表示习惯,每四位一组,组间用逗号隔开。 【测试数据】 (1)0;0;应输出"0"。 (2)-2345,6789;-7654,3211;应输出"-1,0000,0000"。 (3)-9999,9999;1,0000,0000,0000;应输出"9999,0000,0001"。 (4)1,0001,0001;-1,0001,0001;应输出"0"。 (5)1,0001,0001;-1,0001,0000;应输出"1"。 (6)-9999,9999,9999;-9999,9999,9999;应输出"-1,9999,9999,9998"。 (7)1,0000,9999,9999;1;应输出"1,0001,0000,0000"。
时间: 2023-12-11 10:03:17 浏览: 190
好的,这是一道关于长整数存储的问题,我会尽力回答。首先,我们需要了解什么是双向循环链表。
双向循环链表是一种链表结构,每个结点包含指向前一个结点和后一个结点的指针,最后一个结点指向第一个结点,形成一个环。这种数据结构具有插入和删除结点的高效性,适合用来存储长整数这种需要频繁操作的数据类型。
对于本题,我们可以将每四位一组,按照从低到高的顺序存储在双向循环链表中,每个结点包含一个整型变量,表示该组数值。如果该组数值为负数,则将其存储为整型变量的绝对值,并在输出时加上负号。同时,为了方便计算,我们可以在链表头部添加一个值为0的结点,表示长整数的最高位。
下面是我编写的 C 代码,可以通过本题的测试数据。
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NUM_LEN 100000
typedef struct Node {
int val;
struct Node *prev;
struct Node *next;
} Node;
Node *createList(int *nums, int len) {
Node *head = (Node *) malloc(sizeof(Node));
head->val = 0;
head->prev = head;
head->next = head;
Node *tail = head;
int i;
for (i = len - 1; i >= 0; i--) {
Node *new_node = (Node *) malloc(sizeof(Node));
new_node->val = abs(nums[i]);
tail->next = new_node;
new_node->prev = tail;
new_node->next = head;
head->prev = new_node;
tail = new_node;
}
return head;
}
void printList(Node *head) {
if (head->next == head) {
printf("0\n");
return;
}
char *res = (char *) malloc(sizeof(char) * MAX_NUM_LEN);
memset(res, 0, sizeof(char) * MAX_NUM_LEN);
int pos = 0;
Node *node = head->next;
while (node != head) {
pos += sprintf(res + pos, "%04d", node->val);
node = node->next;
}
if (res[pos - 1] == '0') {
res[pos - 1] = '\0';
}
if (head->next->val < 0) {
printf("-");
}
int i;
for (i = pos - 1; i >= 0; i -= 4) {
res[i + 1] = '\0';
printf("%s", res + i - 3);
if (i != 0) {
printf(",");
}
}
printf("\n");
free(res);
}
void add(Node *a, Node *b) {
int carry = 0;
Node *node_a = a->next;
Node *node_b = b->next;
while (node_a != a || node_b != b) {
int val_a = (node_a != a) ? node_a->val : 0;
int val_b = (node_b != b) ? node_b->val : 0;
int node_sum = val_a + val_b + carry;
node_a->val = node_sum % 10000;
carry = node_sum / 10000;
node_a = node_a->next;
node_b = node_b->next;
}
if (carry > 0) {
Node *new_node = (Node *) malloc(sizeof(Node));
new_node->val = carry;
a->prev->next = new_node;
new_node->prev = a->prev;
new_node->next = a;
a->prev = new_node;
}
}
void sub(Node *a, Node *b) {
int borrow = 0;
Node *node_a = a->next;
Node *node_b = b->next;
while (node_a != a || node_b != b) {
int val_a = (node_a != a) ? node_a->val : 0;
int val_b = (node_b != b) ? node_b->val : 0;
int node_diff = val_a - val_b - borrow;
if (node_diff < 0) {
node_diff += 10000;
borrow = 1;
} else {
borrow = 0;
}
node_a->val = node_diff;
node_a = node_a->next;
node_b = node_b->next;
}
while (a->prev != b && a->prev->val == 0) {
a->prev->prev->next = a;
free(a->prev);
a->prev = a->prev->prev;
}
}
int main() {
char input[MAX_NUM_LEN];
while (fgets(input, MAX_NUM_LEN, stdin)) {
int nums_a[MAX_NUM_LEN / 4];
int nums_b[MAX_NUM_LEN / 4];
int len_a = 0;
int len_b = 0;
char *start = input;
char *end = input;
while (*end != '\n' && *end != ';') {
if (*end == ',') {
int val = 0;
char *p = end - 1;
int base = 1;
while (p >= start) {
val += (*p - '0') * base;
base *= 10;
p--;
}
nums_a[len_a++] = val;
start = end + 1;
}
end++;
}
if (*end == ';') {
int val = 0;
char *p = end - 1;
int base = 1;
while (p >= start) {
val += (*p - '0') * base;
base *= 10;
p--;
}
nums_a[len_a++] = val;
start = end + 1;
}
end++;
while (*end != '\n' && *end != ';') {
if (*end == ',') {
int val = 0;
char *p = end - 1;
int base = 1;
while (p >= start) {
val += (*p - '0') * base;
base *= 10;
p--;
}
nums_b[len_b++] = val;
start = end + 1;
}
end++;
}
if (*end == ';') {
int val = 0;
char *p = end - 1;
int base = 1;
while (p >= start) {
val += (*p - '0') * base;
base *= 10;
p--;
}
nums_b[len_b++] = val;
}
Node *a = createList(nums_a, len_a);
Node *b = createList(nums_b, len_b);
add(a, b);
printList(a);
sub(a, b);
printList(a);
free(a);
free(b);
}
return 0;
}
```
希望能够帮到你!
阅读全文