Del 2

Funktioner
Strukturer
Pointere (“pegepinde”)
Input og output

Funktioner

En funktion i C ligesom i matematik tager et antal argumenter og returnerer en værdi:

1
2
3
4
type func_name(type1 arg1, type2 arg2, ...) {
    ...
    return ...;
}

Eksempel:

1
2
3
int add_one(int x) {
    return x+1;
}

Vi har allerede set en funktion:

1
2
3
4
int main() {
    printf("Hello world!\n");
    return 0;
}

Funktioner kan også tage ingen argumenter og returnere ingenting, indikeret med void:

1
2
3
void print_hej(void) {
    printf("Hej!\n");
}

Del programmer op i små funktioner, som hver laver en lille del. Gør funktionerne så generelle at de kan genbruges mange steder.

Bemærk: C læser fra top til bund. Når den ser en funktion, så husker den at den eksisterer. Men hvis man først definerer en funktion i bunden som man skal bruge i toppen, så giver C fejl. Den måde man løser det på er at definere “prototype” til funktionen i toppen.

1
2
3
4
5
6
7
8
9
10
11
int add_one(int x); /* Prototype aka. forward declaration */

int main() {
    int y = add_one(41);

    return 0;
}

int add_one(int x) {
    return x+1;
}

Strukturer (“Structs”)

Et array var bare et chunk memory, hvor der var plads til et antal af elementer af samme type. En struct er på samme måde en samling, men af forskellige typer. Det svarer til et meget primitivt objekt/klasse.

1
2
3
4
struct Person {
    char name[16];
    int  age;
};

Person struct

1
2
3
4
5
6
struct Person  person;

person.name[0] = 'B';
person.name[1] = 'o';
person.name[2] = 'b';
person.age     = 42;

Hvis man vil slippe for at skrive struct Person, men bare Person, så kan man skrive

1
2
3
4
5
6
typedef struct Person Person;

struct Person {
    char name[16];
    int  age;
};

og så

1
Person person;

Sidespring: Stak vs. Heap

Hvert program får tildelt en mængde hukommelse og det opdeles på denne måde:

Memory process

Stakken og heapen vokser mod hinanden jo mere plads programmet bruger.

Variabler som defineret i funktioner ligger på stakken. Man kunne snakke længe om stakken, men lad os bare hold det til at variablerne kun lever indtil funktionen er færdig med at blive kaldt.

Hvis man vil gemme data, så det er tilgængeligt mellem funktionskald, så gemmer man det på heapen. Vi kommer til at se hvordan man gør det senere.

Vi kan zoome ind på stakken og se hvordan vores Person instans ligger:

Person struct color

Memory zoom

Note: Når vi tegner hukommelsen for vores program som sådan nogle blokke, så vælger vi lidt selv hvordan de forskellige structs, arrays og andet ligger - bare de ligger i de rigtige blokke.

Hver lille firkant er én byte og har en adresse:

Vi skriver normalt adresser i hexidecimal for at de er nemmere at genkende som adresser, men man kan bare tænke på dem som tal, der er unikke for den firkant.

Adressen til name arrayet er 0x4a2b og 16 bytes længere henne har vi age som har adressen 0x4a3b. Man kan også tale om adressen til hele structen, som bare er adressen hvor den starter. I tilfældet med Person er det også 0x4a2b. En anden interessant observation er at adressen til første element i arrayet er den samme som adressen til selve arrayet. Det virker måske trivielt, når man ser det på en tegning, men det er ofte noget man ikke tænker over.

Pointers

En variabel er bare en kasse (en chunk i memory), der indeholder en værdi. Der er intet særligt over en pointer. Det er bare en kasse, hvis værdi er en adresse til en anden kasse. Og en adresse er bare et tal - intet farligt over det heller.

1
2
3
4
5
int  a = 8;
int* p = &a;

*p = 32;
/* a is now 32 */

* betyder “Dette er en adresse” eller “Giv mig værdien som man kommer til hvis man følger adressen”.

& betyder “Giv mig adressen af”.

Man kan se dem som pile (venstre) eller bare adresser (højre):

Int pointer

Pointers & Structs

Lad os udvide vores person-struct til at have en far og en mor:

1
2
3
4
5
6
7
8
typedef struct Person Person;

struct Person {
    char   name[16];
    int    age;
    Person father;
    Person mother;
};

Hvad er problemet her? Hvordan ville det se ud?

Struct in struct

Hvor meget plads fylder Person?

Løsningen:

1
2
3
4
5
6
7
8
typedef struct Person Person;

struct Person {
    char    name[16];
    int     age;
    Person* father;
    Person* mother;
};

Struct with pointers

Pointers & Malloc

Hvor kommer pointers så fra? Svaret er malloc.

malloc finder plads et sted på heapen (i stedet for stakken) af den størrelse man beder om og den returnerer en adresse til starten af den chunk memory.

1
2
int* a = malloc(4);
*a = 42;

Man bør dog aldrig selv angive størrelsen som et tal. C har en indbygget funktion sizeof som kan finde ud af det selv og som tager højde for forskellige ting som C kan finde på at gøre, fx padding eller alignment. Dette er bedre:

1
2
int* b = malloc(sizeof(int));
*b = 42;

Lad os se hvordan vi laver en Person og sætter dens age:

1
2
3
4
5
6
7
Person* person = malloc(sizeof(Person));

person.age = 42; /* Doesn't work! */

(*person).age = 42; /* This does! */

person->age = 42; /* Shorthand! */

Lad os prøve at sætte father pointeren i vores struct:

1
2
3
4
5
Person* person = malloc(sizeof(Person));

person->father = malloc(sizeof(Person));

person->father->age = 83;

Constructors

Man skal lave sine egne constructors i C:

1
2
3
4
5
6
7
8
9
10
11
Person* create_person(int age, Person* father) {
    Person* person = malloc(sizeof(Person));
    person->age    = age;
    person->father = father;
    return person;
}

int main() {
    Person* grandpa = create_person(83, NULL);
    Person* bob     = create_person(42, grandpa);
}

Det kan virke som slavearbejde, men ofte er det en rigtig god idé at lave constructors til alle ens structs. Det giver en mere high-level måde at tænke på dem på.

Deconstructors

Man skal selv rydde op efter sig i C. Der er ingen garbage collector som i Java og Python.

Man kan sige at man er færdig med et stykke memory man har fået fra malloc vha. funktionen free:

1
2
3
Person* person = malloc(sizeof(Person));
...
free(person);

Ligesom det er smart at lave constructors, så er det også en god idé at lave deconstructors. Normalt er det bare en funktion, der kalder free, men ofte skal der gøres mere end bare det.

1
2
3
4
5
void destroy_person(Person* person) {
    /* Clean up other stuff */
    ...
    free(person);
}

Pointers & Arrays

Som vi så før var structs bare en chunk memory som vi kunne tilgå forskellige dele af. Arrays are ikke anderledes. Hvis vi laver et array, så får vi bare en pointer til starten af det stykke memory. Ud fra det kan vi se:

1
2
3
4
5
int arr[16];

arr[5] = 17;

*(arr + 5) = 17; /* Same thing! */

Man kan så spørge om det ikke burde være arr + 5 * 4, nu hvor ints er 4 bytes. Men C ganger op automatisk fordi den kan se at vi arbejder med ints.

Det samme gælder selvfølgelig når vi bruger malloc:

1
2
3
4
5
int* arr = malloc(16 * sizeof(int));

arr[5] = 17;

*(arr + 5) = 17; /* Same thing! */

Det er forresten lidt ufleksibelt at have arrays direkte inde i structs, så vi kan lave vores Person om:

1
2
3
4
5
6
7
8
typedef struct Person Person;

struct Person {
    char*   name; /* Instead of char name[16]; */
    int     age;
    Person* father;
    Person* mother;
};

Struct with more pointers

Man kan blot tænke på char* som strings.

Nu kan vi begynde at forstå char** argv fra

1
2
3
4
int main(int argc, char** argv) {
    ...
    return 0;
}

Det er en array af strings: Første pointer betyder at det er en array af char*. Og char* er et array af char, også kendt som en string.

Structs + Funktioner = Datastrukturer

Lad os prøve at lave en simpel datastruktur: En linked list af ints.

Linked list

Lad os starte med at lave struct-layoutet:

1
2
3
4
5
6
typedef struct LinkedList LinkedList;

struct LinkedList {
    int         data;
    LinkedList* next;
};

Vi kan starte med at lave en constructor:

1
2
3
4
5
6
LinkedList* linkedlist_create(int first_element) {
    LinkedList* ll = malloc(sizeof(LinkedList));
    ll->data = first_element;
    ll->next = NULL;
    return ll;
}

Dernæst laver vi en funktion til at tilføje et nyt element:

1
2
3
4
5
6
LinkedList* linkedlist_insert(int element, LinkedList* list) {
    LinkedList* head = malloc(sizeof(LinkedList));
    head->data = element;
    head->next = list;
    return head;
}

Og nu kan vi lave listen oven for således:

1
2
3
LinkedList* ll = linkedlist_create(17);
ll = linkedlist_insert(42, ll);
ll = linkedlist_insert(5, ll);

Input & Output

Vi har allerede set hvordan man printer output til terminalen: printf. På en meget tilsvarende måde kan man læse fra terminalen med scanf.

1
2
3
4
5
6
7
8
9
10
char name[64];
int  age;

printf("What is your name?\n");
scanf("%s", name);
printf("Hi %s!\n", name);

printf("What is your age?\n");
scanf("%d", &age);
printf("Cool! My friend is also %d years old\n", age);

Men man kan skrive til andet end terminalen. Fx kan man åbne og skrive til filer. Der findes en printf variant til dette: fprintf.

1
2
FILE* f = fopen("names.txt", "w");
fprintf(f, "Bob\n");

Læs en fil tegn for tegn:

1
2
3
4
5
6
7
8
FILE* f = fopen("names.txt", "r");

char c;
while ((c = fgetc(f)) != EOF) {
    printf("%c", c);
}

/* Output: Bob */

Læs linje for linje:

1
2
3
4
5
6
FILE* f = fopen("names.txt", "r");

char buf[256];
while (fgets(buf, sizeof(buf), f)) {
    printf("line: %s", buf);
}

Bemærk at hvis en linje er længere end 256 tegn, så vil fgets skrive ud over arrayet og overskrive andet data.

Opgaver

Gå tilbage til opgaverne i del 1 og lav 1-2 af løsningerne om til funktioner. Eksempler:
- Lav en funktion int fib(int n), der returnerer det nte fibonacci tal.
- Lav en funktion bool is_prime(int n), der tjekker om n er et primtal.
Gå tilbage til opgaverne i del 1 og lav 1-2 af løsningerne om, så de tager input fra terminalen.
Lav en Point struct med et x og et y koordinat som er integers. Lav en constructor til at lave et punkt givet et x og et y koordinat. Lav en funktion, som tager to punkter og lægger dem sammen (Lav et nyt punkt hvor resultatet gemmes i og returner det).
Lav en doubly linked list.
Lav et resizable array.
Lav et binært søgetræ med ints.
Lav en min/max heap med ints.