Technik_de_hashing_exploration_structure

Commenter

Contenu du snippet

/******************************************************************************
  • Techniques de hashing Exploration d une grosse base de donnies Si une *
  • structure contient : Numiro,nom,prenom,adresse, revenu... et que le *
  • fichier est non trii, on conserve dans une table de h-codes la cli d'acchs *
  • : numiro ou nom et l'adresse dans la base *
                      • Je revise ca pour demain donc il n est pas de moi mais c est C°°!*******************************************************************/

Source / Exemple : 


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define DIMTAB 1024

struct base {	/* La structure de la base */
   int       num;
   char      nom[24];
   char      prenom[24];
   char      adr[64];
   float     rev;
};

long      thash[DIMTAB];	/* La table de h-codes */

void
wh(long, char *);
void
lecinfo(void);
void
lecbase(void);
void
genstruct(struct base *);
char     *
genchar(int);

char      buffer[256];
FILE     *fich;
char      nomfich[24];
int       nb;

main(int argc, char **argv)
{

   int       i;
   /* argv[1] contient le nombre d'individus ` creer */
   if (argc != 2) {
      printf("Erreur mise en oeuvre \n");
      exit(1);
   }
   if (!(nb = atoi(*++argv))) {
      printf("\nArgument non numerique");
      exit(2);
   }
   printf("\n Nombre de personnes = %d\n", nb);
   printf("\nNom du fichier : ");
   scanf("%s", nomfich);

   printf("\nCreation du fichier %s", nomfich);

   /* Open for write */
   if ((fich = fopen(nomfich, "w+")) == NULL) {
      printf("Erreur d ouverture fichier\n");
      exit(5);
   }
   lecinfo();
   lecbase();

   fclose(fich);

   return (0);
}

void
lecinfo(void)
/* Creation de la base par generation aleatoire */
/* On utilise la fonction genstruct()           */

{
   struct base pp2;
   int       i, posfich;
   for (i = 0; i < DIMTAB; i++)
      thash[i] = 0;
   for (i = 0; i < nb; i++) {
      genstruct(&pp2);
      /* Impressions de controle */
      printf("\n pp2: %s %s %d ", pp2.nom, pp2.prenom, pp2.num);
      printf(" %s %f\n", pp2.adr, pp2.rev);
      fwrite(&pp2, sizeof(pp2), 1, fich);
      /*


           
  •  posfich donne la position de cette information dans la base 

    •        
  • /

      posfich = i * sizeof(pp2);
      /* wh cree le h-code et le stocke dans la table */
      wh(posfich, &pp2.nom);
   }
}

void
lecbase(void)
/*


     
  •  Lecture d'une information dans la base on demande la cle recherchee on

    •  
  •  calcule le h-code 

    •  
  • /

{
   struct base pp2;
   char      cle[24] = "xxx";
   int       j;
   long      posh = 0;
   while (1) {
      printf("\nCle recherchee:");
      scanf("%s", cle);
      posh = 0;
      if (strlen(cle) == 0)
	 break;
      /* Calcul de l adresse avec la fonction de h-code */
      for (j = 0; j < strlen(cle); j++)
	 posh += cle[j] * j;
      posh %= DIMTAB;
      printf("Poste de la table %d valeur %ld\n", posh, thash[posh]);
      if (thash[posh] == 0) {
	 printf("\n%s existe pas", cle);
	 continue;
      }
      fsetpos(fich, &thash[posh]);
      fread(&pp2, sizeof(pp2), 1, fich);
      if (strcmp(pp2.nom, cle) != 0)
	 do {
	    posh++;
	    fsetpos(fich, &thash[posh]);
	    fread(&pp2, sizeof(pp2), 1, fich);
	 } while (thash[posh] != 0);
      /* ce cas ne doit pas se produire */
      if (thash[posh] == 0) {
	 printf("\n%s existe pas", cle);
	 continue;
      }
      printf("cle=%s  nom=%s revenu=%f\n", cle, pp2.nom, pp2.rev);

   }
}

void
wh(long i, char *str)
/*


     
  •  calcul de la fonction de h-code : ici code ASCII * position dans cle 

    •  
  • /

{
   int       posh, j;
   posh = 0;
   for (j = 0, posh = 0; j < strlen(str); j++) {
      posh += str[j] * j;
   }
   posh %= DIMTAB;
   while (thash[posh] != 0)
      posh++;
   thash[posh] = i;
   printf("\n Controle position %d contenu %ld", posh, i);
}

void
genstruct(struct base * pp2)
/* generation aleatoire des informations */
{
   pp2->num = random(256);
   pp2->rev = 1.678 * random(31000);
   strcpy(pp2->nom, genchar(8));
   strcpy(pp2->prenom, genchar(24));
   strcpy(pp2->adr, genchar(64));

}

char     *
genchar(int n)
/* generation aleatoire d'une chaine de caracthres */
{
   char      alpha[27] = "abcdefghijklmnopqrstuvwxyz";
   int       x, j;
   char      str[256];
   strcpy(str, "");
   x = random(n - 3) + 3;
   for (j = 0; j < x; j++)
      strncat(str, &alpha[random(27)], 1);
   return (str);
}
S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (zeusdsl)