Étude des tableaux associatifs
Préliminaires
L’épreuve est composée d’un problème unique, comportant 34 questions. Le problème consiste en l’étude et l’implémentation d’un tableau associatif en C, suivant différentes méthodes.
Le problème est divisé en 4 sections distinctes :
-
l’implémentation du tableau associatif en utilisant une structure d’arbre (section 1),
-
l’ajout d’un « ramasse miettes » pour gérer la mémoire (section 2),
-
l’implémentation du tableau associatif en utilisant un algorithme probabiliste (section 3),
-
la conception d’un analyseur syntaxique pour créer un tableau associatif à partir d’une chaîne de caractères (section 4).
Les quatre sections sont indépendantes.
Travail attendu
Les résultats attendus pour certaines questions pourront être admis afin de faciliter la résolution des questions suivantes. Le langage C constitue l’unique langage autorisé pour le traitement des questions de programmation.
Une attention particulière sera portée quant à la correction et la lisibilité du code proposé.
Si une tolérance raisonnable peut être envisagée sur certains aspects syntaxiques dans le cadre d’une épreuve réalisée sur support papier (par exemple, l’oubli d’un « ; »), un code difficilement lisible ou l’emploi de fonctions ou structures de contrôle non conformes aux standards du langage C, notamment celles empruntées à d’autres langages, sera sanctionné.
Un soin particulier sera également apporté à la gestion de la mémoire, à la bonne initialisation des structures ainsi qu’au contrôle systématique des allocations mémoires.
La gestion rigoureuse des erreurs sera valorisée (l’utilisation d’assert est recommandée), de même que la qualité, la simplicité et la lisibilité du code.
En conformité avec le programme officiel, il sera admis que certains en-têtes standards soient présupposés comme inclus dans le code : , , , , , , et .
Les tableaux associatifs
Les tableaux associatifs
sont des structures de données permettant un accès rapide à une valeur à partir d’une clef. Afin de simplifier l’écriture du code, nous considèrerons que les clefs sont toujours de type char* et les valeurs de type int.
1 – Implémentation par un arbre binaire de recherche Le but de cette section est d’étudier une implémentation d’un tableau associatif reposant sur un arbre binaire de recherche.
Nous adopterons une approche fonctionnelle pour l’implémentation des structures de données, en les considérant comme immuables. Ainsi, chaque fonction de manipulation renverra systématiquement une nouvelle version modifiée de la structure, sans altérer l’originale.
Cette méthode présente l’avantage d’éliminer les effets de bord lors des appels de fonction. Toutefois, elle implique une augmentation du nombre d’allocations mémoire, puisque chaque modification nécessite la création d’une copie de la structure de données.
Dans cette section nous ne nous occuperons pas de la récupération de la mémoire, car nous introduirons en section 2 un « ramasse miettes » pour gérer la mémoire automatiquement.
Arbre binaire de recherche
Définitions : Soit A un arbre binaire de recherche. On notera avec une lettre minuscule (par exemple x ou y) un nœud de A, et avec une lettre majuscule (par exemple {T_1,T_2} ou {T_3}) un sous-arbre de A.
Soit x un nœud, on notera {x_{\mathrm{gauche}}} et {x_{\mathrm{droit}}}, respectivement le sous-arbre gauche et le sous-arbre droit de x. On rappelle que la taille d’un arbre est égale au nombre de nœuds qu’il contient.
Pour un arbre de racine x, on notera h(x) sa hauteur, et on définit récursivement la hauteur d’un arbre par :
-
la hauteur d’un arbre vide est {-1},
-
{h(x)=\max(h(x_{\mathrm{gauche}}),h(x_{\mathrm{droit}}))+1}.
Pour un arbre de racine x, on définit la valeur d’équilibre par : {e(x)=h(x_{\mathrm{gauche}})-h(x_{\mathrm{droit}})} On qualifiera d’équilibré un arbre binaire de recherche A si pour tout nœud x de A, {-1\le e(x)\le1} Définition : On définit un nœud d’un arbre binaire de recherche par la structure suivante :
|
1 2 3 4 5 6 7 8 |
struct abrNoeud_s { char* clef; int valeur; struct abrNoeud_s* fils_gauche; struct abrNoeud_s* fils_droit; }; typedef struct abrNoeud_s abrNoeud; |
On utilisera la valeur du champ clef pour ordonner les nœuds de l’arbre, en utilisant l’ordre alphabétique.
La signature de la fonction est :
|
1 |
char* copie_chaine(char* chaine) |
Indication C : On considèrera que la chaîne de caractères passée en paramètre (chaine) n’est jamais NULL.
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres