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>> {

并将您使用的地方替换ComparableT. 这样,您就知道 T 至少实现了 Comparable 的方法。

Oracle 的泛型教程应该能够帮助您掌握它们的窍门。


您可能遇到的一个问题是您从静态函数中引用成员变量,例如leftHalf

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

nodes是成员变量,即非静态变量,所以不能从静态方法中调用。对于那个例子,你必须从 pass 中获取它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不扩展可比!

你有两个解决方案是

  1. 使 NodeList 扩展 Comparable 以便您可以将其传递给MyList.addEnd
  2. 为接受NodeList的addEnd做一个重载(即同名的不同方法),并将传递的NodeList中的所有项目添加到MyList

或者想出一个更适合您班级需求的不同解决方案。


虽然我意识到您正在实施一个链表只是为了提高您的面试技巧(祝您好运!),但我只想补充一点,Java 中已经有一个通用的LinkedList可用。

于 2011-03-03T19:38:42.857 回答
1

为什么您两次发布几乎相同的问题?您可以扩展您的问题,添加评论等。

我们已经给了你这个提示。:)

于 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 回答