python - Python链表合并排序不起作用
问题描述
我有一个我已经工作了一段时间的 uni 任务,但我似乎无法弄清楚出了什么问题。目标是将两个已排序的链表合并为一个排序的链表。
唯一允许我更改的函数是 merge(a,b) 函数。我三重检查,但我不断收到以下错误:
in __repr__
out += str(node.weight)
AttributeError: 'ItemList' object has no attribute 'weight'
有没有人可以弄清楚我应该改变什么?我很失落。
我的代码:
from __future__ import annotations
from typing import Optional
from dataclasses import dataclass
@dataclass
class Node:
weight: float
link: Optional[Node] = None
def merge(a: ItemList, b: ItemList) -> c:
"""
This function takes two linked lists, assumed sorted, and merges them
in-place, without creating new Nodes, just by changing the links.
"""
# create a new ItemList and dummynode as head:
c = ItemList()
c.head = Node(0)
# List1 is empty then return b
if a.head is None:
c._length += len(b)
b._length -= len(b)
return b
# if List2 is empty then return a
if b.head is None:
c._length += len(a)
a._length -= len(a)
return a
# If the weight of the element of a is smaller or equal to b's weight
if a.head.weight <= b.head.weight:
# We assign the weight of a's head to the head of c
c.head.weight = a.head.weight
#Give list a a new head (depletion) and subtract one from the length of a
a.head = a.head.link
a._length -= 1
# We will go through the algorithm again (recursively) to check for the element next-in-line.
c.head.link = merge(a, b)
# If the weight of the element of a is smaller or equal to b's weight
else:
# We assign the weight of a's head to the head of c
c.head.weight = b.head.weight
#Give list b a new head (depletion) and subtract one from the length of b
b.head = b.head.link
b._length -= 1
# We will go through the algorithm again (recursively) to check for the element next-in-line.
c.head.link = merge(a, b)
# return the merged list
return c
class ItemList:
head: Optional[Node]
def __init__(self):
"""Initialize an empty linked list for warehouse items."""
self.head = None
self._length = 0
def __len__(self) -> int:
return self._length
def insert(self, val: int) -> ItemList:
"""Insert a new item with given weight, at the beginning of the list"""
new_node = Node(weight=val, link=self.head)
self.head = new_node
self._length += 1
return self
def __repr__(self):
"""This function prints the list in a nice way."""
node = self.head
out = "["
while node is not None:
out += str(node.weight)
if node.link is not None:
out += ", "
node = node.link
out += "]"
return out
warehouse = (
ItemList()
.insert(8)
.insert(6)
.insert(4)
.insert(2)
.insert(0)
)
warehouse2 = (
ItemList()
.insert(9)
.insert(7)
.insert(5)
.insert(3)
.insert(1)
)
print(merge(warehouse,warehouse2))
解决方案
你可以写一个递归mergeNodes
函数:
def mergeNodes(a: Node, b: Node):
"""
This function takes two linked lists of Nodes, assumed sorted, and
merges them into a single linked list of Nodes, in-place, without
creating new Nodes, just by changing the links.
"""
if a is None:
return b
if b is None:
return a
if a.head.weight <= b.head.weight:
a.link = mergeNodes(a.link, b)
return a
else
b.link = mergeNodes(a, b.link)
return b
合并列表变得非常简单:
def merge(a: ItemList, b: ItemList) -> ItemList:
"""
This function takes two ItemList objects, assumed sorted, and merges them
into a new ItemList, without creating new Nodes, just by changing the links.
the original objects are destroyed
"""
# create a new ItemList:
c = ItemList()
c._length = a._length + b._length;
c.head = mergeNodes(a.head, b.head)
# clear the original lists because the links are no longer consistent
a._length = 0
a.head = None
b._length = 0
b.head = None
return c
请注意,它merge
应该是类的方法,ItemList
并将作为参数传递的列表合并到self
.
推荐阅读
- python - 姜戈。在 ckeditor 编辑器中显示 HTML 元素
- json - 自定义 Api 响应并稍后在其他 React 组件上使用它
- sql - 如何优化这个 sql server 更新请求
- java - 一个非常简单的案例在 IBM i 中不使用 itext 写入 pdf 文件
- sql - SQL Select - Get a count of data as a separate column error
- powershell - 通过 Powershell 使用 -- 参数运行批处理填充
- c++ - 我可以期待多线程的“现实世界”性能改进是什么?
- python - 如何区分蓝色(圆形)和其他(任意方向的矩形/多边形)类型的轮廓
- javascript - Stripe Checkout 会话将优惠券应用于一次性费用而不是订阅
- f# - 具有类型约束的泛型类上的 F# 模式匹配