Java、泛型、合并、比较

Question

这是我的问题:

名为 merge 的方法，可将 2 个无序列表连接成第三个无序列表。假设 list_1 和 list_2 没有任何共同的键。生成的列表应该是一个未排序的列表，其中包含 list_1 和 list_2 中的所有项目(保留顺序)。

我遇到的问题是我需要使用泛型来回答这个问题。我有正常合并方法的代码如下..

// Merge Method
    public OrderedArrayList merge(OrderedArrayList list2){
        OrderedArrayList result = new OrderedArrayList(length + list2.length);
        int list1Index = 0;
        int list2Index = 0;
        for (int i = 0; i < result.maxSize; i++) {
            if (list1Index == list.length) {
                result.insert(list2.list[list2Index]);
                list2Index++;
            } else if (list2Index == list2.length) {
                result.insert(list[list1Index]);
                list1Index++;
            } else if (list[list1Index] < list2.list[list2Index]) {
                result.insert(list[list1Index]);
                list1Index++;
            } else {
                result.insert(list2.list[list2Index]);
                list2Index++;
            }
        }
        return result;
    }

我已经在泛型部分工作了好几天。求救!! 这是我的类(class):

//Interface: ArrayListADT 
//works for int 
public interface ArrayListADT1<T> extends Comparable{ 
    public boolean isEmpty(); //Method to determine whether the list is empty. 
    public boolean isFull();  //Method to determine whether the list is full. 
    public int listSize();    //Method to return the number of elements in the list. 
    public int maxListSize(); //Method to return the maximum size of the list. 
    public void print();      //Method to output the elements of the list. 
    public boolean isItemAtEqual(int location, T item); //Method to determine whether item is the same as the item in the list at location. 
    public void insertAt(int location, T insertItem);   //Method to insert insertItem in the list at the position 
    public void insertEnd(T insertItem); //Method to insert insertItem at the end of the list. 
    public void removeAt(int location);  //Method to remove the item from the list at location. 
    public T retrieveAt(int location);   //Method to retrieve the element from the list at location. 
    public void replaceAt(int location, T repItem); //Method to replace the element in the list at location with repItem. 
    public void clearList();  //Method to remove all the elements from the list. 
    public int search(T searchItem);    //Method to determine whether searchItem is in the list. 
    public void remove(T removeItem);   //Method to remove an item from the list. 
}

//Class: ArrayListClass1<T> implements 
//Interface: ArrayListADT 
public abstract class ArrayListClass1<T> implements ArrayListADT1<T>, Comparable{
    protected int length; // to store the length of the list
    protected int maxSize; // to store the maximum size of the list
    protected T[] list; // array to hold the list elements

    // Default constructor
    public ArrayListClass1() {
        maxSize = 100;
        length = 0;
        list = (T[]) new Object[maxSize];
    }

    // Alternate Constructor
    public ArrayListClass1(int size) {
        if (size <= 0) {
            System.err.println("The array size must be positive. Creating an array of size 100.");
            maxSize = 100;
        } else
            maxSize = size;
        length = 0;
        list = (T[]) new Object[maxSize];
    }

    public boolean isEmpty() {
        return (length == 0);
    }

    public boolean isFull() {
        return (length == maxSize);
    }

    public int listSize() {
        return length;
    }

    public int maxListSize() {
        return maxSize;
    }

    public void print() {
        for (int i = 0; i < length; i++)
            System.out.print(list[i] + "  ");
        System.out.println();
    }

    public boolean isItemAtEqual(int location, T item) {
        if (location < 0 || location >= length) {
            System.err.println("The location of the item to be compared is out of range.");
            return false;
        }
        return list[location] == item;
    }

    public void clearList() {
        for (int i = 0; i < length; i++)
            list[i] = null;
        length = 0;
        System.gc(); // invoke the Java garbage collector
    }

    public void removeAt(int location) {
        if (location < 0 || location >= length)
            System.err.println("The location of the item to be removed is out of range.");
        else {
            for (int i = location; i < length - 1; i++)
                list[i] = list[i + 1];
            length--;
        }
    }

    public T retrieveAt(int location) {
        if (location < 0 || location >= length) {
            System.err.println("The location of the item to be retrieved is out of range.");
            return null;
        } else
            return list[location];
    }

    public abstract void insertAt(int location, T insertItem);

    public abstract void insertEnd(T insertItem);

    public abstract void replaceAt(int location, T repItem);

    public abstract int search(T searchItem);

    public abstract void remove(T removeItem);
}

//Class: OrderedArrayList1 extends 
//Super class: ArrayListClass 
public class OrderedArrayList1<T> extends ArrayListClass1<T>{

  public OrderedArrayList1() {
    super();
  }

  public OrderedArrayList1(int size) {
    super(size);
  }

  // implementation for abstract methods defined in ArrayListClass

  // ordered list --> binary search
  public int search(T item) {
    int first = 0;
    int last = length - 1;
    int middle = -1;

    while (first <= last) {
      middle = (first + last) / 2;
      Comparable<T> listElem = (Comparable<T>) list[middle];
      if (listElem.compareTo(item)==0)
        return middle;
      else
        if (listElem.compareTo(item) > 0)
        last = middle - 1;
      else
        first = middle + 1;
    }
    return -1;
  }

  public void insert(T item) {
    int loc;
    boolean found = false;
    if (length == 0) // list is empty
      list[length++] = item; // insert item and increment length
    else if (length == maxSize) // list is full
      System.err.println("Cannot insert in a full list.");
    else {
      for (loc = 0; loc < length; loc++) {
        Comparable<T> temp = (Comparable<T>) list[loc];
        if (temp.compareTo(item) >= 0) {
          found = true;
          break;
        }
      }
      // starting at the end, shift right
      for (int i = length; i > loc; i--)
        list[i] = list[i - 1];
      list[loc] = item; // insert in place
      length++;
    }
  }

  /*
   * Another version for insert:
   * public void insert(int item) {
   * int loc;
   * boolean found = false;
   * if (length == 0) //list is empty
   * list[length++] = item; //insert item and increment length
   * else if (length == maxSize) //list is full
   * System.err.println("Cannot insert in a full list.");
   * else {
   * int i = length - 1;
   * while (i >= 0 && list[i] > item) {
   * list[i + 1] = list[i];
   * i--;
   * }
   * list[i + 1] = item; // Insert item
   * length++;
   * }
   * }
   */

  public void insertAt(int location, T item) {
    if (location < 0 || location >= maxSize)
      System.err.println("The position of the item to be inserted is out of range.");
    else if (length == maxSize) // the list is full
      System.err.println("Cannot insert in a full list.");
    else {
      System.out.println("Cannot do it, this is a sorted list. Doing insert in place (call to insert).");
      insert(item);
    }
  }

  public void insertEnd(T item) {
    if (length == maxSize) // the list is full
      System.err.println("Cannot insert in a full list.");
    else {
      System.out.println("Cannot do it, this is a sorted list. Doing insert in place (call to insert).");
      insert(item);
    }
  }

  public void replaceAt(int location, T item) {
    // the list is sorted!
    // is actually removing the element at location and inserting item in place
    if (location < 0 || location >= length)
      System.err.println("The position of the item to be replaced is out of range.");
    else {
      removeAt(location);// method in ArrayListClass
      insert(item);
    }
  }

  public void remove(T item) {
    int loc;
    if (length == 0)
      System.err.println("Cannot delete from an empty list.");
    else {
      loc = search(item);
      if (loc != -1)
        removeAt(loc);// method in ArrayListClass
      else
        System.out.println("The item to be deleted is not in the list.");
    }
  }

  /*
   * Another version for remove:
   * public void remove(T item) {
   * int loc;
   * if (length == 0)
   * System.err.println("Cannot delete from an empty list.");
   * else {
   * loc = search(item);
   * if (loc != -1) {
   * for(int i = loc; i < length - 1; i++)
   * list[i] = list[i + 1]; //shift left
   * length--;
   * }
   * else
   * System.out.println("The item to be deleted is not in the list.");
   * }
   * }
   */

  /*
   * 
   * KATHERINE'S
   * 
   */
  // The start of Assignment 3
  // Merge Method

  public OrderedArrayList1<T> merge(OrderedArrayList1<T> list2){
    OrderedArrayList1 result = new OrderedArrayList1(length + list2.length);
    int list1Index = 0;
    int list2Index = 0;
    for (int i = 0; i < result.maxSize; i++) {
      Comparable<T> temp = (Comparable<T>)list[list1Index];
      T [] temp1 = new T list2[list1Index];
      if (list1Index.equals(list[list1Index])) {
        result.insert(list2.list[list2Index]);
        list2Index++;
      } else if (list2Index.equals(list[list1Index])) {
        result.insert(list[list1Index]);
        list1Index++;

      }else if (temp.compareTo(list2) < 0) {
        result.insert(list[list1Index]);
        list1Index++;
      } else {
        result.insert(list2.list[list2Index]);
        list2Index++;
      }
    }
    return result;
  }
  // Split Method
  public <T extends Comparable<T> > void split(OrderedArrayList1<T> lessThanKey, OrderedArrayList1<T> greaterThanKey, T splitKey) {
    int i;

    for (i = 0; i < length; i++) {
      T temp = (T)list[i];
      if (temp.compareTo(splitKey)<0)
        lessThanKey.insert(temp);
      else
        greaterThanKey.insert(temp);
    }
  }
}

我现在已经在 Merge Generics 方法上工作了大约 12 个小时。我尝试过很多不同的方法。我真的很感激一些帮助。谢谢!

Answer 1

让我们一步一步解决这个问题。

首先，您需要将两个列表合并在一起。仅当列表包含相同类型的元素时，这才有可能，并且从逻辑上讲，结果将是相同类型的新列表。因此，我们最终得到以下方法:

public <T extends Comparable<T>> List<T> merge(List<T> first, List<T> second) {
    final List<T> merged = new ArrayList<T>();
    merged.addAll(first);
    merged.addAll(second);
    return merged;
}

您只需要使用自定义列表实现即可，但原理是相同的。

其次，在实现列表时，不要扩展 Comparable。仅当您需要比较类的实例时才需要它。相反，使元素具有可比性，如示例方法中所示。