[C] Listy, funkcja malloc a złożoność pamięciowa

MlodyMatematykAmator
Użytkownik
Użytkownik
Posty: 55
Rejestracja: 23 mar 2019, o 17:45
Płeć: Mężczyzna
wiek: 19
Lokalizacja: Kraków
Podziękował: 16 razy

[C] Listy, funkcja malloc a złożoność pamięciowa

Post autor: MlodyMatematykAmator » 23 gru 2019, o 13:47

Witam. Mam pytanie dotyczące złożoności pamięciowej, a funkcji malloc w C.

Załóżmy, że mam pewną listę niecykliczną (posiadającą "dwie komórki": Lista -> wart oraz Lista -> nast). Moim celem jest to, aby z elementów listy o wartościach nieparzystych (Lista -> wart) stworzyć odrębną listę i usunąć je z listy pierwotnej, aby były dwie listy - jedna o wartościach nieparzystych, druga o wartościach parzystych.

Sam 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?

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ą

Kod: Zaznacz cały

free(x);
mamy złożoność pamięciową liniową czy stałą?

Pozdrawiam,
Damian
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 8838
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 37 razy
Pomógł: 1879 razy

Re: [C] Listy, funkcja malloc a złożoność pamięciowa

Post autor: Dasio11 » 23 gru 2019, o 15:12

MlodyMatematykAmator pisze:
23 gru 2019, o 13:47
Sam 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ą

Kod: Zaznacz cały

free(x);
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.

ODPOWIEDZ