I wrote a program which inserts and finds elements in an hash table.
Each element of the table is a dinamic list, which holds all elements
having the same hash value (calculated by an int hashFunction(char
*key, int elements) ), so the table is an array of dynamic lists.
The version of the program I've attached to this message works fine;
but it's the result of an accurate debugging. I discovered that my
problems consisted in just 4 lines of code. Now I solved them, but I
still haven't realized why! I 'd like to know what exactly was wrong
with my old code (in just 4 lines, I repeat) and what is right with
the new one.
The 4 lines of code are contained in this function:
void insertElement(elementType *table[], elementType *element){
int position;
elementType *last;
position = hashFunction(element->ID, TABLE_ELEMENTS);
elementType *elem;
elem = (table[position]);
if (elem == NULL){
table[position] = element;
}
else{
last = table[position];
while (last->next != NULL){
last = last->next;
}
last->next = element;
}
}
Now try to change the lines:
while (last->next != NULL){
last = last->next;
}
last->next = element;
with that of the old version of the program:
while (last != NULL){
last = last->next;
}
last = element;
So what's wrong with this? And why do the other four lines work? (The
more I read the two versions, the more I think they are equivalent).
Thanks
Simba
/*********************************************/
Here is the complete program:
Hint: if you want to test the two versions of the program, insert at
run time these IDs: a, b, f, l, h. (a and f, b and l, have the same
hash value).
#include <stdio.h>
#include <string.h>
#define TABLE_ELEMENTS 5
#define FALSE 0
#define TRUE 1
struct elementType{
char *ID;
char *information;
struct elementType *next;
};
typedef struct elementType elementType;
/*
hashFunction
given a key, it returns the corresponding table index
input: key, table elements
output: table index
*/
int hashFunction(char *key, int elements){
int value = 0;
for (; *key; key++){
value+= (7 * (*key));
}
return (value % elements);
}
/*
inputElement
it reads a new element
input: none
output: pointer to the element just read
*/
elementType* inputElement(){
elementType *element = (elementType*)malloc(sizeof(elementType));
element->ID = (char*)malloc(20);
element->information = (char*)malloc(20);
element->next = NULL;
printf ("ID: ");
scanf ("%s", element->ID);
printf ("Informazione: ");
scanf ("%s", element->information);
printf("\n");
return element;
}
/*
insertElement
it inserts a new element in the table
input: pointer to the table, pointer to the element
to insert
output: none
*/
void insertElement(elementType *table[], elementType *element){
int position;
elementType *last;
position = hashFunction(element->ID, TABLE_ELEMENTS);
elementType *elem;
elem = (table[position]);
if (elem == NULL){
table[position] = element;
}
else{
last = table[position];
while (last->next != NULL){
last = last->next;
}
last->next = element;
/* what's wrong?
while (last != NULL){
last = last->next;
}
last = element;
*/
}
}
/*
initializeTable
it initializes the table with the NULL value for each
element
input: pointer to the table, its number of elements
output: none
*/
void initializeTable(elementType *table[], int elements){
int i;
for(i = 0; i < elements; i++){
table[i] = NULL;
}
}
/*
printElement
it prints an element's fields
input: pointer to the element to print
output: none
*/
void printElement(elementType *element){
printf ("ID: %s\n", element->ID);
printf ("Informazione: %s\n", element->information);
printf ("\n");
}
/*
printTable
prints all the not-NULL values of the table
input: pointer to the table, its number of elements
output: none
*/
void printTable(elementType *table[], int elements){
int i;
elementType *element;
for(i = 0; i < elements; i++){
element = table[i];
while (element != NULL){
printElement(element);
element = element->next;
}
}
}
/*findElement
it finds an element in the table
input: pointer to the table, number of elements, key of
the element to find
output: element's index, if it was find
-1, else
*/
int findElement(elementType *table[], int elements, char *ID){
int position;
int found;
elementType *element;
position = hashFunction(ID, elements);
found = FALSE;
if ((table[position] != NULL) && (strcmp(table[position]->ID, ID)
== 0)){ //trovata al primo colpo
found = TRUE;
}
else{
element = table[position];
while ((element != NULL) && (found == FALSE)){
if (strcmp(element->ID, ID) == 0){
found = TRUE;
}
element = element->next;
}
}
return ((found == TRUE)? position : -1);
}
int main(){
int i;
char *key = (char*)malloc(20);
int position;
elementType *table[TABLE_ELEMENTS];
initializeTable(&table, TABLE_ELEMENTS);
printf ("Insert %d elements: \n\n", TABLE_ELEMENTS);
for (i = 0; i < TABLE_ELEMENTS; i++){
insertElement(&table, inputElement());
}
printf ("\nYou inserted:\n\n");
printTable(&table, TABLE_ELEMENTS);
printf("\n\n");
printf ("Insert a key to find: ");
scanf ("%s", key);
position = findElement(&table, TABLE_ELEMENTS, key);
if (position >= 0){
printf ("The element was found at the position %d.\n\n",
position);
}
else{
printf ("The element wasn't found.\n\n");
}
system("PAUSE");
return 0;
}
