probleme la tabele de dispersie(hash table)


  1. #1
    Addicted! kyoto's Avatar kyoto nu prea este agreeat de catre ceilalti utilizatori
    Data de inscriere
    19-03-2007
    Locaţie
    ECU
    Sex
    M
    Mesaje
    1,613
    Mesaje bazar
    98
    Putere Reputatie
    0
    Reputatie
    -17
    Puncte CF
    20.0
    Usergroups:

    probleme la tabele de dispersie(hash table)

    dupa cum spune si titlul, am intampinat probleme la implementarea in standard C, a unui program ce lucreaza cu tabele de dispersie
    trebuie sa precizez ca eu am ales ca metoda de solutionare a coliziunilor prin inlantuire
    LE: asta e codul meu pana acum:
    Cod:
    #include<conio.h>
    #include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    #include<string.h>
    
    //Here we define our list structure
     typedef struct _List_t{
      char *string;
      struct _List_t *next;
    }List_t;
    //Here we define our hashtable itself
     typedef struct _HashTable_t{
      int size;
      List_t **table;
    }HashTable_t;
    
    //Here we will create our hashtable and reserve memory for it
      HashTable_t CreateTable(int);
      HashTable_t CreateTable(int *size)
       {
        HashTable_t *NewTable;
          NewTable=(HashTable_t*)malloc(sizeof(HashTable_t));
          NewTable->table=(List_t**)malloc(sizeof(List_t));
    
    	  NewTable->size=*size;
        //the table elements must be set to NULL
          for(int i=0;i<NewTable->size;i++)
              NewTable->table[i]=NULL;
      return *NewTable;
       }
    //Defining the hash function
     unsigned int hash(HashTable_t,char []);
     unsigned int hash(HashTable_t hashtable, char str[])
      {
       int hashval=0;
       int *a,*b,*p;
     
       if (str!=NULL)
         {
    		 for(int i=0;i<20;i++)
               hashval=str[i]*(*a);
    		   hashval=(hashval+(*b))%(*p);
         }
       return hashval%hashtable.size;
      } 
    
    //We need to define our search function
     List_t search(HashTable_t, char[]);
     List_t search(HashTable_t hashtable, char str[])
        {
        List_t *list;
        unsigned int hashval;
         list=(List_t*)malloc(sizeof(List_t));
    	 hashval=hash(hashtable,str);
            for(list=hashtable.table[hashval];list->next!=NULL;list=list->next)
             if(strcmp(str,list->string))
              return *list;
         }
    
    //We need the insertion function
     int insert(HashTable_t,char[]);
     int insert(HashTable_t hashtable, char str[])
      {
       List_t *NewList;
       List_t *CurentList;
       unsigned int hashval=hash(hashtable,str);
      //CurentList is used as a sentinel, to see if our key is already in the table
         CurentList=(List_t*)malloc(sizeof(List_t));
    	 *CurentList=search(hashtable,str);
    	   if(CurentList)
    		   printf("Element already  there, try again!");
    	   free(CurentList);
    	   exit(0);
    //If the elemnt is not redundant we'll insert it
         NewList=(List_t*)malloc(sizeof(List_t));
         
    	 strcpy(NewList->string, str);
    	 NewList->next=hashtable.table[hashval];
         hashtable.table[hashval]=NewList;
       return 0;
      }
    
    //The Clearkey function only erases the given key, Clear Table on the other hand erases the entire table
    
    void ClearKey(HashTable_t hashtable,char str[]);
    void ClearKey(HashTable_t hashtable,char str[])
     {
    	List_t *list,*temp;
    	int hashval=hash(hashtable,str);
          //The index of the table is actually the head of the list
    	  list=hashtable.table[hashval];
    	  while(list!=NULL)
    	  { 
          //If we found what we are looking for erase it
    	    if(list->string=str)
    	      {
    	      temp=list;
    	      list=list->next;
    	      free(temp);
    	      }
    	   }
     }
    
     void ClearTable(HashTable_t);
     void ClearTable(HashTable_t *hashtable)
      {
    	List_t *list,*temp;
    	
    	 if(hashtable!=NULL)
    	   for(int i=0;i<hashtable->size;i++)
    		{
    		 list=hashtable->table[i];
    	     while(list!=NULL)
    	      {
    		  temp=list;
    		  list=list->next;
    		  free(temp);  
    	      }
    	    }
    	free(hashtable->table);
    	free(hashtable);
      }
    
    void main()
    {
    HashTable_t MyHashTable;
    char s[20];
    int a,b,p,selection,TableSize=12;
    
    MyHashTable=CreateTable(TableSize);
    
    printf("HashTable created!\n");
    for(int i=0;i<MyHashTable.size;i++)
      printf("%d",MyHashTable.table[i]);
       
    printf("hash function is (A*Key+B)Mod P)Mod %d",MyHashTable.size);
       printf("enter the value for A:");scanf("%d",&a);
       printf("enter the value for B:");scanf("%d",&b);
       printf("enter the value for P:");scanf("%d",&p);
    
    printf("Select an operation\n");
    printf("1. Insert   2. Search   3. Erase   Other=Quit\n");
      scanf("%d",&selection);
      printf("Your selection is:%d",selection);
    
    printf("\nEnter the key:");
     scanf("%c",s);
    
    while(selection<5){
    	if(selection=1)
    		insert(MyHashTable,s);
    	else if(selection=2)
    		search(MyHashTable,s);
    	else if(selection=3)
            ClearKey(MyHashTable,s);
    	else
    		printf("Invalid Selection");
    	         }
    getch();
    }
    Last edited by kyoto; 17-08-2010 at 14:55.
    romanu' n-are noroc, dar se pricepe la tot

    Visul romanesc, cosmarul europei

  2. #2
    Addicted! kyoto's Avatar kyoto nu prea este agreeat de catre ceilalti utilizatori
    Data de inscriere
    19-03-2007
    Locaţie
    ECU
    Sex
    M
    Mesaje
    1,613
    Mesaje bazar
    98
    Putere Reputatie
    0
    Reputatie
    -17
    Puncte CF
    20.0
    Usergroups:
    l-am refacut si am rezolvat
    asadar se poate inchide
    Last edited by kyoto; 11-09-2010 at 21:18.
    romanu' n-are noroc, dar se pricepe la tot

    Visul romanesc, cosmarul europei
    Vrei mai putine reclame? Inregistreaza-te sau logheaza-te

  3. #3
    Trance Addicted! Reaver's Avatar Reaver este o raza de lumina in ochii tuturor Reaver este o raza de lumina in ochii tuturor Reaver este o raza de lumina in ochii tuturor Reaver este o raza de lumina in ochii tuturor Reaver este o raza de lumina in ochii tuturor Reaver este o raza de lumina in ochii tuturor
    Data de inscriere
    29-09-2005
    Locaţie
    Far, far away!
    Varsta
    43
    Sex
    M
    Mesaje
    1,994
    Mesaje bazar
    226
    Putere Reputatie
    47
    Reputatie
    598
    Puncte CF
    41.0
    Usergroups:
    Din cate vad eu, ai implementat un set, nu un hashtable. Un hashtable poate stoca perechi <key, value> si face hash pe key.
    Vrei mai putine reclame? Inregistreaza-te sau logheaza-te

Google+

Cautati logo-ul CraiovaForum?

Iata cateva variante: