Java Queue Merge, начинающий - PullRequest
Новая
       4

Java Queue Merge, начинающий

0 голосов
/ 19 ноября 2009

Я пытаюсь написать метод, который будет принимать две очереди (предварительно отсортированные связанные списки) и возвращать объединенный в порядке возрастания результирующий объект очереди. Я вставил класс Queue , метод слияния начинается на полпути вниз.

У меня проблемы с вызовом слияния, вот как я пытаюсь вызвать его из моего основного метода , может кто-нибудь помочь с этим вызовом с new1 и new2. Большое спасибо всем!

Пожалуйста, дайте мне знать, если кто-нибудь заметит что-то неуместное. Спасибо! 

///////////////// //Testing with a call of merge method & 2 Queues///////////////////

public class test {
public static void main (String args[]){


 Queue new1 = new Queue();
 new1.enqueu(1);
 new1.enqueu(3);
 new1.enqueu(5);

 Queue new2 = new Queue();
 new1.enqueu(2);
 new1.enqueu(4);
 new1.enqueu(6);

    merge(new1, new2);

 //How to call merge? Queue.merge(new1, new2)???
/////////////////Queue/Merge method below////////////////////////


public class Queue {
private Node first, last;
public Queue(){
first = null;
last = null;
}

public void enqueu(int n){
 Node newNode = new Node(n);
 if (first == null)
 {
  first = newNode;
  last = newNode;

 }
 else
 {
  last.setNext(newNode);
  last = newNode;
 }
 }



public int dequeue(){
int num = first.getNum();
first = first.getNext();
if(first == null)
last = null;
return num;
}

public Boolean isEmpty() { return first == null; }



////////////////////////Begin Queue merge/////////////////////////////////


Queue merge(Queue q1, Queue q2) {
 Queue result = new Queue();
 boolean q1empty = q1.isEmpty();
 boolean q2empty = q2.isEmpty();
 while (!(q1empty || q2empty)) { 
 if (q1.first.getNum() < q2.first.getNum()) {
 result.enqueu(q1.dequeue());
 q1empty = q1.isEmpty();
 } else {
 result.enqueu(q2.dequeue());
 q2empty = q2.isEmpty();
 }
 }
 if (!q1empty) {
 do {
 result.enqueu(q1.dequeue());
 } while (!q1.isEmpty());
 } else if (!q2empty) {
 do {
 result.enqueu(q2.dequeue());
 } while (!q2.isEmpty());
 }
 return result;
 }}

Ответы [ 2 ]

3 голосов
/ 19 ноября 2009

У вас есть то, что кажется ошибкой здесь: 

Queue new1 = new Queue();
new1.enqueu(1);
new1.enqueu(3);
new1.enqueu(5);

Queue new2 = new Queue();
new1.enqueu(2);
new1.enqueu(4);
new1.enqueu(6);

Вы добавили шесть элементов к new1 и ноль к new2.

Поскольку ваш метод merge является методом экземпляра класса Queue, вам необходимо вызывать его в экземпляре Queue, например 

Queue q = new Queue();
Queue merged = q.merge(new1, new2);

Однако, поскольку слияние, по-видимому, не имеет побочных эффектов и не изменяет состояние экземпляра Queue, вы, вероятно, захотите просто сделать этот метод статическим, чтобы он принадлежал к очереди class , а не экземпляр очереди. Например: 

static Queue merge(Queue q1, Queue q2) {
     ...
}

//in main()...
Queue merged = Queue.merge(new1, new2);
0 голосов
/ 19 ноября 2009

Простой подход к объединению двух отсортированных итераторов в другой итератор: 

public static Iterator<Object> merge(final Iterator<Object> it1,
        final Iterator<Object> it2, final Comparator<Object> comp) {
    return new Iterator<Object>() {
        private Object o1 = it1.hasNext() ? it1.next() : null, o2 = it2
                .hasNext() ? it2.next() : null;
            @Override
        public boolean hasNext() {
            return o1 != null || o2 != null;
        }

        @Override
        public Object next() {
            if (o1 == null && o2 == null)
                throw new NoSuchElementException();
            Object ret;
            if (o1 == null) {
                ret = o2;
                o2 = it2.hasNext() ? it2.next() : null;
            } else if (o2 == null) {
                ret = o1;
                o1 = it1.hasNext() ? it1.next() : null;
            } else {
                if (comp.compare(o1, o2) <= 0) {
                    ret = o1;
                    o1 = it1.hasNext() ? it1.next() : null;
                } else {
                    ret = o2;
                    o2 = it2.hasNext() ? it2.next() : null;
                }
            }
            return ret;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("Not implemented");
        }
    };
}
...