8.5.oefeningen.md

Oefeningen 8.5 · Slide 125

Theorie

Oefening 8.5.1

Breid de klasse GelinkteLijst uit met een methode size. De methode heeft als resultaat het aantal elementen van een gelinkte lijst.

size(I: /): aantal: geheel getal
    * Preconditie: de gelinkte lijst l bestaat
    * Postconditie: het aantal elementen van l werd geretourneerd.
    * Gebruikt: /
BEGIN
    i <- 0
    ref <- eerste           // Met anker: ref <- anker.volgende
    ZOLANG ref ≠ null DOE
        ref <- ref.volgende
        i <- i + 1
    EINDE ZOLANG

    RETOUR (i)
EINDE

Oefening 8.5.3

Pas de klasse Knoop aan zodat met de objecten van deze klasse een dubbelgelinkte lijst kan aangemaakt worden. Noem de nieuwe klasse KnoopDubbel. Schrijf vervolgens voor dubbelgelinkte lijsten met twee ankercomponenten de basisfuncties van de klasse DubbelGelinkteLijst in pseudocode uit.

DubbelGelinkteLijst
- eerste : KnoopDubbel - laatste : KnoopDubbel
+ DubbelGelinkteLijst( ) + verwijder(ref : KnoopDubbel) : Element + voegToeVoor(ref : KnoopDubbel, x: Element): / + voegToeNa(ref : KnoopDubbel, x: Element): /

Een lege dubbel gelinkte lijst

DubbelGelinkte(I: /): /
    * Preconditie: /
    * Postconditie: er werd een nieuwe lege dubbelgelinkte lijst aangemaakt
    * Gebruikt: KnoopDubbel
BEGIN
    eerste <- nieuwe KnoopDubbel()
    laatste <- nieuwe KnoopDubbel()

    eerste.volgende <- laatste
    laatste.vorige <- eerste
EINDE

Een vakje verwijderen in een dubbel gelinkte lijst

verwijder(I: ref: KnoopDubbel): x: Element
    * Preconditie: de dubbelgelinkte lijst l bestaat
    * Postconditie: de knoop met referentie ref werd verwidjerd uit l; de waarde van het data-veld van de verwijderde knoop werd geretourneerd.
    * Gebruikt: /
BEGIN
    x <- ref.data

    ref.vorige.volgende = ref.volgende
    ref.volgende.vorige = ref.vorige

    RETOUR (x)
EINDE

Een vakje invoegen voor een ander

voegToeVoor(I: ref: KnoopDubbel, x: Element): /
    * Preconditie: de dubbelgelinkte lijst l bestaat
    * Postconditie: voor de knoop, waarnaar gerefereerd wordt door de referentie ref, werd een nieuwe knoop met data-veld x toegevoegd
    * Gebruikt: KnoopDubbel
BEGIN
    hulp <- nieuwe KnoopDubbel()

    hulp.data <- x

    hulp.vorige <- ref.vorige
    hulp.volgende <- ref

    ref.vorige.volgende <- hulp
    ref.vorige <- hulp
EINDE

Oefening 8.5.4

Een wachtrij kan geïmplementeerd worden door twee referenties k en s. De knoop k refereert naar de kop van de wachtrij, de knoop s refereert naar de staart van de wachtrij. Herschrijf alle basisbewerkingen voor een wachtrij corresponderend met deze implementatie.

Queue
- k : Knoop - s : Knoop
+ Queue(n: geheel getal) + empty( ) : boolean + enqueue(x : Element) : / + dequeue( ) : Element + front( ) : Element

Queue(I: /) : /
    * Preconditie: /
    * Postcondite: er werd een nieuwe wachtrij aangemaakt, deze wachtrij bestaat als lege wachtrij
    * Gebruikt: /
BEGIN
    k <- null
    s <- null
EINDE

empty(I: /) : vlag: boolean
    * Preconditie: de wachtrij q bestaat
    * Postcondite: de waarde true of false werd geretourneerd, afhankelijk van het feit of de wachtrij q leeg is of niet.
    * Gebruikt: /
BEGIN
    RETOUR (k = null)
EINDE

enqueue(I: x: Element) : /
    * Preconditie: de wachtrij q bestaat
    * Postcondite: het element x werd aan de staart van de wachtrij q toegevoegd
    * Gebruikt: empty, Knoop
BEGIN
    hulp <- nieuwe Knoop()
    hulp.data <- x

    ALS empty() DAN
        k <- hulp
    ANDERS
        s.volgende <- hulp
    EINDE ALS

    s <- hulp
EINDE

dequeue(I: /) : x: Element
    * Preconditie: de wachtrij q bestaat en is niet leeg
    * Postcondite: de kop van de wachtrij q werd verwijderd en geretourneerd
    * Gebruikt: /
BEGIN
    x <- k.data

    ALS k = s DAN
        k <- null
        s <- null
    ANDERS
        k <- k.volgende
    EINDE ALS

    RETOUR (x)
EINDE