S*******C
发帖数: 822 | 1 Input: WORD.LST
And a randomly picked 1000 words from the same WORD.LST for querying.
This is a list of > 100,000 English words. It is sorted alphabetically.
Your task is to create a Compact Trie. Each node of trie will contain,
(1) A leading character (possibly empty (for root))
(2) String Label (possibly null (for root))
(3) Boolean IsWord , indicating whether the current node represents a whole
word or not (this is helpful when one word may be a prefix of another).
(4) Node *RightSIbling
(5) Node *FirstChild
If a node stores "stock" as the label string then leading character should
be 's'
You will need a method for FindChild, which takes FirstChild and a character
c as input and searches for correct node by following RightSibling pointers
until it finds the node with c as its leading character.
How to create a Trie.
You can use repeated insertions: you'll need following insert method...
Input Trie T (as Node *root) , and a String newWord ;
First run a find method on newWord until it fails : it could fail in two
ways
(i) It fails in the middle of some label -- in this case split this nodes
label into two parts: make two child nodes of this node, one having the rest
of the label string, along with original node's FirstChild pointer, and
second child gets the remaining part of the original word as a new node.
Organize these two children as a sorted linked list. And make its leftmost
node as FirstChild pointer of original node.
(ii) it fails to find appropriate child while searching for leading
character, then simply insert a new Node at this point in the child list,
and put the remaining part of the word as label for this node.
----------------------------------------------------------------------------
---
Now the Hashing part, speed up FindChild operation by using a HashTable,
Use a chaining based global Hashtable. Use the number of lines N in WORD.LST
as the size of Hashtable[N].
HashEntryNode will have following fields:
{Node *parent,
char c
Node *child
HashEntryNode *next
}
The Hashtable is an array of HashEntryNode* Hashtable[N] .
Hash function will take two values as an input Node *parent and char c and
calculate hash value between 0.. N-1. |
|
