Kapitel 9
Arrays og Pointere

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. Vi ser først på 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.


Introduktion til arrays

Arrays i C - Motivation og Introduktion
Slide Indhold Stikord
Referencer 

Et antal motiverende og introducerende eksempler på erklæring, initialisering og anvendelse af arrays

Program: Motivation for arrays - et stort antal simple variable.
#include <stdio.h>

int main(void) {

  /* Declarations: */
  double table0, table1, table2, table3, table4, 
         table5, table6, table7, table8, table9, table10;

  /* Initializations: */
  table0 =  2 * 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;

  /* Access - printing: */
  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>

#define TABLE_SIZE 11

int main(void) {

  /* Declaration: */
  double table[TABLE_SIZE];
  int i;

  /* Initialization: */
  for(i = 0; i < TABLE_SIZE; i++)
    table[i] = (double)(2 * i);

  /* Access - printing: */
  for(i = 0; i < TABLE_SIZE; i++)
    printf("%f\n", table[i]);

  printf("\n");
  
  return 0;
}

Program: Eksplicit array initialisering - kun i erklæringer.
#include <stdio.h>
#define TABLE_SIZE 11

int main(void) {

  /* Declaration and initialization: */
  double table[TABLE_SIZE] = 
    {0.0, 5.0, 8.0, 9.9, 10.2, 8.5, 99.9, 1.0, -5.2, 7.5, 9.4};
  int i;





  /* Access - printing: */
  for(i = 0; i < TABLE_SIZE; i++)
    printf("%f ", table[i]);

  printf("\n");
  
  return 0;
}

Program: En variant af eksplicit array initialisering.
#include <stdio.h>
#define TABLE_SIZE 11

int main(void) {

  /* Declaration and initialization: */
  double table[] = 
    {0.0, 5.0, 8.0, 9.9, 10.2, 8.5, 99.9, 1.0, -5.2, 7.5, 9.4};
  int i;





  /* Access - printing: */
  for(i = 0; i < TABLE_SIZE; i++)
    printf("%f ", table[i]);

  printf("\n");
  
  return 0;
}

Generelle egenskaber af arrays
Slide Indhold Stikord
Referencer 

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

  • Alle elementer er af samme type - element typen

  • Index typen er altid en heltalstype

  • Indexet angiver en plads i tabellen

  • Elementerne i et array a tilgås med subscripting notation: a[i]

    • Subscripting er en operator 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

  • Når et array er skabt har det faste nedre og øvre indeksgrænser

    • Den nedre indeksgrænse er altid 0 i C.

Henvisning

Arrays i C - begrænsninger
Slide Indhold Stikord
Referencer 

Arrays i C er ikke første klasses data

  • Begrænsninger

    • To arrays kan ikke assignes til hinanden

    • Et array kan ikke overføres som en værdi-parameter

      • Et aktuelt parameter array kopieres ikke i sin helhed til den tilsvarende formelle parameter

      • Der overføres en pointer til det første element

    • Et lokalt array kan ikke umiddelbart returneres fra en funktion

Program: Illustration af at arrays ikke kan assignes til hinanden - compilerer ikke.
#include <stdio.h>
#define TABLE_SIZE 11

int main(void) {
  double a[TABLE_SIZE], b[TABLE_SIZE];
  int i;

  for(i = 0; i < TABLE_SIZE; i++)
    a[i] = 2*i;

  b = a;  /* Compile-time error:                                               */
          /* incompatible types when assigning to 'double[11]' from 'double *' */
  return 0;
}

Program: Illustration af at et array ikke kopieres ved parameteroverførsel - compilerer og kører.
#include <stdio.h>
#define TABLE_SIZE 11

void f (double p[TABLE_SIZE]){
  int i;

  for(i = 0; i < TABLE_SIZE; i++)
    p[i] = p[i] * 2;  // p is NOT a local copy of the actual parameter. 
                      // It is a pointer to the actual parameter array.
}

int main(void) {
  double a[TABLE_SIZE];
  int i;

  for(i = 0; i < TABLE_SIZE; i++)
    a[i] = 2*i;

  for(i = 0; i < TABLE_SIZE; i++)    /* 0 2 4 6 ... */
    printf("Before calling f: a[%d] = %f\n", i, a[i]);

  printf("\n");

  f(a);  // The elements of a are not copied to f.
         // Instead a pointer to the first element in a is passed to f.
         // OK - but maybe not as intended. Compiles and runs.

  for(i = 0; i < TABLE_SIZE; i++)    /* 0 4 8 12 ... */
    printf("After calling f: a[%d] = %f\n", i, a[i]);

  return 0;
}

Program: Program output.
Before calling f: a[0] = 0.000000
Before calling f: a[1] = 2.000000
Before calling f: a[2] = 4.000000
Before calling f: a[3] = 6.000000
Before calling f: a[4] = 8.000000
Before calling f: a[5] = 10.000000
Before calling f: a[6] = 12.000000
Before calling f: a[7] = 14.000000
Before calling f: a[8] = 16.000000
Before calling f: a[9] = 18.000000
Before calling f: a[10] = 20.000000

After calling f: a[0] = 0.000000
After calling f: a[1] = 4.000000
After calling f: a[2] = 8.000000
After calling f: a[3] = 12.000000
After calling f: a[4] = 16.000000
After calling f: a[5] = 20.000000
After calling f: a[6] = 24.000000
After calling f: a[7] = 28.000000
After calling f: a[8] = 32.000000
After calling f: a[9] = 36.000000
After calling f: a[10] = 40.000000

Program: Et array der overføres som input parameter - compilerer ikke.
#include <stdio.h>
#define TABLE_SIZE 11

void f (const double p[TABLE_SIZE]){
  int i;

  for(i = 0; i < TABLE_SIZE; i++)
    p[i] = p[i] * 2;  // Compile time error: 
                      // Assignment of read only location

}

int main(void) {

  double a[TABLE_SIZE];
  int i;

  for(i = 0; i < TABLE_SIZE; i++)
    a[i] = 2*i;

  for(i = 0; i < TABLE_SIZE; i++)
    printf("Before calling f: a[%d] = %f\n", i, a[i]);

  printf("\n");

  f(a);  // The array a is passed as a pointer.

  for(i = 0; i < TABLE_SIZE; i++)
    printf("After calling f: a[%d] = %f\n", i, a[i]);

  return 0;
}

Program: Illustration af at arrays ikke umiddelbart kan returneres fra en funktion - compiler warnings.
#include <stdio.h>
#define TABLE_SIZE 11

double* f (int n){
  double a[TABLE_SIZE];   // A local array.
  int i;

  // Initializing all elements of a to n:
  for(i = 0; i < TABLE_SIZE; i++)  
    a[i] = (double)n;

  return a;       // Returning local array.
                  // Compiler Warning:
                  // Returns address of a local variable.
}

int main(void) {
  int i;
  double *c;

  c = f(3);       

  // c now refer to a de-allocated array
  // returned from f.

  // Printing elements of returned array.
  // Hoping that all elements are 3:
  for(i = 0; i < TABLE_SIZE; i++)
    printf("After calling f: c[%d] = %f\n", i, c[i]);

  return 0;
}

Program: Program output.
After calling f: c[0] = 3.000000
After calling f: c[1] = 0.000000
After calling f: c[2] = 0.000000
After calling f: c[3] = 0.000000
After calling f: c[4] = 0.000000
After calling f: c[5] = 3.000000
After calling f: c[6] = 8947928554782001198551418340977640912557521000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.000000
After calling f: c[7] = 0.000000
After calling f: c[8] = 4131750093777943436617066662265546422010637000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.000000
After calling f: c[9] = 4918305738180689085091037303284256682706747000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.000000
After calling f: c[10] = 0.000000

Program: Illustration af at arrays kan returneres fra en funktion - med et lille trick - compilerer og kører korrekt.
#include <stdio.h>
#define TABLE_SIZE 11

double* f (int n){
  static double a[TABLE_SIZE];   // A local array, storage class static.
  int i;

  // Initializing all elements of a to n:
  for(i = 0; i < TABLE_SIZE; i++)
    a[i] = (double)n;

  return a;       // Returning local array.
                  // No compiler warning any more.
}

int main(void) {
  int i;
  double *c;

  c = f(3);       // c now refer to array returned from f

  for(i = 0; i < TABLE_SIZE; i++)
    printf("After calling f: c[%d] = %f\n", i, c[i]);

  return 0;
}

Program: Program output.
After calling f: c[0] = 3.000000
After calling f: c[1] = 3.000000
After calling f: c[2] = 3.000000
After calling f: c[3] = 3.000000
After calling f: c[4] = 3.000000
After calling f: c[5] = 3.000000
After calling f: c[6] = 3.000000
After calling f: c[7] = 3.000000
After calling f: c[8] = 3.000000
After calling f: c[9] = 3.000000
After calling f: c[10] = 3.000000


Mere om Pointers

Pointer variable
Slide Indhold Stikord
Referencer 

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

Pointere som ikke peger på noget dataobjekt skal have værdien NULL

Program: Erklæring og initialisering af et antal variable, hvoraf nogle er pointer variable.
  int i = 5, *ptr_i = &i, j = 7, *ptr_j = NULL;
  char c = 'a', *ptr_c = &c;

Figur. Situationen før de to assignments

Program: Erklæring og initialisering af et antal variable, hvoraf nogle er pointer variable.
  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>
#include <stddef.h>

int main(void) {
  int i = 5, *ptr_i = &i, j = 7, *ptr_j = NULL;
  char c = 'a', *ptr_c = &c;

  ptr_j = &j;
  ptr_i = ptr_j;

  printf("i=%d, ptr_i=%p, *ptr_i = %d\n", i, ptr_i,  *ptr_i); 
  printf("j=%d, ptr_j=%p, *ptr_j = %d\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=0x28cd1c, *ptr_i = 7
j=7, ptr_j=0x28cd1c, *ptr_j = 7
c=a, ptr_c=0x28cd1b, *ptr_c = a

Addresse og dereferencing operatorerne
Slide Indhold Stikord
Referencer 

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

Program: Fremhævelse af adresse og dereferencing udtryk programmet fra forrige side.
  int i = 5, *ptr_i = &i, j = 7, *ptr_j = NULL;
  char c = 'a', *ptr_c = &c;

  ptr_j = &j;
  ptr_i = ptr_j;

  printf("i=%d, ptr_i=%p, *ptr_i = %d\n", i, ptr_i,  *ptr_i); 
  printf("j=%d, ptr_j=%p, *ptr_j = %d\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

Pointer eksempler - en opgave
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.
ExpressionEquivalent Expression
p == &ip == (& i)
p = i + 7p = (i + 7)
* * & p* (* (& p))
r = & xr = (& x)
7 * * p / * q + 7((7 * (* p)) / (* q)) + 7
* (r = & j) *= * p(* (r = (& j))) *= (* p)
 

Henvisning

Opgave 9.2. En pointer øvelse

På den tilknyttede slide finder du nogle erklæringer af double og int variable, herunder pointere til sådanne.

Du finder også en tabel med udtryk, både med og uden parenteser som afklarer operator-prioriteringerne.

Beregn værdierne af alle de udtryk, som giver mening.

Check dine resultater ved at indføre udtrykkene i et lille C program.

Pointer typer i C og generiske pointere
Slide Indhold Stikord
Referencer 

Pointere til forskellige typer er usammenlignelige

Generiske pointere af typen void * kan pege på data af vilkårlige typer

Program: Illustration af pointervariable af forskellige typer - giver compileringsfejl.
#include <stdio.h>
#include <stddef.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 a double */
  c = &h;  /* OK                                */
  d = &j;  /* Error: d cannot point to an int   */
  f = &j;  /* OK. f is a generic pointer        */

  printf("%d, %c, %f, %d\n", *i, 
                             *c,
                             *d,
                             *f   /* Error: dereferencing */ 
        );                        /*      pointer to void */
}

Program: Et lignende program - kan oversættes og køres.
#include <stdio.h>
#include <stddef.h>

int main(void){

  int    *i,    j = 1;
  char   *c,    h = 'a';
  double *d,    e = 2.0;
  void   *f;

  i = &j;  /* OK. i is an int pointer           */
  c = &h;  /* OK. c is a char pointer           */
  d = &e;  /* OK. d is a double pointer         */
  f = &j;  /* OK. f is a generic pointer        */

  printf("%d, %c, %f, %d\n", *i, 
                             *c,
                             *d, 
                             *(int *)f);
}

Program: Program output.
1, a, 2.000000, 1

  • Den generiske pointer type i C:   void *

    • Der kan castes til og fra den generiske pointer type

    • Man kan ikke følge en generisk pointer ved brug af dereferencing operatoren.

    • Der kan ikke udføres pointer aritmetik på generiske pointere

Henvisning


Call by reference parametre

Call by reference parametre
Slide Indhold Stikord
Referencer 

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: Program output.
3  7
3  7

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;           /* We want to exchange the values of a and b */

  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: Program output.
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.


Pointers og arrays

Pointers og arrays (1)
Slide Indhold Stikord
Referencer 

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

Program: Program output.
Distance: 4
7.000000 35.000000 3.000000 4.000000 6.000000 

Pointers og arrays (2)
Slide Indhold Stikord
Referencer 

Vi omskriver det introducerende og motiverende eksempel til en variant med pointere

Program: Et simpelt program med arrays - fra starten af lektionen - med subscripting.
#include <stdio.h>

#define TABLE_SIZE 11

int main(void) {

  /* Declaration: */
  double table[TABLE_SIZE];
  int i;

  /* Initialization: */
  for(i = 0; i < TABLE_SIZE; i++)
    table[i] = (double)(2 * i);

  /* Access - printing: */
  for(i = 0; i < TABLE_SIZE; i++)
    printf("%f\n", table[i]);

  printf("\n");
  
  return 0;
}

Program: Et tilsvarende program - med pointer tilgang til elementerne.
#include <stdio.h>

#define TABLE_SIZE 11

int main(void) {

  /* Declarations: */
  double table[TABLE_SIZE], *tp;


  /* Initialization: */
  for(tp = table; tp < table + TABLE_SIZE; tp++)
    *tp = (double)(2 * (tp - table));

  /* Access - printing: */
  for(tp = table; tp < table + TABLE_SIZE; tp++)
    printf("%f\n",  *tp);

  printf("\n");
  
  return 0;
}

Program: Output fra programmerne.
0.000000
2.000000
4.000000
6.000000
8.000000
10.000000
12.000000
14.000000
16.000000
18.000000
20.000000

Henvisning

Pointers og arrays (3)
Slide Indhold Stikord
Referencer 

Forskellige ækvivalente udtryksformer omkring arrays

Program: Illustration af pointertilgang til arrays.
  double a[5] = {5.0, 7.0, 9.0, 3.0, 1.0};
  double *pa = &a[0]; 

  • a[i] kan også skrives som

    • *(pa + i)

    • *(a + i)

    • *(&a[0] + i)

  • a kan også skrives som

    • pa

    • &a[0]

Program: Illustration af de ækvivalente array udtryksformer - både i L-værdier og R-værdier.
#include <stdio.h>

int main(void) {

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

  pa[0]        = 12.0;
  *(pa + 1)    = 13.0;
  *(a + 2)     = 14.0;
  *(&a[0] + 3) = 15.0;

  printf("pa[0] = %f\n",         pa[0]);
  printf("*(pa + 1) = %f\n",     *(pa + 1));
  printf("*(a + 2) = %f\n",      *(a + 2));
  printf("*(&a[0] + 3) = %f\n",  *(&a[0] + 3));

  return 0;
}

Program: Output fra programmerne.
pa[0] = 12.000000
*(pa + 1) = 13.000000
*(a + 2) = 14.000000
*(&a[0] + 3) = 15.000000

Pointer aritmetik
Slide Indhold Stikord
Referencer 

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

  • Følgende er lovligt i C - herunder lovlig pointeraritmetik:

    • Assignment af pointere af samme type: p = q

    • Assignment af pointer til NULL eller 0: p = 0 eller p = NULL

    • Addition og subtraktion af en integer i til en pointer p: 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 "Imperative Programming"

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

Program: Output fra programmet.
Length of "monkey" = 6
Length of "Imperative Programming" = 22

Index out of bounds
Slide Indhold Stikord
Referencer 

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 when i is 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 when i is 5 */
    table[i] += 5.0;
    printf("Element %i is: %f\n", i, table[i]);
  }  

  printf("\n");
  
  return 0;
}

Program: Muligt program output.
Element 0 is: 6.100000
Element 1 is: 7.200000
Element 2 is: 8.300000
Element 3 is: 9.400000
Element 4 is: 10.500000
Segmentation fault (core dumped)

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.

Eksempel: Bubble sort
Slide Indhold Stikord
Referencer 

Bubble sort er en klassisk, men ikke særlig effektiv sorteringsalgoritme

Program: Function bubble_sort 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])          /* Comparison           */
          swap(&a[j-1], &a[j]);    /* Exchange             */
   }
}   

Program: Hele 'bubble sort' programmet - med løbende udskrift af arrayet.
#include <stdio.h>

void   bubble_sort(int a[], int n);
void   prn_array(char* s, const 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);         /* Notice how the size of a is found */
  prn_array("Before", a, n);
  bubble_sort(a, n);                   
  prn_array(" After", a, n);
  putchar('\n');
  return 0;
}

void bubble_sort(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 , const int a[] , int n){
   int   i;

   printf("\n    %s sorting:", s);
   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;
}

Program: Output fra bubble sort programmet.
    Before sorting:    7    3   66    3   -5   22  -77    2

    During sorting:  -77    7    3   66    3   -5   22    2

    During sorting:  -77   -5    7    3   66    3    2   22

    During sorting:  -77   -5    2    7    3   66    3   22

    During sorting:  -77   -5    2    3    7    3   66   22

    During sorting:  -77   -5    2    3    3    7   22   66

    During sorting:  -77   -5    2    3    3    7   22   66

    During sorting:  -77   -5    2    3    3    7   22   66

     After sorting:  -77   -5    2    3    3    7   22   66

Billedserie: Illustration af de forskellige faser i boblesorteringenIllustration 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.

Brug af qsort fra standard biblioteket
Slide Indhold Stikord
Referencer 

Normalt anvender vi en eksisterende og effektiv sorteringsfunktion fra standard bibliotektet frem for en ineffektiv sorteringsfunktion, vi selv har skrevet

qsort fra stdlib.h

Program: Anvendelse af qsort til sortering af et heltals array.
#include <stdio.h>
#include <stdlib.h>

void   prn_array(char* s, const int a[], int n);
int element_compare(const void *ip1, const void *ip2);

int main(void){
  int   a[] = {7, 3, 66, 3, -5, 22, -77, 2};
  int   n;

  n = sizeof(a) / sizeof(int);    /* Notice how the size of a is found */
  prn_array("Before", a, n);
  
  qsort(a, n, sizeof(int), element_compare);

  prn_array(" After", a, n);
  putchar('\n');
  return 0;
}

int element_compare(const void *ip1, const void *ip2){
  int result;
  int *ipi1 = (int *)ip1,         /* Cast parameters to pointers to int */
      *ipi2 = (int *) ip2;

  if (*ipi1 < *ipi2)
     result = -1;
  else if (*ipi1 > *ipi2)
     result = 1;
  else
     result = 0;

  return result;
}

void prn_array(char* s , const int a[] , int n){
   int   i;

   printf("\n    %s sorting:", s);
   for (i = 0; i < n; ++i)
      printf("%5d", a[i]);
   putchar('\n');
}

Program: En variant af anvendelse af qsort - med int_compare funktion.
#include <stdio.h>
#include <stdlib.h>

void   prn_array(char* s, const int a[], int n);
int int_compare(const int i1, const int i2);
int element_compare(const void *ip1, const void *ip2);

int main(void){
  int   a[] = {7, 3, 66, 3, -5, 22, -77, 2};
  int   n;

  n = sizeof(a) / sizeof(int);    /* Notice how the size of a is found */
  prn_array("Before", a, n);
  
  qsort(a, n, sizeof(int), element_compare);

  prn_array(" After", a, n);
  putchar('\n');
  return 0;
}

int element_compare(const void *ip1, const void *ip2){
  int result;
  int *ipi1 = (int *)ip1,         /* Cast parameters to pointers to int */
      *ipi2 = (int *) ip2;

  return int_compare(*ipi1, *ipi2);
}

int int_compare(const int i1, const int i2){
  if (i1 < i2)
    return -1;
  else if (i1 > i2)
    return 1;
  else 
    return 0;
}


void prn_array(char* s , const int a[] , int n){
   int   i;

   printf("\n    %s sorting:", s);
   for (i = 0; i < n; ++i)
      printf("%5d", a[i]);
   putchar('\n');
}

Program: Output af programmerne.
    Before sorting:    7    3   66    3   -5   22  -77    2

     After sorting:  -77   -5    2    3    3    7   22   66

  • qsort afhænger af en funktion - overført som en function pointer - der sammenligner to array elementer

  • element_compare(const void *ep1, const void *ep2)

  • element_compare(e1, e2)

    • negativ: e1 anses for at være mindre end e2

    • nul: e1 anses for at være lig med e2

    • positiv: e1 anses for at være større end e2

Array input og output parametre
Slide Indhold Stikord
Referencer 

Anbefalede teknikker til overførsel af array parametre til funktioner

  • Et array overføres som rent input til en funktion

    • Marker den formelle parameter med en const modifier

    • Pladser i et sådant arrays kan ikke ændres

  • Et array tilbageføres som rent output fra en funktion

    • Overfør arrayet som en pointer

  • Et array overføres som både input og output til/fra en funktion

    • Samme tilfælde som rent output

    • Illustreret ved bubble_sort

Et godt og simpelt eksempel kan ses på side 415 i lærebogen, 8'th ed

Opgave 9.3. Polynomier

I denne opgave vil vi repræsentere et polynomium p af grad n som et array af koeficienter a0, ..., an, hver af typen double,

   p(x) = a0 + a1 x + a2 x2 + ... + an xn

hvor an er forskellig fra nul.

Skriv et C program som indlæser et polynomium af grad højst 8, og som kan beregne polynomiets værdi for forskellige x værdier.

Opdel din problemløsning i delproblemer, get_polynomium, som indlæser et polynomium i et array, og eval_polynomium, som beregner polynomiets værdi for en given x værdi:

void get_polynomium(double coeff[], int* degreep);
double eval_polynomium(const double coeff[], int degree, double x);

Denne opgave svarer til opgave 14 side 464 i 6. udgave af lærebogen


Arrays af flere dimensioner

Arrays af to dimensioner
Slide Indhold Stikord
Referencer 

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.

Gennemløb af arrays med to dimensioner
Slide Indhold Stikord
Referencer 

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.
  int a[2][3] = {{1, 2, 3}, {4, 5, 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: De viste gennemløb i et helt C program.
#include <stdio.h>

int main(void) {
  int i, j, k;
  int sum1 = 0, sum2 = 0;
  int a[2][3] = {{1, 2, 3}, {4, 5, 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: %d\n", sum1);
  printf("Second method: The sum is: %d\n", sum2);
  
  return 0;
}

Program: Program output.
First method:  the sum is: 21
Second method: The sum is: 21

Program: En variation der afslører rækkenfølgen hvorefter elementerne besøges.
#include <stdio.h>

int main(void) {

  int i, j, k;
  int sum1 = 0, sum2 = 0;
  int a[2][3] = {{1, 2, 3}, {4, 5, 6}};

  for (i = 0; i < 2; i++)        /* Revealing sequence of access */ 
    for (j = 0; j < 3; j++){
      printf("a[%1d,%1d] = %d\n", i, j, a[i][j]);
      sum1 += a[i][j];  
    }

  printf("\n\n");

  for (k = 0; k < 2 * 3; k++){   /* Revealing sequence of access */ 
    printf("Element %1d = %d\n", k, *(&a[0][0] + k));
    sum2 += *(&a[0][0] + k);  
  } 

  printf("\n\n");

  printf("First method:  the sum is: %d\n", sum1);
  printf("Second method: The sum is: %d\n", sum2);
  
  return 0;
}

Program: Program output.
a[0,0] = 1
a[0,1] = 2
a[0,2] = 3
a[1,0] = 4
a[1,1] = 5
a[1,2] = 6


Element 0 = 1
Element 1 = 2
Element 2 = 3
Element 3 = 4
Element 4 = 5
Element 5 = 6


First method:  the sum is: 21
Second method: The sum is: 21

Program: Endnu en variation.
#include <stdio.h>

int main(void) {

  int i, j, k;
  int sum1 = 0.0, sum2 = 0, sum3 = 0, *pa;
  int a[2][3] = {{1, 2, 3}, {4, 5, 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);  

  for (i = 0;  i < 2; i++){
    pa = *(&a[0] + i);
    for (j = 0; j < 3; j++)
      sum3 += *(pa + j);  
  }  

  printf("First method:  the sum is: %d\n", sum1);
  printf("Second method: The sum is: %d\n", sum2);
  printf("Third method: The sum is: %d\n", sum3);
  
  return 0;
}

Program: Program output.
First method:  the sum is: 21
Second method: The sum is: 21
Third method: The sum is: 21

C understøtter arrays af vilkårlig mange dimensioner

Tre- og flerdimensionelle arrays er umiddelbare generaliseringer af to dimensionelle arrays

Arrays af to dimensioner overført som parametre
Slide Indhold Stikord
Referencer 

Der er nogle særlige forhold om angivelse af array dimensioner der skal iagttages når arrays overføres som parametre

Program: Et to-dimensiolt array der overføres som parameter til en funktion - OK.
#include <stdio.h>

int array_sum(int matrix[2][3], int rows, int columns);

int main(void) {
  int sum;
  int a[2][3] = {{1, 2, 3}, {4, 5, 6}};

  sum = array_sum(a, 2, 3);
  printf("The sum is: %d\n", sum);
  
  return 0;
}

int array_sum(int matrix[2][3], int rows, int columns){
  int i, j, sum = 0;;

  for (i = 0; i < rows; i++)
    for (j = 0; j < columns; j++)
      sum += matrix[i][j];  

  return sum;
}

Program: Et to-dimensiolt array der overføres som parameter til en funktion - også OK.
#include <stdio.h>

int array_sum(int matrix[][3], int rows, int columns);

int main(void) {
  int sum;
  int a[2][3] = {{1, 2, 3}, {4, 5, 6}};

  sum = array_sum(a, 2, 3);
  printf("The sum is: %d\n", sum);
  
  return 0;
}

int array_sum(int matrix[][3], int rows, int columns){
  int i, j, sum = 0;;

  for (i = 0; i < rows; i++)
    for (j = 0; j < columns; j++)
      sum += matrix[i][j];  

  return sum;
}

Program: Et to-dimensiolt array der overføres som parameter til en funktion - forkert.
#include <stdio.h>

int array_sum(int matrix[][], int rows, int columns);

int main(void) {
  int sum;
  int a[2][3] = {{1, 2, 3}, {4, 5, 6}};

  sum = array_sum(a, 2, 3);
  printf("The sum is: %d\n", sum);
  
  return 0;
}

int array_sum(int matrix[][], int rows, int columns){  /* error: array type has incomplete element type */
  int i, j, sum = 0;;

  for (i = 0; i < rows; i++)
    for (j = 0; j < columns; j++)
      sum += matrix[i][j];  

  return sum;
}

Når arrays overføres som parametre kan den yderste dimension stå åben

Alle andre dimensioner skal angives konkret og korrekt


Statisk og dynamisk lagerallokering

Statisk lagerallokering
Slide Indhold Stikord
Referencer 

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

Program: Illustration af statisk lagerallokering i C.
#include <stdio.h>
#define N  500
#define K   10

void f(void) {
  int i;
  double tab1[N];       /* allocation of N doubles */
  double tab2[N*K];     /* allocation of N*K doubles */

  /* Use tab1 and tab2 */

  /* Implicit deallocation of tab1 and tab2 memory at the end of f */
}

int main(void){
  // ...
  f();
  // ...
}

Udtryk som indgår i indeksgrænser for et array skal være statiske udtryk

Dynamisk lagerallokering (1)
Slide Indhold Stikord
Referencer 

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) {

  /* Prompt for size of array: */
  int n;
  printf("Enter an integer size:\n");
  scanf("%d",&n);

  /* In a block, attempt static allocation of a[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 -ansi -pedantic -Wall static-alloc.c
static-alloc.c: In function main:
static-alloc.c:10: warning: ISO C90 forbids variable length array a

Program: Et program der foretager dynamisk allokering af et array - calloc.
#include <stdio.h>
#include <stdlib.h>

int main(void){
  int *a, i, n, sum = 0;

  /* Prompt for size of array: */
  printf("Enter an integer size:\n");
  scanf("%d",&n);
   
  /* Allocate space for n ints. Dynamic allocation. 
     Returns a generic pointer to the allocated meory. 
     The memory is bit-wise initialized to 0. */
  a = (int *)calloc(n, sizeof(int));  
                                  
  if (a == NULL){
     printf("Cannot allocate enough memory. Bye");
     exit(EXIT_FAILURE);
  }

  /* Initialize the array somehow: */
  for (i = 0; i < n; i++)
     a[i] = 2*i;

  /* Use the memory as an int array. Sum up the elements: */
  for (i = 0; i < n; i++)
      sum += a[i];

  free(a);                      /* FREE THE SPACE */

  printf("Sum of %d elements: %d\n", n, sum);

  return 0;
}

Program: Et program der foretager dynamisk allokering af et array - malloc.
#include <stdio.h>
#include <stdlib.h>

int main(void){
  int *a, i, n, sum = 0;

  /* Prompt for size of array: */
  printf("Enter an integer size:\n");
  scanf("%d",&n);
   
  /* Allocate space for n * sizeof(int) bytes. Dynamic allocation.
     Returns a generic pointer to the allocated meory.
     NOT initialized to 0.  */
  a = (int *)malloc(n * sizeof(int));  
                                   
  if (a == NULL){
     printf("Cannot allocate enough memory. Bye");
     exit(EXIT_FAILURE);
  }

  /* Initialize the array somehow: */
  for (i = 0; i < n; i++)
     a[i] = 2*i;

  /* Sum up the elements: */
  for (i = 0; i < n; i++)
      sum += a[i];

  free(a);                      /* FREE THE SPACE */

  printf("Sum of %d elements: %d\n", n, sum);

  return 0;
}

Program: Et program der dynamisk allokerer et to-dimensionelt array.
#include <stdio.h>
#include <stdlib.h>

#define N 4
#define M 6

int main(void) {
  int *pint, i, j;

  // Allocate space for a N x M matrix:
  pint = (int *)malloc(N*M*sizeof(int));

  if (pint == NULL){
     printf("Cannot allocate enough memory. Bye");
     exit(EXIT_FAILURE);
  }

  // Initialize the matrix:
  for (i=0; i<N; i++)
   for (j=0; j<M; j++)
     *(pint + M*i + j) = (i+1) * (j+1);

  // Print the matrix nicely:
  for (i = 0; i < M * N; i++){
    printf("%4i ", *(pint + i));
    if ((i+1) % M == 0) printf("\n");
  }

  // Free the space:
  free(pint);

  return 0;
}

Program: Output fra programmet.
   1    2    3    4    5    6 
   2    4    6    8   10   12 
   3    6    9   12   15   18 
   4    8   12   16   20   24 

Henvisning

Dynamisk lagerallokering (2)
Slide Indhold Stikord
Referencer 

  • 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.

  • Funktionerne returnerer generiske pointere.

  • Check altid returværdien af calloc og malloc for at se om allokeringen lykkes.

  • 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.

Dynamisk allokering af PPM billeder
Slide Indhold Stikord
Referencer 

En m x n matrix af unsigned int kan håndteres via typen unsigned int **

Denne type tillader attraktiv tilgang til pixels via udtryk af formen matrix[x][y]

I den faktiske implementation er bredden, højden og alle pixels pakket sammen i en struct

Figur. The organization of the memory allocated for a PPM image

Program: Funktionen der allokerer plads til et PPM billede.
unsigned int **alloc_image(int m, int n){
  int i;
  unsigned int **dpp = (unsigned int **)malloc(m * sizeof(unsigned int *));
  if(dpp == NULL) {
    fprintf(stderr, "out of memory\n");
    exit(1);
  }
  for(i = 0; i < m; i++) {
    if((dpp[i] = (unsigned int *)malloc(n * sizeof(unsigned int))) == NULL) {
        fprintf(stderr, "out of memory\n");
        exit(1);
    }
  }
  return dpp;
}


void init_image(unsigned int **image, unsigned int width, unsigned int height,
                unsigned int red, unsigned int green, unsigned int blue){
  int x,y ;

  for(y = 0; y < height; y++)
    for (x = 0; x < width ; x++){
      image[x][y] = (red << 16) | (green << 8) | blue;
    }
}

ppm *make_image(unsigned int width, unsigned int height, pixel background_pixel){
  /* Allocate the struct: */
  ppm *the_image = malloc(sizeof(ppm));   

  /* Initialize the fields: */
  the_image->width = width;
  the_image->height = height;
  the_image->pixels = alloc_image(width,height);

  /* Initialize all pixels of image: */
  init_image(the_image->pixels, width, height, 
             get_red(background_pixel),
             get_green(background_pixel),
             get_blue(background_pixel));

  /* Return the pointer to the image: */
  return the_image;  
}

void set_pixel(ppm *image, unsigned int x, unsigned int y, pixel p){
  unsigned int **pixel_table = image->pixels;
  if (x >= 0 && x < image->width && y >= 0 && y < image->height)
     pixel_table[x][y] = (unsigned int)p;
}

pixel get_pixel(ppm *image, unsigned int x, unsigned int y){
  unsigned int **pixel_table = image->pixels;
  return (pixel)(pixel_table[x][y]);
}

/* Return the width of the image */
unsigned int image_width(ppm *img){
  return img->width;
}

/* Return the height of the image */
unsigned int image_height(ppm *img){
  return img->height;
}

void write_image(ppm *image, char *file_name){
  FILE *image_file;
  unsigned int **pixel_table = image->pixels;
  unsigned int r, g, b;
  int x, y;
  char width_height_str[50];

  image_file = fopen(file_name, "wb");  

  /* Write PPM header: */
  fputs("P6\n", image_file); 
  sprintf(width_height_str, "%d %d\n", image->width, image->height);
  fputs(width_height_str, image_file);
  fputs("255\n", image_file);

  /* Write pixels: */
  for(y = 0; y < image->height; y++)
    for (x = 0; x < image->width; x++){
         r = (pixel_table[x][y] >> 16) & 0xff;
         g = (pixel_table[x][y] >> 8) & 0xff;
         b = pixel_table[x][y] & 0xff;
         fputc(r, image_file);  fputc(g, image_file); fputc(b, image_file);
    }

  fclose(image_file);
}

int blank_char(int ch){
  return (ch == 32 || ch == 10 || ch == 12);
}

ppm *read_image(char *file_name){
  ppm *the_image = malloc(sizeof(ppm));     /* Allocate the ppm struct: */
  FILE *image_file;
  unsigned int **image;

  int ch, ch1, ch2, red, green, blue,
      width, height, pixel_depth,  x, y;

  image_file = fopen(file_name, "rb");  

  /* Get two first chars - expected 'P6': */
  ch1 = fgetc(image_file); ch2 = fgetc(image_file); 

  if (ch1 == 'P' && ch2 == '6'){
    fscanf(image_file, " %d", &width);  fscanf(image_file, " %d", &height);
    fscanf(image_file, " %d", &pixel_depth);

    if (pixel_depth == 255){
      the_image->width = width;
      the_image->height = height;
      the_image->pixels = alloc_image(width,height);      
      image = the_image->pixels;

      /* Read blank stuff before image: */
      while (blank_char(ch = fgetc(image_file))); 
      ungetc(ch, image_file);

      /* Read the image bytes */
      for(y = 0; y < height; y++)
        for (x = 0; x < width ; x++){
          red = fgetc(image_file); green = fgetc(image_file); blue = fgetc(image_file);
          image[x][y] = (red << 16) | (green << 8) | blue;
        }

      return the_image;
     }
     else {
       printf("Unsupported pixel depth. Bye.");
       exit(-1);
    }
  }
  else {
    printf("The image file does not seem to be PPM, P6 file. Bye.");
    exit(-1);
  }
}

void release_image(ppm *image){
  int i;
  for(i = 0; i <= image->width; i++)
    free(image->pixels[i]);
  free(image->pixels);
  image->pixels = NULL;
  image->width = 0;
  image->height = 0;
}

Program: Eksempel på en funktion der tilgår pixels i et PPM billede.
pixel get_pixel(ppm *image, unsigned int x, unsigned int y){
  unsigned int **pixel_table = image->pixels;
  return (pixel)(pixel_table[x][y]);
}

Henvisninger

Flere Opgaver
Slide Indhold Stikord
Referencer 

Opgave 9.11. Reduktion af et array

Vi har tidligere i undervisningsmaterialet set hvordan vi kan reducere/kombinere en række tal med en 'binær funktion' (en funktion fra to doubles til én double).

I denne opgave skal I skrive en funktion

  double combine_right (double a[], int n, 
                        double (*combiner)(double, double))

som kombinerer alle n elementer i a, på samme måde som combine gør det for fire faste tal. Antag at n >= 2. Skriv først en version, combine_right, der kombinerer elementerne fra højre mod venstre. Skriv også gerne en version, combine_left, som kombinerer i den modsatte retning.

Afprøv dit program på tilsvarende måde, som vi gjorde da vi første gange mødte combine funktionen.

Opgave 9.11. bsort

Omskriv bubblesort funktionen så den ligner qsort så meget som muligt. Du skal ikke lave om på algoritmen bag bubblesort - det handler parametrene til funktionen. Kald den nye variant af bubblesort for bsort.

Dette indebærer at bsort skal have fire parametre:

  1. En pointer til det array der skal sorteres
  2. Antallet af elementer i arrayet
  3. Byte-størrelsen af hvert element
  4. En sammenligningsfunktion (med int returværditype og to generiske pointere som input parametre).

Start gerne med at generalisere den eksisterende version af bubblesort med en sammenligningsfunktion.

Når dette er på plads bedes du overveje hvordan du vil håndtere ombytningen af elementer. (Hint: Overvej at bruge memcpy fra string.h når du skal kopiere array elementer).

Du kan bruge følgende prototype af funktionen:

  void bsort(void *base, size_t n, size_t size,
             int(*compar)(const void *, const void *))

hvor size_t er en passende unsigned integer type (som altid findes i C)

Opgave 9.11. Dynamisk allokering og qsort

Brug malloc til at allokere plads til 100 doubles. Check at allokeringen blev gennemført, og dealloker dit lager når du er færdig med at bruge det.

Opfat det allokerede lager som et array af 100 doubles, og indskriv 100 tilfældige tal i dit array. Udskriv dem på skærmen.

Brug nu qsort til at sortere dine tal. Udskriv dem igen, så du kan se at dit array rent faktisk er blevet sorteret.

Opgave 9.11. Barcode scanning

Dette er opgave 5 side 469 i PSPD (8ed). Opgaven er taget med for at have et naturligt sted at organisere løsningen på opgaven.

Opgave 9.11. Iterativ løsning af 'uger, dage, timer, minutter og sekunder' opgaven

Denne opgave hører logisk til i lektionen om iterative kontrolstrukturer. Men da det viser sig at arrays er helt essentielle for at kunne håndterer udfordringen, har vi valgt at placere den her.

Når man ser på en typiske løsning af opgaven, der omregner et sekundtal til normaliserede uger, dage, timer, minutter og sekunder, kan man tydeligt se at division og restuddragen gentages fire gange på en given rest.

I denne opgave vil vi forsøge at programmere dette med en iterativ kontrolstruktur. Omskriv altså løsningen på den oprindelige opgave til et program, der gentager divisionen og restuddragning, i en passende løkke.

For at kunne arbejde med tidsdelene (og enhedsnavnene) på en realistisk måde, er det attraktivt at benyttes arrays.

Som altid, er det godt at formulere løsningen på problemet i en funktion. Her en funktion med én input-parameter (sekundtallet), og én output parameter (et array med de beregnede tidsdele).

Notér og bemærk hvilke udfordringer det gav at skrive programmet om på den ønskede måde. Vurder også om det er umangen værd at lave denne ændring af programmet.

Opgave 9.11. Multiple terningekast.

siden om tilfældige tal, har vi set en simpel funktion, der simulerer et kast med en terning.

I nogle sammenhænge er der behov for kast med n terninger, hvor n > 1. I det simple tilfælde kan vi naturligvis blot kaste én terning n gange (i en løkke). I andre tilfælde har vi behov for at have adgang til udfaldene af de n terninger samtidigt, i et array, for at kunne vurdere de n kast under ét. Vi vil senere på kurset få brug for netop denne mulighed.

Skriv derfor en funktion roll_multiple_dies, med en heltals parameter n, der kaster n terninger, og som afleverer et array af de n terningekast.

Afleveringen af de n kast kan ske på to måder: gennem en parameter af pointer type eller via funktionens returværdi. Allokering af arrayet kan også varieres: enten allokerer roll_multiple_dies plads, eller også er der allerede allokeret plads, når roll_multiple_dies kaldes. Hvis roll_multiple_dies allokerer plads med dynamisk lagerallokering, i hvert kald, udestår der et efterfølgende arbejde med passende kald af free.

Skriv, ud fra denne analyse, din foretrukning variant af funktionen roll_multiple_dies.

Programmer endvidere, i main, 10 kald af af roll_multiple_dies. Giv indledningsvis brugeren mulighed for at indlæse størrelsen n (antallet af terninger). Udskriv, for hvert kald af roll_multiple_dies, udfaldet af de n terningekast.

Opgave 9.11. Associative arrays.

Et array i C indiceres altid med et heltal, hvilket sikrer simpel og effektiv tilgang til elementer i arrayet. Men i mange sammenhænge er det fristende og nyttigt at indicere et array med værdier af andre typer, så som en tekststreng.

Lad os eksempelvis antage at vi ønsker at holde styr på alderen af navngivne personer ved brug af et array, alder_af_person. For "Peter" kan vi dermed tilgå alderen med alder_af_person["Peter"] .

alder_af_person kan ikke være et array i C, men konceptuelt kan vi opfatte alder_af_person som et associativt array: Et sådant array associerer navnet på en person med personen alder. Generelt giver det god mening, på denne måde, at associere en vilkårlig værdi/objekt s af typen S til en værdi t i typen T via et associativt array a. Vi slår T-værdien op med a[s], givet s i typen S.

Spørgsmålet er nu hvordan vi kan bruge arrays i C til at arbejde med associative arrays. Ideen er simpel nok. Lad os illustrere den med S som en teksstreng, og T som int, og a som alder_af_person. Personens navn skal først, med en funktionen h, konverteres til et lovligt indeks i et C-array. h("Peter") skal returnere et ikke-negativt heltal, nemlig det heltal hvor alderen af "Peter" skal findes. Hermed kan vi fra pesonens navn, "Peter", tilgå Peter's navn med

   alder[h("Peter")]

hvor alder er et C array:_

   int alder[MAX_PESON_INDEX];

Hvis vi først antager at vi har et lille univers af mulige tekststrenge, kan vi ret let skrive en h-funktion , som eksplicit afbilder et navn (en streng) til et indeks (et heltal). Denne h-funktion sikrer at hver tekststreng tildeles hvert sit indeks. Skriv en sådan h -funktion for navnene på dine medstuderende i din projektgruppe, således at du kan indsætte og slå alderen af en studerende op i et associativt array (undgå danske bogstaver i navnene).

Hvis vi derimod antager at vi har et meget stort univers af mulige teksstrenge, så som hele Danmarks befolkning, bliver det meget besværligt at skrive funktionen h . Hvis vi forsøger vil det sikkert også bliver meget dyrt at kalde den, fordi funktionen muligvis vil lave et arbejde proportionalt med befolkningens størrelse. Men vi kan forsøge at beregne et passende heltal ud fra tegnene i personens navn, og normalisere tallet til et indeks i det ønskede interval. (Funktionen kan eksempelvis tage alle, eller udvalgte, tegn i navnet, addere dem som de små heltal de jo er, og normalisere summet med modulo operatoren). Problemet er nu, at to forskelle navne kan afbildes til det samme indeks. Vi siger at der sker en kollision.

Skriv, som en øvelse, en h-funktion efter denne ide, og prøv den af på navnene i jeres projektgruppe. Oplever I kollisionsproblemet i denne øvelse?

Vi har med dette introduceret ideen om hashtabeller og hashfunktioner , som er vigtige i mange praktiske sammenhænge, hvor vi også skal udtænke strategier til håndtering af kollision.

Opgave 9.11. Fletning af to sorterede arrays

Dette er opgave 11 side 471-472 i Problem Solving and Program Design in C, eighth global edition. Denne opgave er taget med her for at have en pladsholder til en løsning.


Samlede referencer
Indhold Stikord
Operatorer i C
C Operator tabellen
Pointer aritmetik
Introduktion og motivation for arrays
Det to-dimensionelle array
PPM grafik funktionerne
Inspiration

 

Kapitel 9: Arrays og Pointere
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: 9. maj 2022, 13:59:48