Chaining Hash Tables (in C)

This is a discussion on Chaining Hash Tables (in C) within the C Programming forums, part of the General Programming Boards category; I'm looking to make an array, and chaining duplicate hash values into a link list. I'm just unsure how to ...

  1. #1
    Deleted Account
    Join Date
    Mar 2005
    Posts
    57

    Chaining Hash Tables (in C)

    I'm looking to make an array, and chaining duplicate hash values into a link list. I'm just unsure how to start with the structs, could anyone help? The problem is i don't noe where to put the headPtr for each array element Thanks.

    i.e for a 2d link list i wud have done

    Code:
    typedef struct *list PtrList
    typedef struct *list2 PtrList2
    
    typedef struct list2
    {
       PtrList2 next;
    
    
    tyepdef struct list
    {
      PtrList next;
      PtrList2 head;
    }
    
    typedef struct overall
    {
       PtrList head;
    }

  2. #2
    {Jaxom,Imriel,Liam}'s Dad Kennedy's Avatar
    Join Date
    Aug 2006
    Location
    Alabama
    Posts
    1,065
    You'd only need one struct. It is okay to have something in your struct that you don't use in one place, but do in another.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >The problem is i don't noe where to put the headPtr for each array element
    Something like this I would imagine:
    Code:
    struct node {
      void *data;
      struct node *next;
    };
    
    struct node *table[SIZE];
    My best code is written with the delete key.

  4. #4
    Deleted Account
    Join Date
    Mar 2005
    Posts
    57
    Thanks, but I still can't pictuer it

    could you maybe expand slightly on it. thanks

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Thanks, but I still can't pictue it
    A chained hash table is nothing more than an array of linked lists. Any simpler and you have either an array or a linked list.

    >could you maybe expand slightly on it
    I already have here.

    >and maybe do it in my coding type of styling
    That I won't do. Learning to read read code is just as important as learning to write it.
    My best code is written with the delete key.

  6. #6
    Deleted Account
    Join Date
    Mar 2005
    Posts
    57
    ok..thanks alot...will try my best

  7. #7
    Deleted Account
    Join Date
    Mar 2005
    Posts
    57
    I can't seem to get it working.

    Code:
    typedef struct abc* abcPtr;
    
    .....etc
    
    typedef struct abc
    {
       defPtr head;
    }abcType;
    
    
    
    typedef struct overall
    {
        abcPtr array[20];
    } overallType

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You're making this way too complicated. Just make an array of linked lists. Hash to see what bucket to drop it in, put it in that list.
    Code:
    struct node *ptr; /* one list */
    struct node *array[ SIZE ]; /* many lists */
    Of course I very very rarely typedef, because they almost never improve readability. The only exception I've ever found is when dealing with function pointers.


    Quzah.
    Hope is the first step on the road to disappointment.

  9. #9
    Deleted Account
    Join Date
    Mar 2005
    Posts
    57
    Well, I can't change my basic struct too much, we are allow to but if you change it too much, they won't work with the function paramenters, which we can't change in our assignment.

    yea, with the typedef's, it actually helps alot with our assignment. trust me ....i might write a snippet of the code here, later....

  10. #10
    Deleted Account
    Join Date
    Mar 2005
    Posts
    57
    btw, this is my error


    ISO C90 does not support flexible array members

    for this declaration: abcPtr array[20];

  11. #11
    Deleted Account
    Join Date
    Mar 2005
    Posts
    57
    if i declare it outside, just as typedef struct abcPtr array[20], it works...why?

    [my reply]: in my code, i did #define ARRAY_SIZE without specifying the number...lol...so all works now
    Last edited by sql.scripter; 09-23-2006 at 08:02 PM.

  12. #12
    Deleted Account
    Join Date
    Mar 2005
    Posts
    57
    Ok, I've got some problems which i can't solve...

    Code:
    typedef struct abc* abcPtr;
    
    typedef struct def
    {
       defPtr next;
       char *fgh;
    }
    
    typedef struct abc
    {
       defPtr head;
    }abcType;
    
    
    
    typedef struct overall
    {
        abcPtr array[20];
    } overallType
    i get errors from the code below, or segmentation faults to be specific...
    say i've created an instance of overall as 'ov' and i pass the address of it to a function as &ov


    Code:
    for(i=0; i<20; i++)
    {
       ov->array[i]->head = NULL;
       ov->array[i] = NULL;
    }
    
    and this error also (chaining off the array)
       newNode->next = ov->array[aNumber]->head;
       ov->array[aNumber]->head = newNode;
    Last edited by sql.scripter; 09-24-2006 at 03:00 AM.

  13. #13
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Aside from the fact that your code is horribly unreadable because you inisit on typedefing everything...
    Code:
    for(i=0; i<20; i++)
    {
       ov->array[i]->head = NULL;
       ov->array[i] = NULL;
    }
    "ov" has an array of poitnters. These pointers don't point at any actual instances, so you can't try to access "head". Doing so is why your program crashes.


    Quzah.
    Hope is the first step on the road to disappointment.

  14. #14
    Deleted Account
    Join Date
    Mar 2005
    Posts
    57
    Quote Originally Posted by quzah
    Aside from the fact that your code is horribly unreadable because you inisit on typedefing everything...
    Code:
    for(i=0; i<20; i++)
    {
       ov->array[i]->head = NULL;
       ov->array[i] = NULL;
    }
    "ov" has an array of poitnters. These pointers don't point at any actual instances, so you can't try to access "head". Doing so is why your program crashes.


    Quzah.
    i'm not quite sure what you mean. could you reclarify it?

    i insist using typedef because that is provided with the startup code for my uni assignment, so yea......

  15. #15
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >i'm not quite sure what you mean. could you reclarify it?
    I get the feeling that you're not ready for this assignment yet. You should be brushing up on pointers, not hash tables.
    My best code is written with the delete key.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Iterable hash tables
    By OnionKnight in forum Tech Board
    Replies: 5
    Last Post: 07-21-2008, 02:02 AM
  2. need help with hash tables with direct chaining
    By agentsmith in forum C Programming
    Replies: 4
    Last Post: 01-05-2008, 03:19 AM
  3. Hash tables - chaining
    By cosmo1996 in forum C Programming
    Replies: 2
    Last Post: 08-14-2007, 11:53 PM
  4. Group Project Help/Volunteer
    By DarkDot in forum C++ Programming
    Replies: 3
    Last Post: 04-24-2007, 11:36 PM
  5. Help with beginning hash tables, please.
    By Will in forum C++ Programming
    Replies: 8
    Last Post: 11-17-2002, 08:51 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21