2

割り当てと1つの要件のリンクリストの作成に取り組んでいるのは、リストパラメータを受け取り、それを現在のリストの最後に追加するconcatという名前のメソッドです。このメソッドで再帰を使用する必要はありませんが、プログラムでは再帰を多用することになっています。このための再帰的アルゴリズムを考え出すことさえ可能かどうか疑問に思っています。私たちのリストクラスにはヘッドノードしかなく、他には何もありません。また、それらは二重にリンクされていません。

私の現在の試みでは、最初の値を再帰的に追加することしかできません。何が悪いのかはわかっていますが、解決策を思い付くことができません。最初のメソッドは、リストが「連結」に渡されるリストで実際に呼び出される方法です。次に、リストの末尾を見つけて、これらを再帰メソッドに渡そうとします。この「ラッパー」メソッドは、再帰メソッドの必須要件です。これが私の試みですが、すべての呼び出しがスタックから外れ、concatへの再帰呼び出しを再入力すると、ノード参照 "pt"をリスト内の次のノードに進めるのに問題があるため、明らかに失敗しています。これが再帰で可能ですが、この値を最初のリストに進めて再帰呼び出しを再入力する方法、またはこの問題に対するより一般的なアプローチについて教えてください。御時間ありがとうございます。

public void concat(MyString list1) {
    CharacterNode tail = null, pt = list1.head;
    // Find the tail of the list
    if (pt == null) {
    } else if (pt.getNext() == null) {
        tail = pt;
    } else {
        while (pt.getNext() != null) {
            pt = pt.getNext();
        }
        tail = pt;
    }
    list1.head = concat(list1.head, tail, list1.head);
}
private static CharacterNode concat(CharacterNode lhead, CharacterNode tail, CharacterNode pt) {
    // Pass in smaller list every time
    // Head traverses down list till the end
    // Add new node with (pt's letter, null link)
    if (lhead == null) {
    // If head is null, we need to add the node
        lhead = new CharacterNode(pt.getCharacter(),null);
    } else if (tail.getNext() == lhead) {
    // If the head is past tail, stop   
    } else {
        // Call concat on a smaller list
        lhead.setNext(concat(lhead.getNext(),tail,pt));
    }
    return lhead;
}

CharacterNodeは次のとおりです。

class CharacterNode {
    private char letter;
    private CharacterNode next;

    public CharacterNode(char ch, CharacterNode link) {
        letter = ch;
        next = link;
    }

    public void setCharacter(char ch) {
        this.letter = ch;
    }

    public char getCharacter() {
        return letter;
    }

    public void setNext(CharacterNode next) {
        this.next = next;
    }

    public CharacterNode getNext() {
        return next;
    }
}

MyString：

class MyString {
    // member variable pointing to the head of the linked list
    private CharacterNode head;

    // default constructor
    public MyString() {
    }

    // copy constructor
    public MyString(MyString l) {
    }

    // constructor from a String
    public MyString(String s) {
    }

    // for output purposes -- override Object version
    // no spaces between the characters, no line feeds/returns
    public String toString() {
    }

    // create a new node and add it to the head of the list
    public void addHead(char ch) {
    }

    // create a new node and add it to the tail of the list -- "wrapper"
    public void addTail(char ch) {
    }

    // Recursive method for addTail
    private static CharacterNode addTail(CharacterNode L, char letter) {
    }

    // modify the list so it is reversed
    public void reverse() {
    }

    // remove all occurrences of the character from the list -- "wrapper"
    public void removeChar(char ch) {
    }

    // Recursive removeChar method
    private static CharacterNode removeChar(CharacterNode n, char letter) {
    }

    // "wrapper" for recursive length()
    public int length() {
    }

    // Returns the length of the linked list
    private static int length(CharacterNode L) {
    }

    // concatenate a copy of list1 to the end of the list
    public void concat(MyString list1) {
    }

    // recursive method for concat
    private static CharacterNode concat(CharacterNode lhead, CharacterNode tail, CharacterNode pt) {
    }
}
4

1 に答える 1

5

2つのリンクリストを連結するには、最初のリストの最後のノードが2番目のリストの最初のノードを指すようにする必要があります。

Node first_list = ...  // head node
Node second_list = ... // head node
...
Node last_node = first_list.getLastNode()
last_node.setNext(second_list)

次に、の実装に集中しますgetLastNode()。これは、再帰または反復のいずれかを使用することで、文字通り2行で非常に簡単に実行できます。

于 2013-03-16T01:35:06.197 に答える