Kurt Nørmark ©
Institut for Datalogi, Aalborg Universitet

Sammendrag Forrige lektion Næste lektion Stikord Referencer Indhold

I denne lektion studerer vi pointere og arrays. Lad os dog erindre, at vi allerede i sidste lektion kiggede på det basale arraybegreb. Vi gennemgår først pointere. Dernæst ser vi på arrays som pointere. Efter dette kommer vi til arrays af flere dimensioner. Vi slutter af med sondringen mellem statisk og dynamisk lagerallokering.

Program: Motivation for arrays - et stort antal simple variable.

#include <stdio.h> int main(void) { double table0, table1, table2, table3, table4, table5, table6, table7, table8, table9, table10; table0 = 0.0; table1 = 2 * 1.0; table2 = 2 * 2.0; table3 = 2 * 3.0; table4 = 2 * 4.0; table5 = 2 * 5.0; table6 = 2 * 6.0; table7 = 2 * 7.0; table8 = 2 * 8.0; table9 = 2 * 9.0; table10 = 2 * 10.0; printf("%f, %f, %f, %f, %f, %f, %f, %f, %f, %f, %f\n", table0, table1, table2, table3, table4, table5, table6, table7, table8, table9, table10); return 0; }

Program: Introduktion af arrays.

#include <stdio.h> int main(void) { double table[11]; int i; for(i = 0; i < 11; i++) table[i] = (double)(2 * i); for(i = 0; i < 11; i++) printf("%f ", table[i]); printf("\n"); return 0; }

Program: Eksplicit array initialisering - kun i erklæringer.

#include <stdio.h> int main(void) { double table[11] = {0.0, 5.0, 8.0, 9.9, 10.2, 8.5, 99.9, 1.0, -5.2, 7.5, 9.4}; int i; for(i = 0; i < 11; i++) printf("%f ", table[i]); printf("\n"); return 0; }

Arrays Slide Indhold Stikord Referencer Lærebog

Et array er en tabel med effektiv tilgang til elementerne via heltallige indeks numre

Figur. Et array med 11 elementer indiceret fra 0 til 10

Generelle egenskaber af et array Alle elementer er af samme type Index angiver en plads i tabellen Elementerne i et array a tilgås med subscripting notation: a[i] Når et array er skabt har det faste nedre og øvre indeksgrænser Den nedre indeksgrænse er altid 0 i C. Elementerne lagres konsekutivt (umiddelbart efter hinanden). Dermed er det simpelt at beregne hvor et element med et bestemt index er lagret Effektiv tilgang via index

Pointere er uløseligt knyttet til programmering i C

Figur. En illustration af to pointer variable. pvar indeholder en pointer til en integer, som peger på adressen af var. pobj indeholder en anden pointer, der peger på et objekt obj1,som ikke er indeholdt i nogen variabel. Fra obj1 peges der på et andet objekt obj2, som 'cyklisk' peger tilbage på obj1.

Den normale måde at tilgå data er gennem navngivne variable. Pointere udgør en alternativ og fleksibel tilgangsvej til data.

Pointer variable Slide Indhold Stikord Referencer Lærebog

Variable der indeholder pointere til dataobjekter af typen T skal erklæres af typen T *

Program: Erklæring og initialisering af et antal variable, hvoraf nogle er pointer variable.

int i = 5, *ptr_i = &i, j = 7, *ptr_j; char c = 'a', *ptr_c = &c; ptr_j = &j; ptr_i = ptr_j;

Figur. Grafisk illustration af variablene i, j, c og deres tilsvarende pointervariable. Læg mærke til værdien af ptr_i, som er sat til at pege på samme værdi som ptr_j, altså variablen j.

Program: Hele programmet inklusive udskrivning af variablenes værdier.

#include <stdio.h> int main(void) { int i = 5, *ptr_i = &i, j = 7, *ptr_j; char c = 'a', *ptr_c = &c; ptr_j = &j; ptr_i = ptr_j; printf("i=%d, ptr_i=%p, *ptr_i = %i\n", i, ptr_i, *ptr_i); printf("j=%d, ptr_j=%p, *ptr_j = %i\n", j, ptr_j, *ptr_j); printf("c=%c, ptr_c=%p, *ptr_c = %c\n", c, ptr_c, *ptr_c); return 0; }

Program: Output fra programmet.

i=5, ptr_i=ffbef534, *ptr_i = 7 j=7, ptr_j=ffbef534, *ptr_j = 7 c=a, ptr_c=ffbef52f, *ptr_c = a

Addresse og dereferencing operatorerne Slide Indhold Stikord Referencer Lærebog

Udtrykket &var beregnes til adressen af variablen var. Udtrykket *ptrValue beregner den værdi, som ptrValue peger på. Operatorerne * og & er unære prefix operatorer med høj prioritet

Henvisning C Operator tabellen

Program: Fremhævelse af adresse og dereferencing udtryk programmet fra forrige side.

int i = 5, *ptr_i = &i, j = 7, *ptr_j; char c = 'a', *ptr_c = &c; ptr_j = &j; ptr_i = ptr_j; printf("i=%d, ptr_i=%p, *ptr_i = %i\n", i, ptr_i, *ptr_i); printf("j=%d, ptr_j=%p, *ptr_j = %i\n", j, ptr_j, *ptr_j); printf("c=%c, ptr_c=%p, *ptr_c = %c\n", c, ptr_c, *ptr_c);

Oparatoren * kaldes også for indirection operatoren For alle variable v gælder at udtrykket *&v er ækvivalent med udtrykket v

Henvisning Pointer Begrebet

CBD side 268 Slide Indhold Stikord Referencer

Program: The variables i, j, p, q, r, and x.

int i = 3, j = 5, *p = &i, *q = &j, *r; double x

Tabel.

Expression Equivalent Expression Value p == &i p == (& i) 1 p = i + 7 p = (i + 7) illegal * * & p * (* (& p)) 3 r = & x r = (& x) illegal 7 * * p / * q + 7 ((7 * (* p)) / (* q)) + 7 11 * (r = & j) *= * p (* (r = (& j))) *= (* p) 15

Henvisning C Operator tabellen

Pointerbegrebet i C Slide Indhold Stikord Referencer Lærebog

Begrebet pointer: En pointer er en værdi som betegner en adresse på et lagret dataobjekt

Værdier af variable kan tilgås via pointere til variablenes indhold Adresseoperatoren & giver os adressen på variablen - hvilket er en pointer til indholdet i variablen Pointere til andre pladser i lageret returneres af de primitiver, der allokerer lager dynamisk calloc og malloc Vi visualiserer ofte en pointer som en pil, som udpeger på en værdi Angivelse af lageradresser ville udgøre en mere maskinnær visualisering Pointere har typer, alt efter hvilke typer af værdier de peger på Pointere til integers, pointere til chars, ... Pointer til void er en generisk pointer type i C Pointere, som ikke peger på noget dataobjekt, skal have værdien NULL

Pointer typer Slide Indhold Stikord Referencer

Vi illustrerer på denne side typecheck af pointer variable

Program: Illustration af pointervariable af forskellige typer - giver compileringsfejl.

#include <stdio.h> int main(void) { int *i, j = 1; char *c, h = 'a'; double *d, e = 2.0; void *f; i = &e; /* error: i cannot point to e */ c = &h; d = &j; /* error: d cannot point to j */ f = &j; /* OK. Generic pointer */ printf("%d, %c, %f, %d\n", *i, *c, *d, *(int *)f); }

Program: Samme program - kan oversættes og køres.

#include <stdio.h> int main(void) { int *i, j = 1; char *c, h = 'a'; double *d, e = 2.0; void *f; i = &j; /* OK */ c = &h; d = &e; /* OK */ f = &j; /* OK. Generic pointer */ printf("%d, %c, %f, %d\n", *i, *c, *d, *(int *)f); }

Ved brug af pointere kan vi realisere call by reference parametre i C

Program: Et forsøg på ombytning af to variables værdi uden pointere - virker ikke.

#include <stdio.h> void swap(int p, int q){ int tmp; tmp = p; p = q; q = tmp; } int main(void) { int a = 3, b = 7; printf("%d %d\n", a, b); /* 3 7 is printed */ swap(a, b); printf("%d %d\n", a, b); /* 3 7 is printed */ return 0; }

Program: En funktion der ombytter værdierne af to int variable.

void swap(int *p, int *q){ int tmp; tmp = *p; *p = *q; *q = tmp; }

Program: Funktionen swap og et hovedprogram, som kalder swap på to variable.

#include <stdio.h> void swap(int *p, int *q){ int tmp; tmp = *p; *p = *q; *q = tmp; } int main(void) { int a = 3, b = 7; printf("%d %d\n", a, b); /* 3 7 is printed */ swap(&a, &b); printf("%d %d\n", a, b); /* 7 3 is printed */ return 0; }

Program: Output fra programmet.

3 7 7 3

Call by reference parametre opnås når pointere overføres som call by value parametre. Vi har allerede mange gange gjort brug af call by reference parametre i scanf.

Et array identificeres i C som en pointer til det første element. Enhver operation der kan udføres med array subscripting kan også udføres med pointere.

Figur. Et array med fem elementer og en pointer til første element

Program: Illustration af pointertilgang til arrays.

double table[5] = {1.0, 2.0, 3.0, 4.0, 5.0}; double *ptr_table; ptr_table = &table[0];

Billedserie: Forskellige opdateringer af table ved brug af pointere

Forskellige opdateringer af table ved brug af pointere

Billed nr. 1. ptr_table peger på elementet med index 0 i table

 

Billed nr. 2. *ptr_table refererer til indholdet i table[0]. Denne celles indehold ændres til 7.0.

 

Billed nr. 3. ptr_table flyttes én plads til højre. Indholdet af denne celle bliver indholdet af cellen table[0] * 5.

 

Billed nr. 4. ptr_table flyttes tre positioner længere til højre. Indholdet af den pågældende celle tælles én op.

 

Billed nr. 5. Indekset af den sidste celle (4) og indexet af table[0] (0) trækkes fra hinanden og tallet skrives ud.

 

Program: Et komplet C program, som illustrerer opdateringerne af table.

#include <stdio.h> int main(void) { int i; double table[5] = {1.0, 2.0, 3.0, 4.0, 5.0}; double *ptr_table; ptr_table = &table[0]; *ptr_table = 7.0; ptr_table = ptr_table + 1; *ptr_table = *(ptr_table-1) * 5; ptr_table += 3; (*ptr_table)++; printf("Distance: %i\n", ptr_table - &table[0]); for(i=0; i<5; i++) printf("%f ", table[i]); printf("\n"); return 0; }

Pointers og arrays (2) Slide Indhold Stikord Referencer Lærebog

Flere elementære eksempler på pointer tilgang til arrays

Program: Illustration af pointertilgang til arrays.

double a[5] = {5.0, 7.0, 9.0, 3.0, 1.0}, *pa = &a[0]; /* Print the elements in a */ for(i = 0; i < 5 ; i++) printf("%f ", a[i]); printf("\n"); /* Modify elements in a via the pointer pa */ *pa = 13.0; pa++; *pa = 19.5;

Program: Hele det ovenstående program.

#include <stdio.h> int main(void) { int i; double a[5] = {5.0, 7.0, 9.0, 3.0, 1.0}, *pa = &a[0]; /* Print the elements in a */ for(i = 0; i < 5 ; i++) printf("%f ", a[i]); printf("\n"); /* Modify elements in a via the pointer pa */ *pa = 13.0; pa++; *pa = 19.5; /* Print the elements in a again */ for(i = 0; i < 5 ; i++) printf("%f ", a[i]); printf("\n"); return 0; }

Program: Output fra programmet.

5.000000 7.000000 9.000000 3.000000 1.000000 13.000000 19.500000 9.000000 3.000000 1.000000

Program: Simpelt program med arrays fra starten af lektionen.

#include <stdio.h> int main(void) { double table[11]; int i; for(i = 0; i < 11; i++) table[i] = (double)(2 * i); for(i = 0; i < 11; i++) printf("%f ", table[i]); printf("\n"); return 0; }

Program: Et program hvor tabellen table tilgås via en pointer. Med rødt og blåt har vi fremhævet de aspekter, som svarer til detaljerne med samme farver i det oprindelige array program: De røde erklæringer af tabellen, og de blå tilgange til array elementerne. Med brunt ser vi et udtryk som udgør betingelsen for afslutningen af forløkkerne. Med lilla ser vi en 'optælling' af pointeren. Denne form for pointeraritmetik diskuterer vi lidt senere i materialet.

#include <stdio.h> #define TABLE_SIZE 11 int main(void) { double table[TABLE_SIZE], *table_ptr = &table[0], *tp; int i; for(tp = table_ptr, i=0; tp < &table[TABLE_SIZE]; tp++, i++) *tp = (double)(2 * i); for(tp = table_ptr; tp < &table[TABLE_SIZE]; tp++) printf("%f\n", *tp); printf("\n"); return 0; }

Program: Output fra programmet.

0.000000 2.000000 4.000000 6.000000 8.000000 10.000000 12.000000 14.000000 16.000000 18.000000 20.000000

Pointers og arrays (3) Slide Indhold Stikord Referencer Lærebog

Program: Illustration af pointertilgang til arrays.

double a[5] = {5.0, 7.0, 9.0, 3.0, 1.0}, *pa = &a[0];

Pointere i forhold til arrays: *(pa + i), *(&a[0] + i) og a[i] har samme værdi, nemlig tabellens i'te element pa, a og &a[0] har samme værdi, nemlig en pointer til det første element i arrayet

Når et array overføres som parameter til en funktion er det reelt en pointer til arrayets første element som overføres Bubble sort programmet på næste side giver flere eksempler på dette.

Eksempel: Bubble sort Slide Indhold Stikord Referencer Lærebog

Boblesortering er en klassisk, men ikke særlig effektiv sorteringsalgoritme

Program: Function bubble som laver 'bubble sort' på arrayet a som har n heltalselementer.

void bubble(int a[] , int n) /* n is the size of a[] */ { int i, j; for (i = 0; i < n - 1; ++i){ for (j = n - 1; j > i; --j) if (a[j-1] > a[j]) swap(&a[j-1], &a[j]); } }

Program: Hele 'bubble sort' programmet - med løbende udskrift af arrayet.

#include <stdio.h> void bubble(int a[], int n); void prn_array(char* s, int a[], int n); void swap(int *p, int *q); int main(void) { int a[] = {7, 3, 66, 3, -5, 22, -77, 2}; int n; n = sizeof(a) / sizeof(int); prn_array("Before", a, n); bubble(a, n); /* bubble sort */ prn_array(" After", a, n); putchar('\n'); return 0; } void bubble(int a[] , int n) /* n is the size of a[] */ { int i, j; for (i = 0; i < n - 1; ++i){ for (j = n - 1; j > i; --j) if (a[j-1] > a[j]) swap(&a[j-1], &a[j]); prn_array("During", a, n); } } void prn_array(char* s , int a[] , int n) { int i; printf("\n%s%s%s", " ", s, " sorting:"); for (i = 0; i < n; ++i) printf("%5d", a[i]); putchar('\n'); } void swap(int *p, int *q) { int tmp; tmp = *p; *p = *q; *q = tmp; }

Billedserie: Illustration af de forskellige faser i boblesorteringen

Illustration af de forskellige faser i boblesorteringen

Billed nr. 1. Det usorterede array

 

Billed nr. 2. Tallet -77 er, som det 'letteste' tal, boblet op foroven gennem en række ombytninger

 

Billed nr. 3. Tallet -5 er, som det 'letteste' resterende tal, boblet op foroven gennem en række ombytninger

 

Billed nr. 4. Tallet 7 er, som det 'letteste' tal, boblet op. Bemærk at de øverste tre tal - de røde - nu er sorteret.

 

Billed nr. 5. Mønstret fortsætter, nu med 3 som bobleren. Nu er de øverste fire tal røde og sorteret.

 

Billed nr. 6. Det næste 3 tal bringes på plads. Bemærk at vi reelt er færdige på dette tidspunkt.

 

Billed nr. 7. Den yderste forløkke fortsætter, men den indre foretager ikke flere ombytninger.

 

Billed nr. 8. Stadig samme situation.

 

Billed nr. 9. Slutbilledet. De røde tal er sorteret, og det sorte tal er større end dem alle.

 

Det er let at set at boblesorteringsprogrammet foretager i størrelsesordenen n2 sammenligninger og ombytninger. De gode sorteringsalgoritmer kan nøjes med i størrelsesordenen n log(n) sammenligninger og ombytninger.

Pointeraritmetik Slide Indhold Stikord Referencer Lærebog

Program: Erklæring af to pointere p og q samt en int i.

T *p, *q; int i;

Følgende former for pointeraritmetik er lovlige i C: Assignment af pointere af samme type: p = q Assignment af pointer til NULL eller 0: p = 0 eller p = NULL Addition og subtraktion af integer til pointer: p + i og p - i Subtraktion af to pointere: p - q Sammenligning af to pointere: p < q Sammenligning af pointere med 0 eller NULL: p == 0, p == NULL, p != NULL eller p > NULL

Program: En funktion som tæller antallet af tegn i en streng.

int my_strlen(char *s){ char *p = s; while (*p != '\0') p++; return p-s; }

Program: Hele programmet.

#include <stdio.h> /* Program from 'The C programming language' by Kernighan and Ritchie. */ #define STR1 "monkey" #define STR2 "programming in C" int my_strlen(char *s){ char *p = s; while (*p != '\0') p++; return p-s; } int main(void) { printf("Length of \"%s\" = %i\n", STR1, my_strlen(STR1)); printf("Length of \"%s\" = %i\n", STR2, my_strlen(STR2)); return 0; }

Index out of bounds Slide Indhold Stikord Referencer Lærebog

For et array a[N] er det programmørens ansvar at sikre, at indexes forbliver i intervallet [0..N-1]

Program: Et eksempel på indicering uden for indeksgrænserne i et array.

double table[5] = {1.1, 2.2, 3.3, 4.4, 5.5}; for(i = 0; i <= 5; i++) /* index out of bounds for i = 5 */ { table[i] += 5.0; printf("Element %i is: %f\n", i, table[i]); }

Program: Hele programmet.

#include <stdio.h> int main(void) { int i; double table[5] = {1.1, 2.2, 3.3, 4.4, 5.5}; for(i = 0; i <= 5; i++) /* index out of bounds for i = 5 */ { table[i] += 5.0; printf("Element %i is: %f\n", i, table[i]); } printf("\n"); return 0; }

Det kørende C program opdager ikke nødvendigvis at indekset løber over den øvre grænse. Programmets opførsel er udefineret i sådanne tilfælde.

Arrays af to dimensioner er et array hvor elementtypen er en anden arraytype

Figur. Illustrationer af et to dimensionelt array. Øverst til venstre illustreres forståelse af de to dimensioner, med to rækker og tre søjler. Vi kunne naturligvis lige så godt have byttet om på rækker og søjler. Nederst til venstre ses en forståelse der understreger at a er et array med to elementer, som begge er arrays af tre elementer. Længst til højre ses den maskinnære forståelse, 'row major' ordningen.

Vi tænker normalt på a som en to-dimensionel tabel med to rækker og tre søjler. Reelt er elementerne lagret lineært og konsekutivt, i row major orden. Elementer som kun afviger med én i det sidste indeks er naboelementer.

Processering af arrays med to dimensioner Slide Indhold Stikord Referencer Lærebog

Det er naturligt at bruge to indlejrede for løkker når man skal processere to dimensionelle arrays Alternativt er det muligt at gennemløbe den samlede tabel lineært, med udgangspunkt i en pointer til det første element.

Program: Erklæring, initialisering og to identiske gennemløb af et to dimensionelt array.

double a[2][3] = {{1.1, 2.2, 3.3}, {4.4, 5.5, 6.6}}; for (i = 0; i < 2; i++) for (j = 0; j < 3; j++) sum1 += a[i][j]; for (k = 0; k < 2 * 3; k++) sum2 += *(&a[0][0] + k);

Program: Det samlede program.

#include <stdio.h> int main(void) { int i, j, k; double sum1 = 0.0, sum2 = 0.0; double a[2][3] = {{1.1, 2.2, 3.3}, {4.4, 5.5, 6.6}}; for (i = 0; i < 2; i++) for (j = 0; j < 3; j++) sum1 += a[i][j]; for (k = 0; k < 2 * 3; k++) sum2 += *(&a[0][0] + k); printf("First method: the sum is: %f\n", sum1); printf("Second method: The sum is: %f\n", sum2); return 0; }

C understøtter arrays af vilkårlig mange dimensioner Tre- og flerdimensionelle arrays er umiddelbare generaliseringer af to dimensionelle arrays

Begrebet statisk lagerallokering: Med statisk lagerallokering afsættes lagerplads implicit når den omkringliggende blok aktiveres. Lagerplads inddrages implicit når blokken forlades.

Program: Illustration af statisk lagerallokering i C.

#include <stdio.h> #define N 500 #define K 10 int main(void) { int i; double tab1[N]; /* allocation of N doubles */ double tab2[N*K]; /* allocation of N*K doubles */ /* do something with tab1 and tab2 */ return 0; }

Statisk lagerallokering er knyttet til erklæringen af variable. Udtryk som indgår i indeksgrænser for et array skal være statiske udtryk

Dynamisk lagerallokering (1) Slide Indhold Stikord Referencer Lærebog

Der er ofte behov for en mere fleksibel og dynamisk form for lagerallokering, hvor det kørende program eksplicit allokerer lager.

Begrebet dynamisk lagerallokering: Med dynamisk lagerallokering afsættes lagerplads eksplicit, når programmet har behov for det.

Program: Et kreativt forsøg på dynamisk allokering - ikke ANSI C.

#include <stdio.h> int main(void) { int n; printf("Enter an integer size:\n"); scanf("%d",&n); { int i; double a[n]; for (i = 1; i < n; i++) a[i] = (double)i; for (i = 1; i < n; i++) printf("%f ", a[i]); printf("\n"); } return 0; }

Program: ANSI C Oversættelse af programmet.

gcc -ansic -pedantic -Wall static-alloc.c

Program: Et program der foretager dynamisk allokering af et array.

#include <stdio.h> #include <stdlib.h> int main(void) { int *a, i, n, sum = 0; printf("\n%s", "An array will be created dynamically.\n\n" "Input an array size n followed by n integers: "); scanf("%d", &n); a = calloc(n, sizeof(int)); /* get space for n ints */ for (i = 0; i < n; ++i) scanf("%d", &a[i]); for (i = 0; i < n; ++i) sum += a[i]; free(a); /* free the space */ printf("\n%s%7d\n%s%7d\n\n", " Number of elements:", n, "Sum of the elements:", sum); return 0; }

Program: Et program der dynamisk allokerer et to-dimensionelt array.

#include <stdio.h> #include <stdlib.h> #define N 2 #define M 3 int main(void) { int *pint, i, j; pint = malloc(N*M*sizeof(int)); for (i=0; i<N; i++) for (j=0; j<M; j++) *(pint + M*i + j) = (i+1) * (j+1); for (i = 0; i < M * N; i++){ printf("%4i ", *(pint + i)); if ((i+1) % M == 0) printf("\n"); } return 0; }

Henvisning Det to-dimensionelle array

Dynamisk lagerallokering (2) Slide Indhold Stikord Referencer Lærebog

Dynamisk lagerallokering Eksplicit allokering med calloc eller malloc fra fra stdlib.h calloc(n, m): Allokerer et nulstillet array med n elementer på hver m bytes. malloc(n): Allokerer n bytes, som ikke nulstilles. Eksplicit deallokering med funktionen free Risiko for dangling references Hvis en pointer til et dynamisk allokeret objekt følges efter at objektet er deallokeret med free

I mange moderne sprog styres lager deallokering af en garbage collector, som frigiver lagerplads, når det ikke længere kan tilgås af programmet.

Kapitel 6: Pointers og Arrays
Kursets hjemmeside     Forfatteren's hjemmeside     Om frembringelsen af disse sider     Forrige lektion (top)     Næste lektion (top)     Forrige lektion (bund)     Næste lektion (bund)     
Genereret: 7. Juli 2010, 15:11:35