Hello everyone, I'm not that much of a talker so I'll get straight to the point: I need to implement a hash table in C++, After reading about this topic and algorithms from the book by Cormen, I started to implement it. I wrote it, but it doesn't work how it should. Ran out of ideas.
this is what I have so far:
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
int a,b,p;
//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,int*,int*,int*,char);
unsigned int hash(HashTable_t hashtable,int *a,int *b,int *p, char str[])
{
int hashval=0;
if (str!=NULL)
{
for(int i=0;str[i];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,a,b,p,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,*a,*b,*p,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,*a,*b,*p,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("\n");
printf("The hash function is (A*Key+B)Mod P)Mod %d\n",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();
}
