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

---

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.

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

---

Thanks, but I still can't pictuer it :(

could you maybe expand slightly on it. thanks

>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. :rolleyes:

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

ok..thanks alot...will try my best :D

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

---

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.

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 :D....i might write a snippet of the code here, later....

btw, this is my error


ISO C90 does not support flexible array members

for this declaration: abcPtr array[20];

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

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;

---

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.

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

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

well, this assignment is an extension of a previous assignment. the first one was a basic singly list list and a binary tree. this assignment is a array with chained linked lists and a binary splay tree.

i'm just unsure how to deal with array of pointers, which is why i'm struggling with it.

Code:

---

struct foo {
    int bar;
};
...
struct foo *baz;
...
baz->bar = 10; /* segfault in the making */

---

Baz doesn't actually point to an allocated instance of 'struct foo', so you can't try to access 'bar'.


Quzah.

Code:

---

struct foo {
    int bar;
};
...
struct foo *baz;
...
baz->bar = 10; /* segfault in the making */

---

hmmm...but that's not what i wrote....i think

in main.c, i created an instance...of say in your example of foo, i.e foo newFoo, and then i pass it's address into a function, i.e &newFoo. Then i would do newFoo->bar = 10;

Quote:

---

Originally Posted by vdk_au

hmmm...but that's not what i wrote....i think

---

It's called teaching. I was showing you that you can't access the members of a structure via a pointer, if your pointer doesn't actually point to anything. Now let's look back at my last post, to see if you can make the connection:

Quote:

---

Originally Posted by quzah

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.

---

There's another problem with this code, that you'd have, if you actually allocated space. It would be a memory leak. But, since you didn't actually allocate anything for your array of pointers to point at, you get a crash.


Quzah.