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

記号列 

コード 

選択肢

ア #define SIZE 10
イ #define SIZE 26
ウ struct trie { int val; triep child[SIZE]; };
エ #include "trie.h"
オ #include <stdlib.h>
カ triep trie_new() {
キ int trie_get(triep p, char *s) {
ク void trie_put(triep p, char *s, int v) {
ケ }
コ for(i = 0; i < 10; ++i) { p->child[i] = NULL; }
サ for(i = 0; i < 26; ++i) { p->child[i] = NULL; }
シ if(*s == '\0') {
ス if(p == NULL) {
セ if(p->child[i] == NULL) {
ソ } else if('0' <= *s && *s <= '9') {
タ } else if('a' <= *s && *s <= 'z') {
チ } else if(*s == '\0') {
ツ } else {
テ triep p = (triep)malloc(sizeof(struct trie));
ト int i = *s - '0';
ナ int i = *s - 'a';
ニ int i;
ヌ p->child[i] = trie_new();
ネ p->val = -1;
ノ p->val = v;
ハ return -1;
ヒ return p->val;
フ return p;
ヘ return trie_get(p->child[i], s+1);
ホ trie_put(p->child[i], s+1, v);

選択肢の行をドラグして上のコード領域に配置してください。 コード領域の行はドラグにより位置が変更できます。 削除したい場合は選択肢の領域に戻してください。