5
Mam problem z posortowaną połączoną listą. Nie mogę wstawić elementu w stałym czasie. Jeśli to możliwe, niż jak mogę to rozwiązać?Jak wstawić element na posortowanej liście połączonej w ramach złożoności o stałym czasie?
I tym razem funkcja złożoności jest Big-O (N)
template <class ItemType>
void SortedType<ItemType>::InsertItem(ItemType item)
{
NodeType<ItemType>* newNode;
NodeType<ItemType>* predLoc;
NodeType<ItemType>* location;
bool moreToSearch;
location = listData;
predLoc = NULL;
moreToSearch = (location != NULL);
while (moreToSearch)
{
if (location->info < item)
{
predLoc = location;
location = location->next;
moreToSearch = (location != NULL);
}
else moreToSearch = false;
}
newNode = new NodeType<ItemType>;
newNode->info = item;
if (predLoc == NULL)
{
newNode->next = listData;
listData = newNode;
}
else
{
newNode->next = location;
predLoc->next = newNode;
}
length++;
}
Nie możesz. Gdybyś mógł to zrobić, zrewolucjonizowałbyś sortowanie, możesz zacząć od pustej, połączonej listy, która z definicji zostanie posortowana, dodaj pierwszy element, nadal posortowany, a następnie kontynuuj, co oznaczałoby, że sortowanie będzie miało postać O (n), to jest niemożliwe. –