Сортировка вставок с односвязным списком в переполнении стека

Я пытаюсь написать метод для моего класса LinkedList, который будет сортировать связанный список объектов Person по их имени. Мой метод компилируется нормально, но когда я пытаюсь отсортировать список людей, вывод неправильный. Это также никогда не прекращает бежать. Например, этот код

Person *p1 = new Person("Kirstie", "Booras");
Person *p2 = new Person("Alex", "Arosenius");
Person *p3 = new Person("Stephanie", "Moewe");
Person *p4 = new Person("Bella", "Moewe");

LinkedList ll;
ll.insertFront(*p1);
ll.insertFront(*p2);
ll.insertFront(*p3);
LinkedList newList = ll.insertionSort();
newList.print();
cout << endl;

Дает этот вывод

Booras, Kirstie

Arosenius, Alex

Может ли кто-нибудь помочь мне понять, где я ошибся с моим алгоритмом? Спасибо!

Это метод, который я использую для сортировки имен по первым и последним:

int Person::compareName(Person p)
{
if (lName.compare(p.lName) > 0)
{
return 1;
}
else if (lName.compare(p.lName) == 0)
{
if (fName.compare(p.fName) > 0)
{
return 1;
}
else return -1;
}
else return -1;
}

Метод сортировки вставкой:

LinkedList LinkedList::insertionSort()
{
//create the new list
LinkedList newList;
newList.front = front;

Node *n;
Node *current = front;
Node *trail = NULL;

for(n=front->link; n!= NULL; n = n->link)//cycle through old chain
{
Node* newNode = n;

//cycle through new, sorted chain to find insertion point
for(current = newList.front; current != NULL; current = current->link)
{
//needs to go in the front
if(current->per.compareName(n->per) < 0)
{
break;
}

else
{
trail = current;

}
}

//if it needs to be added to the front of the chain
if(current == front)
{
newNode->link = newList.front;
newList.front = newNode;
}
//else goes in middle or at the end
else{
newNode->link = current;
trail->link = newNode;
}

return newList;
}

0

Решение

В вашем внутреннем цикле for есть ссылка current->, а в другом — внутренняя петля for. Я предполагаю, что у вас действительно есть ссылка current = current-> в цикле for или она ничего не делает. Если так, вы пропустите все остальные элементы.

У вас также есть язык — вы не создаете новые узлы, вы изменяете узлы в своем первоначальном списке. Это значит, что вы меняете список по мере его прохождения, что приведет к повреждению списка при его сортировке. Поведение не определено и зависит от порядка добавления элементов.

0

Другие решения

Даже после того, как вы исправили любые проблемы со связанными списками (которые я не рассматривал), ваш compareName() функция имеет недостаток — при сравнении Person объекты с одинаковой фамилией могут возвращаться из функции без указания значения (в случаях, когда Name.compare(p.fName) <= 0).

Получение неопределенного результата от функции сравнения приведет к поломке любого вида.

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

0

По вопросам рекламы [email protected]