一応、途中までなんで恐縮なんですが、今日のアルゴリズムとデータ構造の持込用のカンペができたのであげときます。 完成してないんで、明日の朝残りはあげる予定です。前日までに完成してなくて本当にごめんなさい。 如月 オーダーについて ある式(まずnについての式)をオーダーにする場合、n→∞にしたとき最も早く無限に近づくものだけ残す。 例n³+an²+bn (a,bは自然数)→ O(n³) となる。 また、オーダー同士の足し算も同様にn→∞にしたとき最も早く無限に近づくものだけ残す。 例 O(n³)+O(n²) → O(n³) さらに、掛け算のときは、中身の掛け算をする。 例 O(n³)*O(n²) → O(n⁵) ヒープについて ヒープとは、わかりやすく言うと次の二つの定義から成り立つ。 1 同じ段なら、葉は常に左から詰められていき、それより上の段の要素は親となり最大で子を二つ持つ。 2 親は常に子より小さい。 ヒープに新しい要素を挿入するときは次のようになる。 定義1を満たすために、一番下の段の一番右に新しい要素をいれる。 次に、ヒープの定義2を満たすまで親と子の交換を繰り返す。 例 ③ ⑥ ④ に5を挿入すると、まず ③ ⑥ ④ ⑤ となり、ここで定義1を満たす。次に定義2を満たすための交換が行われる。 ③ ⑤ ④ ⑥ ここで、挿入が終了する。 さらに 2を挿入すると ③ ③ ② ⑤ ④ → ② ④ → ③ ④ ⑥ ② ⑥ ⑤ ⑥ ⑤ というふうに、木は変化していく。 また、DELETEMIN(最小値の削除)をする場合は次のようになる。 まず、一番下の段の一番右の要素を根(一番上の要素)に移す(上書きともいえる)。 次に、挿入のときと同じように、定義2を満たすまで親と子の交換を繰り返す。ただし、 このとき交換する子はもうひとつの子と比べて小さいほうである。もちろん、子がひとつしかないときは、その子と交換する。 例 ② ③ ④ ⑥ ⑤ ⑦ のヒープにDERETEMINNを行うと、 まず、 ⑦ ③ ④ ⑥ ⑤ となり、次に定義2を満たすための交換を行う。 ③ ⑦ ④ ⑥ ⑤ このとき、③と交換したのは④よりも小さいからである。さらに ③ ⑤ ④ ⑥ ⑦ となって、操作は終了する。 問題として、配列の状態を答えるような問題が出た場合は まず、木を作る。 例 a[0] =10, a[1] =9, a[2] =8, a[3] =7, a[4] =6, a[5] =5, a[6] =4, a[7] =3, a[8] =2, a[9] =1 である場合、木にすると ⑩a[0] ⑨a[1] ⑧a[2] ⑦a[3] ⑥a[4] ⑤a[5] ④a[6] ③a[7] ②a[8] ①a[9] である。 あとは、書いてあるプログラムどおりに交換を行えばいい。 双方向リストや待ち行列などのプログラムの穴埋めについては、ネットの先生の解答集を参照したほうが早いと思うので説明は割愛。 二分探索木について 二分探索木とは、わかりやすくいうと次のただひとつの定義から成り立つ。 1 ある要素xからみてその左の部分は必ずxより小さく、右の部分は必ず大きい。 このとき、部分というのは木にしたときの、子を根とした木のことである。 例 ⑦ ③ ⑪ ① ⑤ ⑨ ⑬ のとき、⑦からみた左の部分とは、 ③ ① ⑤ のことであり、右の部分とは ⑪ ⑨ ⑬ のことである。 別の言い方をすれば、常に親は左の子と右の子の間の数であり、子どうしでは常に左のほうが小さいともいえる。 挿入する場合、ヒープと違い交換は行われない。 例6,8,3,7,4,2,1,5を順番に入れる場合以下のようになる ⑥ ⑥ ⑥ ⑥ ⑥ → ⑧ → ③ ⑧ → ③ ⑧ → ③ ⑧ → ⑦ ④ ⑦ ⑥ ⑥ ⑥ ③ ⑧ → ③ ⑧ → ③ ⑧ ② ④ ⑦ ② ④ ⑦ ② ④ ⑦ ① ① ⑤ また、削除する場合は少し複雑で、 ① 削除する要素xが子をもっていなければxを削除する ② 子を一つ持っていればxを削除した後子をxの位置に移動する。 ③ 最後に子を二つ持っていた場合右部分木の最小要素(もしくは左部分木の最大要素)yを見つけ、yをxの位置に移動する(上書きともいえる)。その後、③の手順をyをxと見て同じことを、yが子を持っていないか、yが子をひとつしか持ってないという状況になるまで繰り返し、最後に前に述べた①もしくは②の手順を使って、終了となる。 例上の二分探索木から3と6をこの順番で削除する場合 ⑥ ⑥ ⑥ ③x ⑧ → ④ ⑧ → ④ ⑧ ② ④y ⑦ ② y ⑦ ② ⑤ ⑦ ① ⑤ ① ⑤ ① となり、まず6が削除され、次に3を削除する。 ⑥x ⑦ ④ ⑧ → ④ ⑧ ② ⑤ ⑦y ② ① ① となる。左部分の最小要素を使った方法も根本的にはこれと同じなので割愛。 ハッシュ法について ハッシュとはあるデータにたいしてランダムに数値を出す式(ハッシュ関数)をつかって だされた、数値のことである。 ハッシュ法とは、あるデータを配列に格納するときに、そのハッシュの値の場所を使う方法である。たとえば、B=8、ハッシュ関数をh(x)=x%B(xをBで割った余り)としたとき、 11というデータを格納すると、11%8=3でハッシュは3と配列をAとすれば、A[3]に11というデータは格納されるということである。 また、内部と外部の違いはハッシュ値が重なってしまった場合の処理の仕方が違う。 内部のほうは、ハッシュ値が重なった場合ハッシュの値の計算を元の値をずらしたりしてやり直し、あいている配列のハッシュ値がでるまでそれを繰り返し、あいてる配列の値がでたらそこに格納する。つまり、配列の箱の中身は常にひとつである。 外部のほうは、ハッシュ値が重なった場合、ポインタによって連結して記憶して格納する。 つまり、3という配列の箱の中に複数のデータが入ってる場合も存在する。