tBane Temat założony przez niniejszego użytkownika |
[C++] Sortowanie Przez Wstawianie Listy Jednokierunkowej » 2023-08-04 07:03:57 Witam! Nie śmiać się proszę - to moja słaba strona a algorytm utracilem. W internecie nie mogłem znaleźc takowego.. Otoz potrzebuje gotowca na sort przez wstawianie dla listy jednokierunkowej (w takiej postaci), bo i tak tego nie zrozumiem, a nawet jak zrozumiem to zapomnę ( po to się kody przechowuje :D). Poniżej przedstawiam strukturę i to co udało mi się w wolnym czasie samemu wytworzyc: class object
{
public:
int value;
object * next;
object( int );
~object();
};
class lista
{
public:
object * firstObject;
lista();
~lista();
void sort();
};
void lista::sort()
{
object * newFirstObject = new object( firstObject );
object * no, no2; if( newFirstObject != NULL )
{
for( object * o = firstObject->next; o != NULL; o = o->next )
{
no = new object( o );
if( no->value < newFirstObject->value )
{
no->next = newFirstObject;
newFirstObject = no;
} else
{
no2 = newFirstObject;
while( no2->next->next != NULL && no->value < no2->value )
no2 = no2->next;
if( no->value < no2->value )
no2->next = no;
else
{
no->next = no2->next;
}
}
}
}
firstObject = newFirstObject;
}
|
|
DejaVu |
» 2023-08-04 09:50:24 Chat GPT: Witaj! Nie ma sprawy, postaram się pomóc. Wygląda na to, że próbujesz zaimplementować sortowanie przez wstawianie dla listy jednokierunkowej. Mam kilka uwag co do Twojego kodu: Konstruktor klasy object przyjmuje jako argument wartość int, ale w kodzie próbujesz przekazać mu wskaźnik na inny obiekt. Konstruktor powinien wyglądać tak: object::object( int val )
{
value = val;
next = NULL;
} W funkcji sort() występują błędy związane z brakiem alokacji pamięci dla obiektów. Przy sortowaniu przez wstawianie nowo tworzone obiekty muszą być dynamicznie alokowane (za pomocą new) i zwalniane po zakończeniu sortowania. Twoja implementacja sortowania przez wstawianie nie jest jeszcze kompletna. Musisz w niej uwzględnić poprawne wstawianie elementów na właściwe miejsca w posortowanej liście. Poniżej znajduje się poprawiona wersja implementacji sortowania przez wstawianie dla Twojej klasy lista: #include <iostream>
class object
{
public:
int value;
object * next;
object( int val );
};
object::object( int val )
{
value = val;
next = nullptr;
}
class lista
{
public:
object * firstObject;
lista();
~lista();
void sort();
};
lista::lista()
{
firstObject = nullptr;
}
lista::~lista()
{
object * current = firstObject;
while( current != nullptr )
{
object * temp = current;
current = current->next;
delete temp;
}
}
void lista::sort()
{
if( firstObject == nullptr || firstObject->next == nullptr )
{
return;
}
object * sorted = nullptr; object * unsorted = firstObject; while( unsorted != nullptr )
{
object * current = unsorted;
unsorted = unsorted->next;
if( sorted == nullptr || current->value < sorted->value )
{
current->next = sorted;
sorted = current;
}
else
{
object * temp = sorted;
while( temp->next != nullptr && current->value >= temp->next->value )
{
temp = temp->next;
}
current->next = temp->next;
temp->next = current;
}
}
firstObject = sorted;
}
int main()
{
lista mylist;
mylist.firstObject = new object( 5 );
mylist.firstObject->next = new object( 2 );
mylist.firstObject->next->next = new object( 8 );
mylist.firstObject->next->next->next = new object( 1 );
mylist.firstObject->next->next->next->next = new object( 3 );
std::cout << "Before sorting: ";
object * current = mylist.firstObject;
while( current != nullptr )
{
std::cout << current->value << " ";
current = current->next;
}
mylist.sort();
std::cout << "\nAfter sorting: ";
current = mylist.firstObject;
while( current != nullptr )
{
std::cout << current->value << " ";
current = current->next;
}
delete mylist.firstObject->next->next->next->next;
delete mylist.firstObject->next->next->next;
delete mylist.firstObject->next->next;
delete mylist.firstObject->next;
delete mylist.firstObject;
return 0;
} Ten kod powinien poprawnie posortować elementy w Twojej liście jednokierunkowej za pomocą sortowania przez wstawianie. Wprowadziłem poprawki związane z alokacją i zwalnianiem pamięci oraz poprawiłem logikę wstawiania elementów na odpowiednie miejsce w posortowanej liście. |
|
tBane Temat założony przez niniejszego użytkownika |
» 2023-08-04 15:35:46 No! I teraz jestem uratowany, czasem zapominam o chacie GPT, ale dobrze też jest mieć dodatkowe źródło wiedzy ;-)
Dziękuję za pomoc DejaVu :-) |
|
tBane Temat założony przez niniejszego użytkownika |
» 2023-08-04 16:12:15 Po wielu negocjacjach z Chatem GPT, udało mi się odzyskać utracony algorytm! Oto mój słynny algorytm sprzed paru lat, który jest prosty czytelny i wymaga zdolności algorytmicznych, których mi niestety brakuje :-) void mapManager::sortObject()
{
if( firstObject != NULL && firstObject->next != NULL )
{
object * newFirst = firstObject;
object * current = firstObject->next;
newFirst->next = NULL;
while( current != NULL )
{
object * next = current->next;
if( current->y < newFirst->y )
{
current->next = newFirst;
newFirst = current;
} else
{
object * search = newFirst;
while( search->next != NULL && search->next->y < current->y )
search = search->next;
current->next = search->next;
search->next = current;
};
current = next;
}
firstObject = newFirst;
}
}
|
|
pekfos |
» 2023-08-04 18:55:14 Tylko po co chcesz używać listy jednokierunkowej? Chcesz gotowca, więc czemu nie std::vector<> i std::sort()? po to się kody przechowuje Nom, na systemach kontroli wersji. Jak choćby darmowych hostingach SVN/Git. |
|
DejaVu |
» 2023-08-04 19:15:46 Takie 'algorytmy' w 99,99999% przypadków mają zastosowanie tylko na studiach, aby nauczyć 'jak są zbudowane algorytmy' (lub jak je się buduje). W 'produkcyjnych' rozwiązaniach używa się gotowców, które są szybsze, stabilne i... czytelne. |
|
pekfos |
» 2023-08-04 19:23:32 I teraz poprawia przedmiot, że potrzebuje kodu drugi raz? Mam przeczucie że chodzi o wydajność. |
|
tBane Temat założony przez niniejszego użytkownika |
» 2023-08-04 21:26:42 Nie, nie na studia. Tworzę RPG 2D i potrzebowałem sortu, co by w odpowiedniej kolejności obiekty renderować.Teraz wszystko śmiga cacy :D i nawet nie zacina przy 2000 tekstur 128x128 na telefonie na oko że 30FPS). Więc jest optymalnie w moim przypadku ;-) ej pefkos, DejaVu mam takie pytanie, czy tematy, które trafiają do kosza później znikają z forum, w sensie czy są trwale usuwane? |
|
| « 1 » |