使用链表求和偶数吗？

Question

我一直在尝试在Python中使用链表来计算一个列表中所有偶数的总和。我觉得我已经写好了链表的部分代码，但我不知道怎么才能只取出偶数并把它们加起来。现在我的代码大概是这样的：

def createList(plist):
    linkedList = None
    # goes backwards, adding each element to the beginning
    # of the list.  
    for index in range(len(plist)-1, -1, -1):
        linkedList = insertValueHead(linkedList, plist[index])
    return linkedList

def sumEvens(linkedList): #This is what I'm looking for help with
    ....


def testSumEvens():
    myList = createList([14, 21, 29, 2, 16, 49, -26])
    print "The sum of the even numbers in the first list is ", sumEvens(myList)
    myList = createList([])
    print "The sum of the even numbers in an empty list is ", sumEvens(myList)
    myList = createList([5, 15, 25])
    print "The sume of the even numbers in the final list is ", sumEvens(myList)

我该怎么做才能让这个代码计算出这些列表的总和呢？比如在第一个列表中，14 + 2 + 16？

Answer 1

使用你在之前的问题中提到的insertValueHead，你可以这样实现sumEvens：

def sumEvens(linkedList):
    if linkedList is not None:
        val = linkedList["data"]
        return (val if val % 2 == 0 else 0) + sumEvens(linkedList["next"])
    return 0

这个代码的作用是：它会检查当前的列表是否为空，如果不为空，就获取数据的值，然后检查这个值是否是偶数，最后递归地返回这个值和列表剩余部分的和。

不过，看到你把列表实现成一个嵌套字典，里面有'data'和'next'这两个部分，我建议你使用一个类来实现，这样可以更好地调整你其他的方法。

class LinkedList:
    def __init__(self, head, tail):
        self.head = head
        self.tail = tail
    def __repr__(self):
        return "LinkedList(%r, %r)" % (self.head, self.tail)

def insertValueHead(linkedList, value):
    return LinkedList(value, linkedList)

def sumEvens(linkedList):
    if linkedList is not None:
        val = linkedList.head
        return (val if val % 2 == 0 else 0) + sumEvens(linkedList.tail)
    return 0

Answer 2

你可以创建一个生成器，它会逐个遍历你的列表：

def iter_list(xs):
    while xs is not None:
        yield get_head(xs)
        xs = get_tail(xs)

这里假设你已经在你的链表类型上定义了可以获取第一个元素（头部）和其余元素（尾部）的函数。

然后你可以用这个生成器来计算偶数元素的总和：

def sum_evens(xs):
    return sum(x for x in iter_list(xs) if x % 2 == 0)

Answer 3

@filmor说得对..

这就是你需要的吗？

def createList(*args):
    new_list=[]

    for arg in args: 
        new_list.append(arg)

    return new_list

def sumEvens(List):

    if List:
        return sum(x for x in List if x % 2 == 0)
    else:
        return "0"


def testSumEvens():
    myList = createList(14, 21, 29, 2, 16, 49, -26)

    print "The sum of the even numbers in the first list is {0}".format(sumEvens(myList))
    myList = createList()
    print "The sum of the even numbers in an empty list is {0}".format(sumEvens(myList))
    myList = createList(5, 15, 25)
    print "The sum of the even numbers in the final list is {0}".format(sumEvens(myList))

testSumEvens()