Download:

https://www.dropbox.com/s/7sxs308s7x7vg6b/FindWordsGame_ChenHanTsai.zip?dl=0

2014/10 – data structure

This month final project is the “find words game”, it is a 4×4 letter word game, the player has to find as many as possible connect word to gain the scores, it use all the content we are taught.

1. Hash table, by loading the dictionaries words, I use the hash function first, and distribute to around 10000 buckets, the empty buckets is 0, and every bucket contains the words is around 10~20, so it is efficient.

2. Binary tree search, the purpose is to detect whether player enter the same words again, by using the insert function and find function, the search result is O(logN), so it is fast.

3.Graph list, the next letters have to be the neighbor of the previous letters, so the graph list is a good tool to check. First check every node first, and if it is a valid letter the player enter, we can check the single link list leaf, and loop through the result until we check whether the player input is correct or not.