5

宿題として、カスタム リンク リストの格納メソッドを作成するように求められました。再帰的メソッドには基本ケースと再帰的ケースが必要であることはわかっていますが、メソッドの再帰的ケースの記述方法を理解するのに苦労しています。これまでのところ、これは私が書いたものですが、私のコードは基本ケースを複数回実行しています。ご案内をお願いできますか？

public class OrderedList {

private Node first;

//Constructor
public OrderedList() {
    this.first = null;
}

//Return the number of items in the list
public int size() {
    int counter = 0;
    Node pointer = this.first;
    while (pointer != null) {
        counter++;
        pointer = pointer.next;
    }
    return counter;
}

//Return an array of copies of the stored elements
public Comparable[] getStore() {

    Comparable[] elements = new Comparable[size()];
    Node pointer = this.first;
    if (this.first == null) {
        return elements;
    } else {
        int i = 0;
        while (pointer != null) {
            elements[i] = pointer.data;
            pointer = pointer.next;
            i++;
        }
        return elements;
    }

}
//true iff item matches a stored element
//Recursive

public boolean contains(Comparable item) {

    //Base case
    if (this.first == null) {

        return false;
    }
    Node pointer = this.first;
    this.first = this.first.next;

    if (pointer.data.compareTo(item) == 0) {

        return true;

    } 
    //Recursive case

    else {

        boolean info = contains(item);
        pointer.next = this.first;
        this.first = pointer;

        return info;
    }
}
4

3 に答える 3

3

まず第一に、私は次のようなことをするのが好きです:

public boolean contains(Comparable item)
{
     return containsHelper(this.first, Comparable item);
}

private boolean containsHelper(Node node, Comparable item)
{
    //base case
    if(node == null)
    {   
         return false;
    }
    else
    {
         if(node.data.compareTo(item) == 0)
         {
             return true;
         }

         return containsHelper(node.next, item);
    }


}

これにより、実装の詳細がユーザーから隠され、そのメソッドを実行したときにリストが上書きされなくなります。

于 2013-07-22T18:21:15.263 に答える
0

私が見ているところによると、else ステートメントが 1 回実行されると、コードは true を返します。再帰はwhileループと非常によく似ており、値が更新されない場合、基本ケースが何度も実行されるため、ブール値を毎回falseに設定する必要があると思います。

于 2013-07-22T18:23:47.303 に答える