Python 带节点的链表：找到最小值

Question

我正在尝试为我的 UnorderedList 创建一个 find_min() 方法：class 它应该在列表中找到最小数量。

def find_min(self):
    current = self.head
    previous = None
    found = False
    while not found:
        if current.getData == None:
            found = True
            minimum = "None"
        else: 
    #this is where i got stuck....

如果列表为空，该方法应该 return "None"。我试图使用 Previous 和 Current 横穿节点并将它们相互比较以查看最小值是多少，但它失败了。

我还做了一个 clear/delete_all 方法，但不能正常工作。它应该从列表中清除所有项目并留下一个空列表。

def clear(self):
    current = self.head
    current.setNext(None)
    endOfList = current.getData()
    self.remove(endOfList)

这是我的两个 classes 的其余部分。

class Node:
def __init__(self,initdata):
    self.data = initdata
    self.next = None

def getData(self):
    return self.data

def getNext(self):
    return self.next

def setData(self,newdata):
    self.data = newdata

def setNext(self,newnext):
    self.next = newnext

class UnorderedList:

def __init__(self):
    self.head = None
    self.count = 0

def isEmpty(self):
    return self.head == None

def add(self,item):
    temp = Node(item)
    temp.setNext(self.head)
    self.head = temp

def size(self):
    current = self.head
    count = 0
    while current != None:
        count = count + 1
        current = current.getNext()
    return count

def search(self,item):
    current = self.head
    found = False
    while current != None and not found:
        if current.getData() == item:
            found = True
        else:
            current = current.getNext()
    return found

def remove(self,item):
    current = self.head
    previous = None
    found = False
    while not found:
        if current.getData() == item:
            found = True
        else:
            previous = current
            current = current.getNext()

    if previous == None:
        self.head = current.getNext()
    else:
        previous.setNext(current.getNext())

def __str__(self):
    result = '['
    current = self.head
    while current != None:
        result += str(current.getData()) + ', '
        current = current.getNext()
    result += ']'
    return result

def append(self, item):
    current = self.head
    while current.getNext() != None:
        current = current.getNext()
    current.setNext(Node(item))

def pop(self):
    current = self.head
    found = False
    endOfList = None
    while current != None and not found:
        if current.getNext() == None:
            found = True
            endOfList = current.getData()
            self.remove(endOfList)
        else:
            current = current.getNext()

def clear(self):
    current = self.head
    current.setNext(None)
    endOfList = current.getData()
    self.remove(endOfList)

任何帮助都将非常感谢。

Answer 1

要找到最小值，只需遍历列表即可。您可以使用 float('inf') 作为合理的初始值以便于比较。

def find_min(self):
    next_node = self.head
    if next_node is None:
        return None

    minimum = float('inf')        
    while next_node:
        value = next_node.getData()
        if value < minimum:
            minimum = value

        next_node = next_node.getNext()

    return minimum

清空列表只需要将self.head设置为None即可。垃圾收集器将完成剩下的工作。

def clear(self):
    self.head = None
    self.count = 0

Python 带节点的链表：找到最小值

Python Linked list with Nodes: find minimum

python

linked-list

nodes