3.1.1. En struct

Sammensatte datatyper er nyttige, når vi i et program har brug for at samle informationer om et "objekt i den virkelige verden".

struct tomat_t {
   int typenummer;
   char artsnavn[80];
   int goedningsforbrug;
   int pladskrav;
   int temperaturkrav;
   int saesonpris[24];
};

Her har jeg forsøgt at beskrive en tomat, sådan som en handelsgartner ville gøre det. Han ville være interesseret i omkostningerne, som er sammensat af gødningsforbrug, udgifter til vanding og opvarmning, forrentning af drivhuse med videre, alt sammen ganget med varigheden af dyrkningsperioden.

Når man erklærer en struct efter ovenstående mønster, indsættes en oplysning i compilerens symboltabel om typens navn, størrelse samt offset og type på de enkelte elementer.

"tomat_t" kaldes en type tag, og den tjener to formål

• dels kan vi senere erklære flere variable af denne type;

• dels kan vi erklære en pointer til samme type inden i vores struct. Derved kan vi "trække dem som perler på en snor".

Ovenstående tomat_t kan altså fungere som typen på en variabel. Når man definerer en variabel, reserveres der noget hukommelse i det færdige program, en plads til denne variabel.

struct tomat_t sunglow;

Det er ikke alle programmører, som kan lide denne notation. Der er der nogle, som benytter sig af typedef til at danne nye typebetegnelser, på den måde slipper man for hele tiden at skrive ordet struct .

typedef struct tomat_tag {   /* taggen er ikke nødvendig i dette eks. */
    int ident;
    char name[80];
    int spacing;
    /* etc - etc. */
} tomat_type, *tomat_ptr;

tomat_type softball;
tomat_ptr current_tomat;

Det er meget rart, at man kan se på ordet tomat_type, at det ikke er en variabel, men er en type. Ellers må man huske, at et ord foran et andet skal være en typebetegnelse. Til gengæld kan det være sværere for compileren at finde ud af at diagnosticere fejl. I C++ er det altid tilladt at udelade nøgleordene struct og class, undtagen i erklæringen af typen.

tomat_type red_sun;

I parentes bemærket er der danske virksomheder, som har haft enorme ekstraudgifter på at bruge danske betegnelser i programmer, som skulle eksporteres, så det er nok klogt ved alle større projekter at erkende babelstårn problematikken og benytte engelsk, latin eller esperanto.

struct tomat_ty {
   int identifikation;
   char art[80];
   int goedningsforbrug;
   int pladskrav;
   int temperaturkrav;
   int saesonpris[24];
} sungold;

I eksempel Eksempel 3-4 er der både erklæret en type, nemlig tomat_ty, og en variabel, sungold. Bør kun anvendes i ultrakorte programmer (stenografi-orienterede;-).

Her er et eksempel på et andet udvalg af informationer om tomater. Det er tænkt som registrering af tomater, der skal deltage i en udstilling, hvor der uddeles præmier for bedste sort, og hvor måske journalister skal have adgang til billedmateriale.

struct tomat {
   int loebenummer;
   int udstiller_nr;
   char navn[80];
   char beskrivelse[280];
   enum billedtype;
   char fotograf[80];
   enum karakter[MAXK];
};

Man må forestille sig, at udstillingsledelsen har et ekstra kartotek over udstillere, og heri kan de finde navn og adresse ud fra udstiller_nr. Desuden har jeg forestillet mig, at man registrerer tidligere karakterer (bedømmelser) for den pågældende tomat. Der er jo forskellige udstillinger, eller det kunne være, at samme tomat-sort deltog for anden gang.

Som regel er der langt flere oplysninger, end vi er interesseret i, sådan rent programmeringsmæssigt. Det er en disciplin for sig selv at udvælge og vurdere informationernes anvendelighed.

3.1.2. Interface til datatype

Sæt nu, at vi ikke rigtigt vidste, om vores tomat-beskrivelse ville kunne holde i hele programmets levetid. Der er flere måder at håndtere behov for ændringer.

Den mest anvendte metode går ud på at isolere repræsentationen af tomaten fra de dele af programmet, som anvender tomat-informationer. Det siger sig selv, at dette kræver ekstra kode. Det er imidlertid med de nye C compilere muligt at optimere den ekstra kode på samme måde som i C++ - nemlig ved at erklære en funktion for inline.

#include <stdio.h>
#include <stdlib.h>

struct tomat_t {
   int typenummer;
   char artsnavn[80];
   int goedningsforbrug;
   int pladskrav;
   int temperaturkrav;
   int saesonpris[24];
};

struct tomat_t *create_tomat(int ident, char *name,
                             int goedningsforbrug, int pladskrav,
                             int temperaturkrav, int *saesonpris)
{
    struct tomat_t *temp;
    if (!(temp = malloc(sizeof(struct tomat_t)))) {
        fprintf(stderr,"Not enough memory\n");
        exit(255);
    }
    memset(*temp,0,sizeof(struct tomat_t));
    temp->typenummer = ident;
    strncpy(temp->artsnavn,name,79);
    temp->goedningsforbrug = goedningsforbrug;
    temp->pladskrav = pladskrav;
    temp->temperaturkrav = temperaturkrav;
    if (saesonpris)
        memcpy(temp->saesonpris,saesonpris,sizeof(temp->saesonpris));
    return temp;
}

main()
{
    struct tomat_t *tomat;
    int dyrkning_dage;
    tomat = create_tomat(1012, "sungold", 450, 30, 27, NULL);
    dyrkning_dage = beregn_periode("2001-08-29", tomat);
    return 0;
}

Læg især mærke til main funktionen. Der oprettes en pointer til tomat-typen. Denne pointer får noget at pege på ved at kalde create_tomat-funktionen med tilhørende initialiseringsparametre. Vi snyder med pris-tabellen, som skulle være initialiseret med fx. gennemsnitspriser for hver uge.

Hvis man nu ændrer struct tomat_t, sådan at pladskrav ændres fra rækkeafstand til arealforbrug, og hvis der yderligere tilføjes oplysninger om optimale dag/nat-temperaturer for den pågældene plantesort, så skulle vi ændre vores initialiserings-funktion. Men hvis der var gammel kode (fx. den main, som er med i eksemplet) der stadig skulle kunne fungere, så ville det være muligt at skrive initialiseringen sådan, at man stadig kunne bruge denne "gamle" main(). Det skulle blot være muligt at beregne (eller anslå) værdien af pladsforbrug ud fra den gamle type oplysninger.

Der er ikke noget i vejen for, at oplysningen om gødningsforbrug, der her afleveres som gram, i stedet kunne gemmes som kilo i en float-variabel. Et kendt eksempel på en lignende programmeringsmetode er FILE typen, som beskrives i Afsnit 3.3.

Ved at anvende interface operationer i stedet for at tilgå tomat-struct'ens data direkte, bliver det muligt at ændre detailler i tomat-struct'en uden at ændre programkode ret mange steder. Får man behov for at konvertere datatyper eller for at dele repræsentationen af informationer op på en anden måde, så vil man slippe godt afsted med det uden større problemer.

Hvis et nye behov kun består i at have flere data til denne struct, for eksempel af hensyn til nye beregningsprogrammer, så er det ikke så vanskeligt at udvide en struct selv om programkoden tilgår de enkelte felter direkte. Problemer med ændringer bliver først alvorlige, når programmernes størrelse og kompleksitet bevirker, at ingen længere har det fulde overblik over flow. Hvilket forekommer :-((

3.1.3. Tabel, array, liste, sekvens, bunke ...

Med et eksempel fra Donald Knuth kunne vi se på, hvordan man kan repræsentere kort og bunker af kort i et kortspil.

En struct, som illustrerer et enkelt kort, kunne for eksempel se således ud:

/* der benyttes bitfields for at vise denne
 * feature. I stærkt memory kritiske applikationer kan det
 * nogen gange betale sig at anvende bitfields. Kode til
 * manipulation af bitfelterne vil imidlertid gøre koden
 * langsommere og større.
 */

struct kort_t {
    unsigned tag:1;        /* bagsiden op = 1 */
    unsigned farve:2;      /* 0 klør, 1 ruder, 2 hjerter, 3 spar */
    unsigned rang:4;       /* 1 = es, 2 = toer, 13 = konge */
    struct kort_t *next;   /* kort nedenunder */
    char titel[11];        /* forkortet navnebetegnelse */
};

Indholdet af et felt i en struct kan være hvad som helst - dog med den lille begrænsning, at C-oversætteren skal kende alle typerne. Med et berømt citat: "Folk kan få bilen i den farve, de ønsker, bare de ønsker den sort." (Henry Ford om Ford-T).

Der er én undtagelse til den regel, at oversætteren skal kende alle typer. Man kan godt have en pointer til et objekt af ukendt størrelse! Det er meget rart, når man har behov for et felt som struct kort_t *next , der henviser til kortet nedenunder. Mere om det senere.

Vi kan have tal eller tekst i et felt - eller en anden struct, hvis den er erklæret tidligere i programmet.

Tag (engelsk: mærke, udtales "tagg") sat lig med 1 betyder, at kortet vender bagsiden opad, tag == 0 betyder, at det vender forsiden op. Feltet farve er selvfølgelig kortspilsfarve d.v.s. klør, ruder, hjerter eller spar. Ved at benytte 2 bits får vi værdierne 0, 1, 2 og 3 til rådighed.

enum farve_t { kloer, ruder, hjerter, spar };

For at knytte en betydning mellem 0 til 3 og kortspilsfarverne kan vi benytte en enumeration (tælleremse, nummer-system). Reglerne for en sådan ses Eksempel A-3. Klør (kloer) bliver en symbolsk betegnelse for 0, ruder for 1 etc. Man kan godt tildele et symbol i en enumeration en værdi, for eksempel enum farve_t { kloer=1, ruder, hjerter, spar }; Imidlertid har jeg ikke gjort det her. Hvis vi anvender kulør-værdierne 0-3 kan vi have dem i 2 bit, ellers må vi bruge flere. Selv om det ikke er essentielt i dette eksempel at spare på bits, så er det en helt almindelig fremgangsmåde.

struct kort_t {
    unsigned tag:1;        /* bagsiden op = 1 */
    enum farve_t farve:2;  /* variabel af enumeration type */
    unsigned rang:4;       /* 1 = es, 2 = toer, 13 = konge */
    struct kort_t *next;   /* kort nedenunder */
    char titel[11];        /* forkortet navnebetegnelse */
};

Rang henviser til kortets værdi med es som ener, konge som tretten'er. Også her kunne vi benytte en enumeration for at få en forbindelse mellem "konge" og tallet 13.

Feltet struct kort_t *next; er et felt, som kan indeholde adressen på et andet kort, i dette tilfælde kunne det være kortet, som ligger nedenunder. I mange tilfælde kunne man nøjes med at angive afstanden fra en base adresse, et offset . Hvis der ikke er noget kort nedenunder, kan vi give feltet værdien 0 som i denne sammenhæng kaldes NULL.

Adressen på et objekt kaldes også et link eller en pointer (vejviser, pegepind) eller reference til dette objekt. I teksten her benyttes ordet pointer om en adressevariabel, ikke om adressen alene.

Der er en sjov ting i denne struct: Feltet next er af samme type, som den selv er, struct kort_t * .

I C sproget er der 4 oplysninger om en pointer, de findes i oversætterens symboltabel:

• selve pointerens adresse (som for enhver anden variabel),

• dens størrelse (antallet af bits eller bytes, som er nødvendige for at adressere en character variabel),

• størrelsen af det, den peger på; det kaldes også skalering,

• Graden af indirection (om det er en pointer til en pointer til en pointer til ... til en dims, antallet af stjerner i deklarationen af variabelen)

En pointer er en variabel. Størrelsen af en pointer er altid kendt. På en 32 bit maskine er den 32 bit (4 bytes). Det er muligt at afsætte plads til en pointer uden at vide, hvad den peger på. At afsætte plads er det samme som at definere variabelen.

Det siger sig selv, at når man afrefererer pointeren, d.v.s. henter eller kopierer det objekt, som den peger på, så skal objektets størrelse være kendt. Denne størrelse kaldes også en skaleringsfaktor. Når man lægger j til en pointer, bliver j ganget med skaleringsfaktoren og resultatet lagt til pointeren.

Når det er nødvendigt, kan man erklære en pointer til et objekt af ukendt størrelse. Det er faktisk det, som vi gør med feltet next. Mens oversætteren arbejder på opbygningen af struct kort_t, er størrelsen på selvsamme struct ikke kendt endnu. Derfor bliver next-pointeren først endeligt tildelt sin skalerings-faktor (størrelsen af det objekt, den peger på) i det øjeblik, at oversætteren er færdig med struct kort_t.

Når vi anvender next feltet til at fortælle, hvilket kort, der ligger nedenunder, så vil vi kunne repræsentere en lille bunke kort på denne måde:

Nu kan vi erklære et "helt kortspil" som et array med 53 kort, 13 i hver farve plus en joker. Definitionen ser ud som her:

struct kort_t kort[53];    /* husk: fra 0 til og med 52. */

Hvis vi erklærer et "helt kortspil" og initialiserer alle kortenes felter, vil de 4 farvers kort kunne initialiseres på følgende måde (hele kildeteksten i filen kort02.c); vi burde give andre navne til 11,12 og 13, altså knægt, dame og konge:

    for (kuloer = kloer; kuloer <= spar; ++kuloer) {
        for (j = 0; j < 13; ++j) {
            kort[kuloer*13+j].tag = 0;
            kort[kuloer*13+j].farve = kuloer;
            kort[kuloer*13+j].rang = j+1;
            sprintf(kort[kuloer*13+j].knavn,"%s %d", farve(kuloer), j+1);
            kort[kuloer*13+j].next = NULL;
        }
    }

Kortspils-farverne bruges som om de var heltal (det er de jo også) og kan endog bruges til at specificere stop og start i for-løkken, som styrer initialisering. Hvis man kompilerer med C++ compileren, altså g++, så vil den dog klage over operationen ++kuloer, men i øvrigt hjælpe med at tjekke, at vi bruger enumerationen uden at tildele den forkerte værdier (som fx. kuloer = 17). gcc vil end ikke nævne, at vi tildeler en variabel af typen farve_t en værdi, der ligger udenfor grænserne. Det gør vi i den funktion, som returnerer en string variabel for farvens navn.

Det er ikke den eneste måde at gøre tingene på. Det er heller ikke den mest effektive, som er et initialiseret statisk array. For at mindske skrivearbejdet kan man generere det meste af C-koden til initialisering af dette statiske array ved hjælp af et awk-program.

Men programmet her er jo ikke et, som kræver ultimativ optimering, så derfor er det nok bedre at lægge vægt på læsevenligheden.

For at gøre programmet endnu mere læsevenlig kan analogt med de fire farver lave en enumeration for rang og tilhørende betegnelse, hvilket vil gøre det muligt at håndtere det korte navnefelt for es, knægt, dame og konge på en bedre måde. (Prøv at gøre det - det er en god øvelse.)

Den anden ting, som kunne påkalde sig en kommentar er, at vi ikke anvender et multi-dimensionalt array og at vi i øvrigt bare forlænger i den anden ende for at få plads til en joker. Læg mærke til hvor vanskeligt det er at håndtere jokeren i kildeteksten kort02.c! Skal den have en rang? Skal den have en farve, og i så fald hvilken? Skal vi ændre vores farve/rang-system, således at man kan håndtere en ekstra farve for jokeren? Skal man have flere jokere og skelne mellem rød joker og sort joker? I kort02.c lader vi jokeren være af typen kloer (0), og giver den blot en højere rang. Hvis den skal bruges i et kortspil eller en kabale af en slags, så må vi sørge for at programkoden tager højde for, at der kan være et ekstra kort. Det er ikke så væsentligt for eksemplet her, så vi lader den ude af betragtning i de følgende eksempler.

Repræsentationen af vort kortspil i hukommelsen ser nu ud som følgende illustration antyder; vi går ud fra, at størrelsen på en struct kort_t er 20 bytes:

adresse (offset):
0            20          40          60          80
+-----------+-----------+-----------+-----------+-----------+...~
| 0 0 0 NULL| 0 0 1 NULL| 0 0 2 NULL| 0 0 3 NULL| 0 0 4 NULL|
|"kloer 1  "|"kloer 2  "|"kloer 3  "|"kloer 4  "|"kloer 5  "|
+-----------+-----------+-----------+-----------+-----------+...~

... og vores lille bunke fra før kan antydes med følgende skitse:

+------+           +------+           +------+
|next: |           |next: |           |next: |
|NULL  |           | 820  |           | 180  |
|      |           |      |           |      |
|      |           |      |           |      |
|      |           |      |           |      |
|      |           |      |           |      |
|klør  |           |ruder |           |spar  |
|10    |           | 2    |           | 3    |
|      |           |      |           |      |
+------+    ....   +------+    ...    +------+
adresse:
180                280                820 

Ovenstående skitse er imidlertid ikke den mest læselige måde at beskrive forbindelsen mellem de tre kort, så man benytter som regel pile i stedet for som på næste illustration.

+----------------+     +----------------+     +----------------+
| 0 1 1       *--+---->| 0 3 2       *--+---->| 0 0 9       *--+----+
| ruder 2        |     | spar  3        |     | klør 10        |    |
+----------------+     +----------------+     +----------------+    |
                                                                    |
                                                                 ___|___
                                                                  -----
                                                                    ~ 

Her er adresserne på hver struct er ikke vist; de er jo også helt irrelevante.

Den anvendte struktur kaldes en linket liste (eller linked liste). Det betyder simpelt hen en sammenkædet liste.

Når en pointer ikke peger på en adresse, sætter man den pr. konvention til 0 eller NULL, en adresse, som intet normalt program nogensinde vil forsøge at røre ved. Det kan tegnes som en jordforbindelse (således som det er forsøgt på ascii-tegningen ovenfor.)

Vores kortspilsrepræsentation er lavet som et array af kort. Den sidste tegning Eksempel 3-6 viser, at arrayet ikke er essentielt for "bunke" teknikken med en next-pointer for hvert kort.

Man kan sætte hvad som helst sammen efter det princip, at et element peger på det næste. Det er en af de væsentligste programmeringsteknikker, og den har derfor fået mange navne: Linket liste eller bare liste, sekvens, tabel. Man kunne sagtens udelade arrayet og blot have to - tre variable af typen kort_t, som man satte sammen i en liste.

Imidlertid er arrayet en udmærket løsning for et kortspil. Kortene er jo til stede alle sammen hele tiden, med mindre vi skal tage højde for en haj, der har kort i ærmet. Man har mulighed for at håndtere kortene som et array, når man for eksempel vil "blande" dem ved at bruge en random - generator til at plukke kortene ud, et efter et, fra arrayet i tilfældig rækkefølge og sætte dem øverst i bunken. Prøv det som en programmeringsøvelse (eller se eksempel kort04.c).

Hver gang vi vil lave en bunke, skal vi have et startkort. Det vil sige, at man skal have en variabel, som kan huske, hvor vi starter henne. Et minimalt eksempel kan se ud som her:

/* kortspillet forudsættes initialiseret.
 * Hvis kildeteksten anvendes uden en initialiseringsloop som i
 * kort02.c, vil alle k->navn felterne være tomme.
 */


struct kort_t k[53];

struct kort_t *kort_bunke_demo()
{
    struct kort_t *start, *temp;
    temp = start = k;               /* starten af vores bunke 
                                     * er første element i array k.
                                     */
    temp->next = k[1+rand()%52];    /* vi plukker et tilfældigt kort
                                     * værdien af 1+rand()%52 ligger
                                     * mellem minimum 1 og max 52 
                                     */
    temp = temp->next;              /* ændring af temp,
                                     * men start er stadig 
                                     * adressen på det første kort
                                     */
    temp->next = NULL;              /* temp peger på de plukkede kort,
                                     * vi nulstiller next feltet på det
                                     * nye kort */
    return start;                   /* returnerer adressen på det første */
}

void bunke-og-vis()
{
    struct kort_t * kp;             /* her får vi start-kortet */
    int nk = 0;
    kp = kort_bunke_demo();
    do {
        printf("Kort nr. %d er %s\n", nk++, kp->knavn);
    } while ( (kp = kp->next) != NULL);
}

Adressen på dette start - kort gemmes uden for kort-arrayet. (Alternativt kan man bruge dobbelt-linkede lister og finde startpunkter som de kort, der har en NULL-pointer. Derfra kan man følge en anden pointerkæde til man igen havner på en NULL pointer - men alt i alt kræver det meget mere programmering.)

I eksemplet kort04.c, som blander kortene og skriver resultatet ud, anvendes variabelen struct kort_t *oeverst som den, der husker starten af bunken.

    /* uddrag af kort04.c */
    {
        struct kort_t *oeverst;
        bland(kort, MAXK, &oeverst);
        show_kortbunke(bunke);
    }

En anden morsom ting ved denne repræsentation er, at kortene kun kan indgå i én bunke. Meget realistisk!

3.1.4. Operationer på datatypen

Det er forhåbentlig blevet klart, at det kan betale sig at spørge, hvilke informationer, som er væsentlige, og hvilke operationer, som skal kunne udføres på disse informationer. Ud fra dette vælger man metoden til at strukturere sine data.

Datastrukturer som lister, array'er, kø og stak (som vi ikke har set eksempler på endnu) og lignende strukturer har hver især deres fordele.

Med den struktur, som vi har valgt i eksempel kort04.c, kunne vi let "se", hvilket kort, der lå øverst. Hvis vi skal lægge et kort ovenpå, så er det nemt nok. Operationerne til at blande dem og gennemløbe (og udskrive) den blandede bunke går helt fint, og kan pakkes ind i funktioner, som gør programmet let at læse.

Men hvis vi vil lægge kort ind midt i bunken, så er denne repræsentation måske ikke den bedste, men den kan dog bruges: Man kan bladre sig frem til den position, man ønsker at indsætte på.

Hvis man anvender et binært træ, kan man indsætte et element i en ordnet sekvens, uden at det koster meget ekstra tid for algoritmen.

Nu er kort-spils arrayet i forvejen sorteret på grund af måden, det er initialiseret, så vi har ikke brug for en sortering af hele kortspillet som sådan. Hvis vi derimod ønsker at programmere en omgang whist eller bridge, skal der først blandes kort og derefter deles ud til fire bunker (spillere). Man ville sikkert foretrække at udskrive spillernes bunker (hænder) ordnet efter kortenes rang. Dér burde vi overveje at repræsentere bunkerne som 4 binære træer.

Dette afsnit er - sammen med de næste afsnit om konkrete og abstrakte datatyper - under omarbejdelse. Hvis du har nogen spørgsmål eller ønsker at bidrage skal du være velkommen. Jeg regner med at få skrevet en hel del i løbet af perioden 24. juni - 31. juli 2001.