[13a1] トライの実装1

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行を置くこと)。