Единый отсортированный связанный список — бесконечный цикл
Я работаю с одним связанным списком, и я хочу отсортировать его от меньшего к большему значениям целого числа. Я думал, что у меня была идея, но затем выполнение заходит в бесконечный цикл, и я не могу ясно понять, почему. Это часть кода, с которой я работал:
class Node {
int data;
Node* next;
public:
Node() { };
void SetData(int aData) { data = aData; };
void SetNext(Node* aNext) { next = aNext; };
int Data() { return data; };
Node* Next() { return next; };
};
class List {
Node *head;
public:
List() { head = NULL; };
void Print();
void Append(int data);
void Delete(int data);
};
void List::Append(int data) {
// Create a new node
Node* newNode = new Node();
newNode->SetData(data);
newNode->SetNext(NULL);
// Create a temp pointer
Node *tmp = head;
if ( tmp != NULL ) {
// Nodes already present in the list
// Parse to end of list anytime the next data has lower value
while ( tmp->Next() != NULL && tmp->Next()->Data() <= newNode->Data() ) {
tmp = tmp->Next();
}
// Point the lower value node to the new node
tmp->SetNext(newNode);
newNode->SetNext(tmp->Next());
}
else {
// First node in the list
head = newNode;
}
}
void List::Print() {
// Temp pointer
Node *tmp = head;
// No nodes
if ( tmp == NULL ) {
cout << "EMPTY" << endl;
return;
}
// One node in the list
if ( tmp->Next() == NULL ) {
cout << tmp->Data();
cout << " --> ";
cout << "NULL" << endl;
}
else {
// Parse and print the list
do {
cout << tmp->Data();
cout << " --> ";
tmp = tmp->Next();
}
while ( tmp != NULL );
cout << "NULL" << endl;
}
}
Я запутался, если список увеличивается бесконечно, или ошибка происходит из-за функции Print …
Извините за, возможно, фиктивные ошибки.
Благодарю.
Решение
Ваша проблема в этих двух строках:
tmp->SetNext(newNode);
newNode->SetNext(tmp->Next());
Вы должны поменять их. Прямо сейчас вы устанавливаете tmp.next = newNode, а затем newNode.next = tmp.next (= newNode), поэтому newNode указывает на себя. Затем обход мимо newNode приводит к бесконечному циклу.
Другие решения
Вы не можете правильно связать два существующих узла. Посмотрите на этот фрагмент вашего кода:
tmp->SetNext(newNode);
newNode->SetNext(tmp->Next());
Если, например, у вас есть этот список:
голова -> 5
и вы хотите вставить узел с номером 4 у вас будет:
голова -> 5 <- тмп
newNode -> 4
С помощью tmp-> SetNext (newNode)
голова (и тмп) -> 5 -> 4 <- новый узел
С newNode-> SetNext (tmp-> Next ());
голова (и тмп) -> 5 -> 4 <- новый узел
Поэтому любая попытка перебрать список приведет к бесконечному циклу:
5
4
4
4
4 …… навсегда
// Point the lower value node to the new node
tmp->SetNext(newNode);
newNode->SetNext(tmp->Next());
Поскольку вы перезаписываете tmp->next во время первого вызова ваш второй вызов newNode->next к newNode сам, создавая цикл. Это вызывает ваш бесконечный цикл при вызове Print 😉
Решение состоит в том, чтобы сделать что-то вроде следующего …
Node* _next = tmp->Next();
tmp->SetNext(newNode);
newNode->SetNext(_next);
При этом ваш код все еще не работает. Проблема в том, что вы не проверяете, нужно ли вам разместить до глава списка; попробуйте сделать что-то следующим образом ..
if ( tmp ) {
// Check whether to become new head
if ( tmp->Data() > newNode->Data() ) {
newNode->SetNext(tmp);
head = newNode;
}
else {
// Nodes already present in the list
// Parse to end of list anytime the next data has lower value
while ( tmp->Next() && tmp->Next()->Data() <= newNode->Data() ) {
tmp = tmp->Next();
}
// Point the lower value node to the new node
Node* _next = tmp->Next();
tmp->SetNext(newNode);
newNode->SetNext(_next);
}
}
else {
// First node in the list
head = newNode;
}
Примечание: вы можете использовать список инициализаторов, чтобы переписать код как …
List() : head(NULL) { };
Кроме того, если NULL эквивалентно 0, вы можете упростить условия формы X == NULL а также X != NULL просто X а также !Xсоответственно.
См мой идеоновая паста для исправленной версии с примером.
int main() {
List l;
l.Append(15);
l.Append(40);
l.Append(7);
l.Print();
return 0;
}
… который производит
7 -> 15 -> 40 -> NULL