De meeste beginners gaan ervan uit dat datastructuren statisch zijn. Dat zijn ze niet. Een gekoppelde stapel is een dynamisch beest. Het groeit en krimpt in een mum van tijd. U wijst geheugen niet vooraf toe. Je pakt het wanneer je het nodig hebt. Laat het los als je klaar bent.
In dit voorbeeld worden gehele getallen gebruikt. Wijzig typedef int stack_data in float of char als je wilt. De logica blijft hetzelfde.
De interface
Kijk naar de kop. Het is een contract.
stack_init zorgt voor de puinhoop. stack_clear wist het. stack_empty vertelt je of er nog iets over is. ‘push’ schuift gegevens naar binnen. ‘pop’ trekt gegevens eruit.
Eenvoudig. Schoon.
De motor
Het codebestand verbergt het lef.
top verwijst naar het nieuwste item. NULL betekent leeg.
stack_init reset top gewoon naar NULL. Klaar.
stack_clear verschijnt totdat het leeg is. Het is een lus. Het is goedkoop.
stack_empty controleert of top NULL is. Retourneert 1 als dit waar is. 0 indien onwaar.
stack_push doet het zware werk.
Het wijst geheugen toe. Stelt de gegevens in. Koppelt deze aan de oude top. Updates top.
stack_pop keert het proces om.
Het pakt de gegevens. Verplaatst ‘van boven’ naar beneden. Bevrijd het oude knooppunt. Retourneert de waarde.
Als de stapel leeg is? Het levert afval op. Pop niet van een lege stapel.
Informatie verbergen
Dit is de sleutel.
Je ziet alleen de kop. Je ziet de code niet.
De stapel kan arrays gebruiken. Wijzers. Bestanden. Een gekoppelde lijst. Het maakt niet uit.
Zolang de interface werkt, maakt het je niet uit hoe deze is gebouwd.
Dat is het verbergen van informatie. Het is niet zomaar een modewoord. Zo bouw je software die niet kapot gaat als je de interne onderdelen verandert.
C Gotcha’s
C vergeeft geen fouten.
- Haakjes zijn belangrijk.
(*p.iis niet hetzelfde als*p.i. Men verwijdert eerst de verwijzing naar de aanwijzer. De ander heeft toegang tot het lid en verwijdert vervolgens de verwijzingen. Als je het verkeerd doet, crash je. - Geheugenlekken. Stel nooit zomaar
top = NULLin. Je bent wees op elk knooppunt in de lijst. Je raakt de gegevens kwijt. Je verliest het geheugen. Gebruik ‘gratis’. Altijd. - Neem headers op.
NULLbevindt zich instdio.h. Als u het vergeet, kan uw code op sommige compilers worden gecompileerd. Het geldt niet voor anderen. Of het definieertNULLop een vreemde manier als nul. Voeg
Wat is het volgende?
De basisstapel is eenvoudig. Echte stacks hebben meer nodig.
Voeg ‘dup’ toe. Dupliceer het bovenste element. Voeg ‘aantal’ toe. Retourneer het aantal items. Voeg ‘toevoegen’ toe. Pop de bovenste twee, voeg ze toe, druk op het resultaat.
Bouw een stuurprogramma. Schrijf een make-bestand. Compileer het. Voer het uit.
Als het crasht, heb je een free gemist. Of je hebt toegang gekregen tot vrijgemaakt geheugen. Debug het.
De realitycheck
Dynamische toewijzing is snel. Totdat het niet meer zo is.
‘malloc’ en ‘gratis’ hebben overhead. In strakke lussen klopt het.
Maar voor algemeen gebruik? Het is flexibel. Het is standaard. Het is wat je in de meeste C-codebases zult zien.
De gekoppelde stapel is een bouwsteen.
Je gebruikt het voor functieaanroepen. Voor expressie-evaluatie. Voor ongedaan maken-knoppen.
Het is overal.
Onthoud gewoon: als je het toewijst, maak je het vrij. Of anders.
“Code is als humor
