[データ構造]:検索(バイナリ検索、線形検索、ハッシュ値)(C)

出典|DO IT C言語材料構造(入門)

この授業では、バイナリ検索、線形検索、ハッシュ法について話します。

1. 국적이 한국인 사람을 찾는다.
2. 나이가 21세 이상 27세 미만인 사람을 찾는다.
3. 어떤 낱말과 발음이 가장 비슷한 이름의 사람을 찾는다.

アドレス帳を検索すると仮定し、どの検索を行っても特定の項目に注目します.これは検索の共通点です.

ここで注目しているのは鍵です.

国籍を検索した人は国籍で、検索年齢の人は年齢です.

データが単純な整数値である場合、データ値はキー値と見なすことができるが、ほとんどの場合、キー値はデータの一部である.ただし、上記の例では、キー値を次のようにします.

1. 키 값과 일치하도록 지정한다.(일본)
2. 키 값의 구간을 지정한다.(21세 이상 27세 미만)
3. 키 값과 비슷하도록 지정한다.(발음이 비슷한 사람)

一般的な資料構造では,検索に関する3つの例がある.

線形検索:ランダムに配列されたデータセットで検索を実行します.

バイナリ検索

ハッシュ:頻繁に追加、削除されるデータセットで高速検索を実行します.(チェーン法、オープンソース法)

ハッシュほう

チェーンメソッド:

同じハッシュ値のデータを線形リストに接続

オープン・アドレス法:

データのハッシュ値が競合したときに災害復旧を行う方法