MlodyMatematykAmator pisze: ↑23 gru 2019, o 13:47Sam algorytm jest dosyć prosty, ale mam kilka pytań dotyczących aspektów technicznych jego wykonania. Po pierwsze, czy tworząc nową listę dla numerów nieparzystych powinniśmy użyć funkcji malloc? Tzn. przy jej tworzeniu:
Kod: Zaznacz cały
Lista* x;
x = (Lista*) malloc (sizeof(Lista));
Czy bez użycia malloca od razu przekierowywać Lista -> nast do listy x i usuwać je z listy pierwotnej?
Opisywana przez Ciebie operacja nie dodaje nowych węzłów, a tylko zmienia połączenia między już istniejącymi. Nie potrzeba do tego dodatkowej pamięci, zatem i funkcja
malloc
nie jest potrzebna.
MlodyMatematykAmator pisze: ↑23 gru 2019, o 13:47
Lista elementów nieparzystych była potrzebna tylko w pewnym celu, w finalnej części zadania już nie jest potrzebna. Czy kończąc program instrukcją
mamy złożoność pamięciową liniową czy stałą?
Złożoność pamięciowa programu to ilość pamięci, która jest niezbędna żeby program mógł być wykonany od początku do końca. Ta ilość oczywiście nie zależy od tego, czy używana pamięć zostaje na końcu zwolniona, więc bardziej prawdopodobna odpowiedź brzmi: złożoność jest liniowa - jednak to tylko odpowiedź orientacyjna, bo przecież w ogóle nie opisałeś, jak działa Twój algorytm, a bez takiej wiedzy niemożliwe jest ustalenie złożoności programu.
Jednak niezależnie od powyższej kwestii, zaalokowaną pamięć warto zwalniać, gdy nie jest już potrzebna. A żeby zrobić to poprawnie, nie wystarczy zwykłe
free(x)
, bo to zwalnia tylko pierwszy element listy, a co gorsza jest to ten element, który pamięta adresy następnych, więc po jego usunięciu powstaje wyciek pamięci. Żeby poprawnie zwolnić pamięć po liście, powinieneś zwolnić wszystkie jej elementy.