[C] Gestione delle collisioni lineare

[n4zgul]

Salute a tutti, ho un piccolo problemino, fare una tabella hash con gestione delle collisioni lineare, ne ho fatta una tramite vettori. Inoltre la funzione di hashing deve essere basata su conversione numerica (base 7, 11 o 16). Non sono un programmatore e non so bene cosa correggere. Un aiutino please

\
/* La gestione delle collisioni viene gestita tramite concatenamento */

#include <stdio.h>
#include <conio.h>
#include <alloc.h>
#include <string.h>
#define n 50

struct studente
   {
   char matr[10];
   char cognome[15];
   char nome[15];
   };

typedef struct studente Studente;

struct record_lista
   {
   Studente info;
   struct record_lista *next;
   };

typedef struct record_lista Rec_lista;    // Crea lista per ogni locazione
della tabella di hash

Rec_lista *tab[n];        // Puntatore alla tabella hash
int ricerca1(char *x,Rec_lista *p);
int h(char *x);
void ins(Studente x ,Rec_lista **);
void leggi(Studente *x);
void ricerca(char *x,Rec_lista *);
void cancella(Studente x, Rec_lista **);
char menu(void);
int visualizza(void);
void stampalista(Rec_lista *p);

void main(void)
   {
      char risp;
      Studente a;
      int i,ok;
      char chiave[10];
      char conf;
      for (i=0;i<n;i++)tab[i]=NULL;
      do   {
            clrscr();
            risp = menu();
            if (risp == '1')
            {
               leggi(&a);                   // Legge i dati dello studente
               i=h(a.matr);
               ok=ricerca1(a.matr,tab[i]);  // Verifica se il record non sia già stato
inserito
               if(!ok) ins(a,&tab[i]);      // Inserisce il record nella locazione
calcolata
            }
            if (risp == '2')
            {
               gotoxy(1,2);
               printf("Inserire matricola da cercare: ");
               scanf("%s",chiave);
               i = h(chiave);
               ricerca(chiave,tab[i]);
            }
            if (risp == '3')

            {
               gotoxy(1,2);
               printf ("Inserire matricola da cancellare: ");
               scanf("%s", chiave);
               i=h(chiave);                         // Trova l'indirizzo della locazione
nella tabella
               ricerca(chiave, tab[i]);              // Verifica se la chiave è presente
nella locazione ottenuta al passo precedente
               printf("\nCancellare? \nS/N: ");
               getch();
               scanf("%s", &conf);
               if (conf=='s')
               {
                  cancella(a, &tab[i]);
                  printf("RECORD CANCELLATO!");
                  getch();
               }
               else
               {
                  printf("Azione annullata!");
                  getch();
               };
            }
            if(risp=='4')
            {
               visualizza();
            }
         }
   while (risp != '5');
   }



char menu()
   {
      char s;
      gotoxy(33,8); printf("1 - Inserisci record");
      gotoxy(33,10);printf("2 - Ricerca");
      gotoxy(33,12);printf("3 - Cancella record");
      gotoxy(33,14);printf("4 - Visualizza");
      gotoxy(33,16);printf("5 - Esci");
      gotoxy(35,19);printf("Scegli...");
      do s = getch();
      while ( (s!='1')&&(s!='2')&&(s!='3')&&(s!='4')&&(s!='5'));
      return(s);
   }



void ins(Studente x,Rec_lista **t)
   {
      Rec_lista *q ;
      q = (Rec_lista *)malloc(sizeof(Rec_lista));
      q->info = x;
      q->next=*t;
      *t=q;
   }


void leggi(Studente *x) // Legge da tastiera i dati dello studente
   {
    gotoxy(1,18); printf("Matricola : "); scanf("%s",x->matr);
    gotoxy(1,19); printf("Cognome   : "); scanf("%s",x->cognome);
    gotoxy(1,20); printf("Nome      : "); scanf("%s",x->nome);
   }



int h(char *x)    // Funzione di hash
   {
      int i,num;
      num=0;
      for (i=0;i<strlen(x);i++)
         num += x[i];
      num = num % n;
      return(num);
   }



void cancella(Studente x, Rec_lista **t)
   {
      Rec_lista *p;
      p=*t;
      *t=p->next;
      free(p);
   }



void ricerca(char *x,Rec_lista *p)  // Ricerca se un elemento da cancellare
è nella lista concatenata alla locazione i della tabella
   {
      int trovato = 0;
      while((p!=NULL)&&!(trovato))
         {
            if (strcmp(x,(p->info).matr)==0)
               trovato =1;
            else p=p->next;
         }
      gotoxy(25,4);
      if (trovato)
         printf("%s  %s",(p->info).cognome,(p->info).nome);
      else
         printf("Chiave non presente");
      getch();
   }



int ricerca1(char *x,Rec_lista *p) // Ricerca se un elemento da inserire è
già presente nella lista concatenata alla locazione i
   {
      int trovato = 0;
      while((p!=NULL)&&!(trovato))
         {
            if (strcmp(x,(p->info).matr)==0)
               trovato =1 ;
            else p=p->next;
         }
      if (trovato)
         {
            printf("Chiave gia' presente");
            getch();
         };
      return(trovato);
   }



void stampalista(Rec_lista *p)
   {
      printf("");
      while(p!=NULL)
         {
            printf(" |->%s  %s",(p->info).cognome,(p->info).nome);
            p=p->next;
         }
      printf("\n");
   }



int visualizza(void)   // Visualizza le posizioni assegnate dalla funzione
di hash
   {
      int i;
      clrscr();
      for (i=0;i<50;i++)
         {
            if (tab[i]==NULL)
               printf("%d: vuoto\n",i);
            else
               {
                  printf("%d:  %s  ",i);
                  stampalista (tab[i]);
               }
            if (((i+1)%10)==0)
               {
                  printf ("Continua...");
                  getch();
                  clrscr();
               }
         }
   }

[byaur]

la conversione numerica di che ?
in generale se questo <che> lo riesci a convertire in un intero poi fai l'operazione modulo <la base che ti interessa> e il risultato sara la chiave della tabella di hash cercata... naturalmente dopo le collisioni le gestisci linerealmente con il codice che hai fatto tu....



vo a dormi...

[byaur]

Originariamente inviato da n4zgul
....

 
int h(char *x)    // Funzione di hash
   {
      int i,num;
      num=0;
      for (i=0;i<strlen(x);i++)
         num += x[i];
      num = num % n;
      return(num);
   }
....

ho visto solo stamattina la tua funzione di hash...
n e globale e uguale a 50 che rappresenterebbe...

così nonè buonissima come funzione di hash,poichè la distrubuzione delle chiavi non è uniforme su tutti gli indici...
la migliore distrubuzuione si ha con n = 2...
inoltre per fare come dici tu, almeno se ho capito, basta modificare la funzione cosi...

 
int h(char *x, int base)    // Funzione di hash
   {
      int i,num, indice;
      num=0;
      for (i=0;i<strlen(x);i++)
         num += x[i];
      indice = num % base;
      return(num);
   }

dove indice è l'indice del vettore dove inserire la chiave e base è la base (7,11,16)... naturalmente se usi base 7 avrai che il range delle chiavi va da 0 a 6... e quindi di conseguenza la dimensione della hashtable ne risente...!!!

VVoVe:

[n4zgul]

Intanto grazie e scusa per la lunga assenza, ma ero a letto mezzo morto e con la febbre altissima
il numero da convertire è la matricola, in particolare la somma dei numeri che la compongono (o direttamente il numero, come verrebbe meglio?).
Il programma che ti ho dato però non gestisce le collisioni in modo lineare (ricerca della prima posizione successiva vuota) ma crea un puntatore ad un vettore per cui è possibile inserire più record nello stesso indice.
In che modo dovrei inserire la collisione in maniera lineare?
Sono semianalfabeta in programmazione