TP 4 : Tableaux dynamiques

On considère la structure suivante de tableau dynamique :

In [7]:

typedef struct darray {
    int* t; // tableau utilisé pour stocker les éléments
    int size; // nombre d'éléments
    int capacity; // taille de t
} darray;

typedef struct darray { int* t; // tableau utilisé pour stocker les éléments int size; // nombre d'éléments int capacity; // taille de t } darray;

On a toujours size $\leq$ capacity et les éléments après l'indice size sont ignorés (ils sont juste là pour avoir de la place pour les prochaines insertions).

Exercice

Écrire une fonction empty de prototype darray* empty() renvoyant un pointeur sur un darray vide (avec t, size, ¢apacity égaux à NULL, 0, 0, respectivement).

Solution

In [2]:

darray* empty() {
    darray* d = (darray*)malloc(sizeof(darray));
    d->t = NULL;
    d->size = 0;
    d->capacity = 0;
    return d;
}

darray* empty() { darray* d = (darray*)malloc(sizeof(darray)); d->t = NULL; d->size = 0; d->capacity = 0; return d; }

Exercice

Écrire une fonction void print_darray(darray*) permettant d'afficher les éléments d'un darray.

Solution

In [3]:

void print_darray(darray* d) {
    for(int i = 0; i < d->size; i++)
        printf("%d", d->t[i]);
}

void print_darray(darray* d) { for(int i = 0; i < d->size; i++) printf("%d", d->t[i]); }

Exercice

Écrire une fonction copy de prototype void copy(int*, int*, n) telle que copy(t1, t2, n) recopie les n premiers éléments du tableau t1 dans le tableau t2.

Solution

In [4]:

void copy(int* t1, int* t2, int n) {
    for(int i = 0; i < n; i++)
        t2[i] = t1[i];
}

void copy(int* t1, int* t2, int n) { for(int i = 0; i < n; i++) t2[i] = t1[i]; }

Exercice

Écrire une fonction void add(darray*, int) telle que add(darray* d, int e) ajoute e à d. Si la capacité de d est insuffisante, on crééra un nouveau tableau t de taille deux fois plus grande.
Attention : Ne pas oublier le free.

Solution

In [26]:

void add(darray* d, int e) {
    if(d->size == d->capacity) {
        int* tmp = d->t; // conserve a->t pour pouvoir le free ensuite
        d->capacity *= 2;
        d->t = (int*)malloc(sizeof(int)*d->capacity);
        copy(tmp, d->t, d->size);
        free(tmp);
    }
    d->t[d->size] = e;
    d->size++;
}
darray* d = empty();
for(int i = 0; i < 4; i++)
    add(d, i);
print_darray(d);

void add(darray* d, int e) { if(d->size == d->capacity) { int* tmp = d->t; // conserve a->t pour pouvoir le free ensuite d->capacity *= 2; d->t = (int*)malloc(sizeof(int)*d->capacity); copy(tmp, d->t, d->size); free(tmp); } d->t[d->size] = e; d->size++; } darray* d = empty(); for(int i = 0; i < 4; i++) add(d, i); print_darray(d);

0123