Python; 链表与遍历！

Question

我现在在学校开始学习Python编程，但对这个问题不知道该怎么解决。有没有什么想法？

输入是一系列用换行符分开的整数。你的程序需要把这些数字放到一个链表里，然后遍历这个链表，找出最大的数字并打印出来。

可以先拿第一个数字，然后进行一个操作：如果下一个数字更大，就把下一个数字拿过来；如果不是，就继续保持当前的数字，然后继续往下看，重复这个过程。

当到达链表的末尾时，就打印出你找到的那个值。

from sys import stdin

class Kubbe:
    vekt = None
    neste = None
    def __init__(self, vekt):
        self.vekt = vekt 
        self.neste = None 

def spor(kubbe):
    # WRITE YOUR CODE HERE
    # Creates linked list
    forste = None
    siste = None
    for linje in stdin:
        forrige_siste = siste
        siste = Kubbe(int(linje))
        if forste == None:
            forste = siste
        else:
            forrige_siste.neste = siste

# Calls the solution function and prints the result
print spor(forste)

输入：示例

54
37
100
123
1
54

需要的输出

123

Answer 1

在Python中，有一个内置的函数叫做 reduce，它可以遍历一个列表，并用你给定的函数对这个列表进行“压缩”。简单来说，如果你有一个包含五个元素的列表 [a,b,c,d,e] 和一个函数 f，它实际上会这样做：

temp = f(a,b)
temp = f( temp, c )
...

你可以利用这个函数写出一个非常简洁的解决方案。

如果你想让这个过程更容易理解，你需要逐个遍历列表中的每个元素，同时在一个变量中存储到目前为止最大的数字。只有当你当前的元素大于这个变量的值时，才更新这个变量。

Answer 2

这是根据你自己的代码和语言给出的一个回答。抱歉如果新的变量和函数名称翻译得不好，因为我不会说挪威语（谷歌翻译工具是我的好帮手）。

评论：就像飞机的空中交通管制一样，大多数国际编程论坛，比如StackOverflow，默认的语言是英语。如果你使用英语，通常能更快得到更好更多的回答——而且这也可能让问题和相关的回答对更多人有用。这只是我的一点看法... ;-)

from sys import stdin

class Kubbe:
    vekt = None
    neste = None
    def __init__(self, vekt):
        self.vekt = vekt
        self.neste = None

def spor():
    # WRITE YOUR CODE HERE
    # Creates linked list
    forste = None
    siste = None
    while True:
        try:
            linje = raw_input()
        except EOFError:
            break
        forrige_siste = siste
        siste = Kubbe(int(linje))
        if forste == None:
            forste = siste
        else:
            forrige_siste.neste = siste
    return forste

def finne_maksimal(lenketliste):
    storste = None
    if lenketliste is not None:
        storste = lenketliste.vekt
        gjeldende = lenketliste.neste
        while gjeldende is not None:
            if gjeldende.vekt > storste:
                storste = gjeldende.vekt
            gjeldende = gjeldende.neste
    return storste

lenketliste = spor()
storste = finne_maksimal(lenketliste)
if lenketliste is None:
    print "tom liste"
else:
    print "storste er", storste

Answer 3

在Python中，“链表”很少被使用，通常我们只用list，也就是Python自带的列表，它其实更像是一个“动态数组”。所以在这个练习的要求中看到链表，确实有点奇怪。

不过重点是，你展示的代码其实已经在创建一个链表了——链表的头节点在forste，每个节点的下一个节点指针在.neste，而节点的内容在.vekt。所以，假设这不是你想问的内容，不管你问题的文字怎么写。

一旦你完全构建好了链表（也就是说，在当前spor代码的最后），简单的方法来遍历这个链表是：

current = forste
while current is not None:
   ...process current.vekt...
   current = current.neste

在你的情况下，“处理”部分的逻辑，当然就像你问题的文字已经说的那样：

   if current.vekt > themax:
       themax = current.vekt

唯一需要注意的是，你需要在这个while循环之前，先把themax设置为“可能的最小数字”；在最近的Python版本中，“负无穷大”是可以可靠地记录和比较的（虽然它只是浮点数，但仍然可以正确地与整数比较），所以：

themax = float('-inf')

这样做是可以的。更优雅的做法可能是把最大值初始设置为第一个节点的内容，这样就不用去处理无穷大了。