Telekin
asked on
hash table with chaining using a dynamic array
I'm trying to create a hash table using chaining and I need to use a dynamic array because if the load of the table gets to a certain point, I need to rehash using a larger table size. I'm using MSVC++ 6.0 and it's throwing some errors that I'll include later. First off, here is my linked list (the chaining part) struct:
struct Node{
struct Node *Next;
int Data;
};
My dynamic array:
struct Node *HashTable;
HashTable = new Node[HASH_TABLE_SIZE];
Now I'm trying to use that as the hash table and to make it larger I do:
HashTable = new Node[NEW_HASH_TABLE_SIZE];
This is the error MSVC++ 6.0 is giving me:
htchain.cpp(139) : error C2501: 'HashTable' : missing storage-class or type specifiers
htchain.cpp(139) : error C2040: 'HashTable' : 'int' differs in levels of indirection from 'struct Node *'
htchain.cpp(139) : error C2440: 'initializing' : cannot convert from 'struct Node *' to 'int'
This conversion requires a reinterpret_cast, a C-style cast or function-style cast
I can't even initialize the table, let alone ever expand it. I tried making a basic dynamic array like this:
int *vector = new int[10];
And that works, but if I try this, it throws the same error:
int *vector;
vector = new int[10];
The odd thing is that if I do:
int *vector = new int[10]; //or this:
struct Node *HashTable[HASH_TABLE_SIZE
There are no errors (but then I can never expand the table size, and that's my problem in the first place!). I'd really appreciate any help, this is really important.
struct Node{
struct Node *Next;
int Data;
};
My dynamic array:
struct Node *HashTable;
HashTable = new Node[HASH_TABLE_SIZE];
Now I'm trying to use that as the hash table and to make it larger I do:
HashTable = new Node[NEW_HASH_TABLE_SIZE];
This is the error MSVC++ 6.0 is giving me:
htchain.cpp(139) : error C2501: 'HashTable' : missing storage-class or type specifiers
htchain.cpp(139) : error C2040: 'HashTable' : 'int' differs in levels of indirection from 'struct Node *'
htchain.cpp(139) : error C2440: 'initializing' : cannot convert from 'struct Node *' to 'int'
This conversion requires a reinterpret_cast, a C-style cast or function-style cast
I can't even initialize the table, let alone ever expand it. I tried making a basic dynamic array like this:
int *vector = new int[10];
And that works, but if I try this, it throws the same error:
int *vector;
vector = new int[10];
The odd thing is that if I do:
int *vector = new int[10]; //or this:
struct Node *HashTable[HASH_TABLE_SIZE
There are no errors (but then I can never expand the table size, and that's my problem in the first place!). I'd really appreciate any help, this is really important.
ASKER
I tried that and it still throws an error.
struct Node *HashTable;
HashTable = new struct Node[HTABLESIZE];
Error:
htchain.h(127) : error C2501: 'HashTable' : missing storage-class or type specifiers
htchain.h(127) : error C2040: 'HashTable' : 'int' differs in levels of indirection from 'struct Node *'
htchain.h(127) : error C2440: 'initializing' : cannot convert from 'struct Node *' to 'int'
This conversion requires a reinterpret_cast, a C-style cast or function-style cast
I can't expand the array because it will throw the same error as above. I'm thinking maybe it has something to do with the fact that the dynamic array is a pointer and the struct has a pointer in it too? I'm not sure, dynamic arrays are a little new to me, but I have been searching online for quite some time and nothing seems to work.
struct Node *HashTable;
HashTable = new struct Node[HTABLESIZE];
Error:
htchain.h(127) : error C2501: 'HashTable' : missing storage-class or type specifiers
htchain.h(127) : error C2040: 'HashTable' : 'int' differs in levels of indirection from 'struct Node *'
htchain.h(127) : error C2440: 'initializing' : cannot convert from 'struct Node *' to 'int'
This conversion requires a reinterpret_cast, a C-style cast or function-style cast
I can't expand the array because it will throw the same error as above. I'm thinking maybe it has something to do with the fact that the dynamic array is a pointer and the struct has a pointer in it too? I'm not sure, dynamic arrays are a little new to me, but I have been searching online for quite some time and nothing seems to work.
ASKER
Could this be the problem?
void HashTableCreate(void)
{
int i;
for(i=0; i<HTABLESIZE; i++){
HashTable[i] = 0;
}
}
Should the initialization be HashTable[i] = null; ?
void HashTableCreate(void)
{
int i;
for(i=0; i<HTABLESIZE; i++){
HashTable[i] = 0;
}
}
Should the initialization be HashTable[i] = null; ?
I'll admit that I guessed at that. :( Sorry.
How cumbersome will it be to typedef the struct?
typedef struct
{
TNode *Next;
int Data;
} TNode;
Some compilers (most, actually) will give an error on the "TNode *Next;" statement as "TNode" isn't yet defined. You'll need a "forward reference" indication and after having been at my desk for about 18 hours so far today it escapes me. :(
It might be as simple as "typedef TNode;" but my brain really is on "frazzle" right now.
Kdo
How cumbersome will it be to typedef the struct?
typedef struct
{
TNode *Next;
int Data;
} TNode;
Some compilers (most, actually) will give an error on the "TNode *Next;" statement as "TNode" isn't yet defined. You'll need a "forward reference" indication and after having been at my desk for about 18 hours so far today it escapes me. :(
It might be as simple as "typedef TNode;" but my brain really is on "frazzle" right now.
Kdo
ASKER
Alright, I tried it again (and I looked up the forward reference at google) and this is what I came up with:
struct node; //forward reference
typedef node *Node; //typedef
struct node
{
Node Next;
int Data;
};
Node *HT; //create dynamic array
HT = new Node[100]; //try to allocate space
This still gives me the same 3 errors... I don't know what's going on. I found this at the following link (linked list basics) http://www.cecs.csulb.edu/~maples/cecs274/C++Notes/C++Ch4B.doc
I appreciate your help very much. I'm still unsure how to do this however. I'm starting to think that I should just create another array like Node *HT[NEWSIZE] and just copy everything from the old list to the new one (rehashing of course into the new table size). I guess this kind of defeats the purpose of dynamic arrays doesn't it? If you have any other ideas I'd be grateful.
struct node; //forward reference
typedef node *Node; //typedef
struct node
{
Node Next;
int Data;
};
Node *HT; //create dynamic array
HT = new Node[100]; //try to allocate space
This still gives me the same 3 errors... I don't know what's going on. I found this at the following link (linked list basics) http://www.cecs.csulb.edu/~maples/cecs274/C++Notes/C++Ch4B.doc
I appreciate your help very much. I'm still unsure how to do this however. I'm starting to think that I should just create another array like Node *HT[NEWSIZE] and just copy everything from the old list to the new one (rehashing of course into the new table size). I guess this kind of defeats the purpose of dynamic arrays doesn't it? If you have any other ideas I'd be grateful.
try this :
typedef struct _Node{
struct Node *Next;
int Data;
}Node;
Node *HashTable;
HashTable = new Node[HASH_TABLE_SIZE];
HashTable = new Node[NEW_HASH_TABLE_SIZE];
Peter
typedef struct _Node{
struct Node *Next;
int Data;
}Node;
Node *HashTable;
HashTable = new Node[HASH_TABLE_SIZE];
HashTable = new Node[NEW_HASH_TABLE_SIZE];
Peter
ASKER
Still errors:
typedef struct _Node{
struct Node *Next; //<----- previous declaration of Node
int Data;
}Node; //error C2371: 'Node' : redefinition; different basic types, see declaration of 'Node'
Node *HashTable;
HashTable = new Node[HTABLESIZE]; //error C2501: 'HashTable' : missing storage-class or type specifiers
//error C2040: 'HashTable' : 'int' differs in levels of indirection from 'struct Node *'
As you can see, I can't even declare HashTable as a new array of Nodes with an original size, let alone with a rehashed size. I've even tried a few things that I'm not sure would affect (like Node **HashTable), but I still have errors.
typedef struct _Node{
struct Node *Next; //<----- previous declaration of Node
int Data;
}Node; //error C2371: 'Node' : redefinition; different basic types, see declaration of 'Node'
Node *HashTable;
HashTable = new Node[HTABLESIZE]; //error C2501: 'HashTable' : missing storage-class or type specifiers
//error C2040: 'HashTable' : 'int' differs in levels of indirection from 'struct Node *'
As you can see, I can't even declare HashTable as a new array of Nodes with an original size, let alone with a rehashed size. I've even tried a few things that I'm not sure would affect (like Node **HashTable), but I still have errors.
put your declaration inside h file with ifndef and include it in cpp file:
Node.h file:
#ifndef __NODE_H
#define __NODE_H
typedef struct _Node{
struct Node *Next;
int Data;
}Node;
#endif
in cpp file :
#include "Node.h"
Node *HashTable;
HashTable = new Node[HTABLESIZE];
Node.h file:
#ifndef __NODE_H
#define __NODE_H
typedef struct _Node{
struct Node *Next;
int Data;
}Node;
#endif
in cpp file :
#include "Node.h"
Node *HashTable;
HashTable = new Node[HTABLESIZE];
ASKER
I tried what you said and the compiler gives me an error that says error C2371: 'Node' : redefinition; different basic types. It is referring to the struct Node *Next inside the typedef struct _Node.
#ifndef __NOODE_H
#define __NOODE_H
typedef struct _Node{
struct Node *Next;
int Data;
}Node; //error: redefinition of struct Node
#endif
If I change the last Node to something else, i.e. "}Node;" becomes "}LNode;" then the program compiles without any errors. When it comes to creating an instance, however, the compiler gives me the same three errors:
error C2501: 'HashTable' : missing storage-class or type specifiers
error C2040: 'HashTable' : 'int' differs in levels of indirection from 'struct _Node *'
error C2440: 'initializing' : cannot convert from 'struct _Node *' to 'int'
This conversion requires a reinterpret_cast, a C-style cast or function-style cast
#ifndef __NOODE_H
#define __NOODE_H
typedef struct _Node{
struct Node *Next;
int Data;
}Node; //error: redefinition of struct Node
#endif
If I change the last Node to something else, i.e. "}Node;" becomes "}LNode;" then the program compiles without any errors. When it comes to creating an instance, however, the compiler gives me the same three errors:
error C2501: 'HashTable' : missing storage-class or type specifiers
error C2040: 'HashTable' : 'int' differs in levels of indirection from 'struct _Node *'
error C2440: 'initializing' : cannot convert from 'struct _Node *' to 'int'
This conversion requires a reinterpret_cast, a C-style cast or function-style cast
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
I tried the hash table from scratch using what you advised and it works! However, I still have a little problem. The way I'm initializing the hash table (in the constructor for my hash table class) is to set all the nodes to 0 initially:
for (int i=0; i<HASH_TABLE_SIZE; i++){
HashTable[i] = 0; //<-- error here
}
It throws this error:
error C2679: binary '=' : no operator defined which takes a right-hand operand of type 'const int' (or there is no acceptable conversion)
Also, for referencing a single node within the hash table, I do this:
struct Node *p;
for(p=HashTable[i]; p!=0;){ //<-- error
//do something if Node is not initialized 0 (null)
}
It throws this error:
error C2679: binary '=' : no operator defined which takes a right-hand operand of type 'struct Node' (or there is no acceptable conversion)
There are several references of this type in my code and they work when I used the old hash table code:
struct Node* HashTable[size];
Instead of the new:
Node *HashTable;
HashTable = new Node[size];
As you can see, I need to initialize the hash table nodes to something in order to tell if there is a node there or not (for fear of referencing something that isn't there and crashing my program). Would you have any suggestions that would work in this case?
for (int i=0; i<HASH_TABLE_SIZE; i++){
HashTable[i] = 0; //<-- error here
}
It throws this error:
error C2679: binary '=' : no operator defined which takes a right-hand operand of type 'const int' (or there is no acceptable conversion)
Also, for referencing a single node within the hash table, I do this:
struct Node *p;
for(p=HashTable[i]; p!=0;){ //<-- error
//do something if Node is not initialized 0 (null)
}
It throws this error:
error C2679: binary '=' : no operator defined which takes a right-hand operand of type 'struct Node' (or there is no acceptable conversion)
There are several references of this type in my code and they work when I used the old hash table code:
struct Node* HashTable[size];
Instead of the new:
Node *HashTable;
HashTable = new Node[size];
As you can see, I need to initialize the hash table nodes to something in order to tell if there is a node there or not (for fear of referencing something that isn't there and crashing my program). Would you have any suggestions that would work in this case?
ASKER
Great job and quick response, didn't quite solve my entire problem though.
We've gotten past the big hurdle. :) Just a couple of little bumps to go.
With regards to the compilation errors, I assume that you create the table as a table of Nodes, not a table of pointers to Nodes. If so, you probably want to initialize the Node structures, not pointers. In your loop:
for (int i=0; i<HASH_TABLE_SIZE; i++){
HashTable[i] = 0; //<-- error here
}
replace the line in error with:
memset (&HashTable[i], 0, sizeof (Node));
The same concept with the second error:
struct Node *p;
for(p=HashTable[i]; p!=0;){ //<-- error
//do something if Node is not initialized 0 (null)
}
'p' is a pointer to a Node, and HashTable[i] is a node. Just modify the line so that the reference is to the address of HashTable[i] using the '&' operator.
Kdo
With regards to the compilation errors, I assume that you create the table as a table of Nodes, not a table of pointers to Nodes. If so, you probably want to initialize the Node structures, not pointers. In your loop:
for (int i=0; i<HASH_TABLE_SIZE; i++){
HashTable[i] = 0; //<-- error here
}
replace the line in error with:
memset (&HashTable[i], 0, sizeof (Node));
The same concept with the second error:
struct Node *p;
for(p=HashTable[i]; p!=0;){ //<-- error
//do something if Node is not initialized 0 (null)
}
'p' is a pointer to a Node, and HashTable[i] is a node. Just modify the line so that the reference is to the address of HashTable[i] using the '&' operator.
Kdo
I assume that these are code snippets, your hash table is wrapped by a class, and that resizing the hash table is a class method?
Editing your code directly, try this:
struct Node *HashTable;
HashTable = new struct Node[HASH_TABLE_SIZE];
HashTable = new struct Node[NEW_HASH_TABLE_SIZE];
Kdo