Упорядоченная вставка, работающая спорадически с примитивными типами и строками - PullRequest
Новая
       30

Упорядоченная вставка, работающая спорадически с примитивными типами и строками

0 голосов
/ 18 ноября 2011

Для задания нас попросили реализовать как упорядоченные, так и неупорядоченные версии LinkedLists в качестве пакетов в Java.Упорядоченные версии просто расширяют неупорядоченные имплементации, переопределяя методы вставки.

Упорядочивание по функции вставки работает ... в некоторой степени.При заданном массиве тестов 

String[] testArray= {"z","g","x","v","y","t","s","r","w","q"};

вывод будет 

q w r s t y v x g z

, когда он должен быть 

g q r s t v w x y z

Однако упорядочение работает нормально, когда элементы не отображаются.т перепутал в стоимости.Например, я первоначально использовал testArray[] выше с обратным алфавитом, и порядок был точно таким, каким он должен быть.

Моя функция добавления 

@Override
public void add(E e){
    Iter iter= new Iter(head.prev);
    int compValue;
    E currentItem= null;

    //empty list, add at first position
    if (size < 1)
        iter.add(e);

    else {

        while (iter.hasNext()){
            currentItem= iter.next(); //gets next item

            //saves on multiple compareTo calls
            compValue= e.compareTo(currentItem); 

            //adds at given location
            if (compValue <= 0)
                iter.add(e, iter.index);

            else //moves on
                currentItem= iter.next();
        }
    }
}

Реализована функциональность итераторакак 

//decided to use iterator to simplify method functionality
protected class Iter implements Iterator<E>, ListIterator<E>{
    protected int index= 0;
    protected Node current= null;

//Sets a new iterator to the index point provided
    public Iter(int index){
        current= head.next;
        this.index=0;
        while (index > nextIndex()) //moves on to the index point
            next();
    }

public void add(E e, int index){
        size++;

        Iter iterator= new Iter(index);

        Node node= new Node();
        Node current= iterator.current.prev;

        node.next= current.next;
        node.prev= current;
        node.next.prev= node;
        node.prev.next= node;

        node.item= e;
    }

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

Случайно, у моего одноклассника есть похожая реализацияи возвращает те же результаты.

Используя естественное упорядочение, как я могу решить эту проблему?

1 Ответ

1 голос
/ 06 декабря 2011

Три вещи о вашей функции add () бросаются в глаза:

  1. Он должен выйти из цикла, как только он вставит новое значение;на самом деле это может и не быть проблемой, но неэффективно продолжать искать
  2. Вы вызываете next_item в верхней части цикла, но вызываете его СНОВА, если значение не добавлено
  3. Если вашВ списке есть только 1 значение, и вы пытаетесь добавить значение, большее, чем значение в списке, не будет ли добавлено новое значение?
...