Я пытаюсь написать метод для моего класса 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;
}
В вашем внутреннем цикле for есть ссылка current->, а в другом — внутренняя петля for. Я предполагаю, что у вас действительно есть ссылка current = current-> в цикле for или она ничего не делает. Если так, вы пропустите все остальные элементы.
У вас также есть язык — вы не создаете новые узлы, вы изменяете узлы в своем первоначальном списке. Это значит, что вы меняете список по мере его прохождения, что приведет к повреждению списка при его сортировке. Поведение не определено и зависит от порядка добавления элементов.
Даже после того, как вы исправили любые проблемы со связанными списками (которые я не рассматривал), ваш compareName()
функция имеет недостаток — при сравнении Person
объекты с одинаковой фамилией могут возвращаться из функции без указания значения (в случаях, когда Name.compare(p.fName) <= 0
).
Получение неопределенного результата от функции сравнения приведет к поломке любого вида.
Поскольку это скорее домашнее задание, я оставлю исправление проблемы в качестве упражнения.