0

ここで ADT の基本的な内容に戻ってインタビューに備えて修正し、その間に Java を学習することで一石二鳥です。一般的なリンクリストを使用してマージソートの単純なアルゴリズムを作成しようとしています(これは私が自分で作成しています)。私が最初に想像していたよりもはるかに難しいことが証明されています! 誰でも私を助けてくれますか？基本的な作業から始めて、さらに進んだらこの投稿を更新します。

一般的なリンク リストの私のコードは次のとおりです。

 public class NodeList<T extends Comparable<T> > {
  private T head;
  public NodeList<T> tail;
  public NodeList( T item, NodeList<T> list ) {
    head = item;
    tail = list;
  } 

}

次のように、作成した別のクラスでこのクラスにアクセスしようとしています。

    public class MyList<T extends Comparable<T>> {

  private NodeList<T> nodes;
  private static int size;
  public MyList( ) { 
    nodes = null; 
  }

  public MyList(T[] array ){
    for( T item : array ) {
      nodes = new NodeList<T>(item, nodes); 
    }
    size = array.length;
  }


  public void add( T item ) { 
    nodes = new NodeList<T>( item, nodes ); 
    size++;
  }


  public void addEnd( T item ) {
    NodeList<T> temp = nodes;
    while ( temp == null || temp.tail != null) {
      temp = temp.tail;
    }
    size++;
    temp.tail = new NodeList<T> ( item, null);
  }

これまでのところ、リストの先頭とリストの末尾にそれぞれジェネリックを追加する必要がある add メソッドと addEnd メソッドまではすべて正しいと思います。

私のコードは次のように続きます:

 public static <S extends Comparable<S>>
    MyList<S> sort( MyList<S> list ) {

    if ( size > 1 ) {

      MyList<S> left  = leftHalf( list );
      MyList<S> right = rightHalf( list );
      list = merge( left, right );
    }

    return list;
  }

  private static <S extends Comparable<S>>
    MyList<S> merge( MyList<S> left, MyList<S> right ) {

  }

  private static <S extends Comparable<S>>
    MyList<S> leftHalf( MyList<S> list ) {
    MyList <S> leftSide = new MyList();
    int middle;
    if(size % 2 == 1) {
     middle = size +1;
    } else {
     middle = size; 
    }
    for ( int countToMiddle = 0; countToMiddle < middle ; countToMiddle++ ) {
      leftSide.addEnd(nodes);
    }


    // return elements from 0 .. list.size() / 2
  }

そして、私はエラーが発生します:

MyList の addEnd(S) は (NodeList) に適用できません

実行時に発生する

leftSide.addEnd(ノード);

誰かがこれの理由を見ることができますか/私の仕事のこの時点まで私が正しいかどうか教えてください? どうもありがとうございました!

4

3 に答える 3

2

NodeList と MyList にComparableアイテムのみを含めたい場合は、ジェネリック パラメーターTを次のようなものに置き換えることができます。

public class NodeList<T extends Comparable> {

または

public class NodeList<T extends Comparable<T>> {

Comparableそして、使用する場所を に置き換えますT。このようにして、T が少なくとも Comparable のメソッドを実装していることがわかります。

ジェネリックに関するOracle のチュートリアルは、それらのコツをつかむのに役立つはずです。

あなたが持っているかもしれない1つの問題は、あなたが持っているように、静的関数からメンバー変数を参照することですleftHalf:

   for ( int countToMiddle = 0; countToMiddle < middle ; countToMiddle++ ) {
      leftSide.addEnd(nodes);
    }

nodesメンバー変数、つまり非静的変数であるため、静的メソッドから呼び出すことはできません。その例では、渡された から取得する必要がありますMyList:

   for ( int countToMiddle = 0; countToMiddle < middle ; countToMiddle++ ) {
      leftSide.addEnd(list.nodes);
    }

メンバー変数を使用しようとする他の静的メソッドについても同じことが言えます。

また、次のようなエラーが発生するaddEnd(S) in MyList<S> cannot be applied to (NodeList<T>)理由Sは、型パラメーターによると Comparable であるためです。NodeList同等に拡張しません！

あなたが持っている2つの解決策は

  1. NodeList を Comparable に拡張して、に渡すことができるようにします。MyList.addEnd
  2. NodeList を受け取る addEnd のオーバーロード (つまり、同じ名前の別のメソッド) を作成し、渡された NodeList 内のすべての項目を MyList に追加します。

または、クラスのニーズにより適した別のソリューションを考え出してください。

面接のスキルを磨くためだけにリンク付きリストを実装していることは承知していますが (幸運を祈ります!)、 Java で既に使用できる汎用のLinkedListがあることを付け加えたいと思います。

于 2011-03-03T19:38:42.857 に答える
1

ほぼ同じ質問を2回投稿するのはなぜですか？質問を拡張したり、コメントを追加したりできます。

そのヒントはすでにお伝えしました。:)

于 2011-03-03T19:42:05.873 に答える
0

クラス NodeList には、ジェネリック T クラスと NodeList を受け取るコンストラクターがないため、エラーが発生しています。実際、この実装は、ノードがすべてのループで参照している参照オブジェクトを置き換えます。それも修正する必要があります。

あなたがすべきことは、 T を Comparable 自体にして、属性を次のように変更することです。

public class NodeList<T extends Comparable> {
    private T head;
    private NodeList tail;
    public NodeList( T item, NodeList list ) {
        head = item;
        tail = list;
    }
}

正確に何のためのコードか教えていただけると助かります。

于 2011-03-03T19:42:33.713 に答える