Python中的链表作业

Question

我必须为我的作业做以下事情：

1. 假设您的链表不为空，并且由变量头指向。编写一个名为 findMin(( 的方法，该方法遍历列表并找到最小值(您可以像数字一样比较字符串(并返回该值。

2. 假设您的链表不为空，并且由变量头指向。编写一个名为 getLast(( 的方法，该方法遍历列表并返回列表中的最后一件事。这是链表链中最后一个节点的值。

3. 完成追加方法。它运行到最后，并将新节点附加到链中的最后一个现有节点。如果链中还没有节点，它将 self.head 设置为该节点。小心！这很棘手！你可以查阅你的教科书。

我

试图解决第一个，但我只是迷路了，我不知道我是否弄乱了类结构还是什么(我刚刚在 3 天前学习课程(

这是我的尝试...

 class LinkedList:
class Node:
    def __init__(self,value):
        self.value = value
        self.next  = none
def __init__(self):
    self.head = None
def findMin(self):
    currentNode = self.head
    minNode = self.head
    while currentNode != none:
        if currentNode.next < currentNode:
            minNode = currentNode
            currentNode = currentNode.next
    return minNode

Answer 1

正如@mgilson评论中提到的，有很多错误，并不是全部列出。

我认为你会从写(在评论中，为什么不写(你认为每行正在做的事情中受益匪浅。

让我们从

 currentNode = self.head

我认为这是试图说"让我们从列表的开头开始，通过设置 currentNode 来指向它"。

如前所述，这似乎是在访问当前节点的成员变量，称为"head"。 但是 Node 类定义没有一个名为 head 的已定义成员！ 和。。。你为什么需要这样做？ 您被告知"当前节点是头部"！

所以你可能的意思是

currentNode = self  # start at the head of the list

下一个：

minNode = self.head

这是说"具有当前已知最小值的节点存储在此节点中">

和以前一样，您可能意味着：

minNode = self # The head currently has the minimum we know about

然后：

while currentNode != none:

首先，如果您使用语法突出显示编辑器，它会立即告诉您"None"具有大写的"N"。

这里没有其他问题。

然后：

    if currentNode.next < currentNode:
        minNode = currentNode
        currentNode = currentNode.next

这是试图说"如果下一个节点的值小于这个节点的值，那么最小值现在是......"实际上是什么？ 说是现在的！ 但事实并非如此：如果这个 if 语句为真，那么下一个语句包含最小值！ 等等，我们不应该与minNode进行比较，而不是当前节点吗？

好像你的意思是

    if currentNode.value < minNode.value:
        minNode = currentNode    # this node is now the smallest we know about

下一行需要在 if 循环之外，因为它将我们移动到下一个节点：

    currentNode = currentNode.next  # move on to the next node

呼，快到了：现在我们必须返回最小值，而不是具有最小值的节点(请仔细阅读说明。

 return minNode.value

呵

呵

Answer 2

好的，让我们做这个功课！

让Node成为一个列表单元格。它有两个字段value和next(在函数式语言中也称为car/cdr或head/tail(。

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

append(node, other)可以定义如下：如果node没有"下一个"节点(即它是最后一个(，则other右附加到此node。否则，获取"下一个"节点，并将other附加到该节点：

    def append(self, other):
        if self.next:
            self.next.append(other)
        else:
            self.next = other

现在让我们定义两个基本函数：map 和 reduce 。 map按顺序将函数应用于每个节点，并返回结果列表：

    def map(self, fn):
        r = [fn(self.value)]
        if self.next:
            r += self.next.map(fn)
        return r

reduce 将函数应用于每个节点，并将结果合并到单个值中：

    def reduce(self, fn, r=None):
        if r is None:
            r = self.value 
        else:
            r = fn(r, self.value)
        if self.next:
            return self.next.reduce(fn, r)
        return r

现在你已经准备好做作业了。

创建列表：

lst = Node(1)
lst.append(Node(8))
lst.append(Node(3))
lst.append(Node(7))

打印所有值：

print lst.map(lambda x: x)

查找最后一个值：

print lst.reduce(lambda r, x: x)

找到最大值：

print lst.reduce(max)

等

如果您有任何疑问，请告诉我们。