Hi, I am having problems with my hash table program. I am implementing it with open addressing. I've been trying to debug it for hours and it is still not fixed. Thanks in advance for helping!
The file input contain names.
When I run my code, the output is:
John
Segmentation fault
The driver:
Code:
int main(void)
{
HashTable hashtable;
Entry item, //item to enter into hash table
target; //target to be searched in the hash table
int flag;
FILE *fp;
char file[MAXCHAR];
int index; //the index of where the target is located
char name[MAXCHAR];
/* Clear terminal */
system("clear");
CreateTable(hashtable);
printf("\nEnter the filename: ");
scanf("%s", file);
if((fp = fopen(file, "r")) == NULL)
Error("File failed to open.\n");
else
{
flag = fscanf(fp, "%s", &item.key);
/* Read file */
while(flag != EOF)
{
printf("%s\n", &item.key);
Insert(hashtable, item);
flag = fscanf(fp, "%s", &item.key);
}
}
fclose(fp);
printf("Enter the name you would like to search: ");
scanf("%s", target.key);
index = RetrieveTable(hashtable, target.key);
strcpy(name, target.key);
printf("%s is located in %d.\n", name, index);
}
The hash table functions
Code:
#define HASHSIZE 37
#define MAXCHAR 35
#define EQ(a,b) (!strcmp((a),(b)))
typedef char *Key;
typedef struct item {
Key key;
} Entry;
typedef Entry HashTable[HASHSIZE];
/*=====================================================================*/
/* Insert: insert an item using open addressing and linear probing.
* Pre: The hash table H has been created and is not full. H has no
* current entry with key equal to that of newitem.
* Post: The item newitem has been inserted into H.
* Uses: Hash.
*/
void Insert(HashTable H, Entry newitem)
{
int pc = 0; /* probe count to be sure that table is not full */
int probe; /* position currently probed in H */
int increment = 1; /* increment used for quadratic probing */
probe = Hash(newitem.key);
printf("probe = %d\n", probe);
while (H[probe].key != NULL && /* Is the location empty? */
strcmp(newitem.key, H[probe].key) && /* Duplicate key present? */
pc <= HASHSIZE / 2) /* Has overflow occurred? */
{
pc++;
probe = (probe + increment) % HASHSIZE;
increment += 2;
} /* Prepare increment for next iteration.*/
if (H[probe].key == NULL)
H[probe] = newitem; /* Insert the new entry. */
else if (strcmp(newitem.key, H[probe].key) == 0)
Error("The same key cannot appear twice in the hash table.");
else Error("Hash table is full; insertion cannot be made.");
}
/*======================================================================*/
/* Hash: determine the hash value of key s.
* Pre: s is a valid key type.
* Post: s has been hashed, returning a value between 0 and HASHSIZE -1
*/
int Hash(Key s)
{
unsigned h = 0;
while(*s != '\0')
{
h += *s;
*s++;
}
return (h % HASHSIZE);
}
/*======================================================================*/
/* Pre: None.
* Post: The hash table H has been created and initialized to be empty.
*
* Hash table must be created by setting the key field of each item to NULL
*/
void CreateTable(HashTable H)
{
int i;
for(i=0; i < HASHSIZE-1 ; i++)
{
H[i].key = NULL;
}
}
/*====================================================================*/
/* Pre: The hash table H has been created.
* Post: If an entry in H has key equal to target, then the function returns
* the index for the entry. Otherwise, the function returns -1.
*/
int RetrieveTable(HashTable H, Key target)
{
int location;
for(location = 0; location < HASHSIZE-1; location++)
if(EQ(H[location].key, target))
return location;
return -1;
}