C Academy · leksjon

Søk og frigjøring

Finn noder og frigjør minne.

Leksjon 4 av 413 trinn

Søk og frigjøring er en gratis leksjon i C Academy på CoddyKit. Dette er leksjon 4 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i C Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i C Academy inneholder totalt 4 leksjoner.

Søk i et BST

Søk utnytter ordningsregelen. Ved hver node sammenligner vi målet med nodeverdien og går videre inn i bare ett av deltrærne.

Fordi vi forkaster halvparten av de gjenværende nodene ved hvert trinn, avhenger søkekostnaden av høyden på treet, ikke av størrelsen.

Rekursivt søk

Det rekursive søket har to basistilfeller: Et tomt deltre betyr at verdien ikke ble funnet, og en samsvarende verdi betyr at den ble funnet.

Ellers rekurserer vi til venstre eller høyre, avhengig av sammenligningen.

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);
}

Iterativt søk

Søk kan også gjøres med en enkel løkke, slik at kostnaden ved rekursjon unngås.

Vi følger pekere nedover i treet til vi finner målet eller kommer til slutten ved 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 */
}

Søk i praksis

Dette programmet bygger et BST og søker etter en verdi som finnes, og en som ikke finnes. Deretter skriver det ut om hver verdi ble funnet.

En returverdi som ikke er NULL, betyr at verdien ble funnet. NULL betyr at verdien ikke finnes i treet.

#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;
}

Finne minimumsverdien

I et BST er den minste verdien den noden som ligger lengst til venstre: fortsett å følge left til den er NULL.

Tilsvarende er maksimumsverdien noden lengst til høyre. Disse hjelpefunksjonene er viktige ved sletting og ved områdesøk.

Node *find_min(Node *root) {
    if (root == NULL) return NULL;
    while (root->left != NULL)
        root = root->left;
    return root;
}

Hvorfor frigjøring er viktig

Hver node ble opprettet med malloc, så hver node må leveres tilbake med free. Hvis De glemmer å frigjøre minnet, oppstår en minnelekkasje.

Men De kan ikke frigjøre en node og deretter lese barnpekerne dens, så rekkefølgen for frigjøring er avgjørende.

Frigjør i post-order

Den sikre måten å frigjøre et tre på er post-order: frigjør begge barna først, og frigjør deretter selve noden.

Dette garanterer at vi leser en nodes left- og right-pekere før minnet til noden frigjøres.

void free_tree(Node *root) {
    if (root == NULL) return;
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

En farlig feil rekkefølge

Hvis De frigjør noden før De rekursivt går inn i barna, oppstår udefinert oppførsel: De ville ha dereferert frigjort minne for å nå deltrærne.

Dette er en klassisk use-after-free-feil. Frigjør alltid barna først.

/* 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);
}

Unngå hengende pekere

Etter at free_tree returnerer, inneholder den opprinnelige rotpekeren fortsatt den gamle adressen, men minnet er borte.

Hvis De setter den tilbake til NULL i kalleren, forhindrer De utilsiktet bruk av en hengende peker.

free_tree(root);
root = NULL;   /* avoid a dangling pointer */

Telle frigjorte noder

Vi kan bekrefte at frigjøringen fungerer, ved å telle nodene under en post-order-gjennomgang og deretter frigjøre hver av dem.

Dette programmet bygger et tre, frigjør det og rapporterer hvor mange noder som ble frigjort.

#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;
}

Søk og frigjøring samlet

En komplett livssyklus: bygg treet, søk i det og frigjør det deretter. Når alle tre trinnene utføres, forblir programmene korrekte og uten minnelekkasjer.

Verktøy som Valgrind kan bekrefte at hver malloc har en tilhørende free.

/* lifecycle
 * 1. insert values     (allocate)
 * 2. search as needed   (read-only)
 * 3. free_tree(root)    (deallocate)
 * 4. root = NULL        (avoid dangling)
 */

Rask sjekk

Resonner rundt trygg frigjøring av minne.

Besvar den i den interaktive leksjonen

Oppsummering

BST-søk sammenligner verdier og går ned i ett deltre per trinn, med en tidskostnad som er proporsjonal med høyden. Minimumsverdien er noden lengst til venstre, og maksimumsverdien er noden lengst til høyre.

Frigjør et tre i post-order, slik at barna frigjøres før forelderen. Sett deretter roten til NULL for å unngå en hengende peker.

Gratis å komme i gang

Lær deg C med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs: 39
Leksjoner: 144

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «Søk og frigjøring» gratis?

Ja – hele teksten i «Søk og frigjøring» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av C Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i C Academy inneholder totalt 4 leksjoner.

Hva lærer jeg i «Søk og frigjøring»?

Finn noder og frigjør minne. Du øver på C Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med C Academy?

Ingen tidligere erfaring er nødvendig. C Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.

Hvor lang tid tar leksjonen «Søk og frigjøring»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne C Academy-leksjonen?

Ja. Alle C Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

← Tilbake til C Academy