Datastruktur
Fra Wikipedia, den frie encyklopedi
Innenfor informatikken er en datastruktur en måte å organisere data på i en datamaskin. Ved behandling av store datamengder er det en nødvendighet å bruke gode datastrukturer slik at effektive algoritmer kan anvendes for å løse beregningene på kortest mulig tid. En god datastruktur kjennetegnes av at den minimerer antallet beregninger CPUen må gjøre, samt minimerer bruk av minneplass og sørger for minst mulig aksesses til platelageret.
Generelt sett er det fire forskjellige grunnleggende operasjoner som må kunne gjøres i en datastruktur:
- Sette inn et element
- Fjerne et element
- Søke etter et bestemt element
- Teste om strukturen er tom
Mange programmeringsspråk inneholder ferdige moduler en programmerer kan bruke til å skape effektive datastrukturer. Disse ligger ferdige i språkets standardbibliotek, slik at de praktiske implementasjonene gjemmes for programmereren.
[rediger] Typer datastrukturer
Datastrukturer kan deles inn i to hovedgrupper, lineære datastrukturer og datastrukturer som baserer seg på grafer.
Blant de lineære datastrukturene finner man lister, herunder lenkede lister. Arrayer, hashtabeller, stacker og køer er andre viktige lineære datastrukturer.
Av datastrukturene som bygger på grafteori, er trær av forskjellige typer den viktigste. Det finnes mange typer trær, de viktigste er binære søketrær og heaper. I tillegg til trær er datastrukturen kalt disjunkte mengder viktig.
