tp nf16 printemps

TP 3 La structure de Buckets

(description et partie 1)

Objectif et données initiales :

Vous faire découvrir une structure de donnée qui mixte les tableaux et les listes chaînées.
Elle s'applique dans le cas où on gère des objets qui ont les propriétés suivantes :

chaque objet possède un "OID" (object identifier)

chaque objet possède une donnée "cle" qui est entière

chaque objet possède des données "data"

OID[clé] est un opérateur qui donne la valeur de clé de l'objet (accès au champ "cle")

idem pour OID[data]

tous les objets sont tels que : 0 <= OID[cle] < U

U n'est pas "trop grand"

les objets sont équitablement répartis dans l'intervalle [0 ... U-1] en tenant compte de leur clé

Par exemple, les objets peuvent être des enregistrements.
Un champ clé existe. Tous les enregistrements
sont stockés dans un tableau de structure de taille maximale NMAX.
Le nombre d'objet n est <= NMAX.
A partir de là on peut facilement définir les opérateurs d'accès
aux informations (OID[clé], OID[data], etc.)

Notations : floor(i) désigne la partie entière inférieure de i
modulus(a,b) retourne a modulo b

Idées de base :

découper l'intevalle [0...U-1] en :

B intervalles de largeur commune L = floor(U/B)

un dernier intervalle de largeur L'=modulus(U,B)

les intervalles sont numérotés de 0 à B

l'intervalle numéro i :

avec i appartenant à [0, ..., B-1], correspond à des valeurs de clés dans l'intervalle [i*L, ..., (i+1)*L[ (et on a donc B intervalles

avec i=B, correspond à des valeurs de clés dans l'intervalle [i*L, ..., U-1] (et on a donc le B+1 ième intervalle de largeur L')

A l'intervalle numéro i correspond donc à un "seau" (bucket) dans lequel on va ranger tous les OID des objets dont la
valeur de clé appartient à l'intervalle. On a donc besoin de structures de données supplémentaires.

Par exemple, si U=17 et B=5 on a L=3. Donc pour :

i=0, on a l'intervalle [0...3[
i=1, on a l'intervalle [3...6[
i=2, on a l'intervalle [6...9[
i=3, on a l'intervalle [9...12[
i=4 (soit B-1), on a l'intervalle [12...15[
i=5 (soit i=B), on a l'intervalle [15...16] (soit [i*L, ..., U-1])

(conseil : faites un petit dessin pour essayer de comprendre)

Enoncé

On gère un tableau Bucket de B+2 listes chaînées. A une liste chaînées pointée par B[i] correspondra un bucket.
On gère les bucket avec des tableaux. Un OID est un entier. Voici les tableaux nécessaires :

Bucket un tableau d'entier de taille B+2 (pourquoi +2 ? voir plus bas), Bucket[i] retourne un indice pour obtenir des informations dans les autres tableaux
Elem tableau d'entier (int) de taille n pour stocker des OID
Next tableau d'entier (int) de taille n pour stocker les chaînages avants
Prev tableau d'entier (int) de taille n pour stocker les chaînages arrières

A un même indice j de Elem, Next et Pred correspondra un paquet d'informations sur un élément
de bucket (ou aucune information).

Exemple, posons j=Bucket[i] :

Elem[j] retourne l'OID du premier objet du bucket numéro i
Next[j] = k est l'indice où sont rangées les informations sur l'élément suivant du même bucket
Prev[j] = m est l'indice où sont rangés les informations sur l'élément précédent du même bucket

Next[j]=-1 signifie que la liste (le bucket) est terminée (c'est le "nil"). Prev[j]=-1 signifie que l'objet dans le bucket
n'a pas de prédécésseur (c'est la tête de la liste).
Donc j<-Bucket[i] c'est tete_de_L !

(conseil : faites un petit dessin pour essayer de comprendre et montrez-le à votre chargé de TD,
on vous dira alors si vous avez compris ou non les idées de base)

La structure de bucket en langage C est donc la suivante :

typedef struct bucket {
        int U; /* valeur maximale de U */
        int B; /* nombre de listes désirées + 2 pour gerer la liste de recuperation, voir le cours sur les listes chainee partie "la gestion memoire" */
        int n_max; /* nombre d'elements maximum a gerer */
        int n_present; /* nombre d'elements actuellement geres dans le bucket */
        int * les_seaux; /* le tableau d'entier qui, pour chaque bucket donne l'indice dans les tableaux Elem, Next et Prev */
                                   /* ou se trouve les informations du premier objet du bucket , le seau supplémentaire (le dernier) est pour la liste
                                      de recuperation */
        int * Elem; /* pointeur vers le tableau des OID geres, dynamiquement sur alloue dans la zone du tas par un (int *)malloc((sizeof(int)*n) */
        int * Next; /* pointeur vers le tableau dedie au chainage avant , dynamiquement sur alloue dans la zone du tas par un (int *)malloc((sizeof(int)*n) */
        int * Prev; /* pointeur vers le tableau dedie au chainage arriere , dynamiquement sur alloue dans la zone du tas par un (int *)malloc((sizeof(int)*n) */
} Bucket;

Il vous suffit donc d'un copy/paste pour avoir cette structure (toute modification est interdite).

MAIS, dans cette première partie vous n'en avez pas besoin.
Nous décrivons le sujet dans sa globalité pour l'instant.

Voici ce que vous allez faire dans le TP3 : la gestion des données de base, c-à-d les "objet".

Les données :

On gère en plus un tableau de structure "Objet".
La déclaration est de la structure est :

typedef struct objet {
         int oid; /* un entier identifiant l'objet de facon unique */
         int cle; /* un entier positif correspondant a la valeur de cle de l'objet */}
         char descriptif[50]; /* c'est en fait ce nous avons appele "DATA", ici un descriptif sous forme de texte de l'objet gere */
Objet;

Nous venons de décrire le type de base que nous allons gérer (dans le futur) au sein de
la (future) structure de bucket que vous allez concevoir.

Dans un premier temps les objets seront rangés tout simplement dans un tableau
d'objet.

La structure qui gére le tableau est :

typdef struct t_objet{
    int n_max; /* nombre d'objet maximum gérable dans le tableau */
    int n_present; /* nombre d'objet présents dans le tableau */
    Objet * tab_objet; /* un pointeur sur le tableau d'objet, qui sera alloue dynamiquement sur la zone du tas avec (Objet *)malloc(sizeof(Objet)*n_max)) */
} T_objet;

Première partie : la gestion du tableau d'objet

ATTENTION :
le nom du fichier source sera impérativement "tp3_NF160<compte>.c" et le
nom du fichier de trace sera impérativement "tp3_NF160<compte>.txt".
Où vous remplacerez "<compte>" par votre numéro de compte.
Exemple : si vous êtes le compte NF16023, vos fichiers se nommeront "tp3_NF16023.c" et "tp3_NF16023.txt"

Vous utiliserez un variable globale DONNEES qui vaut 0 initialement et qui vaudra 1 dès qu'un tableau
d'objet aura été créé.

C'est la seule et unique variable globale que vous utiliserez.
C'est une contrainte que vous devrez impérativement respecter.
Si nous en trouvons une autre, le TP sera noté zéro !

On fixe :

#define UMAX 64
#define NMAX 1024

Bien que cela ne soit pas encore utile, mais au moins cela sera fait !

Repondez aux questions associées aux points à traiter dans le fichier de trace.

concevoir une fonction dont le prototype est :
T_objet * creer_tableau(int nmax);
elle crée un tableau de nmax objet avec un malloc (Cf. supra) et l'initialise correctement.
Elle met à jour la variable DONNEES.
Si le tableau existe déjà, elle retournera le pointeur NULL.

Q : dans quelles conditions cette fonction retourne le pointeur NULL ?

concevoir une fonction dont le prototype est :
int objet_dans_le_tableau(T_objet * tableau, Objet * obj);
Elle répond -1 si l'objet n'est pas dans le tableau et l'emplacement de l'objet (l'indice) s'il est dans le tableau.

Q : quelles sont ses complexités en notations GRAND_OMEGA et GRAND_O ?
justifiez clairement.

concevoir une fonction simple dont le prototype est :
int czi_un_objet(Objet * obj);
elle effectue la saisie des caractéristiques d'un objet.
MAIS pas directement dans le tableau, dans une variable tampon intermédiaire !
On vérifira que 0<=cle <= UMAX, si c'est le cas la fonction retourne 1 et 0 sinon.
idem pour oid qui doit être >=0 et pour le nombre de caractère qui doit être <=49.

concevoir une fonction dont le prototype est :
int range_un_objet(T_objet * tableau, Objet * obj);
Elle range un nouvel objet dans le tableau sauf : s'il existe déjà ou si le tableau est plein (gestion des débordement).
Elle retourne 1 si l'opération s'est bien déroulée et 0 sinon.
On ne tolérera pas les "trous" dans le tableau, les objets seront toujours contigus.

Q : quelle solution proposez-vous pour répondre au dernier point du cahier des charges de cette fonction ?
Q : cette fonction ne permet pas de distinguer les cas d'échecs de "rangement" pourquoi ?

concevoir une fonction dont l'en-tête est :
int supprime_objet(T_objet * tableau, int num);
qui supprime l'objet dont l'OID est num du tableau d'objet.
AVANT d'invoquer cette fonction il faudra vérifier que l'objet existe dans le tableau !
Elle retourne 1, si l'opération s'est bien déroulé 0 sinon.

à partir de ces fonctions de base qui seront impérativement implémentées telles
qu'elles sont définies, concevez un menu qui permette de créer un tableau d'objet, de saisir un objet
d'en supprimer un du tableau, de les consulter en précisant un OID et de les afficher tous par paquet de 5 objets.

7/
Pour une utilisation claire (pour l'utilisateur) les fonctions :
T_objet * creer_tableau(int NMAX);
int range_un_objet(T_objet * tableau, Objet * obj);
int supprime_objet(T_objet * tableau, int num);

sont insuffisantes.

Sans toucher au cahier des charges de ces fonctions (vous ne les modifiez pas une fois
qu'elles répondent au cahier des charges), ajouter d'autres fonctions
qui les utilisent et améliorent les fonctionnalités.

Pour savoir pourquoi creer_tableau, range_un_objet, et supprime_objet ont échoué par exemple.