0

LinkedList データ構造を作成するという現在の割り当てに取り組んでおり、他の方法と同様にそれを作成しましたが、完全に正常に動作します。toString メソッドを作成するという最後の質問です。どちらが想定されています：

「リストの文字列表現を返す toString メソッド。各項目をコンマで区切り、項目を中かっこで囲みます (例: {1,4,7,5})。パブリック toString メソッドは、プライベートな再帰メソッドを呼び出して生成する必要があります。コンマで区切られた項目のリスト (パブリック メソッドに中括弧を追加することはできます)"

public toString メソッドが機能しています。

    public String toString() {
    int size = getSize();
    String str = "{ ";
    Link current = first;

    for(int i = 0; i < getSize(); i++, current = current.next) {
        str += current.getiData() + " ";
    }

    str += " }";
    return str;
}

(一時的に += を使用するだけで、StringBuilder を使用する必要があることはわかっています。) ただし、プライベート メソッドについては、それを記述することさえ混乱しています。今のところ、これを行うことを考えることができる唯一の方法は次のとおりです。

private String toString(int x) {
    if(i > 0) {
        toString(--x);
    }
    return ", ";
}

これはばかげているだけです（そして実際には再帰ではありません）、誰が何をすべきかを明確にし、および/または疑似コードを提供できますか?

4

3 に答える 3

5

このようなものが必要です（再帰の基本的な考え方を示しますが、機能しません）

privat String toString(Link link) {
  if (link.isLast()) {
    return link.value();
  }
  else {
    return link.value() + toString(link.next());
  }
}
于 2013-06-02T21:07:31.563 に答える
5

コードの観点からは他の回答が適切だと思いますが、そこにたどり着く方法を理解するのに役立つ理論を追加したかっただけです。再帰を行うときは、基本ケースと再帰ケースの 2 つが常に必要です。基本ケースは解決するのが信じられないほど単純なものであり、再帰ケースは、解決可能な単純なケースに向かって作業する方法です。

Linked List は一種の再帰的なデータ構造そのものです。たとえば、10 個のアイテムのリンク リストがある場合、9 個のアイテムのリンク リストが関連付けられた単一のノードとして描くことができます。

したがって、基本ケース（@Chrisの回答から借りる）の場合、 on を実行する最も単純なリストtoString()は空のリストです。したがって、基本ケースは次のようになります(疑似コード):

if(list is empty)
{
   return "";
}

次に、再帰ケースは、既存のリンク リストを取得し、基本ケースに向かって下向きに作業する必要があります。これを行う最も簡単な方法は、解決できることがわかっている問題の小さな部分を切り離して解決し、残ったわずかに小さな問題に取り組むことです。Linked List を印刷する場合、つまり、リストから 1 つの項目を取得し、それを文字列に変換してから、残りのリストを気にすることができます。したがって、再帰的なケースは次のようになります (疑似コード):

if(list is not empty)
{
   String x = take the current node and translate it to a string;

   Add x to your running value of the String value of the entire list

   Recursively call this function with the next node in the list
   (you reduce your list size by 1 with each call and work down to your base case of an empty list)
}

この問題を再帰的に解決する方法を理解するのに役立つことを願っています。それを機能させる方法には確かにたくさんのバリエーションがあります。ループを記述する「正しい」方法が 1 つとないように、再帰的に行う「正しい」方法は 1 つではありませんが、通常は、一般的な「基本ケース」および「再帰ケース」の考え方から始めるのが最適です。

于 2013-06-02T21:16:43.020 に答える
1

toStringメソッドのシグネチャにはパラメーターがなく、別のメソッドが必要であるため、これはやや奇妙です。リンクされたリストでは、各ノードには次のノードへのdataとがあります。pointer

public String getData(Node n, String value)
{
     if(n == null)
     {
         // We know we're at the end, so don't proceed.
         return value;
     }
     else
     {
         // n isn't empty, and ignoring the lack of stringbuilder
         value += n.getData();
         // Make a recursive call with the next value in the list, and the new string.
         return getData(n.next(), value);
     }
}
于 2013-06-02T21:06:28.600 に答える