Hash table: some lines of code involving pointers

Discussion in 'C Programming' started by Simone Battagliero, Apr 14, 2004.

  1. 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;
    }
    Simone Battagliero, Apr 14, 2004
    #1
    1. Advertising

  2. Simone Battagliero

    CBFalconer Guest

    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 () ()
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net> USE worldnet address!
    CBFalconer, Apr 14, 2004
    #2
    1. Advertising

  3. Simone Battagliero wrote:
    > 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;
    > }
    > }




    --
    Daniel Sjöblom
    Remove _NOSPAM to reply by mail
    =?ISO-8859-1?Q?Daniel_Sj=F6blom?=, Apr 14, 2004
    #3
  4. Simone Battagliero

    Old Wolf Guest

    CBFalconer <> 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?
    Old Wolf, Apr 16, 2004
    #4
  5. > > 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.
    Simone Battagliero, Apr 16, 2004
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Oliver Wong
    Replies:
    5
    Views:
    432
    Oliver Wong
    Nov 2, 2005
  2. Christopher Benson-Manica

    Pointer arithmetic involving NULL pointers

    Christopher Benson-Manica, Sep 10, 2004, in forum: C Programming
    Replies:
    22
    Views:
    938
    Dan Pop
    Sep 14, 2004
  3. cerr

    pointers, pointers, pointers...

    cerr, Apr 7, 2011, in forum: C Programming
    Replies:
    12
    Views:
    654
  4. rp
    Replies:
    1
    Views:
    494
    red floyd
    Nov 10, 2011
  5. Srijayanth Sridhar
    Replies:
    19
    Views:
    596
    David A. Black
    Jul 2, 2008
Loading...

Share This Page