Der er et tæt samspil mellem pointere og arrays i C. Dette er et udpræget kendetegn ved C. Samspillet gælder ikke generelt for andre programmeringssprog.

24.1 Pointers og arrays (1) 24.4 Eksempel: Bubble sort 24.2 Pointers og arrays (2) 24.5 Pointeraritmetik 24.3 Pointers og arrays (3) 24.6 Index out of bounds

 

24.1.  Pointers og arrays (1)
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

I figur 24.1 illustrerer vi at table identificeres af en pointer til det første element i arrayet. For at illustrere dette klart har vi her lavet en ekstra variabel, ptr_table. Denne variabel er ikke nødvendigt idet udtrykket &table[0], giver os den ønskede pointer. Husk her, at udtrykket &table[0] skal læses som adressen på plads 0 i table.

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

Hvis du skifter til 'slide view' af materiale (eller hvis du blot følger dette link) kommer du til en trinvis udvikling af figur 24.1. Følg de enkelte trin, og vær sikker på du forstår pointerens bevægelse hen over tabellen. I program 24.1 viser vi programmet for de trin, som gennemføres på figur 24.1 i den trinvise udvikling.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#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;
}

24.2.  Pointers og arrays (2)
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Vi vil her se flere eksempler på elementær pointertilgang til elementer i et array.

I program 24.2 herunder har vi et array med fem reelle tal (doubles). I den blå del etablerer vi en pointer til det første element i arrayet. I den røde del bruger vi denne pointer til at ændre de første to elementer i tabellen. Udskriften i program 24.3 afslører de ændringer vi har lavet via pointeren pa.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#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;
}

1
2

5.000000 7.000000 9.000000 3.000000 1.000000 
13.000000 19.500000 9.000000 3.000000 1.000000

I vores motivation for arrays så vi på et simpelt program, som erklærer, initialiser og udskriver et array. Det var program 21.2. Herunder, i program 24.4 viser vi en alternativ version af program 21.2 som bruger pointere til gennemløb (initialisering og udskrivning) af elementerne. Outputtet af programmmet vises i program 24.5.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#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;
}

1
2
3
4
5
6
7
8
9
10
11

0.000000
2.000000
4.000000
6.000000
8.000000
10.000000
12.000000
14.000000
16.000000
18.000000
20.000000

24.3.  Pointers og arrays (3)
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Inden vi ser på et 'rigtigt eksempel', bubblesort i afsnit 24.4, vil vi her fastslå en ækvivalens mellem array indeks notation og pointer (aritmetik) notation. Vi vender tilbage til pointeraritmetik i afsnit 24.5.

Lad ligesom i program 24.2 a være et array, og lad pa være en ekstra pointer variabel som peger på det første element i a:

*(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

24.4.  Eksempel: Bubble sort
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Foreløbig slut med de helt små kunstige eksempler. Vi ser her på et program der kan sortere et array af heltal. Vi bruger bubblesort algoritmen, som er én af de forholdsvis velkendte sorteringsalgoritmer.

Kernen i sorteringsalgoritmen vises herunder. j løber fra bagenden af vores array tilbage til i. i bliver gradvis større i takt med at den ydre forløkke gør fremskridt. Billedlig talt bobler de lette elementer (de mindste elementer) op mod forenden af tabellen.

1
2
3
4
5
6
7
8
9
10

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]);
   }
}

Herunder, i program 24.7 ser vi et komplet program, hvori bubble funktionen fra program 24.6 er indsat næsten direkte. (Den brune del, kaldet af prn_array, er dog tilføjet).

I main ser vi med blåt et udtryk der måler størrelsen (antallet af elementer) i tabellen a. Læg godt mærke til hvordan dette sker. sizeof er en operator, som giver størrelsen af en variabel eller størrelsen af en type. Størrelsen lægges over i variablen n.

Med rødt viser vi kaldet af bubble på a og n. Tabellen a overføres som en reference til arrayet. Dette er fordi a i bund og grund blot er en pointer til tabellen, som omtalt i afsnit 24.1.

Forneden i program 24.7 ser vi funktionen swap, som vi udviklede i afsnit 23.1. swap laver de primitive skridt i sorteringsarbejdet, nemlig naboombytningerne i boble processen.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#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;
}

På den slide, som er tilknyttet dette afsnit, har vi illustreret de enkelte skridt i boblesorteringen. Du kan også se disse skridt her.

24.5.  Pointeraritmetik
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Vi skal her se, at man kan bruge de aritmetiske operatorer i udtryk hvor der indgår pointere.

1
2

T *p, *q;
int i;

Variablene p, q og i vist herover sætter scenen for punkterne herefter.

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

Når vi i f.eks. p + i adderer et heltal til en pointer bliver pointeren optalt i logisk enheder, ikke i bytes. Med andre ord er C smart nok til at addere et passende antal bytes til p, som svarer til størrelsen af typen T* i erklæringerne i program 24.8.

Vi viser et praktisk eksempel på pointeraritmetik i et program vi har lånt fra bogen 'The C Programming Language'. I funktionen my_strlen benytter det røde og det blå udtryk pointeraritmetik. Funktionen beregner antallet af tegn i en C tekststreng. Vi har ikke endnu diskuteret tekststrenge. Det vi ske i kapitel 27.

1
2
3
4
5
6
7
8

int my_strlen(char *s){
  char *p = s;

  while (*p != '\0')
    p++;

  return p-s;
}

I program 24.10 viser vi funktionen i konteksten af et komplet C program.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#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;
}

24.6.  Index out of bounds
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Når man programmerer med arrays er der altid fare for at man kan adressere uden for arraygrænserne. I de fleste sprog vil man få en fejlbesked fra det kørende program, hvis dette sker. I C skal man ikke regne med at få en sådan advarsel. Typisk vil man blot tilgå (læse eller skrive) data uden for arrayet. Dette kan have alvorlige konsekvenser.

Vi ser nedenfor på et typisk eksempel, hvor lidt uforsigtighed i en forløkke (det røde sted) betyder at vi adresserer a[5]. Husk på, at det kun giver mening at referere a[0], ..., a[4].

1
2
3
4
5
6
7

  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]);
  }

Når man kører programmmet kan der ske lidt af hvert. Typisk vil man få fat i et bitmønster i a[5] (otte bytes), som fortolkes som et double. Dette kan give 'sjove' resultater.