Help with beginning hash tables, please.

[imported_Will]

recently my mom has become obsessed with "word jumbles" in our local paper, which are scrambled letters that you have to unscramble to form a word. for example, the correct answer to "btior" is "orbit."

sometimes she gets to one she can't solve though, (and annoys the family with requests for help) and so I decided to write a program to just do them automatically.

I'm planning to later compare the permutations that it generates to a word list, but for now, I'm just printing out all the possible combinations and letting the user sift through them.

someone suggested setting up a hash table with the word list stored in it. I don't know anything about hash tables, however, so this would be a good learning opportunity. from what I have looked up online, I should make an array of linked lists to prevent collisions.

here is where I get confused though. how could I dynamically create linked lists? what I mean is, you obviously can't do something like

for (int X = 1; X < 20; X++)
{
list<string> listX;
}
I think I know (knew) some method on how to do something like this, but it's hazy now.

another question: will I have to create a linked list class from scratch? I've previously used linked lists, but they were the STL kind. I've never actually created my own linked list structure.

also, if anyone has any good sites for introductions to hash tables, or any personal advice, I'd be appriciative.

finally, here's my current code:

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
string jumbled;
int i=0;
int loop=0;
int garbage = 1;

cout << "enter your string (no capitals)"<<endl;
cin >> jumbled;

sort(jumbled.begin(), jumbled.end());

cout<<endl;
cout<< "all possible permutations of your string:"<<endl;

do
{

for (i = 0; i < jumbled.size(); i++)
cout << jumbled[i];

loop++;
cout << "\n";

if (loop%20 == 0)
{
cout << "press 0 to quit, any other number to continue"<<endl;
cin >> garbage;
}

if (garbage == 0)
return 0;
}
while(next_permutation(jumbled.begin(), jumbled.end()));

cout <<endl << "to exit, enter any number."<<endl;
cin >> garbage;

return 0;
}

[GnuVince]

Hum... this looks like the anagram problem. You could probably use that.


input a jumble word
sort jumble word letters
iterate through all words in a word file
sort word letters
if sorted jumble words = sorted dict word
print unsorted dict word


Something like this

[stuka]

I only wonder why you're outputting the strings 1 character at a time - why not just [CODE}cout << jumbled;[/CODE]

[jemfinch]

If you're using the STL, just use the map or hash_map containers (hash_map isn't standard STL, but you probably have it anyway).

No need to reinvent the wheel.

Jeremy