アルゴリズムイントロダクション 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

分からない。

11.3-3

以下略。

数学的基礎とデータ構造 (アルゴリズムイントロダクション)
T. コルメン R. リベスト C. シュタイン C. ライザーソン
近代科学社
売り上げランキング: 32572