Structs en gekoppelde datastructuren in C

Een struct groepeert samenhangende waarden in één record. De velden hebben namen en kunnen verschillende typen hebben. Een sensormeting heeft bijvoorbeeld zowel een identifier als een temperatuur nodig.

Een record definiëren en initialiseren

struct reading {
    int id;
    double temp_c;
};
struct reading r = {.temp_c = 21.5, .id = 7};
r.temp_c += 0.5;

De definitie introduceert het type struct reading; reading is de structtag. De afsluitende puntkomma hoort na de sluitende accolade. Het definiëren van het type reserveert geen object. De declaratie van r maakt één object en . selecteert de velden ervan. Hier wordt de temperatuur 22,0 °C. Als alleen een tag is gedeclareerd, bevat de typenaam struct: voor reading r; is een afzonderlijke typedef nodig.

Een initialisator zoals {7, 21.5} volgt de declaratievolgorde. Met veldaanduidingen zoals .id = 7 kun je velden in een andere volgorde noemen. Velden die in een initialisator ontbreken, krijgen nulwaarden, dus initialiseert {0} het hele record. Een lokale declaratie struct reading r; zonder initialisator laat de velden onbepaald totdat er waarden aan zijn toegewezen.

Een veld heeft een eigen type en adres. Om een temperatuur met scanf te lezen, gebruik je scanf("%lf", &r.temp_c) en controleer je of de retourwaarde 1 is. De punt bindt vóór &, dus geeft dit het adres van het double-veld door.

De waarden kopiëren en vergelijken

struct reading s = r;
s.temp_c = -4.0;
int same = r.id == s.id && r.temp_c == s.temp_c;

Een toewijzing kopieert alle velden. Als je s.temp_c wijzigt, blijft r.temp_c op 22,0 staan. Vaste arrays binnen structs worden ook gekopieerd: een veld char name[32] hoort bij het record. Dit werkt ook al kunnen afzonderlijke C-arrays niet met = worden toegewezen. Pointervelden vragen extra aandacht, omdat de gekopieerde pointer nog naar hetzelfde object wijst.

C definieert == niet voor hele structs. Vergelijk de velden die voor je taak de gelijkheid bepalen. memcmp vergelijkt ruwe bytes, inclusief opvulling, en kan een verschil melden tussen records waarvan de veldwaarden gelijk zijn.

De geheugenindeling volgen

Velden staan in declaratievolgorde, zonder opvulling vóór het eerste veld. De compiler kan ongebruikte bytes tussen velden en aan het einde toevoegen om aan uitlijningseisen te voldoen. Op een gangbaar 64-bitsplatform met een int van 4 bytes en een uitlijning van 4 bytes neemt struct { char c; int i; char d; } 12 bytes in. De velden beginnen op offsets 0, 4 en 8. Als je de volgorde wijzigt naar int i; char c; char d;, wordt de grootte doorgaans 8 bytes. Gebruik sizeof voor de werkelijke grootte en offsetof uit <stddef.h> voor een offset.

Structs kunnen genest zijn. Met struct point { double x_m, y_m; }; en struct rect { struct point corner; double width_m, height_m; }; bereik je met box.corner.x_m de x-coördinaat van het hoekpunt in meters. Een struct kan geen volledig veld van zijn eigen type bevatten: daarvoor zou een oneindig groot object nodig zijn. Een pointer naar zijn eigen type heeft een vaste grootte en maakt gekoppelde knopen mogelijk.

Een typedef geeft een bestaand type een andere naam. Die verandert hoe je het type schrijft, niet hoe de objecten van dat type zich gedragen. typedef double meters; maakt meters tot een andere naam voor double.

Een struct een naam geven en op waarde doorgeven

typedef struct {
    int id;
    double temp_c;
} reading;

reading make_reading(int id, double t) {
    reading r = {id, t};
    return r;
}
void warm_copy(reading r) {
    r.temp_c += 1.0;
}

Je kunt nu reading r = make_reading(7, 21.5); declareren. Een struct teruggeven geeft zijn waarde terug. De aanroep warm_copy(r) geeft de functie een kopie, zodat de temperatuur van de aanroepende functie 21,5 °C blijft. Een kopie van een klein record is vaak de duidelijkste interface als het object van de aanroepende functie ongewijzigd moet blijven.

Een type dat naar zichzelf verwijst, heeft zijn tag binnen de definitie nodig:

typedef struct node {
    int number;
    struct node *next;
} node;

De alias node komt beschikbaar na de declaratie. Binnen deze accolades benoemt struct node het onvolledige type al en kan het voor een pointer worden gebruikt. De tag en de alias mogen dezelfde schrijfwijze hebben, omdat tags een eigen naamruimte gebruiken.

Het object van de aanroepende functie via een pointer bereiken

void warm(reading *p) {
    p->temp_c += 1.0;
}
reading r = {7, 21.5};
reading *p = &r;
p->temp_c -= 1.5;
warm(&r);

De aftrekking verandert r.temp_c in 20,0; warm verandert de waarde daarna in 21,0. De functie ontvangt een kopie van het adres en beide pointers bereiken nog steeds hetzelfde record. Gebruik -> met een pointer en . met een structobject. p->temp_c betekent (*p).temp_c. De haakjes zijn nodig omdat veldtoegang sterker bindt dan derefereren: *p.temp_c probeert een veld van p te selecteren voordat * wordt toegepast.

Om te lezen zonder de struct te kopiëren, laat je de functie const reading *p ontvangen. Een toewijzing aan p->temp_c via die pointer wordt afgewezen. De pointervariabele kan nog wel veranderen, bijvoorbeeld als die door een array beweegt. reading *const p maakt daarentegen de pointer zelf vast. Bij structs met pointervelden maakt een pointer naar een const-gekwalificeerde struct de afzonderlijk gereserveerde gegevens waarnaar die velden wijzen niet alleen-lezen.

Een heaprecord een eigenaar geven

Neem <stdlib.h> op voor geheugenallocatie en <stdbool.h> voor dit resultaat dat aangeeft of de bewerking is geslaagd:

bool make_heap_reading(reading **out, int id, double t) {
    reading *p = malloc(sizeof *p);
    if (p == NULL) return false;
    *p = (reading){.id = id, .temp_c = t};
    *out = p;
    return true;
}

De functie schrijft pas naar *out nadat de geheugenallocatie is geslaagd. De aanroepende functie kan reading *item = NULL; declareren, make_heap_reading(&item, 8, -2.0) aanroepen, een mislukt resultaat afhandelen en later free(item) aanroepen. sizeof *p bepaalt de grootte van het type waarnaar wordt gewezen, ook voordat p naar een geïnitialiseerd record wijst; deze expressie leest dat record niet.

Een pointer naar een automatische lokale struct wordt ongeldig wanneer de functie terugkeert. Geef de structwaarde of een heapallocatie met een duidelijke eigenaar terug. Door &r terug te geven vanuit een functie waarvan de lokale variabele r is, kun je de levensduur van die variabele niet verlengen.

Een array van structs bewaart records naast elkaar. Gebruik een index om een record te selecteren en daarna een punt om een veld te selecteren. Daardoor werken doorlopen, zoeken en sorteren grotendeels zoals bij een array van getallen.

Records doorlopen met een expliciet aantal

reading readings[4] = {
    {1, 21.5}, {2, -3.0}, {3, 18.25}, {4, 30.0}
};
size_t n = sizeof readings / sizeof readings[0];
size_t best = 0;
for (size_t i = 1; i < n; ++i) {
    if (readings[i].temp_c > readings[best].temp_c)
        best = i;
}

Hier is reading de alias voor de struct met een identifier en een temperatuur. De beste index loopt op van 0 naar 3, dus heeft het warmste record id 4 en temperatuur 30,0 °C. Beginnen met een bestaand element werkt ook als elke temperatuur negatief is; beginnen met nul als verondersteld maximum kan misgaan. Deze doorloop vereist minstens één element. Een herbruikbare zoekfunctie moet een lege array melden voordat die element 0 leest.

Het aantal met sizeof werkt waar readings een array is. In een functieparameter wordt een arraydeclaratie een pointer, dus geef je n afzonderlijk door. (items + i)->temp_c en items[i].temp_c bereiken hetzelfde veld.

Een vergelijkingsfunctie voor qsort aanleveren

Neem <stdlib.h> op. Voor eindige temperatuurwaarden geeft deze vergelijkingsfunctie een teken terug zonder een klein temperatuurverschil om te zetten naar een geheel getal:

int cmp_temp(const void *a, const void *b) {
    const reading *x = a;
    const reading *y = b;
    return (x->temp_c > y->temp_c)
         - (x->temp_c < y->temp_c);
}
/* With the array above: */
qsort(readings, n, sizeof readings[0], cmp_temp);

De vergelijkingsfunctie ontvangt adressen van elementen. Negatief betekent dat het eerste eerder komt, nul betekent gelijk en positief betekent later. De gesorteerde id-volgorde is 2, 3, 1, 4. Als je het onbewerkte double-verschil teruggeeft, wordt een verschil zoals −0,25 afgekapt tot nul. Geheeltallige sleutels van elkaar aftrekken kan overlopen. Door eerst te vergelijken voorkom je die fouten. qsort behoudt de oorspronkelijke volgorde van gelijke elementen niet.

Een array vergroten zonder het geheugen te verliezen

Houd het aantal gebruikte elementen en de capaciteit afzonderlijk bij. Gebruik voor een gereserveerde array met positieve cap een tijdelijke pointer wanneer je de capaciteit verdubbelt. Neem <stdint.h> op voor SIZE_MAX:

if (cap > SIZE_MAX / 2 / sizeof *items) return false;
size_t new_cap = 2 * cap;
reading *tmp = realloc(items, new_cap * sizeof *items);
if (tmp == NULL) return false;
items = tmp;
cap = new_cap;

Deze instructies horen binnen een functie die bool teruggeeft; items is de arraypointer en cap de positieve capaciteit. Bij een fout blijft het oude geheugen beschikbaar. Als de bewerking slaagt, kan het geheugenblok verplaatst zijn, dus moeten oude pointers naar de elementen worden vervangen. Een begincapaciteit van nul heeft een eigen eerste geheugenallocatie nodig.

Bepalen wat een kopie bezit

Met typedef struct { char *name; int age; } person; kopieert person b = a; het adres in name. Beide records bereiken dezelfde string. Als je beide kopieën als eigenaar zou vrijgeven, zou je hetzelfde geheugen twee keer vrijgeven. Voor een onafhankelijke kopie reserveer je strlen(a.name) + 1 bytes, controleer je of dat is gelukt en gebruik je strcpy uit <string.h>. Een vast veld char name[32] wordt met de struct gekopieerd. strdup reserveert geheugen en kopieert, maar hoort bij POSIX en C23, niet bij de C17-standaardbibliotheek.

Een enumeratie geeft leesbare namen aan geheeltallige keuzewaarden. Namen zoals HIGH maken het doel van een voorwaarde zichtbaar zonder dat de lezer hoeft te onthouden wat het getal 10 voorstelt.

De nummering volgen

enum weekday { MON, TUE, WED, THU, FRI, SAT, SUN };
enum level { LOW = 1, MEDIUM, HIGH = 10, CRITICAL };
enum level alert = HIGH;

Een weggelaten eerste waarde is nul. Bij later weggelaten waarden wordt de vorige waarde telkens met één verhoogd. Zo is MON 0 en SUN 6; de niveaus zijn 1, 2, 10 en 11. Een expliciete waarde laat het tellen op dat punt opnieuw beginnen. Verschillende constanten kunnen een waarde delen, maar identieke waarden kunnen niet als afzonderlijke case-labels in dezelfde switch voorkomen.

Een alias kan een declaratie verkorten: typedef enum { RED, YELLOW, GREEN } light; maakt light signal = RED; mogelijk. Enumeratieconstanten delen de gewone naamruimte voor identifiers binnen hun geldigheidsgebied. Twee verschillende enumeraties kunnen niet allebei RED declareren in hetzelfde geldigheidsgebied. Voorvoegsels zoals in LIGHT_RED en PAINT_RED houden de namen afzonderlijk.

Elke keuze afhandelen

const char *level_name(enum level value) {
    switch (value) {
        case LOW: return "low";
        case MEDIUM: return "medium";
        case HIGH: return "high";
        case CRITICAL: return "critical";
    }
    return "unknown";
}

Elke return beëindigt zijn geval. Als een geval in plaats daarvan een actie uitvoert en daarna moet stoppen, geef je het een break; als de uitvoering het volgende label bereikt, gaat die daar verder. Bij GCC schakelt -Wall waarschuwingen in voor ontbrekende enumeratiegevallen als er geen default is; Clang meldt zulke weglatingen ook standaard. Een waarschuwing kan een ontbrekend geval aan het licht brengen als je later een constante toevoegt.

Invoer valideren als een verzameling keuzes

Het enumeratietype dwingt niet af dat een waarde tot de benoemde verzameling behoort. C17 staat toewijzing vanuit een geheel getal toe, dus kan enum level x = 42; compileren. Een controle of het getal van 1 tot en met 11 loopt, laat nog steeds onbenoemde waarden zoals 6 toe. Controleer de werkelijk toegestane waarden:

#include <stdbool.h>
bool valid_level(int value) {
    return value == LOW || value == MEDIUM
        || value == HIGH || value == CRITICAL;
}

Pas na die controle mag invoer een niveau worden. Voor de opeenvolgende weekdagen volstaat een bereikcontrole van MON tot en met SUN. In een gewone C17-enumeratie hebben de enumeratieconstanten het type int. C23 ondersteunt daarnaast een opgegeven onderliggend type, zoals enum color : unsigned char; die syntaxis hoort niet bij C17.

Namen afdrukken en aantallen gebruiken

printf("%d\n", SUN) drukt “6” af, niet “SUN”. Voor opeenvolgende waarden die bij nul beginnen, geeft een namenarray de tekst: const char *day_names[] = {"Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"};. Na validatie van een index is day_names[SUN] gelijk aan “Sun”. Om zo’n array met een niveauwaarde zoals HIGH te indexeren, is een andere koppeling tussen waarden en namen nodig omdat de niveauwaarden niet opeenvolgend zijn.

Als je DAY_COUNT direct na SUN toevoegt, krijgt die de waarde 7, bruikbaar als lusgrens of arraygrootte. De constante telt dagen, maar is zelf geen geldige dag. Enumeratienamen volgen de regels van C voor geldigheidsgebieden en kunnen door debuggers worden getoond; een #define voert daarentegen tekstvervanging door de preprocessor uit.

Een union geeft meerdere velden dezelfde opslag. Die past bij een waarde die een van verschillende soorten kan zijn. Een struct geeft elk veld een eigen opslagplaats en past bij een record dat al die waarden samen nodig heeft.

Eén alternatief opslaan

union value {
    int i;
    double d;
    char c;
};
union value v = {.d = 2.5};

Alle velden beginnen op hetzelfde adres. De union moet ruimte bieden aan het grootste veld en aan de uitlijningseisen voldoen; met een double van 8 bytes neemt deze union op gangbare platforms 8 bytes in. Een gewone initialisator {42} initialiseert het eerste veld, i; .d = 2.5 kiest expliciet d.

Als je na de initialisator v.i = 42 schrijft, vervang je het opgeslagen alternatief. Als je daarna v.d leest, wordt 42 niet omgezet naar een double: de opgeslagen bytes worden met een andere representatie geïnterpreteerd. Die representatie kan ongeldig zijn. Lees het veld dat hoort bij de waarde die je hebt opgeslagen.

Vastleggen welk veld geldig is

Combineer de union met een enumeratie. De enumeratie is de tag en de union is de gegevensinhoud:

enum kind { K_INT, K_DOUBLE, K_CHAR };
struct tagged {
    enum kind kind;
    union value as;
};
struct tagged make_double(double d) {
    return (struct tagged){.kind = K_DOUBLE, .as = {.d = d}};
}

Een hulpfunctie stelt beide onderdelen samen in. Code die schrijft, houdt de twee velden op elkaar afgestemd. Als code t.as.i schrijft maar t.kind op K_DOUBLE laat staan, kiest code die later leest de verkeerde representatie.

#include <stdio.h>
void print_cell(struct tagged t) {
    switch (t.kind) {
        case K_INT: printf("%d", t.as.i); break;
        case K_DOUBLE: printf("%.1f", t.as.d); break;
        case K_CHAR: printf("%c", t.as.c); break;
    }
}

Als je deze functie aanroept voor cellen met 42, 2,5 en 'x', en tussen de aanroepen spaties afdrukt, levert dat “42 2.5 x” op. Elk geval kiest zowel het bijpassende veld als de bijpassende opmaak. Een token van een rekenprogramma kan op dezelfde manier een getal of een operator bevatten.

Op gangbare 64-bitsplatforms nemen een enumeratie van 4 bytes, opvulling en deze union van 8 bytes samen 16 bytes in voor struct tagged. Een struct die de enumeratie plus alle drie de alternatieven afzonderlijk opslaat, neemt doorgaans 24 bytes in. Dit zijn voorbeelden van geheugenindeling; vraag de werkelijke grootten van de typen op met sizeof.

Kleine vlaggen in bitvelden samenpakken

struct flags {
    unsigned int ready : 1;
    unsigned int mode : 3;
};

De breedte volgt op de dubbele punt. Een veld zonder teken van 1 bit bevat 0 of 1; een veld van 3 bits bevat 0 tot en met 7. Als je 9 in mode opslaat, blijven de drie laagste bits behouden en wordt 1 opgeslagen. Hierbij gaat informatie verloren, dus valideer een modus vóór opslag als grotere waarden op een fout wijzen.

Een bitveld heeft geen afzonderlijk adresseerbare locatie, dus is &flags.mode ongeldig voor een variabele met de naam flags. De volgorde en opslagindeling hangen af van de implementatie. Gebruik een bitvelddeclaratie niet als overdraagbare garantie voor een exacte bestands- of apparaatindeling. Een opgegeven breedte bepaalt het waardenbereik van het veld, niet de indeling van elke byte eromheen.

Een enkelvoudig gekoppelde lijst slaat elk item op in een afzonderlijk gereserveerde knoop. Elke knoop bevat zijn waarde en het adres van de volgende knoop. De koppointer wijst naar de eerste knoop; NULL markeert zowel een lege lijst als het einde van een keten.

De verwijzing definiëren en vooraan invoegen

#include <stdbool.h>
#include <stdlib.h>
typedef struct node {
    int number;
    struct node *next;
} node;

bool prepend(node **head, int value) {
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    n->number = value;
    n->next = *head;
    *head = n;
    return true;
}

Begin met node *list = NULL;. Roep prepend(&list, value) aan en handel een mislukt resultaat af. De functie ontvangt het adres van de koppointer van de aanroepende functie. *head duidt daardoor de pointer aan die moet veranderen. Als de functie alleen node *head zou ontvangen en aan die lokale pointer zou toewijzen, zou de koppointer van de aanroepende functie ongewijzigd blijven.

De volgorde van de laatste toewijzingen behoudt de oude lijst. Verbind eerst de nieuwe knoop met de oude eerste knoop en vervang daarna de koppointer. Als je die instructies omkeert, wordt n->next op n zelf gezet en gaat de oude keten verloren. Als 1, 2 en 3 binnenkomen, levert herhaald vooraan invoegen eerst 1 op, dan 2 → 1 en dan 3 → 2 → 1 → NULL. Vooraan invoegen keert de volgorde van binnenkomst om.

Doorlopen zonder de eigenaar te verplaatsen

#include <stdio.h>
void print_list(const node *head) {
    for (const node *p = head; p != NULL; p = p->next)
        printf("%d ", p->number);
}

De doorlooppointer p beweegt terwijl head beschikbaar blijft. Het voorbeeld drukt “3 2 1 ” af met een spatie aan het einde. Bij een lege lijst wordt de lusinhoud nul keer uitgevoerd. Er is geen arrayindex: elke stap leest één verwijzing om de volgende knoop te vinden. De gereserveerde geheugenblokken kunnen verspreid in het geheugen liggen en bij het invoegen van een knoop worden bestaande knopen niet verplaatst.

Achteraan toevoegen

bool append(node **head, int value) {
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    *n = (node){.number = value, .next = NULL};
    node **link = head;
    while (*link != NULL) link = &(*link)->next;
    *link = n;
    return true;
}

link begint bij de koppointer van de aanroepende functie. Daarna gaat de pointer naar het adres van elk next-veld totdat die de afsluitende nulverwijzing aanduidt. Daar toewijzen werkt ook voor een lege lijst. Zonder bewaarde staartpointer moet je bij elke toevoeging achteraan eerst de bestaande keten tot het einde volgen. Een functie kan ook een nieuwe koppointer teruggeven, mits de aanroepende functie die opslaat en een mislukte geheugenallocatie afhandelt zonder de oude lijst te verliezen.

Knopen in een veilige volgorde vrijgeven

void clear_list(node **head) {
    while (*head != NULL) {
        node *old = *head;
        *head = old->next;
        free(old);
    }
}

Lees de opvolger terwijl old nog bestaat, verplaats de koppointer en geef daarna de oude knoop vrij. Na de lus is de koppointer van de aanroepende functie NULL. Als je old->next leest nadat old is vrijgegeven, is dat gebruik na vrijgave, ook als het geheugen ongewijzigd lijkt. Een geheugencontroleprogramma kan helpen ongeldige leesbewerkingen en vergeten geheugenallocaties aan het licht te brengen; ook als een latere bewerking mislukt, moet het opruimen worden uitgevoerd.

Bij het doorzoeken van een lijst volg je steeds één verwijzing. Voor invoegen en verwijderen is meer nodig: het adres van de verwijzing die moet veranderen. Die verwijzing kan de koppointer zijn of een next-veld in een eerdere knoop.

Zoeken op waarde

Met het type node met de velden number en next:

node *find(node *head, int value) {
    for (node *p = head; p != NULL; p = p->next)
        if (p->number == value) return p;
    return NULL;
}

Bij een overeenkomst wordt het adres van de gevonden knoop teruggegeven. Bij een ontbrekende waarde wordt NULL teruggegeven. Om de 1.000e knoop te bereiken, moet je vanaf de koppointer 999 verwijzingen volgen, ook als je de positie van tevoren weet.

Een pointer bijhouden naar de verwijzing die verandert

Een node ** kan naar de koppointer of naar het next-veld van een knoop wijzen. Noem die link: *link is de knoop die momenteel via die verwijzing wordt bereikt. Als je verdergaat met link = &(*link)->next, verandert welke verwijzing je bekijkt; de lijst verandert niet.

bool insert_sorted(node **head, int value) {
    node **link = head;
    while (*link != NULL && (*link)->number < value)
        link = &(*link)->next;
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    n->number = value;
    n->next = *link;
    *link = n;
    return true;
}

Neem <stdbool.h> en <stdlib.h> op. De invoerlijst moet al oplopend zijn gesorteerd. Stop vóór de eerste waarde die niet kleiner is dan de nieuwe waarde, zodat dubbele waarden vóór gelijke waarden komen. De linkerkant van && controleert op NULL voordat de rechterkant de knoop derefereert. Als je die controles omwisselt, wordt aan het einde een nulpointer gederefereerd.

Als je 5, 2, 8 en 4 invoegt, is de uiteindelijke lijst 2 → 4 → 5 → 8. Bij het invoegen van 4 in 2 → 5 → 8 gaat link van de koppointer naar 2.next. De nieuwe knoop wijst naar 5 en 2.next wordt omgeleid naar de nieuwe knoop. Als het nieuwe item het kleinste is, duidt link nog steeds de koppointer aan. Aan het einde duidt die de afsluitende nulverwijzing aan.

Loskoppelen vóór vrijgeven

bool remove_first(node **head, int value) {
    node **link = head;
    while (*link != NULL && (*link)->number != value)
        link = &(*link)->next;
    if (*link == NULL) return false;
    node *old = *link;
    *link = old->next;
    free(old);
    return true;
}

De lus vindt de inkomende verwijzing. Door het doel daarvan als old te bewaren, blijft de knoop beschikbaar terwijl *link wordt gewijzigd zodat die naar de opvolger wijst. Pas daarna wordt de verwijderde knoop vrijgegeven. Als je 5 uit 2 → 4 → 5 → 8 verwijdert, krijg je 2 → 4 → 8. Verwijder je daarna 2, dan verandert de koppointer en blijft 4 → 8 over. Als de waarde ontbreekt, geeft de functie onwaar terug zonder de lijst te wijzigen.

Een versie met twee pointers houdt prev en cur bij. Als prev een nulpointer is, is de gevonden knoop de eerste en moet de koppointer veranderen; werk anders prev->next bij. Als je het geval van de eerste knoop vergeet, blijft een pointer naar vrijgegeven geheugen achter. De versie met het adres van de verwijzing handelt beide gevallen af met dezelfde toewijzing.

Controleer lege invoer, een lijst met één knoop, een overeenkomst bij de eerste en laatste knoop en een ontbrekende waarde. Bepaal bij elke wijziging de inkomende verwijzing, de betrokken knoop en zijn opvolger voordat je een toewijzing schrijft. Geen enkele overgebleven knoop mag onbereikbaar worden en geen enkele verwijzing mag naar een vrijgegeven knoop wijzen.

De vraag is welke bewerkingen je programma uitvoert. Arrays en lijsten kunnen dezelfde waarden bevatten, maar bereiken en verplaatsen die waarden op verschillende manieren.

De bewerkingen vergelijken

Bij een lijst kost het vinden van een positie nog steeds werk. Invoegen na een knoop waarvan je al een pointer hebt, gaat direct, maar voor verwijderen heb je ook de voorganger of de verwijzing naar de knoop nodig. Met alleen het adres van de knoop moet je bij een enkelvoudig gekoppelde lijst doorgaans vanaf de koppointer lopen om die inkomende verwijzing te vinden.

Ook opslag is van belang. Op een typisch 64-bitsplatform neemt een knoop met een int van 4 bytes en een pointer van 8 bytes na opvulling 16 bytes in. Voor 1.000 gehele getallen gebruiken knopen 16.000 bytes plus de administratie van de geheugenallocatie; een aaneengesloten array van gehele getallen gebruikt 4.000 bytes. De array doorlopen is meestal sneller omdat waarden die dicht bij elkaar liggen samen worden opgeslagen.

Lijstgegevens bij elkaar houden

typedef struct {
    node *head;
    node *tail;
    size_t count;
} list_t;

Initialiseer een omhullende struct met list_t list = {0};. De regels voor een lege lijst zijn head == NULL, tail == NULL en count == 0. Elke geslaagde invoeging of verwijdering moet zowel het aantal als de verwijzingen bijwerken. Een mislukte geheugenallocatie verandert geen van beide.

Met een staartpointer zijn na een gecontroleerde geheugenallocatie deze toewijzingen nodig om achteraan toe te voegen:

n->next = NULL;
if (list.tail == NULL) list.head = n;
else list.tail->next = n;
list.tail = n;
++list.count;

Hier is n een geïnitialiseerde knoop. Voor de eerste knoop worden kop- en staartpointer gelijk. Bij het verwijderen van de laatste knoop moet de staartpointer terug worden verplaatst; bij een enkelvoudig gekoppelde lijst is daarvoor de voorganger nodig. Als je de enige knoop verwijdert, zet je beide uiteinden op NULL en het aantal op nul.

In beide richtingen verbinden

typedef struct dnode {
    int value;
    struct dnode *prev, *next;
} dnode;
typedef struct {
    dnode *head, *tail;
} dlist;

void unlink_node(dlist *list, dnode *d) {
    if (d->prev != NULL) d->prev->next = d->next;
    else list->head = d->next;
    if (d->next != NULL) d->next->prev = d->prev;
    else list->tail = d->prev;
    free(d);
}

Deze functie ontvangt een bestaande knoop die bij de lijst hoort. Beide buren worden bijgewerkt voordat de knoop wordt vrijgegeven. Aan de uiteinden verandert de functie de kop- of staartpointer in plaats van een ontbrekende buur. Een dubbel gekoppelde lijst kan achteruit worden doorlopen en een bekende knoop verwijderen zonder naar zijn voorganger te zoeken, maar vereist een extra pointer per knoop en meer te onderhouden verwijzingen.

Gegevens in eigendom vóór hun knoop vrijgeven

Een word_node kan eigenaar zijn van zowel een gereserveerde knoop als een via word bereikbare gereserveerde string. Bewaar next, roep free(n->word) aan, daarna free(n), en ga naar de bewaarde opvolger. Als je alleen de knoop vrijgeeft, ontstaat een geheugenlek voor de string. n->word lezen nadat de knoop is vrijgegeven, is ongeldig. Eigenaarschap beschrijft welke code elk gereserveerd geheugenblok moet vrijgeven, ook als meerdere pointers het kunnen bereiken.

Een stapel verwijdert het laatst toegevoegde item als eerste: laatst erin, eerst eruit (LIFO). De bewerkingen definiëren een abstract datatype, ongeacht of een array of gekoppelde knopen de waarden bevatten. push voegt bovenaan toe, pop verwijdert het bovenste item en peek leest het bovenste item zonder het te verwijderen.

Een array en een aantal gebruiken

#include <stdbool.h>
#define STACK_CAP 100
typedef struct {
    int items[STACK_CAP];
    int top;
} stack;

bool push(stack *s, int value) {
    if (s->top == STACK_CAP) return false;
    s->items[s->top++] = value;
    return true;
}
bool pop(stack *s, int *out) {
    if (s->top == 0) return false;
    *out = s->items[--s->top];
    return true;
}

Initialiseer met stack s = {0};. Hier is top het aantal opgeslagen items, dus is de hoogste bezette index top - 1. Een geslaagde push schrijft naar de volgende vrije plaats en verhoogt het aantal. Een geslaagde pop verlaagt eerst het aantal en leest daarna die index. De aanroepende functie levert een geldige out-pointer en controleert het resultaat voordat zij de waarde gebruikt.

Als je 4, 7 en 1 op de stapel zet en vervolgens twee keer verwijdert, krijg je 1 en 7 terug en blijft 4 over. Zonder capaciteitscontrole schrijft een push op een volle stapel naar items[STACK_CAP], voorbij het einde. Zonder controle op een lege stapel daalt de top met teken van 0 naar −1 en leest pop items[-1]. Beide toegangen zijn ongedefinieerd gedrag.

De eerste knoop van een lijst als bovenkant gebruiken

Een gekoppelde stapel voegt bij een push een nieuwe knoop vooraan in, nadat de geheugenallocatie is gecontroleerd. Pop verwijdert de eerste knoop:

bool pop_linked(node **top, int *out) {
    if (*top == NULL) return false;
    node *old = *top;
    *out = old->number;
    *top = old->next;
    free(old);
    return true;
}

node heeft een geheel getal number en een next-pointer. Een gekoppelde stapel heeft geen vaste arraycapaciteit, maar een push kan mislukken als de geheugenallocatie mislukt. Er zijn nog steeds controles op een lege stapel nodig en knopen die aan het einde overblijven, moeten worden vrijgegeven.

Geneste haakjes controleren

Lees de invoer van links naar rechts. Zet elk openingshaakje, elke openingsblokhaak of openingsaccolade op de stapel. Haal bij elk sluitend teken een teken van de stapel en controleer of de soorten overeenkomen. Een sluitend teken zonder openingsteken gaat direct mis. Controleer ten slotte of de stapel leeg is: overgebleven openingstekens betekenen ook dat de tekens niet kloppen.

De tekst “( [ ] { } )” is in balans. Bij “( ]” past het sluitende teken niet bij het verwijderde openingsteken. Bij “( ( )” blijft na het lezen één openingsteken over. Als je alleen openings- en sluitingstekens telt, mis je een onjuiste nesting zoals “( [ ) ]”.

Postfixexpressies evalueren

Zet getallen op de stapel zodra ze binnenkomen. Haal bij een binaire operator eerst de rechteroperand en daarna de linkeroperand van de stapel, bereken left operator right en zet het resultaat op de stapel. Voor “3 4 + 2 *” combineert + 3 en 4 tot 7 en combineert * daarna 7 en 2 tot 14. Voor “9 4 -” haal je 4 als rechteroperand en 9 als linkeroperand van de stapel, wat 5 oplevert. Omkeren levert −5 op. Wijs onvoldoende operanden af en vereis één eindresultaat; bij deling moet de rechteroperand bovendien ongelijk aan nul zijn.

Functieaanroepen hebben levensduren in de vorm van een stapel: een aangeroepen functie keert terug voordat de aanroepende functie verdergaat. Elke actieve aanroep heeft een stackframe nodig, dus kan zeer diepe recursie de aanroepstapel uitputten, ook als heapallocaties slagen.

Een wachtrij verwijdert het vroegst toegevoegde item als eerste: eerst erin, eerst eruit (FIFO). Toevoegen gebeurt achteraan; verwijderen gebeurt vooraan. Nadat je A, B en C hebt toegevoegd, geven de volgende twee verwijderingen A en B terug. Dit past bij werk dat op volgorde van binnenkomst moet worden afgehandeld.

Beide uiteinden van een gekoppelde wachtrij bijhouden

Met knopen die de velden number en next bevatten en met <stdbool.h> en <stdlib.h> opgenomen:

typedef struct { node *head, *tail; } queue;

bool enqueue(queue *q, int value) {
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    *n = (node){.number = value, .next = NULL};
    if (q->tail == NULL) q->head = n;
    else q->tail->next = n;
    q->tail = n;
    return true;
}
bool dequeue(queue *q, int *out) {
    if (q->head == NULL) return false;
    node *old = q->head;
    *out = old->number;
    q->head = old->next;
    if (q->head == NULL) q->tail = NULL;
    free(old);
    return true;
}

Initialiseer met queue q = {0};. Toevoegen stelt de verwijzing van de oude laatste knoop in voordat de staartpointer wordt verplaatst. Bij de eerste knoop wordt ook de koppointer ingesteld. Verwijderen verplaatst de koppointer naar voren. Als daarmee de enige knoop wordt verwijderd, moet ook de staartpointer NULL worden. Anders schrijft de volgende toevoeging via een staartpointer naar een niet meer bestaand object. Voor geen van beide bewerkingen hoeft de lijst te worden doorlopen.

Een vaste array als ring hergebruiken

Bij een gewone arraywachtrij die altijd van index 0 verwijdert, moeten de overgebleven waarden worden verschoven. Een ringbuffer houdt in plaats daarvan een index voor de voorkant en een aantal items bij:

#define CAP 4
typedef struct {
    char items[CAP];
    unsigned head, count;
} ring;

bool ring_put(ring *q, char value) {
    if (q->count == CAP) return false;
    q->items[(q->head + q->count) % CAP] = value;
    ++q->count;
    return true;
}
bool ring_get(ring *q, char *out) {
    if (q->count == 0) return false;
    *out = q->items[q->head];
    q->head = (q->head + 1) % CAP;
    --q->count;
    return true;
}

Initialiseer een ring met {0}. head duidt altijd het voorste item aan als de wachtrij niet leeg is. De volgende invoegindex is de voorkant plus het aantal items, met terugloop door % CAP. Lees het voorste item voordat je head verplaatst. Het aantal onderscheidt leeg van vol zonder een plaats op te offeren.

De terugloop volgen

Voeg A, B en C toe op plaatsen 0, 1 en 2. Verwijder A: de kopindex wordt 1 en het aantal wordt 2. D komt op plaats 3; E komt op plaats 0. De fysieke array bevat nu E, B, C, D, maar de logische verwijdervolgorde is B, C, D, E. De ring is vol omdat het aantal 4 is, ook al staat de voorkant op index 1.

Een ander ontwerp houdt de kopindex en de index van de volgende vrije plaats achteraan bij, zonder een aantal. In dat ontwerp kunnen gelijke indexen leeg of vol betekenen, dus een veelgebruikte werkwijze laat één plaats ongebruikt. Leeg is head == tail; vol is (tail + 1) % CAP == head. Meng die werkwijze niet met de capaciteitsregels van de versie met een aantal. Wachtrijen ondersteunen ook het niveau voor niveau bezoeken van bomen door knopen te bewaren die op hun beurt wachten.

Een binaire boom geeft elke knoop hoogstens twee kinderen, links en rechts genoemd. De wortel is de bovenste knoop. Een blad heeft geen kinderen en een knoop vormt samen met al zijn nakomelingen een deelboom. Een ontbrekend kind en een lege boom worden voorgesteld door NULL.

De vertakkingen voorstellen

typedef struct tnode {
    int key;
    struct tnode *left;
    struct tnode *right;
} tnode;

Elke kindpointer leidt naar de wortel van een andere boom. Dezelfde definitie beschrijft daardoor een blad, een grote vertakte boom of een lange keten. Hoogte telt verbindingen op het langste pad van wortel naar blad: een wortel alleen heeft hoogte 0. Gebruik −1 voor een lege boom, zodat de twee lege deelbomen van een blad vanzelf tot hoogte 0 leiden. Als je in plaats daarvan niveaus telt, krijg je één meer.

De regel op hele deelbomen toepassen

Een binaire zoekboom ordent de sleutels. Voor elke knoop zijn alle sleutels in zijn linkerdeelboom kleiner en alle sleutels in zijn rechterdeelboom groter. Sla elke sleutel één keer op. Deze voorwaarde geldt ook voor nakomelingen verderop. Een wortel 50 met linkerkind 30 en een rechterkind 60 onder die 30 is ongeldig: 60 staat nog steeds in de linkerdeelboom van 50.

Voeg 50, 30, 70, 20, 40, 60 en 80 in een lege binaire zoekboom in. De wortel is 50; 30 en 70 zijn de kinderen. De kinderen van 30 zijn 20 en 40 en die van 70 zijn 60 en 80. Elke keuze voor een tak behoudt de grenzen die van de voorouders zijn geërfd.

Bij elke stap één tak kiezen

#include <stddef.h>
tnode *search(tnode *t, int key) {
    while (t != NULL) {
        if (key == t->key) return t;
        if (key < t->key) t = t->left;
        else t = t->right;
    }
    return NULL;
}

Zoeken naar 60 in het voorbeeld bezoekt 50, gaat naar rechts naar 70 en dan naar links naar 60: drie knopen. Zoeken naar 65 volgt hetzelfde pad en probeert dan het rechterkind van 60. Dat kind is NULL, dus ontbreekt 65. Je hoeft de linkerdeelboom van 50 niet te bekijken, omdat elke sleutel daar kleiner is dan 50.

De recursieve vorm handelt eerst t == NULL en een passende sleutel af en doorzoekt daarna het gekozen kind. De controle op een lege deelboom is het basisgeval. Zonder die controle derefereert een mislukte zoekopdracht uiteindelijk een nulpointer. De versie met een lus stopt op dezelfde grens zonder recursieve aanroepen toe te voegen.

De vorm het werk laten verklaren

Een perfect gebalanceerde boom met 20 niveaus bevat 1.048.575 sleutels en een zoekopdracht bezoekt hoogstens 20 knopen. Als je in plaats daarvan de al gesorteerde sleutels 10, 20, 30, 40, 50 invoegt, ontstaat een keten naar rechts. De hoogte is 4 en bij het zoeken naar 50 bezoek je alle vijf de knopen. De ordeningsregel van een binaire zoekboom alleen houdt de boom niet kort. Zelfbalancerende bomen zoals AVL-bomen herschikken takken om de hoogte te beheersen.

Om een minimum te vinden, volg je linkerkinderen totdat de volgende linkerverwijzing NULL is. Voor een maximum volg je rechterkinderen. In het voorbeeld met zeven knopen zijn deze sleutels 20 en 80. Dezelfde richtingskeuzes werken bij elke wortel van een deelboom, omdat de ordeningsregel daar ook geldt.

Boomfuncties werken op een deelboom en verbinden hun resultaat met de ouder. Maak het geval van een lege deelboom expliciet en onderscheid bewerkingen die verwijzingen wijzigen van bewerkingen die alleen knopen bezoeken.

Via de deelboomverwijzing invoegen

Met tnode dat key, left en right bevat, neem je <stdbool.h> en <stdlib.h> op:

bool insert(tnode **link, int key) {
    if (*link == NULL) {
        tnode *n = malloc(sizeof *n);
        if (n == NULL) return false;
        *n = (tnode){.key = key, .left = NULL, .right = NULL};
        *link = n;
        return true;
    }
    if (key < (*link)->key) return insert(&(*link)->left, key);
    if (key > (*link)->key) return insert(&(*link)->right, key);
    return true;
}

Roep aan met insert(&root, key) en controleer het resultaat. Een bestaande sleutel laat de boom ongewijzigd en geldt als succes. Via het adres van de verwijzing kan de invoeging zowel de wortel van de aanroepende functie als een kindpointer bijwerken. Bij een interface die de wortel teruggeeft, sla je elk resultaat op: t->left = insert(t->left, key) en root = insert(root, key). Als je een teruggegeven geheugenallocatie negeert terwijl de oorspronkelijke deelboom leeg was, blijft die knoop ongekoppeld en ontstaat een geheugenlek.

Kiezen wanneer je de wortel bezoekt

Bij het invoegen van 50, 30, 70, 20, 40, 60, 80 is de uitvoer in inorde “20 30 40 50 60 70 80”. Preorde geeft “50 30 20 40 70 60 80”; postorde geeft “20 40 30 60 80 70 50”.

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

Stel na free_tree(root) bij de eigenaar root = NULL in. De functie geeft eerst de kinderen vrij, zodat de functie hun adressen uit de nog bestaande ouder kan lezen. Het aantal knopen is nul voor een lege deelboom, anders één plus het aantal van beide kinderen. De hoogte is −1 voor een lege deelboom, anders één plus de grootste hoogte van de kinderen. Het voorbeeld heeft 7 knopen en hoogte 2.

Verwijderen zonder de volgorde te verstoren

Een blad wordt NULL. Een knoop met één kind wordt vervangen door dat kind. Bij twee kinderen kopieer je de kleinste sleutel uit de rechterdeelboom naar de knoop en verwijder je die opvolger daarna van zijn oorspronkelijke positie:

tnode *erase(tnode *t, int key) {
    if (t == NULL) return NULL;
    if (key < t->key) t->left = erase(t->left, key);
    else if (key > t->key) t->right = erase(t->right, key);
    else {
        if (t->left == NULL || t->right == NULL) {
            tnode *child = t->left != NULL ? t->left : t->right;
            free(t);
            return child;
        }
        tnode *s = t->right;
        while (s->left != NULL) s = s->left;
        t->key = s->key;
        t->right = erase(t->right, s->key);
    }
    return t;
}

Roep aan als root = erase(root, key). Als je 50 uit het voorbeeld verwijdert, komt 60 in de wortel en wordt de oude knoop met 60 verwijderd. De uitvoer in inorde wordt “20 30 40 60 70 80”; preorde wordt “60 30 20 40 70 80”. Een opvolger kan een rechterkind hebben, dus moet bij het verwijderen dat kind opnieuw worden gekoppeld.

Gebruik voor woordsleutels het teken van strcmp, geen pointergelijkheid, en geef elk woord in eigendom zijn eigen geheugenallocatie. Geef het woord vóór zijn knoop vrij. Als je bij zulke records een knoop met twee kinderen verwijdert, heb je ook een eigendomsplan nodig voor het verplaatste woord en een eventuele bijbehorende waarde; als je een pointer met eigenaarschap kopieert en daarna het woord van de oorspronkelijke knoop vrijgeeft, blijft een pointer naar een niet meer bestaande sleutel achter.

Een hashtabel kiest een startlocatie op basis van een sleutel. Een hashfunctie levert een getal op; dat getal modulo een positief aantal buckets geeft een index. Bij botsingsafhandeling met ketens staat in elke bucket een gekoppelde lijst, zodat een zoekopdracht de gekozen keten doorzoekt.

Hashen en gelijkheid onderscheiden

Een bruikbare hash is deterministisch, snel te berekenen en verdeelt de verwachte sleutels over de buckets. Gelijke sleutels moeten gelijke hashes opleveren. Verschillende sleutels kunnen nog steeds een index delen: dat is een botsing en elke tabel moet die afhandelen. Als er meer mogelijke sleutels dan buckets zijn, zijn sommige botsingen onvermijdelijk.

Voor woorden die met een letter beginnen op een ASCII-compatibel systeem wijst toupper((unsigned char)word[0]) - 'A' 26 letterbuckets toe; “Luigi” begint in bucket 11. Veel Engelse woorden beginnen met “s” en weinig met “x”, dus kan deze regel zeer ongelijke ketens opleveren. De expliciete typeconversie is nodig omdat functies uit <ctype.h> een waarde vereisen die als een teken zonder teken kan worden weergegeven, of EOF. Controleer de beginletter en de aanname over de tekenset voordat je deze indexregel gebruikt.

Een hash op basis van de som van tekencodes heeft ook zwakke punten. Met ASCII-codes en tien buckets geeft de som voor “cat” 99 + 97 + 116 = 312 en komt die in bucket 2; de som voor “dog” is 314 en komt in bucket 4. “act” geeft ook 312. Bij optellen gaat de lettervolgorde verloren, dus veroorzaakt elke herschikking een botsing.

Tekenvolgorde in de hash verwerken

unsigned long hash_word(const char *word) {
    unsigned long h = 5381;
    const unsigned char *p = (const unsigned char *)word;
    while (*p != '\0') {
        h = h * 33 + *p;
        ++p;
    }
    return h;
}

Dit djb2-patroon gebruikt rekenkunde zonder teken, waarbij overloop op een vastgelegde manier terugloopt. Overloop bij getallen met teken zou ongedefinieerd gedrag zijn. Voor de ASCII-strings “cat” en “act” zijn de waarden 193.488.125 en 193.486.013. Bereken de rest met hash_word(word) % N, waarbij N het positieve aantal buckets is. De lettervolgorde verandert deze hashes, hoewel de restberekening nog steeds een botsing kan opleveren.

Als een tabel “Cat” en “cat” als gelijk behandelt, moeten zowel het hashen als het vergelijken dezelfde regel voor hoofdletters en kleine letters gebruiken. Als je dat onderscheid alleen bij het vergelijken negeert, kunnen gelijke sleutels in verschillende buckets terechtkomen, waar de zoekopdracht ze niet zal vergelijken. Een negatieve rest van een hash met teken is ook ongeschikt als arrayindex.

Een strategie voor botsingen kiezen

Botsingsafhandeling met ketens slaat elke botsing op in de gekoppelde lijst van een bucket. De zoekopdracht vergelijkt sleutels totdat een overeenkomst wordt gevonden of het einde is bereikt. Open adressering slaat tabelitems op in de array zelf. Bij lineair sonderen probeert de functie bij een botsing de volgende plaats en loopt aan het einde terug. Het zoeken volgt dezelfde sondeervolgorde en kan dus meerdere plaatsen in de array bekijken.

Indexen opnieuw berekenen als de tabel groeit

De bezettingsgraad is het aantal opgeslagen sleutels gedeeld door het aantal buckets. Twaalf sleutels in acht buckets geven gemiddeld 1,5 tabelitems per bucket. Zestien buckets verlagen dat gemiddelde tot 0,75. Dit gemiddelde garandeert niet dat elke keten kort is; een slechte hash kan alle sleutels bij elkaar plaatsen.

Een bucketindex hangt af van het aantal buckets. Nadat je geheugen voor een grotere bucketarray hebt gereserveerd en die hebt geïnitialiseerd, bereken je de index van elke opgeslagen sleutel opnieuw voor het nieuwe aantal en koppel je de sleutel daar opnieuw. Als je de oude koppointers naar de nieuwe buckets met hetzelfde nummer kopieert, blijven sleutels op plaatsen waar de nieuwe zoekopdracht niet zal zoeken. Een tabel met ketens kan meer tabelitems dan buckets bevatten; open adressering heeft ongebruikte plaatsen nodig voor nieuwe tabelitems en betrouwbaar sonderen.

Een tabel met ketens combineert een array, lijstverwijzingen, stringvergelijking en eigenaarschap. Elk tabelitem is eigenaar van zijn gekopieerde sleutel. De bucketarray is eigenaar van de ketens en elke keten eindigt bij NULL.

Buckets initialiseren en tekst opzoeken

#include <stdbool.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#define N 26
typedef struct entry {
    char *key;
    int count;
    struct entry *next;
} entry;
static entry *table[N];

Statische opslag begint met nulpointers in elke bucket. Een lokale array heeft daarentegen een initialisator nodig zoals entry *table[N] = {NULL};. Gebruik de functie hash_word zonder teken die begint bij 5381 en elke byte met vermenigvuldiger 33 verwerkt.

entry *find_word(const char *key) {
    size_t i = hash_word(key) % N;
    for (entry *e = table[i]; e != NULL; e = e->next)
        if (strcmp(e->key, key) == 0) return e;
    return NULL;
}

strcmp vergelijkt tekst. e->key == key zou controleren of de pointers dezelfde locatie aanduiden. Twee afzonderlijke buffers kunnen gelijke woorden bevatten, dus is pointergelijkheid geen manier om een woord op te zoeken.

Een bestaande sleutel tellen of een nieuwe plaatsen

bool add_word(const char *key) {
    entry *e = find_word(key);
    if (e != NULL) {
        if (e->count == INT_MAX) return false;
        ++e->count;
        return true;
    }
    e = malloc(sizeof *e);
    if (e == NULL) return false;
    e->key = malloc(strlen(key) + 1);
    if (e->key == NULL) {
        free(e);
        return false;
    }
    strcpy(e->key, key);
    e->count = 1;
    size_t i = hash_word(key) % N;
    e->next = table[i];
    table[i] = e;
    return true;
}

De aanroepende functie levert een string die eindigt op een nulteken. De controle op INT_MAX meldt een fout voordat een aantal buiten het bereik van de int-opslag zou lopen. De extra byte in de stringallocatie bevat '\0'. Als de tweede geheugenallocatie mislukt, geef je het nog niet gekoppelde tabelitem vrij. De koppointer van de bucket verandert pas nadat beide geheugenallocaties en de initialisatie zijn geslaagd.

Als je in plaats daarvan e->key = key opslaat, behoud je de opslag van de aanroepende functie. Als invoer herhaaldelijk één buffer hergebruikt, kan elke opgeslagen pointer het nieuwste woord tonen. Door de tekst te kopiëren krijgt elk tabelitem een levensduur die onafhankelijk is van die buffer. strdup biedt die bewerking in POSIX en C23; expliciete geheugenallocatie en strcpy werken in C17.

In een voorbeeld met tien buckets en de som van tekencodes laat het invoegen van “cat”, “dog”, “act” de keten “act” → “cat” achter in bucket 2 en “dog” in bucket 4. Zoeken naar “tac” doorzoekt bucket 2, vergelijkt beide woorden en bereikt NULL. Een passende bucket is alleen een mogelijke locatie, geen bewijs van een gelijke sleutel.

Gegevensinhoud, knopen en koppointers van buckets vrijgeven

void clear_table(void) {
    for (size_t i = 0; i < N; ++i) {
        entry *e = table[i];
        while (e != NULL) {
            entry *next = e->next;
            free(e->key);
            free(e);
            e = next;
        }
        table[i] = NULL;
    }
}

Het bewaren van next en het vrijgeven van de sleutel gebeuren terwijl het tabelitem nog bestaat. Door elke bucket terug te zetten, kan die opnieuw worden gebruikt. Geheugencontroleprogramma’s helpen de uitgevoerde paden te controleren; ook paden bij mislukte geheugenallocatie moeten opruimen. Hashvolgorde is geen gesorteerde volgorde. Om alfabetisch af te drukken, verzamel je sleutels om te sorteren of sla je ze op in een binaire zoekboom.

Bij open adressering is voor verwijderen een verwijderingsmarkering nodig, zodat zoeken via een verwijderde plaats doorgaat naar latere botsende sleutels. Een werkelijk ongebruikte plaats kan een mislukte zoekopdracht beëindigen. Sondeervolgordes moeten begrensd zijn en de tabel moet groeien voordat elke plaats bezet is.