getLastIndexOf（int item）LinkedList

Question

私は現在、クラスとオンラインの両方でデータ構造の学習に取り組んでいる新入生comp sciの学生です。

私も新しく積み重ねていますが、これは過去に多くの助けになりました。

私の現在の問題は、LinkedListで検索して、番号がリストに表示されている最後のインデックスを返すことです。

これは、その項目の最後の出現であることを何らかの形で確認してから索引を戻すまで、再帰と継続的な検索を多少行う必要があると思います。

私の最初の学期のJavaコースでは、再帰をまったくカバーすることはできませんでした。

私はフラットアウトの答えを求めていません、私はちょうど方向が必要です。あるいは、再帰を見て正しい道を進んでいることを私に安心させますか？

また、これまでに私が試したことがあります。助けてくれてありがとう！

public int getLastIndexOf(int lastItem) { //goal is to return the lastindex at which that number appears last 
    Node current; 
    current = head; 
    int count = 0; //count variable 
    while (current.next != null) { //go through list 
     if (current.dataItem == lastItem) { 
      //check rest of the list for if that number exists beyond 
     } 
     count++; //increment count for every time loop executes 
     current = current.next; //moves onto next node to check 
    } 
    return -1; 
} 

Answer 1

リストが、テールと呼ばれる別のリストの後に続くノードであると考えてください。これは擬似コードであり、2つのメソッドが必要であることに注意してください。privateはノードを1つ取ります。これはサブリストです。

public int getLastIndexOf(value) { 
    return getLastIndexOf(head, value); 
} 

private int getLastIndexOf(sublist, value) { 
    //check the tail first (because we want last index) 
    if (sublist.tail != null) {//list has a tail 
     int lastIndexInTail = getLastIndexOf(sublist.tail, value); //recursion 
     if(lastIndexInTail != -1) 
      return lastIndexInTail + 1; //it's in the sub list, the sub list starts at idx 1 
    } 

    // it's not in the tail, check this head 
    if (sublist.data == value){ 
     return 0; //it's at the front of this list 
    } 

    return -1; //it's not in the head or in the tail of sublist 
} 

Answer 2

あなたがそうのような試合をしていたときにあなただけのインデックスを保存し、上書きすることができます：

public int getLastIndexOf(int lastItem) { //goal is to return the lastindex at which that number appears last 
    Node current; 
    current = head; 
    int count = 0; //count variable 
    int lastIndex = 0; 
    while (current.next != null) { //go through list 
     if (current.dataItem == lastItem) { 
       lastIndex = count; 
     } 
     count++; //increment count for every time loop executes 
     current = current.next; //moves onto next node to check 
    } 
return lastIndex; 

をですから、lastIndexの中で試合の位置を保存し、複数の一致theresの場合は、それを「最新の」値で上書きします。

Answer 3

あなたがここに役に立つかもしれないTopcoderから再帰

このチュートリアルでそれをしたい場合。

私の2セントは、次のとおりです。

再帰と繰り返し（しばらくなど、のためのように、ループは）あなたの現在の問題を解決するために使用することができます。

あなたの現在のコードは再帰的ではありません。反復的です。再帰は、同じ関数を何回か呼び出していくつかの終了条件まで繰り返すときに発生します。

再帰関数は2つの部分があります

1. 基本条件を - 再帰
2. に再帰条件を停止するときを示しています - のは、これを見てみましょう再帰を行うには

を示しています例を挙げて説明する。 "Hello World"を10回印刷したいとします。ここでは、反復的に

for(int i = 0; i < 10; i++){ 
    System.out.println("Hello World"); 
} 

そして、ここでそれを行うだろうかだと、あなたがそれを行う方法である再帰的

void helloWorldPrinter(int index){ 
    //This is the base condition, tells us to stop when we've reached 10 
    if(index == 10){ 
     return; 
    } 
    else{ 
     //Print for the n th hello world 
     System.out.println("Hello World"); 
     //call the same function for printing the next (n+1 th) hello world 
     helloWorldPrinter(index+1); //Looks similar to the i++ in the loop right? 
    } 
} 

再帰は逆さまの木のように見えるのデータ構造であり、バイナリツリーに非常に便利です。 対再帰的コードを書くときに覚えておくことができるコンセプトは、オブザーバとしてデータ構造を見て、その上でアクションを実行するようなものです。データ構造内の要素であるかのように再帰が進みます。 （次の再帰呼び出し）

ここで、このロジックを拡張してリンクリストの最後の項目を見つけることができると考えています。このための反復的な解法は、再帰的な解法よりはるかに簡単です。

ロジックは次のとおりです。

Loop over list (iterative or recursive) 
    If element is found, note down the index 
End Loop if list has been traversed completely 
return the element index