-2

我正在寻找一个返回不包含特定节点的链表的函数。

这是一个示例实现：

Nil = None                  # empty node

def cons(head, tail=Nil):
    """ Extends list by inserting new value. """
    return (head, tail)

def head(xs):
    """ Returns the frst element of a list. """
    return xs[0]

def tail(xs):
    """ Returns a list containing all elements except the first. """
    return xs[1]

def is_empty(xs):
    """ Returns True if the list contains zero elements """
    return xs is Nil

def length(xs):
    """                                                                                                                                                                               
    Returns number of elements in a given list. To find the length of a list we need to scan all of its                                                                               
    elements, thus leading to a time complexity of O(n).                                                                                                                              
    """
    if is_empty(xs):
        return 0
    else:
        return 1 + length(tail(xs))

def concat(xs, ys):
    """ Concatenates two lists. O(n) """
    if is_empty(xs):
        return ys
    else:
        return cons(head(xs), concat(tail(xs), ys))

如何实现一个remove_item功能？

4

2 回答 2

2 
def remove_item(xs, value):
    if is_empty(xs):
        return xs
    elif head(xs) == value:
        return tail(xs) # or remove_item(tail(xs), value) to remove all
    else:
        return cons(head(xs), remove_item(tail(xs), value))

注意：我不是 Lisp 程序员，我不一定以最好的方式做到这一点。

[编辑：我可能误解了您删除特定节点的意思。如果您从后缀xs而不是值 in开始，xs则原理相同，但涉及的测试value不同]

于 2013-10-14T13:26:40.507 回答
0

如果你想要一个尾递归解决方案，你可以说：

def remove_item(xs, value):
  before_rev, after = split_remove(Nil, xs, value)
  return reverse_append(before_rev, after)

def reverse_append(a, b):
  if is_empty(a):
    return b
  else:
    return reverse_append(tail(a), cons(head(a),b))

def split_remove(before_rev, xs, value):
  if is_empty(xs):
    return (before_rev, xs)
  elif head(xs) == value:
    return (before_rev, tail(xs))
  else:
    return split_remove(cons(head(xs), before_rev), tail(xs), value)

虽然不知道 Python 有没有做尾调用优化

于 2014-04-17T20:48:46.033 回答