Таким образом, задача состоит в том, чтобы реализовать связанный список и сортировку слиянием, которая сортирует связанные списки. Я полностью осознаю, что в промышленности мне, скорее всего, не придется реализовывать что-либо из этого, но я чувствую, что это хороший способ попрактиковаться в Java. Вот что у меня есть на данный момент:
Класс узла:
public class Node<E extends Comparable<E>>
{
public E data;
public Node<E> next;
public Node(E data)
{
this.data = data;
next = null;
}
public void printData()
{
System.out.print(data + " ");
}
}
Класс LinkedList:
public class LinkedList<E extends Comparable<E>>
{
protected Node<E> root;
protected int size = 0;
public LinkedList()
{
root = null;
}
public void addBeg(E e)
{
Node<E> newNode = new Node<E>(e);
newNode.next = root;
root = newNode;
size++;
}
public Node deleteBeg()
{
Node<E> temp = root;
if(!isEmpty())
{
root = root.next;
size--;
}
return temp;
}
public void setRoot(Node<E> newRoot)
{
root = newRoot;
}
public boolean isEmpty()
{
return root == null;
}
public Node<E> getRoot()
{
return root;
}
public void printList()
{
Node<E> cur = root;
while(cur!=null)
{
cur.printData();
cur=cur.next;
}
System.out.println();
}
}
Класс MergeSorter:
public class MergeSorter<E extends Comparable<E>>
{
public MergeSorter()
{
}
private void split(LinkedList<E> list, LinkedList<E> firHalf, LinkedList<E> secHalf)
{
//if 0 or only 1 elements in the list - it doesn't seem to work, however
if(list.getRoot() == null || list.getRoot().next == null)firHalf = list;
else{
Node<E> slow = list.getRoot();
Node<E> fast = list.getRoot().next;
while(fast!=null)
{
fast = fast.next;
if(fast!=null)
{
fast = fast.next;
slow = slow.next;
}
}
//If I use the following line firHalf list is empty when in the caller of this method (it's not in this method, however). Don't understand why ):
//firHalf = list;
firHalf.setRoot(list.getRoot());
secHalf.setRoot(slow.next);
slow.next = null;
}
}
private LinkedList<E> merge(LinkedList<E> a, LinkedList<E> b)
{
LinkedList<E> mergedList = new LinkedList<E>();
Node<E> dummy = new Node<E>(null);
Node<E> tail = dummy;
while(true)
{
if(a.getRoot() == null){
tail.next = b.getRoot();
break;
}
else if(b.getRoot() == null){
tail.next = a.getRoot();
break;
}
else
{
if(a.getRoot().data.compareTo(b.getRoot().data) <= 0)
{
tail.next = a.getRoot();
tail = tail.next;
a.setRoot(a.getRoot().next);
}
else
{
tail.next = b.getRoot();
tail = tail.next;
b.setRoot(b.getRoot().next);
}
tail.next = null;
}
}
mergedList.setRoot(dummy.next);
return mergedList;
}
public void mergeSort(LinkedList<E> list)
{
Node<E> root = list.getRoot();
LinkedList<E> left = new LinkedList<E>();
LinkedList<E> right = new LinkedList<E>();
if(root == null || root.next == null) return; //base case
split(list, left, right); //split
mergeSort(left);
mergeSort(right);
list = merge(left, right); // when this mergeSort returns this list should be
// referenced by the left or right variable of the
// current mergeSort call (but it isn't!)
}
}
Я довольно новичок в Java (исходя из фона C), поэтому я искренне сожалею заранее, если мой код совершенно неверен. Когда я тестирую методы разделения и слияния в классе MergeSorter независимо друг от друга, кажется, что все работает (разбиение списка, состоящего из 0 или 1 элемента, не работает и сводит меня с ума, но для сортировки слиянием это не нужно). Однако метод mergeSort не работает, и я не могу понять, как это сделать. Я пытался отлаживать его сам, и, кажется, есть проблема, когда две половины сливаются в один список, а затем возвращается рекурсия. На недавно объединенный список должна ссылаться либо левая, либо правая переменная текущего вызова mergeSort, но вместо этого я получаю только последний элемент, а не весь список.
