Hash table: some lines of code involving pointers

[Simone Battagliero]

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 = 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;
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;
}

 

[CBFalconer]

.... snip ...

void insertElement(elementType *table[], elementType *element){

int position;
elementType *last;

position = hashFunction(element->ID, TABLE_ELEMENTS);

elementType *elem;
elem = (table[position]);

You are using some sort of non-portable extension here. You
should not declare objects after executable code. Move these up
after "elementType...".

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).

last is a local object, not a member of the table.

For a portable functional hash system, see:

<http://cbfalconer.home.att.net/download/hashlib.zip>

 

[=?ISO-8859-1?Q?Daniel_Sj=F6blom?=]

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]);

You already got help with your problem, but the next lines can be
replaced with (unless you have some weird requirement that older
elements must come last?)

element->next = elem;
table[position] = element;

if (elem == NULL){
table[position] = element;
}
else{
last = table[position];
while (last->next != NULL){
last = last->next;
}
last->next = element;
}
}

 

[Old Wolf]

... snip ...

void insertElement(elementType *table[], elementType *element){

int position;
elementType *last;

position = hashFunction(element->ID, TABLE_ELEMENTS);

elementType *elem;
elem = (table[position]);

You are using some sort of non-portable extension here. You
should not declare objects after executable code.

C99, perhaps?

 

[Simone Battagliero]

Now try to change the lines:

last is a local object, not a member of the table.

So the problem is with the last assignment, isn't it?
You want to say that when I write

last = element;

I'm just changing a local element; instead with

last->next = element;

I change an element of the table, rigth?
Thanks for your help, CBFalconer

You already got help with your problem, but the next lines can be
replaced with (unless you have some weird requirement that older
elements must come last?)

element->next = elem;
table[position] = element;

Thanks Daniel for this nice observation.