Блог

У меня есть простой связанный список. Узел содержит строку (значение) и значение int (количество).

В linkedlist при вставке мне нужно вставить новый узел в алфавитном порядке. Если в списке есть узел с таким же значением, то я просто увеличиваю количество узлов.

Я думаю, что мой метод действительно облажался.

  public void addToList(Node node){
        //check if list is empty, if so insert at head
        if(count == 0 ){
            head = node;
            head.setNext(null);
            count  ;
        }
        else{
            Node temp = head;
            for(int i=0; i<count; i  ){
                //if value is greater, insert after
                if(node.getItem().getValue().compareTo(temp.getItem().getValue()) > 0){
                    node.setNext(temp.getNext());
                    temp.setNext(node);                   
                }
                //if value is equal just increment the counter
                else if(node.getItem().getValue().compareTo(temp.getItem().getValue()) == 0){
                    temp.getItem().setCount(temp.getItem().getCount()   1);
                }
                //else insert before
                else{
                    node.setNext(temp);
                }
            }
        }      

    }
  

Итак, это вставка всех моих строк, но не в алфавитном порядке. Вы видите какую-либо ошибку?

  public Node findIsertionPoint(Node head, Node node){
        if( head == null)
            return null;

        Node curr = head;
        while( curr != null){
            if( curr.getValue().compareTo(node.getValue()) == 0)
                return curr;
            else if( curr.getNext() == null || curr.getNext().getValue().compareTo(node.getValue()) > 0)
                return curr;
            else
                curr = curr.getNext();
        }

        return null;
    }

    public void insert(Node node){
        Node newNode = node;
        Node insertPoint = this.findIsertionPoint(this.head, node);
        if( insertPoint == null)
            this.head = newNode;
        else{
            if( insertPoint.getValue().compareTo(node.getValue()) == 0)
                insertPoint.getItem().incrementCount();
            else{
                newNode.setNext(insertPoint.getNext());
                insertPoint.setNext(newNode);
            }
        }
        count  ;
    }
  

В вашем коде есть несколько ошибок:

• Вставка в / перед head на самом деле должна происходить в двух разных сценариях:
  • Если список пуст, head становится node
  • Если список не пуст, но node меньше первого элемента, head также становится node
    • В любом случае, node ссылки на то, на что head указывалось раньше ( null или на реальный узел), и head теперь указывают на node .
• Если вы не вставляете перед head , то вы, должно быть, вставляете после некоторого узла. Нам просто нужно найти, где находится это место. Возможны два сценария:
  • node.getValue() > temp.getValue() , и node.getValue() < temp.getNext().getValue()
  • node.getValue() > temp.getValue() и temp.getNext() == null
    • В любом случае, node вставляется между temp и temp.getNext()

Я предлагаю инкапсулировать поиск точки после вставки в его собственную функцию. То есть, учитывая список и значение, он должен возвращать узел. Если этот узел имеет то же значение, что и значение поиска, то просто увеличьте; в противном случае вставьте после. В качестве особого случая, верните null , чтобы указать, что точка вставки находится перед head .

В псевдокоде это будет выглядеть следующим образом:

 FUNCTION findInsertionPoint(Node head, V value) RETURNS Node
  // return null if value needs to be inserted before head
  IF head == null OR value < head.getValue()
     RETURN null;

  // otherwise, either return a node with the given value,
  // or return a node after which value should be inserted
  Node curr = head;
  REPEAT
     IF curr.value == value
        RETURN curr;
     ELSEIF curr.getNext() == null OR curr.getNext().getValue() > value
        RETURN curr;
     ELSE
        curr = curr.getNext();

PROCEDURE insert(V value) {
  Node newNode = NEW Node(value);
  Node insertPoint = findInsertionPoint(this.head, value);
  IF insertPoint == null // insert before head
     newNode.setNext(this.head);
     this.head = newNode;
  ELSE
     IF insertPoint.getValue() == value
        insertPoint.incrementCounter();
     ELSE // insert after insertPoint
        newNode.setNext(insertPoint.getNext());
        insertPoint.setNext(newNode);
  

Обновление: я вижу, что вы перевели мой псевдокод на Java, но по какой-то причине вы опустили коды, которые касаются вставки перед, head когда head значение не является пустым. В частности, вы необъяснимым образом опустили эту часть:

 IF head == null OR value < head.getValue()
             // ^^^^^^^^^^^^^^^^^^^^^^^^^^
  

и эта часть:

 IF insertPoint == null 
   newNode.setNext(this.head); // <<<<<<<<<<<
   this.head = newNode;
  

Оба они необходимы; это то, что позволяет "A" вставлять перед head in [ "B", "C", "D" ] .

Вам нужно понять, почему они важны, и действительно спросите себя, почему вы решили их удалить. Объясните нам, мне, себе, почему вы это сделали; осознайте ошибку и извлеките из нее урок.

Для этого вместо разработки с нуля моего собственного отсортированного списка я бы реализовал интерфейс Queue или расширил уже существующий PriorityQueue (или любую другую отсортированную коллекцию, которая может подойти лучше). Я бы определил класс Node как реализацию сопоставимого интерфейса или создал бы экземпляр моей очереди с помощью экземпляра Comparator и переопределил метод добавления PriorityQueue, чтобы добавить новый узел, только если другого объекта еще нет в очереди, увеличивая счетчик в противном случае. При использовании java > 5.0 для безопасности типов я бы использовал generic, чтобы разрешить только объекты Node в очереди.

Я думаю, вы хотите использовать одну из реализаций Multiset из коллекций Google.

Мультимножество работает аналогично набору, но допускает дубликаты (и подсчитывает их!). Посмотрите на TreeMultiset:

Мультимножество, которое поддерживает порядок расположения своих элементов либо в соответствии с их естественным порядком, либо с явным компаратором.

Не видя полного кода, трудно выполнять отладку. Я думаю, проблема в том, что вы задаете

  Node temp = head; 
  

перед циклом, но вам нужно переназначить temp while при переходе по списку к текущему элементу. В этом случае вы продолжаете сравнивать с head .

• Вы позаботились о случае, когда list изначально пусто. Вы также должны позаботиться об особом случае, когда новый узел находится в начале списка. Если ваш список является B->C->D и вы вставляете A .
• Полезно установить node.next значение null (если еще не сделано). Так что, если узел будет вставлен в конце, у нас будет null следующий из последних узлов.
• Вам необходимо обновить temp, чтобы перейти к следующему узлу, если вставка невозможна. Таким образом, вам не хватает temp = temp.next;

Поскольку это домашнее задание, я не собираюсь давать вам никакого исходного кода. Я вижу одну большую проблему с кодом:

Предположим, в вашем списке уже есть два разных элемента, и вы вставляете новый элемент. В вашем коде вы проверяете, node больше head , и если да, то вставляете его сразу после, игнорируя остальные элементы в списке.

Ваш код делает что-то вроде этого. Есть некоторые недостающие детали, которые вы можете заполнить самостоятельно.

1. Если список пуст, установите head = node , head->next = NULL и готово.

2. В противном случае, если node->value < head->value , установите node->next = head, head = node .

3. В противном случае, если node->value == head->value , head->count ;

4. В противном случае установите tmp = head . Пока tmp->next->value < node->value , установите tmp=tmp->next . (проверьте наличие нулей!).

5. Если tmp->next == NULL , (т. е. вы достигли конца списка), то установите tmp->next = node , и все готово.

6. В противном случае, если tmp->next->value == node->value (т. е. вы достигли узла с тем же значением) tmp->next->count .

7. В противном случае, если node->next = tmp->next, tmp->next = node , и выйти