アルゴリズムイントロダクション 11 章「基本データ構造」
数学的基礎とデータ構造 (アルゴリズムイントロダクション)の 11章
11.1-1
リニアサーチする。
11.1-2
ポインタの offset を key にする。
11.1-3
T[k] を同じキーを持つものリストにする。
11.2-1
略。
11.2-2
[0]-><10>-><20>-><15>
[1]
[2]-><17>-><12>
[3]-><33>-><28>
[4]-><19>
[5]-><5>
[6]
[7]
[8]
[9]
11.2-3
探索:logn
挿入: O(nlogn)
削除: O(1)
11.2-4
スロットに割り当て済みフラグをつける
挿入:フラグオンなら挿入。オフなら自分が先頭で挿入
検索:オフなら検索終了。オンならリニアサーチ
削除:普通の hash table と同じ。
11.3-1
検索キーのハッシュ値でリニアサーチ。
11.3-2
分からない。