アルゴリズムのご相談2

質問

度々すいません。
また考え方の課題なんですけど、
各配列のDataの中に順不同なバラバラなデータが入っているときに、
その中から最も0に近いIndexでDataが空白になっている箇所を探すには、
どういった検索方法が高速なのでしょうか？
この場合、頭から探すしかないのでしょうか？

----------------
| Index | Data
----------------
| 0 | 123
----------------
| 1 | abc
----------------
| 2 | xyz
----------------
| 3 | ←
----------------
| 4 | 456
----------------
| 5 |
----------------
| 6 | ABC
----------------
| 7 | XYZ
----------------
| 8 | 789
----------------
| 9 | ijk
----------------
| … | …

回答No.1

mikaemi · ベストアンサー

レコードのData部分を、空白にするときや非空白にする際に、プログラムに何も情報を憶えさせていないというなら、頭から調べるのが一番早いと思いますね。

どういう動作を想定しているのかわからないのでなんとも言えませんが、たとえば、

　　・非空白のDataをレコードに登録するときは、必ず、空白であるDataのレコードで一番小さいインデクスものから埋めていく。

　　・空白のDataを持つレコードに関しては、一番小さいインデクスしか調べない。

などの条件があるなら、非空白のDataをレコードに登録する際や、空白のDataをレコードに登録する際に、

　　・「インデクスの変数(startとしますと)を一つ持っておき、start未満のインデクスには、空白のDataを持つレコードがない」ようにしておく（空白のDataを持つインデクスを探す場合は、startから調べればよい）。

とか、

　　・ヒープ構造で空白のインデクスを管理しておく。
　　　http://www.codereading.com/algo_and_ds/ds/heap.html

とか、できますけどね^^

お礼

ヒープ構造体？？
ちょっと調べてみます。
ありがとうございます。

回答No.2

tatsu99

登録の時に、何の情報も付加しないなら頭から検索する以外にないですね。
また、空いている領域は、必ず０に近いほうでないとだめな理由はなんですか。ただ、「どこでも良いから空いているところを素早く探せばよい」といのでは、いけませんか。
登録時の条件、削除時の条件についてもっと、具体的に、なにをなさりたいのかを提示していただけると、もっと具体的なアドバイスが、得られるかと思います。
最も速く、空きエリアを検索したいと言うことであれば、空きエリアを管理するキューを作成するのが、最も良いと考えます。

お礼

なるほど、キューという考え方も良いかもしれませんね。
ありがとうございます