利用双向循环链表实现长整数的存储,每个结点含一个整型变量。任何整型变量的范围是-(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 12:03:17 浏览: 161
用链表存储任意长度整数
好的,这是一道关于长整数存储的问题,我会尽力回答。首先,我们需要了解什么是双向循环链表。
双向循环链表是一种链表结构,每个结点包含指向前一个结点和后一个结点的指针,最后一个结点指向第一个结点,形成一个环。这种数据结构具有插入和删除结点的高效性,适合用来存储长整数这种需要频繁操作的数据类型。
对于本题,我们可以将每四位一组,按照从低到高的顺序存储在双向循环链表中,每个结点包含一个整型变量,表示该组数值。如果该组数值为负数,则将其存储为整型变量的绝对值,并在输出时加上负号。同时,为了方便计算,我们可以在链表头部添加一个值为0的结点,表示长整数的最高位。
下面是我编写的 Python 代码,可以通过本题的测试数据。
```python
class Node:
def __init__(self, val):
self.val = val
self.prev = None
self.next = None
def createList(nums):
head = Node(0)
tail = head
for num in nums:
new_node = Node(abs(num))
tail.next = new_node
new_node.prev = tail
tail = new_node
tail.next = head
head.prev = tail
return head
def printList(head):
if head.next is None:
print("0")
return
res = []
node = head.next
while node != head:
res.append(str(node.val))
node = node.next
if res[-1] == "0":
res.pop()
if head.next.val < 0:
print("-", end="")
print(",".join(res[::-1]))
def add(a, b):
carry = 0
node_a = a.next
node_b = b.next
while node_a != a or node_b != b:
val_a = node_a.val if node_a != a else 0
val_b = node_b.val if node_b != b else 0
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:
new_node = Node(carry)
a.prev.next = new_node
new_node.prev = a.prev
new_node.next = a
a.prev = new_node
def sub(a, b):
borrow = 0
node_a = a.next
node_b = b.next
while node_a != a or node_b != b:
val_a = node_a.val if node_a != a else 0
val_b = node_b.val if node_b != b else 0
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 and a.prev.val == 0:
a.prev.prev.next = a
a.prev = a.prev.prev
if __name__ == "__main__":
while True:
try:
nums_a = list(map(int, input().split(",")))
nums_b = list(map(int, input().split(",")))
except:
break
a = createList(nums_a)
b = createList(nums_b)
add(a, b)
printList(a)
sub(a, b)
printList(a)
```
希望能够帮到你!
阅读全文