Innholdsoversikt for programutvikling

Litt om datastrukturer

• Begrepet datatype
• Datatype for sammenkjedet liste
• Varianter av listeimplementasjonen
• To-veis-lister
• Sirkulær liste
• Sammensatte lister: liste av lister
• Kort om andre lineære strukturer

Begrepet datatype

Hver gang vi deklarerer en variabel (eller et datafelt) når vi programmerer i java, må vi spesifisere hva datatypen for variabelen skal være (int, double, String, etc.). Det samme gjelder for konstanter. Vi skal nå aller først se litt nærmere på hva som ligger i begrepet datatype. Datatypen til en variabel vil være avgjørende for

• hvilke verdier vi kan tilordne variabelen;
• hvilke operasjoner vi kan utføre på eller med variabelen.

Dette er da også alt som vi egentlig trenger å vite for å kunne bruke en variabel. Vi kan derfor si at en datatype er karakterisert av disse to egenskapene.

Eksempler

Av datatyper som er det vi kan kalle innebygde i selve javaspråket har vi blant annet

  boolean
  char
  int
  int[]
  etc.

I tillegg til de innebygde datatypene har vi datatyper definert i form av klasser. For vi vet at alle klassedefinisjoner samtidig definerer en datatype. De aller fleste datatypene vi bruker i et javaprogram er definert i form av klasser. En stor del av dem importerer vi fra javas klassebibliotek, noen ganger for å modifisere dem ved at vi definerer våre egne subklasser. Dessuten definerer vi våre egne datatyper tilpasset det programmet vi skal lage.

Kikker vi litt nærmere på de innebygde datatypene listet opp ovenfor, ser vi at datatypen int[] skiller seg fra de tre første typene ved at den er sammensatt av komponenter som vi kan skille ut. Vi kaller den derfor en sammensatt eller strukturert type, i motsetning til de første, som er primitive eller atomiske. (Ordet 'primitiv' betyr i dette tilfelle 'grunnleggende, det som kommer først', mens ordet 'atomisk' kommer fra gresk og betyr 'noe som ikke kan deles opp'.)

En strukturert datatype kalles også en datastruktur. Datatypen int[] er en statisk datastruktur: Når vi oppretter et objekt av denne typen, det vil si en array, må den tilordnes en bestemt størrelse og denne størrelsen kan ikke endres når programmet kjører. Denne virkemåten er grei nok i mange tilfeller, men den forutsetter at vi kjenner til plassbehovet på det tidspunktet objektet blir opprettet. I mange tilfeller vil vi vite lite om plassbehovet på et så tidlig tidspunkt, eller plassbehovet vil variere mye under veis. I slike tilfeller ville det være bedre å ha en dynamisk datastruktur, det vil si en struktur som kunne øke eller minke i størrelse mens programmet kjører, avhengig av hvor mye data det var behov for å lagre. En dynamisk datastruktur kan vi få til ved å kjede sammen objekter ved hjelp av pekere (referanser). Hvert objekt inneholder da adressen til det neste objektet i strukturen. Objekter kan tilføyes til strukturen eller fjernes fra strukturen etter behov mens programmet kjører. Sammenkjedingen kan gjøres på mange forskjellige måter og dermed resultere i forskjellige typer av strukturer. Noen av dem er etter hvert blitt det vi kan kalle standardstrukturer eller "klassikere". En av disse er den strukturen som kalles sammenkjedet liste eller kort og godt liste. På en figur kan vi illustrere den slik:

Pilene symboliserer objektreferanser (pekere), mens boksene symboliserer objekter. Elementene (objektene) i en sammenkjedet datastruktur kalles noder. En node i en liste inneholder altså, i tillegg til øvrige datafelter, en referanse til neste element (node) i lista. Dessuten må det for lista være en egen referanse til den første noden. Den siste noden i lista er her karakterisert ved at dens neste-referanse har verdien null. Detaljene kan imidlertid utformes på andre måter. Noen muligheter er skissert lenger ute i notatet, under overskriften Varianter av listeimplementasjonen.

Grunnen til at dette opplegget lar seg implementere i java, er at det i en klassedefinisjon er tillatt å ha referanser av den typen som klassen selv definerer. Programmet i følgende eksempel gir et enkelt eksempel på hvordan dette fungerer i praksis. Dette programmet gir imidlertid ingen dynamisk struktur: Antall noder er bestemt som en konstant i programmet. Eksemplet har bare til hensikt å vise hvordan objekter kan kjedes sammen til en liste.

Programeksempel 1

Når man skal programmere en listestruktur, kan detaljene skrives på mange forskjellige måter. I dette eksemplet er node-objektene definert i form av en indre klasse i klassen Miniliste som definerer selve listeobjektet. Dette må ikke oppfattes som noe mønster for hvordan det skal være. Det er ikke noe i veien for å definere node-objektene i form av en frittstående klasse. Navnet på klassen kan selvsagt også velges fritt. Navn bør i denne sammenheng som i andre sammenhenger velges slik at navnene er selvforklarende. Innholdet i fila Miniliste.java er gjengitt nedenfor.

 1 public class Miniliste
 2 {
 3   private Node første;
 4
 5   public Miniliste( int antNoder )
 6   {
 7     første = new Node( 0 );
 8     Node løper = første;
 9
10     for ( int i = 1; i < antNoder; i++ )
11     {
12       løper.neste = new Node( i );
13       løper = løper.neste;
14     }
15   }
16
17   public String getListedata()
18   {
19     String data = "Listeinnhold:\n";
20     Node løper = første;
21     while ( løper != null )
22     {
23       data += løper.getInfo() + "\n";
24       løper = løper.neste;
25     }
26     return data;
27   }
28
29   private class Node
30   {
31     private int info;
32     Node neste;
33
34     public Node( int data )
35     {
36       info = data;
37       neste = null;
38     }
39
40     public int getInfo()
41     {
42       return info;
43     }
44   }
45 }

Vi merker oss her spesielt den indre klassen Node. Den definerer objektene som blir kjedet sammen. For å få til sammenkjedingen, har den datafeltet

    Node neste;

Dette er av samme type som den typen klassen selv definerer, noe som altså er tillatt. Datafeltet har som oppgave å være en peker til det neste Node-objektet i den sammenkjedete lista. Opprettingen og sammenkjedingen av Node-objektene skjer i konstruktøren til den omgivende klassen Miniliste.

I testprogrammet Minilistetest.java som er gjengitt nedenfor, blir det opprettet et listeobjekt av den typen som blir definert av klassen Miniliste. Lista blir gjennomløpt ved kall på metoden getListedata og innholdet blir vist i vinduet som er gjengitt til høyre. For enkelhets skyld er programmets main-metode lagt inn i samme klassen Minilistetest som definerer vinduet, oppretter listeobjektet og viser dets innhold.

 1 import javax.swing.*;
 2
 3 public class Minilistetest extends JFrame
 4 {
 5   private JTextArea output;
 6
 7   public Minilistetest()
 8   {
 9     super( "Miniliste" );
10
11     output = new JTextArea( 20, 20 );
12     output.setEditable( false );
13     getContentPane().add( output );
14     Miniliste liste = new Miniliste( 15 );
15     output.setText( liste.getListedata() );
16
17     setSize( 200, 400 );
18     setVisible(true);
19   }
20
21   public static void main( String[] args )
22   {
23     Minilistetest vindu = new Minilistetest();
24     vindu.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE );
25   }
26 }

Husk på at når programmets main-metode oppretter vindusobjektet, så vil instruksjonene i konstruktøren til vindusklassen Minilistetest bli utført. I tillegg til instruksjonene som har med selve vinduet å gjøre, er det instruksjonen for å opprette listeobjekt:

  Miniliste liste = new Miniliste( 15 );

Som en følge av dette vil instruksjonene i konstruktøren til listeklassen Miniliste bli utført, og med 15 som konstruktørparameter. Gjennomgå for deg selv disse instruksjonene og prøv å tegne opp på en figur virkningen av de enkelte instruksjonene! Bruk den figuren du kommer fram til (som bør være en liknende figur som den som er tegnet opp ovenfor) til å gjennomgå for deg selv det som skjer som følge av vindusklassens instruksjon

    output.setText( liste.getListedata() );

Som nevnt ovenfor, er listeeksemplet vi nettopp har sett på egentlig ikke en dynamisk struktur, siden størrelsen er bestemt på forhånd. Vi skal i det følgende ta for oss listeeksempler som virkelig er dynamiske. Men først skal vi se litt nærmere på noen operasjoner som kan være aktuelle å utføre for en liste, og hvordan vi kan programmere disse operasjonene.

Innsetting og fjerning av noder

Noder kan settes inn eller fjernes hvor som helst i en sammenkjedet liste. For at koden for dette skal bli riktig, er det imidlertid viktig å være nøye med detaljene. Det er også av avgjørende betydning at instruksjonene kommer i riktig rekkefølge. Det er til svært god hjelp å tegne hjelpefigurer der referansene (pekerne) tegnes som piler. Vi skal nå se på noen eksempler for å illustrere dette. For å få enklest mulig kode, antar vi at node-objektene er definert som i programeksemplet foran, med pakkeaksess for neste-pekerne.

Eksempel 1

Sett inn en ny node som inneholder tallet 4 etter noden som inneholder tallet 3 i lista

Av figuren kan vi se at det som må gjøres, er å få satt neste-pekeren i noden som inneholder 3 til å peke på den nye noden, samt å sette neste-pekeren i den nye noden til å peke på noden som inneholder 5.

Det første vi må gjøre, er å finne innsettingspunktet, som er noden som inneholder tallet 3. Når vi skal lete etter den, så må vi huske på at det eneste som vi i utgangspunktet kjenner til, er pekeren (det vil si adressen) til den første noden. Vi må derfor starte på den og så lete oss utover i lista til vi finner noden som inneholder 3. Der skal vi stoppe opp. Kode for dette kan vi skrive slik:

   Node løper = første;
   while ( løper.getInfo() != 3 )
     løper = løper.neste;
   // løper vil nå peke på noden som inneholder 3

NB! Forutsetningen for at denne koden skal virke, er at det i lista virkelig finnes en node som inneholder 3.

Om vi ikke har gjort det før, må vi nå opprette den nye noden som skal inn i lista:

  Node ny = new Node( 4 );

Dermed er det klart for å hekte den nye noden inn i lista. Det er da av avgjørende betydning at instruksjonene skrives i riktig rekkefølge, ellers kan det oppstå brudd i lista. Følgende instruksjoner kan brukes:

  ny.neste = løper.neste;
  løper.neste = ny;

Dermed er vi ferdige! Prøv å tegne inn på en figur hva som er virkningen av de enkelte instruksjonene!

Eksempel 2

Fjern noden som inneholder 3 fra lista

Av figuren ser vi at for å oppnå dette, må vi sette neste-pekeren i noden som inneholder 2 til å peke på noden som inneholder 4, istedenfor å peke på noden som inneholder 3. Resultatet av det vil være at dersom vi gjennomløper lista ved å følge neste-pekere fra starten av lista, så vil noden som inneholder 3 bli hoppet over. Den hører dermed ikke lenger til i lista.

Vi skal altså oppdatere neste-pekeren i noden som er foran den vi skal fjerne. Kode for å finne noden som er foran den som skal ut av lista, kan vi skrive slik:

  Node løper = første;
  while ( løper.neste.getInfo() != 3 )
    løper = løper.neste;
  //løper vil nå peke på noden som er foran den som inneholder 3

NB! Forutsetningen for at denne koden skal virke, er at det i lista virkelig finnes en node som inneholder 3, og at dette ikke er den første noden.

For å kople ut av lista den noden som inneholder 3, kan vi nå skrive denne instruksjonen:

  løper.neste = løper.neste.neste;

Resultatet av dette vil også være at det nå ikke lenger er noen peker som peker på noden som inneholder 3. Den vil derfor automatisk bli slettet.

Datatype for sammenkjedet liste

Eksemplene foran brukte en svært primitiv liste. Hensikten var å demonstrere noen enkle operasjoner med pekere. En liste har felles egenskaper med en array på den måten at vi kan sette inn elementer i den og fjerne elementer fra den. Arraytypen er forhåndsdefinert i selve java-språket. En listetype må defineres ved å skrive nødvendig programkode ved å bruke java-språket. (Det er også mulig å gjøre det i andre programmeringsspråk.) For å definere en listetype må vi gjøre følgende:

• definere en datatype for nodene (i form av en klasse)
• definere en datatype Liste (eventuelt et annet navn) for selve listeobjektet

I klassen Liste må vi definere operasjoner for å sette inn noder, fjerne noder, gjennomløpe lista, etc. Detaljene i dette kan utformes på mange forskjellige måter. Ofte "skreddersyr" vi en liste til det den skal brukes til. Vi skal ta for oss et slikt eksempel der nodene er Bok-objekter, det vil si objekter som representerer bøker. For å begrense eksemplets omfang, er det bare boktittel som blir lagret i Bok-objektene, i tillegg til den neste-pekeren som er nødvendig for å få kjedet sammen Bok-objektene til en liste. Neste-pekeren blir gitt pakke-aksess for at det skal kunne refereres direkte til den. Programkoden som har med selve listestrukturen å gjøre, er imidlertid uavhengig av hvor mye data som ellers legges inn i Bok-objektene. Den er også uavhengig av hvilken type objekter som blir kjedet sammen. Så istedenfor Bok-objekter kan du tenke deg en hvilken som helst annen type objekter. Det avgjørende for å kunne kjede sammen til en liste, er at det i hvert objekt i kjeden er en neste-peker som kan peke til et annet objekt av samme type (eller til et objekt av en subklasse-type).

Bok-klassen er definert i fila Bok.java. Innholdet er gjengitt nedenfor.

 1 //Representerer én enkelt bok
 2 public class Bok
 3 {
 4   private String tittel;
 5   Bok neste;
 6
 7   public Bok( String nyTittel )
 8   {
 9     tittel = nyTittel;
10     neste = null;
11   }
12
13   public String toString()
14   {
15     return tittel;
16   }
17 }

I listeklassen Bokliste blir det bare definert metoder for innsetting av nye Bok-objekter (bakerst i lista) og for utskrift av listeinnholdet. Definisjonen av listeklassen er gjengitt nedenfor. Den finnes i fila Bokliste.java.

 1 //Representerer en samling av bøker
 2 public class Bokliste
 3 {
 4   private Bok første;
 5
 6   public Bokliste()
 7   {
 8     første = null;
 9   }
10
11   //Setter inn et nytt Bok-objekt bakerst i lista.
12   public void settInn( Bok ny )
13   {
14      if ( ny == null )
15        return;
16
17     if ( første == null )
18       første = ny;
19     else
20     {
21       Bok løper = første;
22       while ( løper.neste != null )
23         løper = løper.neste;
24       løper.neste = ny;
25     }
26   }
27
28   //Gjennomløper boklista og returnerer alle boktitlene, 
29   //en på hver linje.
30   public String toString()
31   {
32     String resultat = "";
33     Bok løper = første;
34
35     while ( løper != null )
36     {
37       resultat += løper.toString() + "\n";
38       løper = løper.neste;
39     }
40
41     if ( !resultat.equals( "" ) )
42       return resultat;
43     else
44       return "Ingen bøker registrert!";
45   }
46 }

I vindusklassen Bokhylle som er gjengitt nedenfor blir det opprettet et objekt av type Bokliste. Vinduet inneholder funksjonalitet for å sette inn bokobjekter i lista og vise hva den inneholder.

 1 //Test av enkel bokliste.
 2 import java.awt.*;
 3 import java.awt.event.*;
 4 import javax.swing.*;
 5
 6 public class Bokhylle extends JFrame
 7 {
 8   private Bokliste bøkene;
 9   private JTextField tittel;
10   private JButton skrivUt;
11   private JTextArea utskrift;
12   private Kommandolytter lytter;
13
14   public Bokhylle()
15   {
16     super( "Test av bokliste" );
17     bøkene = new Bokliste();
18     Container c = getContentPane();
19     c.setLayout( new FlowLayout() );
20     c.add( new JLabel( "Ny boktittel: " ) );
21     tittel = new JTextField( 25 );
22     c.add( tittel );
23     skrivUt = new JButton( "Skriv bokliste" );
24     c.add( skrivUt );
25     utskrift = new JTextArea( 10, 30 );
26     utskrift.setEditable( false );
27     c.add( new JScrollPane( utskrift ) );
28     lytter = new Kommandolytter();
29     tittel.addActionListener( lytter );
30     skrivUt.addActionListener( lytter );
31     setSize( 400, 300 );
32     setVisible( true );
33   }
34
35   public void settInnBok()
36   {
37     Bok ny = new Bok( tittel.getText() );
38     bøkene.settInn( ny );
39     tittel.setText( "" );
40   }
41
42   public void skrivBokliste()
43   {
44     utskrift.setText( bøkene.toString() );
45   }
46
47   private class Kommandolytter implements ActionListener
48   {
49     public void actionPerformed( ActionEvent e )
50     {
51       if ( e.getSource() == tittel )
52         settInnBok();
53       else if ( e.getSource() == skrivUt )
54         skrivBokliste();
55     }
56   }
57 }

Nødvendig main-metode for programmet finnes i fila Boksamling.java. Den oppretter et vindusobjekt av type Bokhylle. Nedenfor er det vist et bilde av vinduet etter at det er satt inn noen Bok-objekter i lista og innholdet av lista er skrevet ut i vinduet.

Når vi skal skrive programkode for manipulering av objekter i en sammenkjedet liste, er det som tidligere nevnt viktig å være nøye med detaljene, samt passe på at instruksjonene kommer i riktig rekkefølge. Dessuten må en huske på å ta hensyn til spesialtilfeller som tom liste og liste med bare én node. Tegning av hjelpefigurer vil alltid være en god hjelp til å få riktig kode.

Som eksempler på flere listemetoder skal vi nå skrive metoder som fjerner henholdsvis første og siste node i den boklista som vi tok for oss ovenfor. Metodene skal dessuten returnere det Bok-objektet som blir fjernet, eller eventuelt null i tilfelle det ikke finnes noe å fjerne. Vi tenker oss at metodene tilføyes i klassen Bokliste.

Metode for å fjerne og returnere første Bok-objekt i lista:

  public Bok fjernFørste()
  {
    Bok returbok = første;
    if ( første != null )
      første = første.neste;
    return returbok;
  }

Tegn for deg selv på en figur hvordan metoden virker! Legg merke til at metoden også vil virke riktig dersom lista er tom. Metoden vil da returnere null, siden første i det tilfellet er lik null. Metoden vil også virke riktig dersom lista på forhånd inneholder bare én node. Da vil den sette første til verdien null, det vil si tømme lista, og returnere det ene objektet som var i lista da metoden ble kalt opp.

Metode for å fjerne og returnere det siste Bok-objekt i lista:

  public Bok fjernSiste()
  {
    Bok returbok = første, løper = første;
    if ( første != null )
    {
      if ( løper.neste == null )
      { // det er bare én node i lista
        første = null;
      }
      else
      { // må finne peker til nest siste node
        while ( løper.neste.neste != null )
          løper = løper.neste;

        // Nå er løper.neste.neste == null,
        //dvs. løper peker på nest siste node.
        returbok = løper.neste;
        løper.neste = null;
      }
    }
    return returbok;
  }

Denne metoden er også skrevet slik at den virker riktig også for de tilfellene at lista på forhånd er tom eller bare inneholder én node. Generelt bør vi selvsagt bestrebe oss på å programmere slik at metodene våre virker på riktig eller hensiktsmessig måte i alle tenkelige situasjoner.

Merknad

En beskrivelse av lister, slik de er implementert i Javas klassebibliotek, med bruk av generiske datatyper, kan du finne i notatet Collections — bruk av generiske datatyper under avsnittet Lister.

Varianter av listeimplementasjonen

Som det har vært nevnt tidligere, er det ofte slik at vi "skreddersyr" en listeimplementasjon til den konkrete situasjonen den skal brukes på. Bokliste-eksemplet som vi har sett på, implementerer en liste med en struktur som vi på en figur kan skissere opp slik:

En klasse som gir denne strukturen kan vi skissere slik:

  class Bokliste
  {
    private Bok første;

    < metoder for listemanipulering >
  }

Vår settInn-metode setter alltid inn bakerst i lista det Bok-objektet som den mottar. Dersom lista er lang, vil innsettingsoperasjonen etter hvert bli en ineffektiv operasjon. Dette fordi vi ved hver innsetting først må lete fra starten av lista til vi finner det siste Bok-objektet i lista. Dette tar lengre tid jo lengre lista er.

Innsettingsoperasjonen kunne blitt mer effektiv dersom vi i listeklassen hadde en egen peker som hele tida pekte på den siste noden i lista. Effektiviteten til innsettingsoperasjonen ville da heller ikke avhenge av listestørrelsen. På en figur kunne vi da skissert listestrukturen på følgende måte:

En klasse som gir denne strukturen kan vi skissere slik:

  class Bokliste
  {
    private Bok første, siste;

    < metoder for listemanipulering >
  }

Skal dette opplegget virke etter hensikten, forutsetter det selvsagt at vi skriver operasjonene for innsetting og fjerning av noder slik at pekeren siste blir oppdatert slik at den hele tida peker på den siste noden i lista (eller er lik null, i tilfelle lista er tom). Metoden for innsetting av ny node bakerst i lista kunne vi skrevet slik:

  public void settInn( Bok nyBok )
  {
    if ( nyBok == null )
      return;
    if ( første == null )
      første = siste = nyBok;
    else
    {
      siste.neste = nyBok;
      siste = nyBok; // eller siste = siste.neste;
    }
  }

"Prisen" å betale for den ekstra effektiviteten, er selvsagt lagerplassen som den ekstra pekeren krever. For en enkelt liste er dette helt uten betydning. Men dersom vi har et program med et stort antall små lister av denne type, er bruken av den ekstra lagerplassen noe som kan ha betydning.

Noe annet som kan være nyttig å ha i en listeklasse, er et datafelt som til enhver tid inneholder antall noder som er satt inn i lista. Dette må selvsagt oppdateres hver gang noder settes inn i eller tas ut av lista. Altså medfører dette ekstra kode og ekstra lagerplass. Igjen må en vurdere behovet for å ha et slikt datafelt.

To-veis-lister

De eksemplene vi har sett på kalles en-veis-lister, fordi gjennomløping av lista bare kan skje i én retning: Vi må begynne forfra og gå bakover ved å følge neste-pekerne. Dersom det er behov for mye søking i lista, er dette tungvint og ineffektivt. Mer effektiv søking kunne vi fått til dersom vi ut fra en gitt node kunne vandre i begge retninger: velge om vi ville vandre forover eller bakover i lista. Lista burde da i tillegg være sortert på en eller annen måte, slik at vi visste i hvilken retning vi burde vandre for å søke videre.

Skal vi kunne søke i begger retninger, må hver node i tillegg til å inneholde en peker til sin etterfølger, også inneholde en peker til sin forløper (det vil si til sin foregående node). Strukturen til lista kunne vi da på en figur skissere opp slik:

En klasse som definerer slike noder kunne vi skissere slik:

  class Node
  {
    Node neste, forrige;
    < andre datafelter >

    < konstruktør >
    < metoder >
  }

"Prisen" å betale for dette ville være

• ekstra lagerplass (en ekstra peker i hver node)
• mer kompliserte operasjoner for å sette inn noder og fjerne noder (flere pekere å oppdatere)

Sirkulær liste, en-veis eller to-veis

I de eksemplene på listeimplementasjon som vi har tatt for oss hittil, har vi latt neste-pekeren i den siste noden være lik null-pekeren. Et annet alternativ er å la denne, altså neste-pekeren i den siste noden, peke tilbake til den første noden. Vi ville da få en sirkulær struktur som vi på en figur kunne skissere opp slik:

Programmeringsmessig ville konsekvensen dessuten bli at en del av listeoperasjonene måtte programmeres litt annerledes.

Det er altså mange valg som kan gjøres når en listestruktur skal implementeres. En må tenke over hvilke behov en har i en konkret situasjon og gjøre de valg som synes mest hensiktsmessige for formålet.

Sammensatte lister: liste av lister

Noen ganger kan det være fornuftig å velge en datastruktur som er bygget opp som en liste av lister. Som et konkret eksempel på en slik situasjon tenker vi oss at det skal lages et register over biler og bileiere. Nå er det slik at hver bil er eid av én person (vi forutsetter dette), men hver person kan eie flere biler. Noen personer eier ingen biler (for øyeblikket), andre eier én eller to, og noen ganske få personer eier et stort antall biler. En mulig måte å organisere et slikt register på, er å legge persondataene inn i listenoder (som kjedes sammen til en liste), en node for hver person. I hver personnode er det en peker til en liste over bilene som denne personen eier. (Lista kan eventuelt være tom.) Billista må da inneholde en annen type noder enn personlista. Hver node i billista må inneholde relevant informasjon om vedkommende bil, samt peker til neste bilnode. Klasser for datastrukturen kan vi dermed skissere opp på denne måten:

  class Bil
  {
    < bildata >
    Bil nestebil;
    ...
  }

  class Billiste
  {
    private Bil førstebil;
    < listemetoder >
  }

  class Person
  {
    < persondata >
    Person nesteperson;
    private Billiste biler;
    ...
  }

  class Personliste
  {
    private Person førsteperson;
    < listemetoder >
  }

Oppgave

Prøv å tegne opp en figur som illustrerer den datastruktur som klasseskissene ovenfor legger opp til!

Kort om andre lineære strukturer

Ved å innføre spesielle restriksjoner for hvor det er tillatt å sette inn elementer eller fjerne elementer i en lineær liste, får vi fram et par andre standard datastrukturer som jeg kort skal nevne, uten å gå nærmere inn på dem.

Kø

En kø får vi dersom vi i en liste tillater innsetting i bare den ene listeenden, kalt enden eller halen til køen, og tillater fjerning bare i den andre listeenden, kalt fronten til køen. Dette er en type struktur som vi har mange eksempler på i dagliglivet, for eksempel kassakøen i en butikk! Også i databehandling er kø en vanlig forekommende struktur, for eksempel køen av utskrivingsjobber til en printer. Prinsippet for virkemåten til en kø blir populært beskrevet som "først inn først ut", siden det er det objektet som først ble satt inn i køen som også vil være det som blir tatt først ut. I engelskspråklige lærebøker vil en finne forkortelsen FIFO (First In First Out) for dette.

Stakk

En struktur av type stakk får vi dersom vi i en liste tillater innsetting og fjerning bare i én og samme listeende, kalt toppen til stakken. I dagliglivet finnes det også eksempler på denne strukturen. Vi får den dersom vi har en stabel av tallerkener eller bøker der det bare er tillatt å flytte én tallerken eller bok om gangen. I databehandling forekommer denne typen struktur i mange sammenhenger, blant annet internt i datamaskinen når den kjører. Da blir for eksempel lokale variable ved metodekall lagret på en stakk. Prinsippet for virkemåten til en stakk blir populært beskrevet som "sist inn først ut", i samsvar med at det sist innsatte objektet vil bli tatt ut først. I engelskspråklig litteratur er dette forkortet til LIFO (Last In First Out).

Merknad

Dette notatet kan bare kalles et lite gløtt inn i emneområdet datastrukturer. En mye grundigere og mer omfattende behandling av datastrukturer blir gitt i kurset Algoritmer og datastrukturer som undervises om høsten andre år i våre datastudier.

Innholdsoversikt for programutvikling

Copyright © Kjetil Grønning og Eva Hadler Vihovde, revidert 2015