Wyszukiwanie i zwalnianie pamięci
Znajdzie Pan/Pani węzły i zwolni pamięć.
Wyszukiwanie i zwalnianie pamięci to bezpłatna lekcja C Academy na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej C Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs C Academy zawiera 4 lekcji w sumie.
Wyszukiwanie w BST
Wyszukiwanie wykorzystuje regułę uporządkowania. W każdym węźle porównujemy szukaną wartość z wartością węzła i przechodzimy tylko do jednego poddrzewa.
Ponieważ na każdym kroku odrzucamy połowę pozostałych węzłów, koszt wyszukiwania zależy od wysokości drzewa, a nie od jego rozmiaru.
Wyszukiwanie rekurencyjne
Wyszukiwanie rekurencyjne ma dwa przypadki bazowe: puste poddrzewo oznacza, że nie znaleziono wartości, a zgodna wartość oznacza jej znalezienie.
W przeciwnym razie wykonujemy rekurencję w lewo lub w prawo, zależnie od wyniku porównania.
Node *search(Node *root, int target) {
if (root == NULL || root->value == target)
return root;
if (target < root->value)
return search(root->left, target);
return search(root->right, target);
}Wyszukiwanie iteracyjne
Wyszukiwanie może również mieć postać prostej pętli, która pozwala uniknąć narzutu rekurencji.
Podążamy za wskaźnikami w dół drzewa, aż znajdziemy szukaną wartość albo dotrzemy do końca oznaczonego przez NULL.
Node *search_iter(Node *root, int target) {
while (root != NULL) {
if (target == root->value) return root;
root = (target < root->value)
? root->left : root->right;
}
return NULL; /* not found */
}Wyszukiwanie w działaniu
Ten program tworzy BST i wyszukuje wartość obecną oraz nieobecną w drzewie, wypisując informację, czy każda z nich została znaleziona.
Niezerowy wskaźnik oznacza znalezienie wartości, a NULL oznacza, że wartości nie ma w drzewie.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
if(!r) return cn(v);
if(v<r->value) r->left=insert(r->left,v);
else if(v>r->value) r->right=insert(r->right,v);
return r;
}
Node *search(Node *r,int t){
if(!r||r->value==t) return r;
return t<r->value ? search(r->left,t) : search(r->right,t);
}
int main(void){
Node *root=NULL;
int d[]={10,5,15,3,7};
for(int i=0;i<5;i++) root=insert(root,d[i]);
printf("7:%s 99:%s\n",
search(root,7)?"found":"no",
search(root,99)?"found":"no");
return 0;
}Znajdowanie minimum
W BST najmniejsza wartość znajduje się w najbardziej lewym węźle: należy podążać za left, aż przyjmie wartość NULL.
Analogicznie maksimum znajduje się w najbardziej prawym węźle. Te funkcje pomocnicze są ważne przy usuwaniu oraz zapytaniach zakresowych.
Node *find_min(Node *root) {
if (root == NULL) return NULL;
while (root->left != NULL)
root = root->left;
return root;
}Dlaczego zwalnianie pamięci ma znaczenie
Każdy węzeł został utworzony za pomocą malloc, więc każdy węzeł musi zostać zwrócony za pomocą free. Pominięcie zwolnienia powoduje wyciek pamięci.
Nie można jednak zwolnić węzła, a następnie odczytywać wskaźników jego dzieci, dlatego kolejność zwalniania ma kluczowe znaczenie.
Zwalnianie w porządku post-order
Bezpiecznym sposobem zwolnienia drzewa jest porządek post-order: najpierw zwalniamy oba dzieci, a dopiero potem sam węzeł.
Gwarantuje to odczytanie wskaźników left i right węzła przed zwolnieniem pamięci zajmowanej przez ten węzeł.
void free_tree(Node *root) {
if (root == NULL) return;
free_tree(root->left);
free_tree(root->right);
free(root);
}Niebezpieczna, błędna kolejność
Jeśli zwolnisz węzeł przed przejściem rekurencyjnym do jego dzieci, spowodujesz niezdefiniowane zachowanie: aby dotrzeć do poddrzew, trzeba będzie wyłuskać zwolnioną pamięć.
To klasyczny błąd use-after-free. Zawsze najpierw zwalniaj dzieci.
/* WRONG: use-after-free */
void bad_free(Node *root) {
if (!root) return;
free(root); /* freed here */
bad_free(root->left); /* reads freed memory! */
bad_free(root->right);
}Unikanie wiszących wskaźników
Po zakończeniu działania free_tree pierwotny wskaźnik korzenia nadal przechowuje stary adres, ale pamięć już nie istnieje.
Ustawienie go z powrotem na NULL w funkcji wywołującej zapobiega przypadkowemu użyciu wiszącego wskaźnika.
free_tree(root);
root = NULL; /* avoid a dangling pointer */Zliczanie zwolnionych węzłów
Możemy potwierdzić poprawność zwalniania, zliczając węzły podczas przechodzenia post-order, a następnie zwalniając każdy z nich.
Ten program tworzy drzewo, zwalnia je i informuje, ile węzłów zostało zwolnionych.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
if(!r) return cn(v);
if(v<r->value) r->left=insert(r->left,v);
else if(v>r->value) r->right=insert(r->right,v);
return r;
}
int free_count(Node *r){
if(!r) return 0;
int c = free_count(r->left) + free_count(r->right);
free(r);
return c + 1;
}
int main(void){
Node *root=NULL;
int d[]={10,5,15,3,7};
for(int i=0;i<5;i++) root=insert(root,d[i]);
printf("freed=%d\n", free_count(root));
root = NULL;
return 0;
}Wyszukiwanie i zwalnianie razem
Pełny cykl życia wygląda tak: utworzenie drzewa, wyszukanie w nim wartości, a następnie jego zwolnienie. Wykonanie wszystkich trzech kroków zapewnia poprawność programu i brak wycieków pamięci.
Narzędzia takie jak Valgrind mogą potwierdzić, że każdemu wywołaniu malloc odpowiada wywołanie free.
/* lifecycle
* 1. insert values (allocate)
* 2. search as needed (read-only)
* 3. free_tree(root) (deallocate)
* 4. root = NULL (avoid dangling)
*/Szybkie sprawdzenie
Przeanalizuj bezpieczne zwalnianie pamięci.
Podsumowanie
Wyszukiwanie w BST porównuje wartości i przy każdym kroku przechodzi do jednego poddrzewa, a jego koszt jest proporcjonalny do wysokości drzewa. Minimum znajduje się w najbardziej lewym węźle, a maksimum w najbardziej prawym.
Zwalniaj drzewo w porządku post-order, aby dzieci zostały zwolnione przed rodzicem, a następnie ustaw korzeń na NULL, by uniknąć wiszącego wskaźnika.
Ucz się C dzięki korepetycjom AI — za darmo
Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.
- Kursy
- 39
- Lekcje
- 144
Często zadawane pytania
Czy lekcja „Wyszukiwanie i zwalnianie pamięci” jest bezpłatna?
Tak — pełny tekst „Wyszukiwanie i zwalnianie pamięci” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu C Academy, przejdź na CoddyKit PRO. Kurs C Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Wyszukiwanie i zwalnianie pamięci”?
Znajdzie Pan/Pani węzły i zwolni pamięć. Ćwiczysz C Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć C Academy?
Nie wymagamy żadnego doświadczenia. C Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Wyszukiwanie i zwalnianie pamięci”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji C Academy?
Tak. Każda lekcja C Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Węzły i struktura drzewa
- Wstawianie do BST
- Przechodzenie drzewa
- Wyszukiwanie i zwalnianie pamięci