Table d adressage dispersé

J AI UNE PB DANS UN PROJET EN ++ C SVP M 'AIDER





ENONCE Implémentation d'une Table d'adressage dispersé
La table d'adressage dispersé est une structure de données stockant des chaînes de
caractères de manière à accélérer leur recherche
Page 2
Comme la figure le montre, la structure de données comporte deux parties:
1. Une table d'adressage dispersé consiste en un tableau de m cases
2. chaque case du tableau contient un pointeur vers le premier noeud (tète) d'une liste
chainée contenant des chaines de caractères, certaines cases peuvent être vides.
Une chaîne apparaît dans exactement une de ces liste.
Pour insérer une chaine C dans cette table d'adressage, nous appliquons à C une
fonction de hachage h telle que h(C) retourne un entier compris entre 0 et m-1. Dans ce
cas, cette chaine est insérée au début de la liste d'indice h(C) dans la table d'adressage,
si elle n'existe pas déjà.
Pour déterminer si une chaine C existe dans la table, nous appliquons la même fonction
h(C), si C existe dans la table d'adressage alors C est dans la liste numéroté h(C), il faut
alors parcourir cette liste pour le vérifier.
Fonction de hachage
Une approche convenable pour le calcul des fonctions de hachage consiste à procéder
comme suit:
La taille m du tableau étant fixée au préalable.
1. Déterminer un entier positif h à partir des valeurs des codes ascii des caractères
C1, C2, .., Ck de la chaine C. il s'agit ic d'additionner les valeurs entières des
caractères de la chaîne.
2. Convertir l'entier h déterminé ci-dessus en un numéro de liste, c'est-à-dire un
entier entre 0 et m-1. Il s'agit en fait de prendre le reste de la division de h par m.
On vous demande de
1. implémenter le TDA ADR donnée dans la page suivante:
2. Ecrire un programme permettant à travers un menu
général de tester les différentes primitives (insertion,
recherche, tri,..)
Page 3
/************************************************** ***************
* Fichier : ADRPRIM.H
* Contenu : Déclaration des primitives du TDA Table Adressage Dispersé
************************************************** ****************/
#ifndef _ADRPRIM_H
#define _ADRPRIM_H
#include "ELTPRIM.H"
#include "ADRSDD.H"
TAB_ADRESSAGE ADRCreer(void);
void ADRDetruire(TAB_ADRESSAGE);
int estVide(TAB_ADRESSAGE);²
int estSaturee(TAB_ADRESSAGE);
int ADRTaille(TAB_ADRESSAGE);
int rechercher(TAB_ADRESSAGE, ELEMENT);
int inserer(TAB_ADRESSAGE, ELEMENT);
// insère l'élément dans la table d'adressage en tête de la liste correspondante à
sa valeur de hachis
int insererLexico(TAB_ADRESSAGE, ELEMENT);
// insère l'élément dans la table d'adressage selon l'ordre lexicographique
void ADRTrier(TAB_ADRESSAGE);
//Trie les éléments de chaque liste selon l'ordre lexicographique
int supprimer(TAB_ADRESSAGE, ELEMENT);
void ADRAfficher(TAB_ADRESSAGE);
TAB_ADRESSAGE ADRCopier(TAB_ADRESSAGE);
int ADRComparer(TAB_ADRESSAGE, TAB_ADRESSAGE);
#endif