アルゴリズムとデータ構造Ⅱ：練習問題

二分木を使って，最近情報数学で学んだ「ポーランド記法」を扱ってみよう。
・詳細はプログラム中にコメントしてある。
・main関数内にて，char型配列polandが宣言されている。ここにはポーランド記法で記述した数式を格納しておく。
・main関数内にて，Node型変数btが宣言されている。これは，polandを二分木（構文木）に変換する際の根（ルート）とする。
・今回，簡単のために一桁の数値と四則演算のみで構成された式を扱う。そのため，本来，ポーランド記法は区切り文字としてスペース等（例：+ 1 2）を入れるが，
　今回は必要ないので除いた（例：+12）（その分，区切り文字の処理をする必要がなくなった）。
・関数は３つあるが，今回実装するのは２つのみ。
・二分木の深さ0〜4までを表示する，PrintBT()関数（実装済）。
・poland（文字列）を二分木に変換する，CreateBT()関数（【実装１】）。
・CreateBT()関数にて生成した二分木を使って，演算結果を返す，CalculateBT()関数（【実装２】）。
※ポーランド記法を理解している前提で作った。

☆プログラム雛形を，こちらからダウンロードしてください。
ダウンロードした雛形には，【実装１】と【実装２】があります。与えられた仕様を満たすようにプログラムを組んでください。

◎解答例はこちら。

複数の英文を用意した。この英文は，idとセットである。この英文をハッシュ法で管理→読み出し→一文字単位での昇順ソート→文字列探索を行う。

【実装１】まずはこの英文たちをハッシュ表を用いて管理してみよう。InsertToHashTable関数を実装する。
引数としてchar *phraseとint idが与えられる。このidをもとに，ハッシュ値を生成し（Hash関数），適切な位置に新たなノードを追加する。
新たなノードを追加する際，衝突の回避法はチェイン法を用いる。チェイン法のためのノードはNode型として定義してある。このノードにはidとphrase変数が用意されており， それぞれ引数で渡されたidとphraseを代入するだけで良い。


【実装２】ハッシュテーブルからデータを読み出す。LoadPhraseWithId関数を実装する。
引数としてint idが与えられる。このidをもつ英文データを参照する。
この関数はNode型ポインタを返す。対象英文が見つかれば，その英文が格納されているNodeのポインタを，見つからなければNULLポインタを返す。 取得したノードは，main関数内のcurrentNodeに代入されるようになっている。
プログラムは，授業で学んだハッシュ法を用いた探索に基づくこと。

【実装３】読み込んだ（currentNodeの）英文の文字ソートを行おう。ここでは二分探索木を作る。InsertToTree関数を実装する。
引数としてTreeNode *root, char cが与えられる。このcを二分探索木の適切箇所に追加したい。
「適切箇所」を次のようにする：rootより小さい値を左側に，等しいor同じ値を右側に配置する。
rootをルートノードとし，与えられたcを適切な箇所にノードとして追加するプログラムを作成する。二分探索木用のノードはTreeNode型として定義してある。 このノードにはdataとleft, right変数が用意されており，dataには引数として与えられたcを代入し，left, rightには子ノードのアドレス（ポインタ）を代入する。
また，この関数はTreeNodeポインタ型を返す，という点を活用すること。
※初回の呼び出しでは，rootノードはNULLが渡される（詳細はMakeTree関数を参照；実装済）。

この関数が正常に動作すれば，実行例のようなソート結果が得られる（上図の場合は「ABCDEFGHI」が得られる）。

【実装４】読み込んだ（currentNodeの）英文の文字列探索を行おう。文字列探索アルゴリズムはKMP法とする。まずは，ずらし表を作成する。InitNext関数を実装する。
ここは授業で作成した，KMP法のずらし表と全く同じように実装して良い。
引数であるchar *ptnがパターン文字列の先頭アドレスとする。また，ずらし表の作成先はグローバル変数として宣言してある，next[]とする。

【実装５】実装４の続き。作成しずらし表を使って，文字列を探索する。SearchInHashTable関数を実装する（少し関数名不適だけども...）。
引数で与えられるchar *text，char *ptnがあり，text中でptnが何箇所で一致するかを探索すること。
こちらも授業で作成したプログラムと同じように実装できる。ただし，今回は「何箇所」見つかったか，という数値を返すようにする。

☆プログラム雛形を，こちらからダウンロードしてください。
ダウンロードした雛形には，【実装１】〜【実装５】があります。与えられた仕様を満たすようにプログラムを組んでください。
必要な変数は各自追加してください。

◎解答例はこちら。