设计一个。单链表存储结构,每个节点存储移项的系数和指数类型都是成型编写,完成产生多项式的函数多项式相加及输出多项式的函数。
时间: 2024-09-24 17:11:13 浏览: 36
设计一个单链表用于存储多项式可以按照这样的思路进行:
首先,创建一个`Node`类,它将包含两个属性:`coefficient`(系数)和`exponent`(指数),以及指向下一个节点的指针`next`。这样,链表的每个节点就可以表示多项式中的一个项。
```python
class Node:
def __init__(self, coefficient=0, exponent=0):
self.coefficient = coefficient
self.exponent = exponent
self.next = None
def __str__(self):
return f"{self.coefficient}x^{self.exponent}" if self.coefficient != 0 else "0"
```
接下来,我们需要两个功能函数:
1. `create_polynomial`:用于构建一个多项式链表,接收一个列表,其中元素是元组,每个元组的第一个值是系数,第二个值是指数。
```python
def create_polynomial(coeff_exp_list):
head = None
current = None
for coeff, exp in coeff_exp_list:
new_node = Node(coeff, exp)
if not head:
head = new_node
current = head
else:
current.next = new_node
current = new_node
return head
```
2. `add_poly`:合并两个多项式链表,通过遍历并添加对应系数和指数的项。
```python
def add_poly(poly1_head, poly2_head):
result_head = None
carry = 0
current1 = poly1_head
current2 = poly2_head
while current1 or current2:
coef1 = current1.coefficient if current1 else 0
coef2 = current2.coefficient if current2 else 0
sum_coef = coef1 + coef2 + carry
carry = sum_coef // 10 # 如果有进位,保存到carry
current_sum_coef = sum_coef % 10
new_node = Node(current_sum_coef, max(current1.exponent if current1 else 0, current2.exponent if current2 else 0))
if not result_head:
result_head = new_node
else:
result_head.next = new_node
result_head = result_head.next
if current1:
current1 = current1.next
if current2:
current2 = current2.next
# 如果最后还有进位未处理,追加一个0x10节点
if carry > 0:
new_node = Node(carry, 1)
if result_head:
result_head.next = new_node
else:
result_head = new_node
return result_head
```
3. `output_polynomial`:用于打印链表表示的多项式。
```python
def output_polynomial(head):
polynomial_str = ""
current = head
while current:
polynomial_str += str(current) + ("+" if current is not head else "")
current = current.next
print(polynomial_str.strip("+"))
```
现在你可以用这些函数来创建、相加和显示多项式了。例如:
```python
# 创建两个多项式
poly1 = create_polynomial([(2, 1), (3, 2)])
poly2 = create_polynomial([(1, 0), (4, 3)])
# 相加
result = add_poly(poly1.head, poly2.head)
# 输出结果
output_polynomial(result)
```
阅读全文