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.

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 Operatorer i C

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.

#include <stdio.h> #define TABLE_SIZE 11 void f (double p[TABLE_SIZE]){ int i; for(i = 0; i < TABLE_SIZE; i++) p[i] = 2*i; } 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 in assignment */ return 0; }

Program: Illustration af at et array ikke kan overføres som en værdiparameter.

#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 i a is passed. // 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.

#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: // Function return address of 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.

#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

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

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 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 = 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

Henvisning Pointer Begrebet

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.

Expression Equivalent Expression p == &i p == (& i) p = i + 7 p = (i + 7) * * & p * (* (& p)) r = & x r = (& x) 7 * * p / * q + 7 ((7 * (* p)) / (* q)) + 7 * (r = & j) *= * p (* (r = (& j))) *= (* p)

Henvisning C Operator tabellen

Opgave 6.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 Slide Indhold Stikord Referencer

Pointere til forskellige typer er usammenlignelige Herunder generiske pointere

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

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

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

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 version 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. 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) { /* Declarations: */ double table[TABLE_SIZE], *table_ptr = &table[0], *tp; int i; /* Initialization: */ for(tp = table_ptr, i=0; tp < &table[TABLE_SIZE]; tp++, i++) *tp = (double)(2 * i); /* Printing: */ for(tp = table_ptr; 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 Introduktion og motivation for arrays

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[0] + i) a kan også skrives som pa &a[0]

Når et array overføres som parameter til en funktion er det reelt en pointer til arrayets første element som overføres

Pointeraritmetik 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 lovlig i C - herunder 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

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

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 ret output Illustreret ved bubble_sort

Et godt og simpelt eksempel på side 413 i PSPD 7'th ed

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("%d\n", a[i][j]); sum1 += a[i][j]; } printf("\n\n"); for (k = 0; k < 2 * 3; k++){ /* Revealing sequence of access */ printf("%d\n", *(&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.

1 2 3 4 5 6 1 2 3 4 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

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. All 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 ints. Dynamic allocation. 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 Det to-dimensionelle array

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 insigned int ** Denne typer 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(EXIT_FAILURE); } for(i = 0; i < m; i++) { if((dpp[i] = (unsigned int *)malloc(n * sizeof(unsigned int))) == NULL) { fprintf(stderr, "out of memory\n"); exit(EXIT_FAILURE); } } 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(EXIT_FAILURE); } } else { printf("The image file does not seem to be PPM, P6 file. Bye."); exit(EXIT_FAILURE); } }

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 Inspiration PPM grafik funktionerne

Opgaver Slide Indhold Stikord Referencer

Opgave 6.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

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: 6. november 2012, 16:27:34