-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 に答える