1

リンク リスト キューの toString() 再帰メソッドを実装する必要があります。先週行ったリンク リストの実装で toString メソッドが正常に機能したことはわかっているので、その Queue 側面の処理方法に何か問題があります。

私のQueueListのtoStringメソッド：

public String toString() 
{ 

    if (front.info == null)
    {
        System.out.println("Error, queue is empty");
        return "";
    }
    if (front.link  == null) //base case: if this is last element in stack
    {

        return  (" \"" + front.info + "\" , ");
    } 
    else //normal recursive function
    {
        return  (" \"" + front.info + "\" , " + front.link.toString());

    }   

}

QueueListのコンストラクタなど：

public class QueueNode 
{
    E info;
    QueueNode link;
}

private QueueNode front;//first element to be placed into queue
private QueueNode rear;//last element to be placed into queue
private int NoE;//counter for number of elements in queue
public QueueList() 
{ 
    front = null;
    rear = null;
    NoE = 0;
}

このテストを使用して、その中で何が起こっているのかを確認しようとしました:

public boolean test() { 
    QueueList<String> q = new QueueList<String>();

    q.enqueue("The Godfather");
    q.enqueue("Casino");
    q.enqueue("Goodfellas");
    String r = q.toString();
    q.PrettyPrint();

出力で

IN -> [ "The Godfather" , QueueList$QueueNode@a3901c6] -> OUT.

front.link.toString()これは、メソッドの再帰部分で言っているためだと思いますが、toStringに変更してもfront.link.info.toString()、私の出力は

IN -> [ "The Godfather" , Casino] -> OUT.

それはおそらく、次のような私のエンキューおよびデキューメソッドと関係があるかもしれません:

public void enqueue(E element) 
{ 

        QueueNode newNode = new QueueNode();//creates new Node to hold element
        newNode.info = element;//set info of new Node to element
        newNode.link = null;//make link null since it's at back of list
        if (rear == null)//checks if queue is empty
        {
            front = newNode;
        }
        else
        {
            rear.link = newNode;//sets second to last node's link to newNode
        }
        rear = newNode;//makes newNode the new last link
        NoE++;//increase counter

}
public E dequeue() throws InvalidOperationException 
{
    if (front == null)//sanitize code
    {
        throw new InvalidOperationException("There is nothing in the queue.");
    }
    E element = front.info;//creates an element file that takes the info in front of queue
    front = front.link;//makes second-to-front element new front
    if (front == null)//if this emptied the queue, make sure rear is also empty
    {
        rear = null;
    }
    NoE--;//reduce counter
    return element;
}

できれば助けてください。ありがとう。

4

1 に答える 1

0

再帰的にする必要はまったくありません。toString実際、そうするのは正しくありません。データ構造は再帰的 (つまりツリー) ではなく、線形です。

たとえば、リストに 100 万個のアイテムが含まれている場合、すぐにスタック スペースが不足します (StackOverflow、文字通り)。

代わりにループを使用してください。

編集:これを再帰的に行う必要がある場合、問題は、再帰メソッドがQueueNode#toStringRecursive()ではなくである必要があることQueue#toString()です。メソッドQueue#toString()はバッファを割り当て、それを再帰を 行う特別なtoStringRecursive()メソッドに提供します。自身のノードの内容のみを担当する必要があります。QueueNodeQueueNode#toString()

方法Queue#toString()

public String toString()
{
    StringBuilder buf = new StringBuilder();
    if (front == null)
        // queue is empty
    else
        front.toStringRecursive(buf);
    return buf.toString();
}

方法QueueNode#toStringRecursive()

public void toStringRecursive(StringBuilder buf)
{
    buf.append(this.toString());
    if (this.link != null)
        this.toStringRecursive(buf);
}

whereQueueNode.toString()は、1 つのノード (それ自体) の文字列化のみを担当します。

これは1 つの方法であることに注意してください。これを の再帰メソッドとして記述することQueueもできますが、呼び出すことはできませんでしたtoString()。Queue#toString()初期条件を設定してから、再帰を呼び出します。

于 2013-10-07T15:55:47.430 に答える