Vous avez récupéré le code source et le fichier trace de vos collègues qui développent si bien du code.
Copiez-les dans une nouvelle directory "TP4"
Utilisez la commande unix "mv" pour les nommer "tp4_NF160<compte>.c" et "tp4_NF160<compte>.txt".
Maintenant ils sont à vous, vous en héritez, vous êtes content ?
Désormais vous compléterez ce code et ce fichier de trace (en précisant pour toute nouvelle
note de développement votre numéro de compte et le numéro du TP).

ATTENTION :
le nom du fichier source sera impérativement "tp4_NF160<compte>.c" et le
nom du fichier de trace sera impérativement "tp4_NF160<compte>.txt".
Où vous remplacerez "<compte>" par votre numéro de compte.

Exemple : si vous êtes le compte NF16023, vos fichiers se nommeront "tp4_NF16023.c" et "tp4_NF16023.txt"

Attention modification (29/10/02) :

Vous utiliserez une autre variable globale C_BUCKET qui vaut 0 initialement
et qui vaudra 1 dès qu'une variable de type Bucket aura été correctement initialisée.
C'est la deuxième  variable globale que vous utiliserez (pas d'autres impératif).

fin de modif

Deuxième partie : (listes chaînées dans des tableaux )

On se préoccupe des listes chaînées mais pas encore des intervalles correspondant à la structure
de bucket.
Donc même si elles apparaissent, les informations B et U n'ont pour l'instant pas d'importance.
Sauf pour une question qui prépare la partie 3.

La structure de bucket est donc la suivante (rappel ) :

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 géré 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;

Comme vous l'avez maintenant compris, on va gérer simultanément plusieurs listes chaînées
dans les tableaux Elem, Next et Prev.

ATTENTION pour mettre au point votre code vous fixerez B=3, donc 3 listes et une liste de récupération.

1/

concevoir une fonction dont le prototype est :
Bucket * creer_la_structure_de_bucket(int U, int B, int n_max);
qui retourne un pointeur vers une structure de bucket correctement initialisée.
n_max est un entier qui donne le nombre maximum de cellule au sein des différents tableaux.
Attention a bien initialiser la structure ! Justifier dans le fichier tp4_NF160<compte>.txt

Q : La B+1 ième liste est la liste de récupération que vaut-elle initialement ?

2/

concevoir une fonction dont le prototype est :
int enleve_liste_recup(Bucket * mon_bucket);
Si la liste de récupération est vide
Q : quelle est la liste de récupération ?
Q : c-à-d ???? expliquer dans tp4_NF160<compte>.txt au moment de l'écriture de la fonction
alors elle retourne -1
sinon cette fonction détache proprement la cellule de tête de la liste de récupération
et retourne l'indice associé à la cellule détachée.
 

4/

concevoir une fonction dont le prototype est :
int enleve_liste_numero(Bucket * mon_bucket,int numero);
Si la liste mon_bucket->les_seaux[numero] est vide alors elle retourne -1
sinon cette fonction détache proprement la cellule de tête de la liste numero
et retourne l'indice associé à la cellule détachée.

Q : la fonction  int enleve_liste_recup(Bucket * mon_bucket); devient-elle redondante ?
      si oui en quoi ?
expliquer dans tp4_NF160<compte>.txt au moment de l'écriture de la fonction

5/

concevoir une fonction dont le prototype est :
int ajoute_liste(Bucket * mon_bucket, int numero_de_cellule, int num_liste);
cette fonction attache proprement la cellule numero_de_cellule en tête de la liste num_liste
et retourne l'indice associé à la cellule attachée.
 

6/

concevoir une fonction dont le prototype est :
int PopFrom( Bucket * Bu, int num);
qui retire le premier objet du bucket numéro num de la structure de bucket Bu et
retourne son OID.
On veillera à ne pas perdre de cellule dans la nature !
 

7/

concevoir une fonction dont le prototype est :
void PushInto(Bucket * Bu, Objet * obj, int num);
qui insère dans la structure de bucket Bu, en tête du bucket numéro num, l'OID de l'objet obj.

8/

concevoir une fonction dont le prototype est :
int RemoveFrom( Bucket * Bu, int num, int OID);
qui retire correctement l'objet d'indentifieur OID du bucket numéro num de la structure de bucket Bu.
(il n'est plus nécessairement en tête, attention aux corrections de chaînages !)

9/ ATTENTION : petite coquille corrigée le 29/10/02

concevoir une fonction dont le prototype est :
int Where(int U, int B, int cle);
qui retourne un numéro de bucket compris entre 0 et B en fonction de U, de B et de cle.
(on trouve quel seau correspond à clé !)
 

10/ ATTENTION : petite coquille corrigée le 29/10/02

concevoir une fonction dont le prototype  est :
int SearchInBucket( Bucket * Bu, Objet * obj);
qui retourne le numéro du seau ou se trouve rangé l'objet
et -1 (et non 0) s'il n'est pas trouvé dans le bucket.

Q : quelle sont ses complexités en notation GRAND_OMEGA et GRAND_O ?
       (en général PAS dans le cas test où le nombre de seau est 3 !)
expliquer dans tp4_NF160<compte>.txt au moment de l'écriture de la fonction
 
 

11/

concevoir une fonction dont le prototype  est :
int NotInBucket( Bucket * Bu, Objet * obj);
qui répond 1 si l'objet obj n'est pas déjà dans la structure de bucket et 0 sinon

Q : cette fonction est-elle redondante ? Si oui en quoi ? Expliquer comment utiliser une
autre fonction déjà construite pour faire le travail. Où se trouvent les
différences dans l'emploi de l'une ou l'autre des fonctions concernées ?
expliquer dans tp4_NF160<compte>.txt au moment de l'écriture de la fonction
 

12/

concevoir une fonction dont le prototype est :
int StoreInBucket( Bucket * Bu, Objet * obj, int num);
Si l'objet est déjà dans la structure de bucket Bu, on ne range rien et on retourne 0
sinon range l'objet obj dans la structure de bucket Bu dans le bucket numéro num et retourne 1.

13/

concevoir une fonction dont le prototype est :
int PrintBucket( Bucket * Bu, int num);
qui affiche par paquet de 10 les informations utiles stockées dans la liste num du bucket Bu.
 

14/

concevez un menu général qui permette de choisir entre un menu qui gère les données initiales (menu_data que
vous avez dèjà fait en partie 1) et un nouveau menu qui permette de tester et gérer la structure de bucket.
Vous concevrez ce dernier menu, on l'appelera menu_buck.

ATTENTION :

Réfléchissez et justifiez vos choix.
En effet, il faut gérer intelligemment la liste de récupération lors les ajouts et suppressions dans LES listes
qui constituent la structure de bucket.