Hachage

Ce programme présente l'usage des tables de hachages.

Le fichier source est ${UPS_HOME}/upsvtm/demo/${UPS_LANGUAGE}/hachage.upl.

Mode compilé

Commande de compilation


upscmp Source=hachage.upl

Commande d'exécution


hachage

Mode interprété


upssng Source=hachage.upl

Fichier source


Source Composant "Exemple d'emploi du type Hachage" Version 4.0.0;



Procedure EcrireHachage(M:Caractere, H:HachageDe Caractere)

/********************************************************/

Variable

/******/

   C : Caractere;



Debut

Ecran.Ecrire(M);

Pour C=H.ParcoursAuDebut() JusquA H.DernierElement() Pas H.Suivant() Faire

   Ecran.Ecrire(C);

Fin Pour

Ecran.Ecrire("\n");

Fin Procedure



Procedure EcrireHachageInverse(M:Caractere, H:HachageDe Caractere)

/****************************************************************/

Variable

/******/

   C : Caractere;

   I : Entier;



Debut

Ecran.Ecrire(M);

I=H.AllouerIterateur();

Pour C=H.ParcoursALaFin(I) JusquA H.PremierElement() Faire

   Ecran.Ecrire(H.Element(I));

Fin Pour

H.LibererIterateur(I);

Ecran.Ecrire("\n");

Fin Procedure



Fonction CalculerCle(C:Caractere) Retourner Entier

/************************************************/

Debut

Si C==Nul Alors

   Retourner 0;

Fin Si

Retourner C[0];

Fin Fonction



Principal Optimiser(NePasFactoriserChaine)

/****************************************/

Variable

/******/

   H : Nul Ou HachageDe Caractere;

   H2 : Nul Ou HachageDe Caractere;

   C : Caractere;



Debut

H=HachageDe(CalculerCle,16);

H=H+"A";

H=H+"B";

H+="C";

H+="D";

H+="E";

H+="F";

H+="G";

H+="H";

H+="I";

EcrireHachage("Suivant()", H);

EcrireHachageInverse("Precedent()", H);

EcrireHachage("Gauche(3)", H.Cloner().Gauche(3));

EcrireHachage("Droite(3)", H.Cloner().Droite(3));

EcrireHachage("Milieu(2,3)", H.Cloner().Milieu(2,3));

C="a";

H2=HachageDe(CalculerCle, 16);

H2+=C;

H2+="b";

H2+="c";

H2+=C;

H2+="b";

H2+="c";

EcrireHachage("Inserer(2)", H.Cloner().Inserer(H2,2));

Ecran.Ecrire("Compter(0)");

Ecran.Ecrire(H2.Compter(C));

Ecran.Ecrire("\n");

Ecran.Ecrire("Compter(1)");

Ecran.Ecrire(H2.Compter(C,1));

Ecran.Ecrire("\n");

EcrireHachage("Remplacer(0)", H2.RemplacerTous(C, "x"));

EcrireHachage("Remplacer(1)", H2.RemplacerTous(C, "x",1));

Ecran.Ecrire("Rechercher(0)");

Ecran.Ecrire(H2.Rechercher(C));

Ecran.Ecrire("\n");

Ecran.Ecrire("Rechercher(1)");

Ecran.Ecrire(H2.Rechercher(C,1));

Ecran.Ecrire("\n");

EcrireHachage("Supprimer(0)", H2.SupprimerTous(C));

EcrireHachage("Supprimer(1)", H2.SupprimerTous(C,1));

Ecran.Ecrire("H[0]");

Ecran.Ecrire(H[0]);

Ecran.Ecrire("H[2]");

Ecran.Ecrire(H[2]);

Ecran.Ecrire("PremierElement()");

Ecran.Ecrire(H.PremierElement());

Ecran.Ecrire("DernierElement()");

Ecran.Ecrire(H.DernierElement());

Ecran.Ecrire("NumeroElement()");

Ecran.Ecrire(H.NumeroElement());

EcrireHachage("AjouterAuDebut()", H.AjouterAuDebut("X"));

EcrireHachage("AjouterALaFin()", H.AjouterALaFin("Y"));

Fin Principal

Résultat de l'exécution

Suivant() A B C D E F G H I Precedent() I H G F E D C B A Gauche(3) A B C Droite(3) G H I Milieu(2,3) C D E Inserer(2) A a a B b b C c c D E F G H I Compter(0) 2 Compter(1) 1 Remplacer(0) b b c c x Remplacer(1) a b b c c x Rechercher(0) 1 Rechercher(1) 1 Supprimer(0) b b c c Supprimer(1) a b b c c H[0] A H[2] C PremierElement() A DernierElement() I NumeroElement() 8 AjouterAuDebut() A B C D E F G X H I AjouterALaFin() A B C D E F G X H I Y