Opgaver og løsninger
Arrays og Pointere

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.

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

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

   p(x) = a₀ + a₁ x + a₂ x² + ... + a_n xⁿ

hvor a_n 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

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.

Her er min løsning:

#include <stdio.h>

double max(double, double);
double min(double, double);
double plus(double, double);
double minus(double, double);

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

int main(void) {
  double result;
  double numbers[] = {5, 7, 8 , 11};
  int n = sizeof(numbers) / sizeof(double);

  result = combine_left(numbers, n, &minus);  /* minus(5, minus(7, minus(8, 11))) = 5 - (7 - (8 - 11)) = -5 */
  printf("Minus combination result: %f\n", result);

  result = combine_left(numbers, n, &plus); 
  printf("Plus combination result: %f\n", result);

  result = combine_left(numbers, n, &min); 
  printf("Min combination result: %f\n", result);

  result = combine_left(numbers, n, &max); 
  printf("Max combination result: %f\n", result);

  return 0;
}


double combine_right(double a[], int n, 
                     double (*combiner)(double, double)){
  double result;
  int i;

  for(i = n-2; i >= 0; --i){
    if (i == n-2)
       result = combiner(a[i], a[i+1]);
    else
       result = combiner(a[i], result);
  }
    
  return result;  
}

double combine_left(double a[], int n, 
                     double (*combiner)(double, double)){
  double result;
  int i;

  for(i = 1; i < n; ++i){
    if (i == 1)
       result = combiner(a[i-1], a[i]);
    else
       result = combiner(result, a[i]);
  }
    
  return result;  
}


double max (double a, double b){
  return a > b ? a : b;
}

double min (double a, double b){
  return a > b ? b : a;
}

double plus(double a, double b){
  return a + b;
}

double minus(double a, double b){
  return a - b;
}

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)

Her et mit bud på en løsning. Programmet er skrevet så bsort er så genkendelig som mulig i forhold til det tidligere program, vi har set på.

Læg mærke til følgende:

• I bsort tilgår vi vores array via en generisk pointer, base. Vi caster denne om til en char pointer, fordi vi dermed arbejder på byte-niveau.
• Vi opdaterer pointeren i byte enheder. Pointeren ind i vores array tælles op med j * size, hvor size er bytstørrelsen af den type af data vi har i vores array.
• I bsort allokerer vi tempspace så swap har en temporær plads den kan bruge til ombytninger. tempspace skal indeholde size bytes.
• Når der skal ombyttes på to elementer i vores array sker dette med brug af memcpy. Kaldet memcpy(d, s, c) kopierer c bytes fra s til d, hvor både s og d er void pointere.

Her er programmet:

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

void swap(char *p, char *q, size_t size, char *temp){
   memcpy(temp, p, size);
   memcpy(p, q, size);
   memcpy(q, temp, size);
}

void bsort(void *base, size_t n, size_t size, int(*compar)(const void *, const void *)){
   int i, j;
   char *bbase = (char*)base,        /* base by byte */
        *tempspace = malloc(size),   /* temp space used by swap */
        *el_j_minus_1_ptr, *el_j_ptr;

   for (i = 0; i < n - 1; ++i){
     for (j = n - 1; j > i; --j){
       el_j_minus_1_ptr = bbase + (j-1) * size;  /* a pointer to element j   */
       el_j_ptr = bbase + j * size;              /* a pointer to element j-1 */
       if (compar((void*)el_j_minus_1_ptr, (void*)el_j_ptr) > 0)
          swap(el_j_minus_1_ptr, el_j_ptr, size, tempspace);
     }
   }
 
   free(tempspace);
}

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

int int_compar(const void *ip1, const void *ip2){
  int result;
  int *ipi1 = (int *)ip1,    
      *ipi2 = (int *) ip2;

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

  return result;
}

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);
  bsort(a, n, sizeof(int), int_compar);
  prn_array(" After", a, n);
  putchar('\n');
  return 0;
}

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.

Her er min løsning:

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

#define N 100

int element_compare(const void *ip1, const void *ip2);
double double_compare(const double d1, const double d2);

int main(void) {
  srand(time(NULL));
  double *store = malloc(N * sizeof(double));
  int i;

  if (store == NULL){
    printf("Cannot allocate sufficient memory. Bye\n");
    exit(EXIT_FAILURE);
  }

  for(i = 0; i < N; ++i)
    store[i] = (double)(rand())/3.0;

  for(i = 0; i < N; ++i){
    printf("%8.3f  ", store[i]);
    if (i%5 == 0) printf("\n");
  }

  qsort(store, N, sizeof(double), element_compare);  

  printf("\n");
  for(i = 0; i < N; ++i){
    printf("%8.3f  ", store[i]);
    if (i%5 == 0) printf("\n");
  }

  free(store);

  return 0;
}

int element_compare(const void *ip1, const void *ip2){
  double *ipi1 = (double *)ip1,       
         *ipi2 = (double *)ip2;

  return double_compare(*ipi1, *ipi2);
}

double double_compare(const double d1, const double d2){
  if (d1 < d2)
    return -1;
  else if (d1 > d2)
    return 1;
  else 
    return 0;
}

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.

Her er min løsning:

#include <stdio.h>
#define BAR_CODE_MAX 12

void prompt_for_bar_code(int *bar_code);
void print_bar_code(const int bar_code[BAR_CODE_MAX]);
void check_bar_code(const int bar_code[BAR_CODE_MAX]);
int check_digit(const int bar_code[BAR_CODE_MAX]);

int main(void) {
  int bar_code[BAR_CODE_MAX], i;      

  printf("Enter bar code (12 digits, separated by spaces):\n");
  fflush(stdout);

  prompt_for_bar_code(bar_code);

  printf("The bar code is: ");   
  print_bar_code(bar_code);
  printf("\n");

  fflush(stdout);

  check_bar_code(bar_code);
  
  return 0;
}

/* A printing function that reports about the status of the bar code */
void check_bar_code(const int bar_code[BAR_CODE_MAX]){
  int chd = check_digit(bar_code);

  if (chd == bar_code[BAR_CODE_MAX - 1]){
    print_bar_code(bar_code);
    printf(" is validated.");
  }
  else {
    print_bar_code(bar_code);
    printf(" contains an error.");
  }
  printf("\n");
}

/* Return the check digit of the bar_code */
int check_digit(const int bar_code[BAR_CODE_MAX]){
  int odd_sum = 0, even_sum = 0, res, i;

  /* so-called odd-numbered positions: */
  for(i = 0; i < BAR_CODE_MAX; i += 2)        // Accumulate all even-indexed numbers
     odd_sum += bar_code[i];

  res = odd_sum * 3;

  /* so-called even-numbered positions: */
  for(i = 1; i < BAR_CODE_MAX - 2; i += 2)    // Accumulate all odd-indexed numbers, not the last
     even_sum += bar_code[i];

  res += even_sum;

  printf("Intermediate result: %d\n", res);

  if (res % 10 == 0)
    return 0;
  else
    return 10 - res % 10;
}

void prompt_for_bar_code(int *bar_code){
  int i;

  for(i = 0; i < BAR_CODE_MAX; i++){
    scanf("%d", bar_code + i);
  }
}

/* prints the barcode */
void print_bar_code(const int bar_code[BAR_CODE_MAX]){
  int i; 
  for(i = 0; i < BAR_CODE_MAX; i++) printf("%d ", bar_code[i]);
}

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.

Her er min løsning:

#include <stdio.h>
#define SECONDS_PER_MINUTE 60
#define SECONDS_PER_HOUR (SECONDS_PER_MINUTE * 60)
#define SECONDS_PER_DAY (SECONDS_PER_HOUR* 24)
#define SECONDS_PER_WEEK (SECONDS_PER_DAY * 7)
#define UNIT_COUNT 5

void decompose_seconds_to_units(int input_seconds, int result_units[]);

int second_amount[] = {SECONDS_PER_WEEK, SECONDS_PER_DAY, SECONDS_PER_HOUR, SECONDS_PER_MINUTE};
char *units[] = {"weeks", "days", "hours", "minutes", "seconds"}; 

int main(void){
  int input_seconds, i;
  int result_units[UNIT_COUNT];

  /* Prompt for input: */
  printf("Read a non-negative number of seconds: ");
  scanf("%d", &input_seconds);

  decompose_seconds_to_units(input_seconds, result_units);

  /* Print the calculated units */
  for(i = 0; i < UNIT_COUNT; ++i)
    printf("%d %s   ", result_units[i], units[i]);

  return 0;
}

/* Decompose the seconds in input_seconds to the units enumerated in the global array units */
void decompose_seconds_to_units(int input_seconds, int result_units[]){
  int i = 0,
      rest_seconds = input_seconds,
      parts = sizeof(second_amount) / sizeof(int);

  while (i < parts){
    result_units[i] = rest_seconds / second_amount[i];
    rest_seconds = rest_seconds % second_amount[i];
    ++i;
  }
  result_units[i] = rest_seconds;
}

Det viser sig at være lidt omstændeligt at introducere en løkke, der beregner quotient og rest. Jeg tror faktisk ikke at det kan betale sig. Hvis der var endnu flere tidsdele, ville jeg dog klart overveje ideen (igen).

På 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.

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.

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.

Her er en mulig løsning på opgaven:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define RES_MAX 100

void merge_arrays(const double a1[], int a1_size, const double a2[], int a2_size,
                  double result[], int *merge_length);

int main(void){

  double ar1[] = {-10.5, -1.8, 3.5, 6.3, 7.2},
         ar2[] = {-1.8, 3.1, 6.3},
         ar_res[RES_MAX];

  int i, merge_length;

  merge_arrays(ar1, sizeof(ar1) / sizeof(double),
               ar2, sizeof(ar2) / sizeof(double),
               ar_res, &merge_length);

  printf("The merged array: \n");
  for(i = 0; i < merge_length; i++)
    printf("%f\n", ar_res[i]);

  return EXIT_SUCCESS;
}


void merge_arrays(const double a1[], int a1_size, const double a2[], int a2_size,
                  double result[], int *merge_length){
  int i1 = 0, i2 = 0, j = 0;

  /* Process elements while there are elements in both a1 and a2: */
  while (i1 < a1_size && i2 < a2_size){
    if (a1[i1] < a2[i2]){
       result[j] = a1[i1]; 
       i1++; j++;
    }
    else if (a1[i1] == a2[i2]){
       result[j] = a1[i1]; 
       i1++; i2++; j++;
    }
    else {
       result[j] = a2[i2]; 
       i2++; j++;
    }
    printf("result[%d] = %f\n", j-1, result[j-1]);
  }

  assert(i1 == a1_size || i2 == a2_size);

  /* A tail of either a1 or a2 may be left - but not both.
     One of the following while loops will therefore be empty. */
  while(i1 < a1_size){
       result[j] = a1[i1]; 
       i1++; j++;
  }     

  while(i2 < a2_size){
       result[j] = a2[i2]; 
       i2++; j++;
  }     

  *merge_length = j;
}