探索

探索(searching)

表の中から、ある特定の値をもつデータを探し出す操作

• レコード構造(record structure)
  表に格納する１つ１つのデータ

• フィールド(field)
  レコード内のデータ

• キー(key)
  探索の対象となるフィールド

• 辞書(dictionary)
  以下の３つの機能をもつ抽象データ型
  1. 挿入―データを表に登録する
  2. 探索―与えられて値をキーに持つデータを探し出す
  3. 削除―与えられた値をキーにもつデータを削除する

探索法の種類

• 線形探索法(linear search)
• 二分探索法(binary search)
• ハッシュ法?
• チェイン法?
• オープンアドレス法?
• 二分探索木(binary search tree)
• AVL木?
• B木

参考文献

• 定本 Cプログラマのためのアルゴリズムとデータ構造(近藤嘉雪,ソフトバンククリエイティブ,1998)