Java, Обобщения, Merge, Сопоставимые

Question

Вот мой вопрос:

Способ по имени объединения, объединяющее 2 маркированных списков в третий. Предположим, что у list_1 и list_2 нет общих ключей. В результате список должен быть несортированным списком, который содержит все элементы из списка_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; 
    } 

Я работаю над секцией дженериков в течение нескольких дней. SOS !! Вот мои классы:

//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 методом дженериков в течение приблизительно 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. Вам нужно только это, если вам нужно сравнить экземпляры вашего класса. Вместо этого сделайте элементы сопоставимыми, как в примере.