Array (datastruktur): Hvad er et array? Typer, indeks og størrelse

Forstå arrays: typer, indeks, størrelse og begrænsninger i forskellige programmeringssprog (fx C). Kort, praktisk guide til indeksering, hukommelse og brug i kode.

I programmeringssprog er et array en måde at lagre flere elementer (f.eks. hele tal) på. Disse elementer skal have samme type (kun hele tal, kun strenge, ...), fordi et array ikke kan lagre forskellige typer elementer i mange sprog. Hvert element i et array har et nummer, så programmøren kan hente elementet ved hjælp af dette nummer. Dette nummer kaldes indekset. I nogle programmeringssprog har det første element indeks 0, det andet element har indeks 1 osv. Men i andre sprog har det første element indeks 1 (og derefter 2, 3, ...).

Når programmøren opretter et array, skal han angive størrelsen på arrayet. Dette er det antal elementer, der kan gemmes i arrayet. Hvis programmøren ønsker at gemme flere elementer, skal han oprette et nyt array. Dette skyldes, at størrelsen på et array ikke kan ændres i mange sprog (dvs. arrayet er "fast størrelse").

Indeksering og baser

De to mest almindelige indekseringskonventioner er:

• 0-baseret indeksering: Første element har indeks 0 (fx C, C++, Java, Python, JavaScript). Fordel: enklere pointer- og adresseberegninger.
• 1-baseret indeksering: Første element har indeks 1 (fx MATLAB, nogle versioner af Fortran og visse skriftsystemer eller biblioteker). Det kan være mere intuitivt i nogle matematiske sammenhænge.

Det er vigtigt at kende sprogets konvention, fordi forkert antagelse kan føre til off-by-one-fejl eller out-of-bounds-adgang.

Hvordan arrays ligger i hukommelsen

• I mange sprog (fx C og C++) gemmes elementerne i et array som en sammenhængende blok i hukommelsen. Det gør det muligt at beregne adressen for element i via startadresse + i * elementstørrelse.
• Denne sammenhængende lagring giver hurtig tilfældig adgang: læsning eller skrivning af et element ved kendt indeks er O(1).
• Nogle højere niveau-sprog (fx Python) implementerer deres "liste"-typer som arrays under motoren, men tillader samtidig at elementerne er forskellige typer. Begrebet "array" kan derfor variere mellem sprog.

Operationer og deres kompleksitet

• Adgang ved indeks: O(1) — direkte adresseberegning.
• Søgning (usorteret): O(n) — lineær søgning gennem arrayet.
• Indsættelse/sletning i midten: O(n) — kræver ofte at flytte elementer for at skabe plads eller fylde hul.
• Tilføjelse i enden: I faste-arrays er det O(1), hvis der er plads; i dynamisk resizable arrays (fx std::vector, ArrayList) er det amortiseret O(1) på grund af kopiering ved udvidelse.

Typer af arrays

• En-dimensionelle arrays: En simpel liste af elementer.
• Multi-dimensionelle arrays: Fx 2D-arrays (tabeller) hvor hvert element selv er et array. I C er disse ofte lagret som rækker efter hinanden (row-major) eller kolonner (column-major afhængig af sprog).
• Static arrays (fast størrelse): Oprettes med en fast størrelse ved kompilering eller ved initialisering, størrelse kan ikke ændres uden at allokere et nyt array.
• Variable-length arrays (VLA): Understøttet i visse standarder (fx C99) hvor størrelsen kan bestemmes ved run-time, men stadig ligger i stack- eller heap-lokation afhængig på implementering.
• Dynamiske/resizable arrays: Abstraktioner som automatisk vokser (fx std::vector i C++, ArrayList i Java, Python lists). De håndterer intern genallokering og kopiering efter behov.

Arrays i C — eksempler og bemærkninger

I C er arrays meget grundlæggende og tæt på hukommelsen. Nogle vigtige punkter:

• En deklaration som int a[10]; allokerer plads til 10 heltal (typen bestemmer størrelsen af hvert element).
• Ved passering til funktioner "falder" et array typisk tilbage til en pointer (decays to pointer), så funktioner ikke automatisk kender arrayets længde.
• C gør normalt ikke bounds-checking — adgang uden for grænserne fører til undefined behavior.
• Til dynamisk allokering bruges malloc/free eller calloc/realloc.

// Statisk array int a[10];  // Dynamisk array int *b = malloc(10 * sizeof(int)); if (b == NULL) { /* fejlbehandling */ } /* brug b[0] ... b[9] */ free(b); 

Fordele og ulemper

• Fordele: Hurtig direkte adgang, lav overhead, forudsigelig hukommelseslayout.
• Ulemper: Fast størrelse (i mange implementationer), dyrt at indsætte/slette midt i arrayet, potentielt manglende bounds-checking i lavniveau-sprog.

Alternativer

• Dynamiske arrays / Vektorer: Tilbyder resizable-opførsel, gemmer typisk elementer i en intern array der ganges op med en faktor når den fyldes.
• Linkede lister: God til hyppige indsættelser/sletninger midt i strukturen, men langsommere tilfældig adgang (O(n)).
• Associative arrays / Hash-kort: Når nøgle-baseret adgang er nødvendig i stedet for indeks-baseret adgang.

Praktiske råd

• Kend dit sprogs regler om indeksering og bounds-checking.
• Vælg arrays når du har brug for hurtig, forudsigelig adgang og kender (eller kan estimere) antallet af elementer.
• Brug dynamiske/resizeable strukturer hvis antallet af elementer varierer meget.
• Husk at frigive hukommelse ved manuel allokering (fx i C).

Spørgsmål og svar

Spørgsmål: Hvad er et array i programmeringssprog?

Spørgsmål: Hvilken type elementer kan gemmes i et array?

Spørgsmål: Hvad er et indeks i et array?

Spørgsmål: Hvordan bestemmes indekset for det første element i et array?

Spørgsmål: Hvad skal en programmør sørge for, når han opretter et array?

Spørgsmål: Hvorfor kan størrelsen af et array ikke ændres?

Spørgsmål: Hvad skal en programmør gøre, hvis han ønsker at gemme flere elementer, end arrayets størrelse tillader?

Søg efter bogstav