Noder og referanser
Definisjon 2: En datastruktur består av en samling elementer, ofte kalt noder, med
innbyrdes relasjoner, ofte kalt referanser. Den viktigste oppgaven til en
datastruktur er å knytte beslektede elementer sammen på en effektiv og
hensiktsmessig måte.
- Relasjonene danner en ordning av elementene ved å definere hvilke naboer
de har. Et slikt naboskap kalles gjerne for topologi. Vi skiller mellom tre
hovedtyper topologier:
- Lineære (en-til-en) strukturer.
Brukes når man har en mengde
elementer ordnet i rekkefølge. En noe kan ha to typer relasjoner, en
referanse til forrige node og en til neste.
- Hierarkiske (en-til-mange) strukturer.
En node kan ha flere
etterfølgende noder (barn), men kun en forrige node (forelder).
- Nettverk (mange-til-mange).
Dannes når relasjonene ikke er
orndet på noen regulær måte. Det finnes ingen forrige- eller
neste-relasjoner, og heller ingen foreldre/barn-relasjoner. Hver node
kan derimot kan derimot ha et vilkårlig antall naboer.
- En algoritme vil vanligvis være knyttet til datastruktur. Hvis vi for
eksempel skal søke etter en verdi i en samling verdier, er det opplagt at søkemetoden avhenger av måten
verdiene er organisert på.
- Ligger for eksempel verdiene i en uordnet tabell, har vi ikke noe annet
valg enn å starte på begynnelsen av tabellen og se på ett og ett element
helt til vi eventuelt finner verdien vi søker etter. Det er med andre ord
ikke mulig å søke på en effektiv måte.
- Vi skal i løpet av kurset se på andre måter å organisere dataene på som
gjør det mulig å søke etter verdier på en effektiv måte.
Inkaene hadde ikke skriftspråk. Istedet benyttet de seg av et komplisert og effektivt system basert på tau og knuter.
Disse quipu'ene
ble bla.a. brukt til å holde regnskap med skatter og innbetalinger, skrive manntall og nedtegne historiske hendelser.
Quipu'en kan sees på som en abstrakt datastruktur.