проблема кругового связанного списка в С++

Почему мой код связанного списка не работает? У него нет проблем с 4 заметками, но когда я добираюсь до 5, отсортированный связанный список, кажется, зависает. Разве он не знает, куда добавить и поместить новый узел?

Я имею в виду, например, первые данные - это имя, начинающееся с буквы А, а вторые начинаются с D, а третьи начинаются с C.. но когда я ввожу 5-е, буква I или K.. моя система как бы зависает или что-то в этом роде ..

Узел

Node * next;
Node * prev;
userData * data;

Список

Node * start;
Node * end;

Функция, которая объявляет новый узел в алфавитном порядке

void addUserData(userData * data){
        string name = data->getName();
        Node* node = new Node(data);

        if(isEmpty()){
            start = node;
            end = node;
            start->Next(end);
            end->Prev(start);
            return;
        }
        else if(!isEmpty() && start == end){
            node->Next(start);
            node->Prev(start);
            start->Next(node);
            start->Prev(node);

            end = node;

            if(start->getUserData()->getName().compare(node->getUserData()->getName())>0){
                end = start;
                start = node;
            }
            return;
        }
        else{
            Node *temp = start;
            if(name.compare("N") < 0){
                while(temp->getNext()->getNext()!=NULL && name.compare(temp->getNext()->getUserData()->getName())>0){
                    temp = temp ->getNext();
                }
            }
            else{
                temp = end;
                while(name.compare(temp->getUserData()->getName())<0){
                    temp = temp ->getPrev();
                }

            }
            if(name.compare(temp->getUserData()->getName())>0){
                node ->Next(temp->getNext());
                node ->Prev(temp);

                temp->Next(node);
                node->getNext()->Prev(node);

                if(name.compare(end->getUserData()->getName())>0){
                    end = node;

                }

            }else if(name.compare(temp->getUserData()->getName())<0){
                node->Next(temp);
                node->Prev(temp->getPrev());

                temp->getPrev()->Next(node);
                temp->Prev(node);

                if(name.compare(start->getUserData()->getName())<0){
                    start = node;
                }

            }else{
                cout<<"Name already exist\n";

            }

        }

    }

person Iqbal    schedule 16.04.2011    source источник
comment
Вы пытались запустить свой код через отладчик? Я не понимаю, как отладчик не покажет вам, почему ваш код ведет себя неправильно, учитывая конкретные входные данные, которые вы ему даете.   -  person DXM    schedule 16.04.2011
comment
Столько всего в этом плохого, что трудно сосчитать. В основном вы строите список как циклический (как после первой, так и второй вставки), но когда вы сканируете список, вы проверяете, являются ли указатели нулевыми.   -  person Raph Levien    schedule 16.04.2011
comment
@ user708280: одно замечание о строках, lhs < rhs обычно легче читать, чем lhs.compare(rhs) < 0. Чем проще читать исходный код, тем легче его отлаживать.   -  person Matthieu M.    schedule 16.04.2011


Ответы (1)


Взгляните на этот раздел:

if(name.compare("N") < 0){
  while(temp->getNext()->getNext()!=NULL && name.compare(temp->getNext()->getUserData()->getName())>0){
    temp = temp ->getNext();
  }
}
else{
  temp = end;
  while(name.compare(temp->getUserData()->getName())<0){
    temp = temp ->getPrev();
  }
}
  1. Yoiu have some untidy logic all through this code. For instance, checking for `NULL` doesn't make much sense, since there should never be a `NULL` in the circle. If you're trying to test the integrity of the list, do it carefully, not like this.
  2. This is the only place in the code where an endless loop can occur, so the problem really has to be here.
  3. Think carefully about what it means to sort a circular list, and what happens if you try to add an element that is either before all the others (in alphabetical order), or after all the others. This is where you hang.
person Beta    schedule 16.04.2011