以下のような命令を受け付けて実行することを繰り返す英和辞書プログラムを考える。命令は標準入力で与えられ、命令の区切りは改行で、1命令中の単語の区切りは空白文字である。各単語に空白文字は現れないと仮定する。
「insert <word> <tango>」: <word>の翻訳が<tango>であるとデータベースに登録する。既に登録されている場合は上書きする。
「delete <word>」: <word>をデータベースから削除する。（"(not found)" を上書きするのではなく、データベースから削除する実装をする。2021.12.28 追記）
「search <word>」: <word>をデータベースから検索し、その翻訳を表示する。 単語がデータベースに存在しないときには、「(not found)」と表示する。
「quit」: プログラムを終了する。
例えば、次のようなものが正しい入力である。
insert orange オレンジ
insert apple リンゴ
insert grape 葡萄
insert pear 梨
insert strawberry 苺
insert raspberry 木苺
insert fig 無花果
insert kaki 柿
insert apricot 杏
insert peach 桃
search apricot
insert orange 蜜柑
search orange
delete orange
search orange
search kaki
quit
この入力に対するプログラムの出力は、以下のようになる。（プロンプトや説明など余計な出力はしない。）
杏
蜜柑
(not found)
柿
内部のデータベースとして二分探索木を使い、上述の単語帳プログラムをCで作成せよ。入力に日本語特有の文字が含まれているが、特に気にせずにコードを書いても問題はない。また、正しい入力のみが入力されると仮定して良い。今回の課題ではstring.hで定義されている関数を用いて良い。
締切: 12/26 23:59
内部のデータベースとして二分探索木を使い、課題AD4と同等のプログラムをSchemeで以下のように実装する。
(let ((t (btree-empty)))
(define (input->string x)
(cond
((symbol? x) (symbol->string x))
((number? x) (number->string x))
((string? x) x)
(else #f)))
(define (main-loop t)
(let ((cmd (read)))
(cond
((equal? cmd 'insert)
(let* ((key (input->string (read)))
(val (input->string (read))))
(main-loop (btree-insert key val t))))
((equal? cmd 'delete)
(let* ((key (input->string (read))))
(main-loop (btree-delete key t))))
((equal? cmd 'search)
(let* ((key (input->string (read)))
(entry (btree-search key t)))
(if (not entry)
(display "(not found)\n")
(begin
(display (cdr entry))
(newline)))
(main-loop t)))
((or (equal? cmd 'quit) (eof-object? cmd))
#t)
(else
(display "(unknown command)\n")
(main-loop t)))))
(main-loop t))
以下の関数を定義して、プログラムを完成させよ。上のコードはレポートには含めないようにすること。二分木の内部表現にはどのようなものを用いてもよい。文字列の比較には、「string=?」「string<?」「string>?」を用いてよい。課題AD4にて上げたサンプル入力が、今回の課題においても正しく動作することを確認してから提出すること。
(define (btree-empty)
;; 空木を返す。
)
(define (btree-null? t)
;; 二分木`t'が空かどうかを真偽値で返す。
)
(define (btree-insert key val t)
;; 文字列`key'をキーとして文字列`val'を二分探索木`t'に挿入し、その木を返す。
)
(define (btree-delete key t)
;; 文字列`key'をキーとする項目を、二分探索木`t'から削除し、その木を返す。
)
(define (btree-search key t)
;; 文字列`key'をキーとして二分探索木`t'を検索し、キーとデータのペアを返す。
;; 見つからない場合は、#fを返す。
)
締切: 12/26 23:59
ハッシュ化されたデータベースを用いて、課題AD4と同様のプログラムをCで作成せよ。ただし、ハッシュ値が衝突した場合の挙動を確かめるために、ハッシュ関数の値域が0以上29以下に収まるように実装すること。データベースの実装は、チェーン法（オープンハッシュ法）でもオープンアドレス法（クローズドハッシュ法）でもよいが、オープンアドレス法を用いる場合には、データベースのサイズ（格納可能なキーの数）を30にすること。（データベースのサイズが30でも正しく正答できるような入力だけが与えられる。）
今回の課題ではstring.hで定義されている関数を用いて良い。また、正しい入力のみが入力されると仮定して良い。
ヒント1: 手元でテストする際、ハッシュ値が衝突しても正しく動作することを確認するために、同じハッシュ値になるような入力を複数与えたり、ハッシュ関数を定数関数にしてみるなどの工夫をするとよい。
ヒント2: テストケースの一部とその出力結果を公開する。2つのファイルの比較を行う際にはdiffコマンドが便利である。自分のプログラムの標準出力をテキストファイルにしたい場合は、リダイレクションを用いれば良い。つまり、a.outがプログラム名であるとするなら、./a.out > output.txtとすることで、output.txtに標準出力の結果が書き込まれる。
締切: 12/26 23:59