Implement Hashing Techniques for searching using linear probing or chaining.
/* Searching a hash table with hash function and separate chaining. */
#include
#include
#include
#include
#define MAXNOS 100 /* Macro definition for maximum numbers to be input */
struct ll_node /* structure of the linked list node */
{
int data; /* stores the key value */
int pos; /* stores the position in the original array */
struct ll_node *next; /* self referencing pointer to the next node */
};
struct ll_node *head = NULL; /* head pointer for the linked list */
struct ll_node *new_ptr = NULL; /* new node allocated */
struct ll_node *cur_ptr = NULL; /* stores current pointer value */
struct ll_node *prv_ptr = NULL; /* stores previous pointer value */
struct ll_node *hash_tbl[10]; /* create the hash table as an array */
/* of head pointers */
void maketble(int *); /* function prototype declaration for building a */
/* hash table and the linked list */
int hashsrch(int); /* function prototype declaration for */
/* searching in the hash table and linked list */
void main(void)
{
int a[MAXNOS] = {0}; /* array to hold the data to search from */
int srch_val; /* stores the value to be searched */
int found; /* stores the result of the search operation */
int i; /* for loop variable */
clrscr();
randomize(); /* seed number is randomized using the time value */
for (i=0; i
a[i] = random(32767) + 1;
}
for (i=0; i<10; i++)
{
hash_tbl[i] = NULL; /* initialize the ten pointers to NULLS */
}
maketble(a); /* calls the function to make a hash table */
input : /* label name for transfer of control through goto */
clrscr();
printf("Hash Table Search with Separate Chaining As Linked Lists\n");
printf("---- ----- ------ ---- -------- -------- -- ------ -----\n\n");
printf("Array of numbers to search from -\n");
for (i=0; i
printf("%2d - %-5d\t",(i+1),a[i]);
}
printf("\nPress to see the 10 linked lists.");
getch();
clrscr();
printf("Hash Table Search with Separate Chaining As Linked Lists\n");
printf("---- ----- ------ ---- -------- -------- -- ------ -----\n\n");
printf("\nContents of the ten different linked lists -\n");
for (i=0; i<10; i++)
{ /* displays the ten different linked lists */
printf("\nLast Digit of the original key = %d\n", i);
cur_ptr = hash_tbl[i]; /* extract the first node's address */
while (cur_ptr != NULL) /* process until end of linked list */
{
printf("%5d[%3d]\t", cur_ptr->data, cur_ptr->pos); /* display the data */
cur_ptr = cur_ptr->next; /* go to the next node */
} /* end of while */
} /* end of for */
printf("\n\nEnter the number to search for [ 0 to end program] - ");
flushall();
scanf("%d", &srch_val); /* ask for the value to search from */
if (srch_val == 0) /* check for program termination */
{
goto end_of_program;
}
found = hashsrch(srch_val);
/* function invoked for searching key */
if ( found == -1) /* check if key is found in data set to search from */
{
printf("\n\n\bKey = %d is NOT found in the data set.\n\n", srch_val);
getch();
}
else
{
printf("\n\n\bKey = %d is found in the data set at position = %d\n\n",
srch_val, found);
getch();
}
goto input;
end_of_program :
printf("\n\n\b End of Program\n");
getch();
}
void maketble(int *key) /* This function loads a hash table */
{ /* and the respective linked list from the given data to search from. */
int i;
int addr;
for (i=0; i
new_ptr = (struct ll_node *) malloc(sizeof(struct ll_node));
/* memory allocation for a new node is done here */
if (new_ptr == NULL)
{
printf("\bMemory allocation failed. Program abnormally terminated.\n\n");
getch();
exit(1); /* If error then abort program */
}
new_ptr->data = key[i]; /* set the data of the new node */
new_ptr->pos = i+1; /* stores the position of the number */
/* in the data set to search from */
new_ptr->next = NULL; /* initializes the next link of the new node */
addr = key[i]%10; /* hash function returns digit [0 to 9] */
if (hash_tbl[addr] == NULL) /* checks if the head pointer is null */
{
hash_tbl[addr] = new_ptr; /* first node insertion */
}
else
{ /* insert the new value into an ordered linked list */
cur_ptr = hash_tbl[addr]; /* extract the head pointer of the linked list */
prv_ptr = NULL;
while (cur_ptr != NULL && cur_ptr->data <= key[i])
{ /* first reach a last node or node with data > key value */
prv_ptr = cur_ptr; /* stores the current node's address */
cur_ptr = cur_ptr->next; /* probe into next node */
}
if (cur_ptr == hash_tbl[addr])
{ /* check if node is to be inserted before the first node */
new_ptr->next = hash_tbl[addr];
hash_tbl[addr] = new_ptr;
}
else if (cur_ptr == NULL)
{ /* check if node is to be inserted after the last node */
prv_ptr->next = new_ptr; /* update next pointer of previous node */
}
else
{ /* node is to be inserted between two existing nodes */
new_ptr->next = prv_ptr->next; /* new nodes next is set */
prv_ptr->next = new_ptr; /* previous nodes next is updated */
}
} /* end of if */
} /* end of for */
} /* end of function to load a hash table */
int hashsrch(int key) /* function definition for */
{ /* searching of the linked list */
int addr;
addr = key%10; /* hash function returns digit [0 to 9] */
cur_ptr = hash_tbl[addr];
while (cur_ptr != NULL && cur_ptr->data < key)
{ /* check and continue if last node of linked list is NOT reached */
/* and node's data is less than the key to be searched */
cur_ptr = cur_ptr->next; /* probe into next node of linked list */
}
if (cur_ptr == NULL)
{
return (-1); /* key NOT found in the linked list */
}
if (cur_ptr->data < key || cur_ptr->data > key)
{
return (-1); /* key NOT found in the linked list */
}
return (cur_ptr->pos); /* key found in the linked list */
} /* end of function for searching of the linked list and hash table */
/* Searching a hash table with hash function and separate chaining. */
#include
#include
#include
#include
#define MAXNOS 100 /* Macro definition for maximum numbers to be input */
struct ll_node /* structure of the linked list node */
{
int data; /* stores the key value */
int pos; /* stores the position in the original array */
struct ll_node *next; /* self referencing pointer to the next node */
};
struct ll_node *head = NULL; /* head pointer for the linked list */
struct ll_node *new_ptr = NULL; /* new node allocated */
struct ll_node *cur_ptr = NULL; /* stores current pointer value */
struct ll_node *prv_ptr = NULL; /* stores previous pointer value */
struct ll_node *hash_tbl[10]; /* create the hash table as an array */
/* of head pointers */
void maketble(int *); /* function prototype declaration for building a */
/* hash table and the linked list */
int hashsrch(int); /* function prototype declaration for */
/* searching in the hash table and linked list */
void main(void)
{
int a[MAXNOS] = {0}; /* array to hold the data to search from */
int srch_val; /* stores the value to be searched */
int found; /* stores the result of the search operation */
int i; /* for loop variable */
clrscr();
randomize(); /* seed number is randomized using the time value */
for (i=0; i
a[i] = random(32767) + 1;
}
for (i=0; i<10; i++)
{
hash_tbl[i] = NULL; /* initialize the ten pointers to NULLS */
}
maketble(a); /* calls the function to make a hash table */
input : /* label name for transfer of control through goto */
clrscr();
printf("Hash Table Search with Separate Chaining As Linked Lists\n");
printf("---- ----- ------ ---- -------- -------- -- ------ -----\n\n");
printf("Array of numbers to search from -\n");
for (i=0; i
printf("%2d - %-5d\t",(i+1),a[i]);
}
printf("\nPress
getch();
clrscr();
printf("Hash Table Search with Separate Chaining As Linked Lists\n");
printf("---- ----- ------ ---- -------- -------- -- ------ -----\n\n");
printf("\nContents of the ten different linked lists -\n");
for (i=0; i<10; i++)
{ /* displays the ten different linked lists */
printf("\nLast Digit of the original key = %d\n", i);
cur_ptr = hash_tbl[i]; /* extract the first node's address */
while (cur_ptr != NULL) /* process until end of linked list */
{
printf("%5d[%3d]\t", cur_ptr->data, cur_ptr->pos); /* display the data */
cur_ptr = cur_ptr->next; /* go to the next node */
} /* end of while */
} /* end of for */
printf("\n\nEnter the number to search for [ 0 to end program] - ");
flushall();
scanf("%d", &srch_val); /* ask for the value to search from */
if (srch_val == 0) /* check for program termination */
{
goto end_of_program;
}
found = hashsrch(srch_val);
/* function invoked for searching key */
if ( found == -1) /* check if key is found in data set to search from */
{
printf("\n\n\bKey = %d is NOT found in the data set.\n\n", srch_val);
getch();
}
else
{
printf("\n\n\bKey = %d is found in the data set at position = %d\n\n",
srch_val, found);
getch();
}
goto input;
end_of_program :
printf("\n\n\b End of Program\n");
getch();
}
void maketble(int *key) /* This function loads a hash table */
{ /* and the respective linked list from the given data to search from. */
int i;
int addr;
for (i=0; i
new_ptr = (struct ll_node *) malloc(sizeof(struct ll_node));
/* memory allocation for a new node is done here */
if (new_ptr == NULL)
{
printf("\bMemory allocation failed. Program abnormally terminated.\n\n");
getch();
exit(1); /* If error then abort program */
}
new_ptr->data = key[i]; /* set the data of the new node */
new_ptr->pos = i+1; /* stores the position of the number */
/* in the data set to search from */
new_ptr->next = NULL; /* initializes the next link of the new node */
addr = key[i]%10; /* hash function returns digit [0 to 9] */
if (hash_tbl[addr] == NULL) /* checks if the head pointer is null */
{
hash_tbl[addr] = new_ptr; /* first node insertion */
}
else
{ /* insert the new value into an ordered linked list */
cur_ptr = hash_tbl[addr]; /* extract the head pointer of the linked list */
prv_ptr = NULL;
while (cur_ptr != NULL && cur_ptr->data <= key[i])
{ /* first reach a last node or node with data > key value */
prv_ptr = cur_ptr; /* stores the current node's address */
cur_ptr = cur_ptr->next; /* probe into next node */
}
if (cur_ptr == hash_tbl[addr])
{ /* check if node is to be inserted before the first node */
new_ptr->next = hash_tbl[addr];
hash_tbl[addr] = new_ptr;
}
else if (cur_ptr == NULL)
{ /* check if node is to be inserted after the last node */
prv_ptr->next = new_ptr; /* update next pointer of previous node */
}
else
{ /* node is to be inserted between two existing nodes */
new_ptr->next = prv_ptr->next; /* new nodes next is set */
prv_ptr->next = new_ptr; /* previous nodes next is updated */
}
} /* end of if */
} /* end of for */
} /* end of function to load a hash table */
int hashsrch(int key) /* function definition for */
{ /* searching of the linked list */
int addr;
addr = key%10; /* hash function returns digit [0 to 9] */
cur_ptr = hash_tbl[addr];
while (cur_ptr != NULL && cur_ptr->data < key)
{ /* check and continue if last node of linked list is NOT reached */
/* and node's data is less than the key to be searched */
cur_ptr = cur_ptr->next; /* probe into next node of linked list */
}
if (cur_ptr == NULL)
{
return (-1); /* key NOT found in the linked list */
}
if (cur_ptr->data < key || cur_ptr->data > key)
{
return (-1); /* key NOT found in the linked list */
}
return (cur_ptr->pos); /* key found in the linked list */
} /* end of function for searching of the linked list and hash table */