De variables a estructures de dades

struct, typedef, enum i linked lists

Jordi Mateo Fornés

Introducció

De variables a estructures de dades

struct · typedef · enum · linked lists

Objectius d’aprenentatge

Objectius d'Aprenentatge

Agrupar dades relacionades amb struct i distingir tipus de variable
Crear àlies de tipus amb typedef
Expressar un conjunt tancat de valors amb enum
Combinar struct amb punters (. vs ->) i memòria dinàmica (malloc)
Construir i recórrer una linked list, i alliberar-la sense deixar punters penjats
Organitzar-ho en .h/.c/Makefile

Prerequisits

Espai de memòria d’un procés (TEXT/DATA/HEAP/STACK)
Punters, malloc/free, ownership.
int **.
.h = interfície / .c = implementació, Makefile.

Recordem què sabem

int age;
float temperature;
char name[50];

Reflexió

Què passa quan aquestes variables formen part de la mateixa entitat?

Exemple — Un estudiant

Imagina que volem representar un estudiant amb nom, edat i nota. Podem fer-ho amb tres variables separades: name, age i grade. Però això no és gaire pràctic.

Si volem passar un estudiant a una funció, hauríem de passar tres arguments.
Si volem crear un array d’estudiants, hauríem de crear tres arrays separats
Si volem afegir un camp més (per exemple, el número d’identificació), hauríem de modificar tot el codi que utilitza aquestes variables.

struct

Agrupar dades relacionades

struct Student {
    char name[50];
    int age;
    float grade;
};

Concepte

Una struct permet agrupar diferents dades sota una mateixa estructura.

Tipus vs variable

struct Student {
    char name[50];
    int age;
    float grade;
};

Concepte

Això no crea cap Student. Defineix un tipus.

struct Student s;

Concepte

Ara sí, hem instanciat el tipus.

Resum

struct Student{...} \(\Rightarrow\) defineix \(\Rightarrow\) tipus \(\Rightarrow\) struct Student s instanciem \(\Rightarrow\) la variable s

Els camps

struct Student s;

s.age = 20;
s.grade = 8.5;

printf("%s\n", s.name);

Reflexió

Què representa s.age?

Concepte

El camp age de la variable s. L’operador és .

Una struct ocupa memòria

typedef

struct Student és una mica llarg

struct Student student1;
struct Student student2;

Podem crear un àlies:

typedef struct {
    char name[50];
    int age;
    float grade;
} Student;

Student student1;
Student student2;

Què fa realment typedef?

Concepte

Una struct defineix un tipus. Un typedef dóna un àlies a un tipus existent, és a dir, dóna un altre nom a un tipus ja existent. Això és útil per fer el codi més llegible i concís.

Exemple — typedef d'un tipus bàsic

typedef unsigned int uint;

Concepte

uint no és un tipus nou amb una representació diferent. És un altre nom per a unsigned int.

enum

Quan una variable només pot tenir alguns valors?

int state;

Però només volem: IDLE, RUNNING, STOPPED.

enum State {
    IDLE,
    RUNNING,
    STOPPED
};

Concepte

enum permet donar noms a un conjunt de constants enteres relacionades.

Utilitzar un enum

enum State state;

state = RUNNING;

if (state == RUNNING) {
    ...
}

Error Comú

Un enum no impedeix assignar-hi qualsevol enter: state = 42; compila igualment. Millora la llegibilitat i la intenció del codi, no és una restricció imposada pel compilador.

Els valors de l’enum

enum State {
    IDLE,
    RUNNING,
    STOPPED
};

Per defecte: IDLE = 0, RUNNING = 1, STOPPED = 2.

Concepte

El compilador associa valors enters als enumeradors. Nosaltres normalment treballem amb els seus noms, no amb els números.

typedef enum

typedef enum {
    IDLE,
    RUNNING,
    STOPPED
} State;

State state = RUNNING;

Concepte

struct + typedef i enum + typedef són dos patrons que trobareu constantment en C.

struct i punters

Un punter a una struct

Student s;
Student *p = &s;

Reflexió

Què conté p?

Concepte

L’adreça de s

`.` vs `->`

Student s;
s.age = 20;

Student *p = &s;
p->age = 20;

Definició

p->age és equivalent a (*p).age.

Per tant, quan tenim un punter a una struct, utilitzem -> per accedir als camps. Si tenim la struct directament, utilitzem ..

Exemple

Student s → s.age
Student *p → p->age

structs i funcions

Passar una struct a una funció

void print_student(Student s)
{
    printf("%s\n", s.name);
}

print_student(s);

Concepte

La funció rep una còpia completa de l’estructura.

Error Comú

A diferència d’un array, que decau a punter quan es passa a una funció, és a dir, es passa l’adreça del primer element, una struct no decau, es copia sencera, camp a camp. sizeof(s) dins de la funció torna a donar la mida completa, no la d’un punter.

Passar un punter a la struct

void change_grade(Student *s, float grade)
{
    s->grade = grade;
}

change_grade(&student, 9.0);

Exemple — Passar un punter a una struct

main ──&student──► change_grade() ──s->grade──► mateixa memòria

Concepte

Passar l’adreça evita la còpia i permet modificar l’original.

Memòria dinàmica amb structs

El problema dels arrays

Student students[100];

Reflexió

Què passa si no sabem quants estudiants tindrem?

Student *students = malloc(n * sizeof(Student));

Concepte

Recordeu que malloc retorna un punter a la memòria reservada al heap. El punter viu a la stack i apunta a objectes del tipus Student la memòria del heap.

malloc i free

Student *s = malloc(sizeof(Student));

s->age = 20;

free(s);

Reflexió

Qui és responsable d’alliberar aquesta memòria?

Concepte

El programa.

Linked list

Per què una linked list?

Imaginem que volem guardar un nombre variable d’estudiants, i que volem afegir-ne sense haver de reservar un array de mida fixa. I a més, volem que cada estudiant conegui el següent.

Exemple — Linked list

[10] → [20] → [30] → NULL

Concepte

Una llista enllaçada (linked list) és una estructura de dades que permet afegir i eliminar elements de manera eficient, sense necessitat de redimensionar un array. Cada element (o node) conté les dades i un punter al següent node.

Un node

typedef struct Node {
    int value;
    struct Node *next;
} Node;

Concepte

Una struct pot contenir un punter a una altra struct del mateix tipus.

Reflexió

Per què struct Node (amb nom) i no una struct anònima com al patró de Student?

Solució

Perquè dins del propi cos (struct Node *next;) encara no existeix cap typedef complet a què referir-se, només el tag struct Node. Aquest ja és prou vàlid com a tipus, perquè només en necessitem un punter (la mida d’un punter no depèn de la mida d’allò a què apunta).

La llista

Reflexió

On són aquests nodes?

Concepte

La variable head és a la stack. Els nodes són al heap.

Crear el primer node

Afegir un segon node

Recórrer i alliberar

Traversal

Concepte

current = current->next no mou el node. Mou el punter.

Alliberar la llista

while (head != NULL) {
    Node *next = head->next;
    free(head);
    head = next;
}

Error Comú

No podem fer free(head) i després llegir head->next — seria exactament un punter penjat, el mateix concepte del Pralab 03. Per això guardem next abans de fer free.

Del programa al mòdul

Una linked list ja és un mòdul

tree project

project
├── main.c
├── linkedlist.c
├── linkedlist.h
└── Makefile

linkedlist.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

typedef struct Node Node;

Node *list_create(int value);
void list_add_front(Node **head, int value);
void list_print(const Node *head);
void list_free(Node *head);

#endif

Definició

typedef struct Node Node; és un tipus incomplet (forward declaration): declara que Node existeix, sense dir encara com és per dins.

Bona Pràctica

QUI inclou linkedlist.h no pot accedir a node->value directament, perquè el compilador no en coneix els camps. Només pot fer servir les funcions que oferim. És una primera mostra real d’encapsulació. El tipus viu a la llibreria, els usuaris de la llibreria veuen només un opaque type.

linkedlist.c

#include "linkedlist.h"
#include <stdlib.h>

struct Node {
    int value;
    struct Node *next;
};

void list_add_front(Node **head, int value)
{
    Node *node = malloc(sizeof(Node));

    node->value = value;
    node->next = *head;
    *head = node;
}

Bona Pràctica

Node **head no és cap concepte nou: és exactament el mateix patró d’int ** del Pralab 04 (out-parameter, perquè la funció pugui modificar el head del cridant), amb Node en lloc d’int.

Síntesi

El mapa final

Resum

struct agrupa dades relacionades sota un mateix tipus; typedef li dona un àlies.
enum expressa un conjunt tancat de valors amb noms, per llegibilitat, no com a restricció imposada.
Una struct es copia sencera en passar-la a una funció (no decau com un array); passar-hi un punter evita la còpia.
Una linked list combina struct autoreferenciada + malloc per crear una estructura de mida variable al heap.
Igual que a la sessió de construcció: separar .h/.c permet amagar la implementació, no només organitzar el codi.

De variables a estructures de dades

Introducció