Trie(トライ)とは、文字列を鍵とする表に使われる手法である。英小文 字「a」〜「z」のみから成る文字列に対応して26分木としてデータ構 造を構成し、根から1文字ずつその文字に対応する枝をたどって行き(節 が無ければ割り当て、「a」〜「z」以外の文字があったらそこで中止)、 文字列が終った位置に値を登録する(今回は値が登録されていないとき は-1を入れることにし、検索時に見付からないときも-1を返す)。
トライを使った表のAPIを次のように定めた。
// trie.h struct trie; typedef struct trie *triep; triep trie_new(); void trie_put(triep p, char *s, int v); int trie_get(triep p, char *s);
また、この実装の冒頭部分を次のように作成した。根のノードは空文字 列に対応していて最初に作るので、トライによる表は構造体が1種類で 済む。なお、文字「a」の文字コードは97でありかつ各英小文字の文字 コードは連続しているとしてよい。
#define SIZE 26 struct trie { int val; triep chid[SIZE]; };
上記2行を含む実装を完成させよ(includeに続いて上の2行を置くこと)。