-------------------------------------------------------------------- Trace d'execution d'un prg de hashcode But : tester si tout marche AlgoSdec : correction de l'exercice F. Balmas May 2002 -------------------------------------------------------------------- // les commandes sont les suivantes // a = ajouter // c = chercher // s = supprimer bach [HASHCODE] a.out // debut du prg, la table est vide >> a toto // ajout d'un 1er elt, il faut creer la freelist Freelist vide ...A nouveau 5 chainons a disposition Freelist : 4 chainons // apres chaque operation, nb d'elts dans freelist Paquet 0 : [] // + detail de la table Paquet 1 : [] Paquet 2 : [] Paquet 3 : [] Paquet 4 : [toto ] // l'elt a ete mis dans le paquet 4 >> a otto // 1 elt avec les memes lettres Freelist : 3 chainons // la freelist decroit Paquet 0 : [] Paquet 1 : [] Paquet 2 : [] Paquet 3 : [] Paquet 4 : [otto toto ] // l'elt est mis dans le meme paquet >> a niche // 1 autre elt Freelist : 2 chainons Paquet 0 : [] Paquet 1 : [] Paquet 2 : [] Paquet 3 : [] Paquet 4 : [niche otto toto ] >> a chien // encore 1 autre Freelist : 1 chainons Paquet 0 : [] Paquet 1 : [] Paquet 2 : [] Paquet 3 : [] Paquet 4 : [chien niche otto toto ] >> a table // apres celui-ci la freelist est vide Freelist : 0 chainons Paquet 0 : [table ] Paquet 1 : [] Paquet 2 : [] Paquet 3 : [] Paquet 4 : [chien niche otto toto ] >> a balte // nouvel ajout --> reconstitution de la freelist Freelist vide ...A nouveau 5 chainons a disposition Freelist : 4 chainons Paquet 0 : [balte table ] Paquet 1 : [] Paquet 2 : [] Paquet 3 : [] Paquet 4 : [chien niche otto toto ] >> a ecran // encore quelques elts pour remplir les paquets Freelist : 3 chainons // et verifier le fonctionnement de la freelist Paquet 0 : [balte table ] Paquet 1 : [ecran ] Paquet 2 : [] Paquet 3 : [] Paquet 4 : [chien niche otto toto ] >> a nacre Freelist : 2 chainons Paquet 0 : [balte table ] Paquet 1 : [nacre ecran ] Paquet 2 : [] Paquet 3 : [] Paquet 4 : [chien niche otto toto ] >> a crane Freelist : 1 chainons Paquet 0 : [balte table ] Paquet 1 : [crane nacre ecran ] Paquet 2 : [] Paquet 3 : [] Paquet 4 : [chien niche otto toto ] >> a chine Freelist : 0 chainons Paquet 0 : [balte table ] Paquet 1 : [crane nacre ecran ] Paquet 2 : [] Paquet 3 : [] Paquet 4 : [chine chien niche otto toto ] >> a titi // nouvelle reconstitution de la freelist Freelist vide ...A nouveau 5 chainons a disposition Freelist : 4 chainons Paquet 0 : [balte table ] Paquet 1 : [crane nacre ecran ] Paquet 2 : [titi ] Paquet 3 : [] Paquet 4 : [chine chien niche otto toto ] >> c titi // chercher 1 elt qui est dans une liste a 1 seul elt Mot connu // ca marche Freelist : 4 chainons Paquet 0 : [balte table ] Paquet 1 : [crane nacre ecran ] Paquet 2 : [titi ] Paquet 3 : [] Paquet 4 : [chine chien niche otto toto ] >> c niche // chercher 1 elt qui est au milieu d'une liste Mot connu // ca marche Freelist : 4 chainons Paquet 0 : [balte table ] Paquet 1 : [crane nacre ecran ] Paquet 2 : [titi ] Paquet 3 : [] Paquet 4 : [chine chien niche otto toto ] >> c toto // chercher 1 elt qui est en fin de liste Mot connu // ca marche Freelist : 4 chainons Paquet 0 : [balte table ] Paquet 1 : [crane nacre ecran ] Paquet 2 : [titi ] Paquet 3 : [] Paquet 4 : [chine chien niche otto toto ] >> c chine // chercher 1 elt qui est en debut de liste Mot connu // ca marche Freelist : 4 chainons Paquet 0 : [balte table ] Paquet 1 : [crane nacre ecran ] Paquet 2 : [titi ] Paquet 3 : [] Paquet 4 : [chine chien niche otto toto ] >> c blate // chercher 1 elt inconnu, qui devrait se trouver dans // une liste qui contient des elts Mot inconnu // ca marche Freelist : 4 chainons Paquet 0 : [balte table ] Paquet 1 : [crane nacre ecran ] Paquet 2 : [titi ] Paquet 3 : [] Paquet 4 : [chine chien niche otto toto ] >> c titj // chercher 1 elt inconnu, qui devrait se trouver dans // une liste vide Mot inconnu // ca marche Freelist : 4 chainons Paquet 0 : [balte table ] Paquet 1 : [crane nacre ecran ] Paquet 2 : [titi ] Paquet 3 : [] Paquet 4 : [chine chien niche otto toto ] >> a titj // ajout de cet elt pour verifier qu'il va bien dans // une liste vide Freelist : 3 chainons // OK Paquet 0 : [balte table ] Paquet 1 : [crane nacre ecran ] Paquet 2 : [titi ] Paquet 3 : [titj ] Paquet 4 : [chine chien niche otto toto ] >> s foo // supprimer un elt qui n'existe pas Freelist : 3 chainons // rien ne se passe, rien n'est modifie Paquet 0 : [balte table ] // c'est correct Paquet 1 : [crane nacre ecran ] Paquet 2 : [titi ] Paquet 3 : [titj ] Paquet 4 : [chine chien niche otto toto ] >> s titj // supprimer 1 elt qui est dans une liste a 1 elt Freelist : 4 chainons // ca marche, la freelist grandit Paquet 0 : [balte table ] Paquet 1 : [crane nacre ecran ] Paquet 2 : [titi ] Paquet 3 : [] Paquet 4 : [chine chien niche otto toto ] >> s nacre // supprimer 1 elt qui est au milieu d'une liste Freelist : 5 chainons // ca marche Paquet 0 : [balte table ] Paquet 1 : [crane ecran ] Paquet 2 : [titi ] Paquet 3 : [] Paquet 4 : [chine chien niche otto toto ] >> s chine // supprimer 1 elt qui est au debut d'une liste Freelist : 6 chainons // ca marche Paquet 0 : [balte table ] Paquet 1 : [crane ecran ] Paquet 2 : [titi ] Paquet 3 : [] Paquet 4 : [chien niche otto toto ] >> s toto // supprimer 1 elt qui est en fin de liste Freelist : 7 chainons // ca marche Paquet 0 : [balte table ] Paquet 1 : [crane ecran ] Paquet 2 : [titi ] Paquet 3 : [] Paquet 4 : [chien niche otto ] >> a foo // ajout ... Freelist : 6 chainons Paquet 0 : [balte table ] Paquet 1 : [crane ecran ] Paquet 2 : [titi ] Paquet 3 : [] Paquet 4 : [foo chien niche otto ] >> s balte // serie de suppression pour vider toute une liste Freelist : 7 chainons Paquet 0 : [table ] Paquet 1 : [crane ecran ] Paquet 2 : [titi ] Paquet 3 : [] Paquet 4 : [foo chien niche otto ] >> s table Freelist : 8 chainons // ca marche Paquet 0 : [] Paquet 1 : [crane ecran ] Paquet 2 : [titi ] Paquet 3 : [] Paquet 4 : [foo chien niche otto ] >> s blate // supprimer 1 elt inexistant Freelist : 8 chainons // pas de probleme Paquet 0 : [] Paquet 1 : [crane ecran ] Paquet 2 : [titi ] Paquet 3 : [] Paquet 4 : [foo chien niche otto ] >> c table // chercher 1 elt qu'on vient de supprimer Mot inconnu // il n'y est plus Freelist : 8 chainons Paquet 0 : [] Paquet 1 : [crane ecran ] Paquet 2 : [titi ] Paquet 3 : [] Paquet 4 : [foo chien niche otto ] >> c balte // idem Mot inconnu Freelist : 8 chainons Paquet 0 : [] Paquet 1 : [crane ecran ] Paquet 2 : [titi ] Paquet 3 : [] Paquet 4 : [foo chien niche otto ] >> // le programme semble raisonnablement fonctionner bach [HASHCODE]