informatique (MP2I/MPI) · Chapitre 1 · Exercice de TD

Problème — Un tableau dynamique, du contrat au coût amorti

Le langage C · niveau 3 (difficile)

Énoncé

On veut une structure de tableau qui grandit toute seule.

Définir un type tableau portant les données, la taille utilisée et la capacité.
Écrire creer, ajouter et detruire, avec leurs spécifications.
Montrer que $n$ appels successifs à ajouter coûtent $O (n)$ au total, alors qu'un appel isolé peut coûter $O (n)$ .

Corrigé de la question 1

1. Le type.


struct tableau_s {
    int* donnees;
    int taille;       /* nombre d'éléments présents */
    int capacite;     /* nombre de cases allouées, capacite >= taille */
};
typedef struct tableau_s tableau;

L'invariant de la structure est écrit dans le commentaire : $0 \leq taille \leq capacite$ , et donnees pointe sur capacite cases valides.

Question 2 : comment l'IA t'aide

2. Écrire creer, ajouter et detruire, avec leurs spécifications.

Élève

Pour ajouter, quand le tableau est plein, je pense augmenter la capacité d'une seule case : on n'alloue que ce dont on a besoin, ça me paraît plus économe.

En mémoire, oui. Mais que coûte chaque agrandissement, sachant qu'il faut recopier tous les éléments dans la nouvelle zone ? Combien coûteraient alors $n$ ajouts successifs depuis un tableau vide ?

Élève

Chaque agrandissement recopie toute la taille actuelle, donc $n$ ajouts coûtent de l'ordre de $1 + 2 + \dots + n$ : c'est quadratique. Il faudrait agrandir beaucoup moins souvent.

Quelle règle d'agrandissement rendrait les recopies rares ? Et dans creer, si la seconde allocation échoue alors que la première a réussi, que dois-tu faire avant de renvoyer NULL ?

L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.

Continue cet exercice avec l'IA

Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.

Continuer avec l'IA — gratuit, sans inscription

Gratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.

Le cours du chapitre · Tous les exercices du chapitre

Continuer avec l'IA, gratuit →