By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,847 Members | 2,392 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,847 IT Pros & Developers. It's quick & easy.

Hash table: some lines of code involving pointers

P: n/a
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;
}
Nov 14 '05 #1
Share this Question
Share on Google+
3 Replies


P: n/a
Simone Battagliero wrote:
.... 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>

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 14 '05 #2

P: n/a
CBFalconer <cb********@yahoo.com> wrote:
Simone Battagliero wrote:

... 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?
Nov 14 '05 #3

P: n/a
> > 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.


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.
Nov 14 '05 #4

This discussion thread is closed

Replies have been disabled for this discussion.