can I have two typedef with the same name but different things inside of it?
Printable View
can I have two typedef with the same name but different things inside of it?
You cannot have two typedefs with the same name, period.Quote:
Originally Posted by -EquinoX-
Sure, as long as they aren't in the same file and never get #included together.
Why would you want to? That would be very confusing.
hmm.. can I cast a typedef? it's basically just a pointer right?
No. A typedef names a type. It has nothing to do with pointers or any other kind of variable. What are you trying to do?Quote:
Originally Posted by -EquinoX-
so I have this:
when I call LinkedListConstruct it returns Words*, when I call HashTableConstruct I want it to return a similar thing too.. Words*, but my hashtable function returns a HashTable* which is a different kind of struct from Words*Code:struct node_t{
char* word;
bla.. bla.. bla
}
typedef struct node_t Words;
So why not call one LinkedListNode and the other HashTableNode?Quote:
Originally Posted by -EquinoX-
I can't because I have a file that I can't change and that file does:
Words* f = DictionaryConstruct(some argument here); <== I can't change this!
and inside dictionary construct I have two types of construct, one is a hashtable construct and a bst construct.. which both returns a different type of struct.. and on the other hand I need to return a pointer to a struct called *Words
I mean when constructing a linked list and a bst, you got two different things going on at the same time:
in a struct of a linked list I have the next node (which is basically another struct inside a struct) I have the data itself. in a bst in the struct I have a left and right tree which is another struct inside a struct and the data
So what you're really asking is "can I make a function return two different things, depending on the phase of the moon and other unrelated things?" The answer is no -- DictionaryConstruct must always return the same type; it should never return sometimes a hashtable and sometimes a search tree. Pick one.
hmm.. so I can only return one? okay then, I'll have to figure out another way through this then.. by the way if I am implementing a hashtable, how can I get all the elements in that hash table if I don't know the key? is there a way to traverse a hash table?
hmm..let me explain my situation here more clearly:
so I have a code optimization assignment to be done. The program basically just takes two files,
first it stores the list of words in a data structure unsortedly in a hash table. Second it takes the second file, which is also a list of words. Before storing the second list of words into a binary tree I want to check first if that word exists in the first file, by checking the hash table. If it does exist then I put that word in a binary tree. In other words, two similar words that exists on both files are put inside a binary tree.
The problem is I have this code that I can't change or do anything to it:
Words* fd = Construct(..)
Words is just a pointer to a struct evertime it constructs that list of words file into a linked list (the current implementation is a linked list). But my HashTable returns a pointer to a struct which supports a hash table, a struct with key and values inside and my BinaryTree returns a pointer to a struct which is a binary tree struct/node that has a left and right subtree.
On the assumption your hash table is an array of linked lists, you can walk each linked list in order.
yes, my hash table is an array of linked list.. so I have to check each array slot it there's a data in that linked list? I guess this wouldn't be so efficient right
is there a way to iterate over a hash table and get the data one by one in a sorted way?
Unless your array of lists is somehow exponentially larger than it needs to be, traversal of a hash table is just as efficient of traversal of anything else; most every traversal is O(n) since you have to visit every item once.Quote:
Originally Posted by -EquinoX-
Unless your hashing mechanism and list-inserting mechanism are very carefully designed, traversal of a hash table will not be in sorted order.
I understand that this will not be a sorted order and that's why I want to traverse the HashTable and put the elements into an array and then sort it using the build in qsort that C has in library.
If you read my problem above, about optimization .. what would you suggest? I understand that using a binary tree would solve this, but inserting into a binary takes O(n log n) and I need something faster
It doesn't actually have to be that much bigger than needed to start making a difference. I recently worked on a project (CornedBee's game of life challenge, actually), where I discovered that using a better hash function actually led to worse iteration performance.Quote:
Originally Posted by tabstop
I could not believe it myself at first. Some investigation with a profiler revealed that the "smart" hash function was spreading things out better (as it was supposed to), but this caused performance to DECREASE when iterating over all the elements in the table, since so much time was spent looking in empty buckets. A good spread makes lookup/insertion more efficient but can actually hurt iteration. So there you go.
This was a normal set of affairs, not a pathological case. So I reverted back to the stupid hash function which didn't spread things out very well, and got the performance back up.
Hmmm. I can't see how spreading things out would cause more empty buckets? Or do you mean that empty buckets were so fast to search (i.e., you don't search them at all) that searching three longer lists was faster than searching twenty shorter lists?Quote:
Originally Posted by brewbuck
tabstop can you answer my question?
My suggestion would be, if you expect a large number of "Words" in your dictionary, and you have to at any point list a set of them in sorted order, to keep a bst around. If you're only going to do "this word was not found" and look up a single word at a time, a hashtable would be fine.
the thing is that after looking at single words and see it they exist or not and store them in a hash table and until that part it's find.. BUT I will have to write that hash table out into a file and it has to BE in a sorted order.. how can I do this with a hash table?
? Insertion into a binary tree is O(log n), or O(n) if you forget to scramble before you build the tree and end up with a linked list.
Average case is O(log2n).
Worst case is O(n).
Mergesort? (IOW: sort each linked list, and then compare the top of each list, write out the first alphabetically, throw it away, and repeat.)Quote:
Originally Posted by -EquinoX-
so I have to write a mergesort to do this? you mean compare each of the front of the list?Quote:
Originally Posted by tabstop
Right. So the question comes down to, when do you want to pay the piper? Insertion into a bst costs O(log n), perhaps O(n), but output in sorted order comes free with any O(n) traversal. Insertion into a hashtable is more or less free (O(1) certainly), but now you have (number-of-linked-lists + 1) sorting problems, and that will cost O(n log n) at the end of the day.Quote:
Originally Posted by -EquinoX-
Edit to add: So n*log(n) for the bst, provided you have even a little bit of randomness in your original word list, vs O(n log n) at the end for the hashtable, which looks more or less like a draw, unless you find yourself sorting often.
Mergesort seems like the obvious choice to me. If your number of linked lists is a power of 2 (or even if it isn't), it will actually make life better to merge them two at a time in the "normal" way rather than try to merge however-many different lists into one.Quote:
Originally Posted by -EquinoX-
the thing is that I have to have an iterator.. I have to have a next method and that will give me the next word in the sorted list
so say my list is
apple
orange
giraffe
and I create an iterator and it goes apple, orange, etc...
do you mean I do a merge sort and put it inside an array?
Ook. Honestly, if it were me? I would add an extra spot in my struct Word or whatever it's called for a link to the next word in line. Read in all the words, put them in a bst, traverse the tree with an extra static pointer keeping track of the previous entry, and set a link from previous to next every step. You could do the same with a hashtable, of course; sort each linked list, and then set links across the lists in the mergesort style.Quote:
Originally Posted by -EquinoX-
tabstop,
I can't change this, I must have an iterator.. there are parts of the code that I can't change, it's like the interface..
hmm..but would it be much faster if I am doing this in a Hash Table?
another easiest thing to do is to store this in a bst that has a threaded pointer.. so I can just traverse them.. but I don't know how fast is this going to be compared to using a hash table
as if I have a really really large list of words that is unsorted that I wan't to insert into a bst it will take a while.. but with the hash table, it's just O(1)
anyone??