前提・実現したいこと
アルゴリズムの勉強をしていて、ハッシュ法のオープンアドレス法で、削除済みフラグを用いない削除方法を
考えたアルゴリズムの問題があるのですが考えてもいまいちわからず答えもないので詰まっています。お力をお貸しください。
詳細
具体的に以下の画像の設問2以降の、問8からがわかりません。
(問1,2,3,4,5,6は今回の質問に直接関係ありませんが多少目を通していただけるとヒントになるのかもしれません。)
このアルゴリズムはオープンアドレス法ですが削除済みというフラグを使えないので、削除した個所をそのままにできない(削除フラグを使わないと正しく探索ができなくなる)ので、削除した個所に別のところからずらして来る(衝突でずらして格納してきたデータを、削除によって空いたところに戻すようなイメージ)ようなアルゴリズムだと考えました。それで
問8-1は「TABLE[i]」
問8-2は「D1」が答えかなと思いました。
問9は「set r <- h(KEY[i])」となっているのでハッシュの値ですが、D3-2のifの条件文から推測するに削除位置より”前”(”前”はiに+1していく方向とする)に本来格納されるべきキーが衝突によってずれて後ろに格納されたものかどうかを判定するキーの値、という風に考えました。
問10は循環するハッシュテーブルの図(循環の線形リストみたいな図になりました)を描いてみたのですが、D3-2の意味を説明というのはわかりませんでした
よろしくお願いいたします。
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2019/06/19 09:58