编程实现计算2个高精度正整数的和。以单链表作为高精度整数的存储结构,头结点后的第一个结点存放个位数(最低位),第二个结点存放士位数,第三个结点存放百位数,以此类推。利用栈实现从高位数到低位数 (逆向)的数据输入和输出。
时间: 2024-01-22 20:18:02 浏览: 56
以下是使用单链表和栈实现高精度正整数相加的Python代码:
```python
class Node:
def __init__(self, val=0, nxt=None):
self.val = val
self.next = nxt
class Stack:
def __init__(self):
self.stack = []
def push(self, val):
self.stack.append(val)
def pop(self):
return self.stack.pop()
def is_empty(self):
return len(self.stack) == 0
def addTwoNumbers(head1: Node, head2: Node) -> Node:
# 先将两个链表的值放入栈中,从低位到高位
stack1, stack2 = Stack(), Stack()
while head1:
stack1.push(head1.val)
head1 = head1.next
while head2:
stack2.push(head2.val)
head2 = head2.next
# 进行相加操作,注意进位
carry = 0
res = None
while not stack1.is_empty() or not stack2.is_empty() or carry:
num1 = stack1.pop() if not stack1.is_empty() else 0
num2 = stack2.pop() if not stack2.is_empty() else 0
total = num1 + num2 + carry
carry = total // 10
curr = Node(total % 10, res)
res = curr
return res
```
在代码中,我们定义了一个 `Node` 类来表示链表的节点,每个节点包含一个值和一个指向下一节点的指针。另外,我们还定义了一个 `Stack` 类来表示栈结构,它包含一个列表作为栈的实现。
在 `addTwoNumbers` 函数中,我们先将输入的两个链表的值从低位到高位依次放入栈中,然后从栈中依次取出值进行相加操作,注意进位。最后再将结果放入链表中返回即可。
阅读全文