線形探索では先頭から要素を一つ一つ調べるので、後ろにある要素ほど探索時間がかかる。そこで、探索のたびに、見つかった要素を先頭に移動すれば、頻繁に検索されるものほど先頭に集まり、平均探索時間が短くなることが期待できる。このような方法を自己組織化探索という。

しかし、移動は配列にとっては大変時間のかかり作業であり、一方リストならばポインタの付け替えだけですむ。したがって、自己組織化探索では、データはリストにより保持される。

<関数名>
  selfSearch 自己組織化探索

<形式>
  LIST *selfSearch(LIST *list, int target);

<引数>
  typedef struct _list {
    int key;       /* 比較のキーとなるフィールド */
    int info;       /* その他のフィールド */
    struct _list *next; /* つぎの要素 */
  } LIST;

  list   (入力) リストへのポインタ
  target (入力) 探索目標とするキーの値

<関数値>
  見つかった場合はその要素へのポインタ。見つからなかった場合は NULL。

注意事項
  リストが正しく作成されていることが前提。細かいことについてはつぎの用例プログラムを参照すること。

用例

<関数本体>
  selfSearch.c

Comments are closed.

Post Navigation