Почему этот цикл while застрял в бесконечном цикле? - PullRequest
Новая
       6

Почему этот цикл while застрял в бесконечном цикле?

0 голосов
/ 16 октября 2010

Я работаю над гибридной структурой данных, которая представляет собой упорядоченный двойной связанный список, в котором каждый узел содержит массив [] SIZE. Моя сложность заключается в методе добавления.

Используя модульное тестирование, предоставленное профессором, тестовая строка разбивается на отдельные символы и добавляется в список с помощью предоставленного компаратора. Тест по умолчанию abcdefghijklmnopqrstuvwxyzaeiou

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

Код, который я придумал: 

boolean add(E item){
    Chunk<E> currentNode= head; //set lookup node to the head

    if (size==0) {
        //new chunk, connect it with head
        Chunk<E> newNode= new Chunk<E>(); 
        newNode.next= head;
        newNode.prev=head;
        head.next= newNode;
        head.prev= newNode;

        //add item and update counters
        ll.insertItem(newNode, item);
        size++;

        //System.out.println(currentNode.items[0]);
    }

    else {
        if (currentNode.next== head) {
            ll.insertItem(currentNode, item);
        }

        while (currentNode.next != head) {
            currentNode= currentNode.next;
            System.out.println(currentNode.items[0]);

            //if the add item is less than first item, move to previous node
            if (comp.compare(item, currentNode.items[0])<0) 
                currentNode= currentNode.prev;

            //if item fits within a chunk
            if (comp.compare(item, currentNode.items[0])> 0 && 
                    comp.compare(item, currentNode.items[currentNode.numUsed-1])<0) {
                ll.insertItem(currentNode, item);


                //otherwise, move search onto next node
            } else {
                currentNode= currentNode.next;
            }
        } 
    }
    return true;
}

ll.insertItem - это вспомогательный метод во вложенном классе, который определяет место в массиве для вставки элемента, и, если массив заполнен, разделяет узел на два узла, копируя вторую половину старого узла новый, затем добавляет элемент в соответствующий узел. Я реализовал его как 

public void insertItem(Chunk<E> node, E item) {
        if(node.numUsed==0) {
            node.items[0]=item;
            node.numUsed++;

        }else if (node.numUsed<chunkSize) {
            for (int i=0; i<=node.numUsed; i++) {
                if (comp.compare(item, node.items[i])>0) {
                    for (int j= node.numUsed; j>i; j--) {
                        node.items[j+1]= node.items[j];
                    }

                    node.items[i]= item;
                    node.numUsed++;
                }
            }
        } else {

            //make new chunk, determine which chunk item should be added
            Chunk<E> newChunk= newChunk(node);
            size++;

            //if item fits in new node
            if (comp.compare(item, newChunk.items[0])>0) {
                insertItem(newChunk, item);
            } else {
                insertItem(node, item); //item fits in old node
            }
        }
    }

То, что я не получаю, - это то, почему это застряло в бесконечном цикле, особенно на первом символе тестовой строки. Поскольку условное if (size==0) выполняется, почему код повторяет добавление символа?

Addenum - запрошено RD 

System.out.println("insertion order: "+order);
    Comparator<String> comp = new StringCmp();
    ((CmpCnt)comp).resetCmpCnt();            // reset the counter inside the comparator
    ChunkList<String> clist = new ChunkList<String>(comp);
    for (int i = 0; i < order.length(); i++){
        String s = order.substring(i, i+1);
        clist.add(s);
    }

1 Ответ

2 голосов
/ 16 октября 2010

Вы не увеличиваете numUsed после добавления первого элемента

это: 

if(node.numUsed==0) {
            node.items[0]=item;

        }

должно быть: 

if(node.numUsed==0) {
            node.items[0]=item;
            node.numUsed++;
        }
...