第7章学習のまとめ

勉強のまとめ
この章では検索を学習し、検索テーブルは同じタイプのデータ要素(またはレコード)からなる集合であり、キーワードに基づいて検索テーブルでそのキーワードが表すレコードの情報を検索する
1.動的検索:検索と同時にテーブルを変更(挿入削除など)、そうでない場合は静的検索
2.ASL平均検索長さ
3.線形テーブルの検索
①順次検索ASL=(n+1)/2
従来の方法
    

int Search_Seq(SSTable ST,KeyType key) //    ST          key     。   ，              ，   0
{
    for(i=ST.length;i>=1;--i)

        if(ST.R[i].key==key) return i; //         
    return 0;
}

欠点:毎回テーブル全体のチェックが完了したか否かを判断する(判断i>=1)
最適化:

int Search_Seq(SSTable ST,KeyType key) //    ST          key     。   ，              ，   0
{
    ST.R[0].key=key;                     //  
    for(i=ST.length;ST.R.[i]!=key;--i)//     
    return i;
}

このときi∈[1,n]が見つかったら
i=0が見つかりません
②折半検索ASL=log 2(n)
前提:シーケンスストレージ、テーブル内のキーワードの順序付け

int Search_Bin(SSTable ST,KeyType key) //    ST          key     。   ，              ，   0
{
    low=1;high=ST.length;   //       
    while(low<=high)
    {
        mid=(low+high)/2;
        if(key==ST.R[mid].key)   return mid;      //       
        else if(key1; //           
        else low=mid+1;                                    //           
    }
    return 0;
}

実際のアプリケーションでは見つからず、レコードを挿入する必要がある場合はreturn low;そして最終的なlowの前に挿入(このときlow>high)
4.ツリーテーブルの検索
ツリーの再帰検索による挿入削除の作成
バランスツリー:左サブツリーと右サブツリーの深さの差の絶対値は1を超えない.左サブツリーと右サブツリーもバランスのとれた二叉木です.
5.ハッシュの検索
記録された記憶位置pとそのキーワードkeyとの間に、p=H(key)Hをハッシュ関数とする特定の対応関係Hが確立される
ハッシュ関数の作成
原則:各キーワードには1つのハッシュアドレスしか対応できません.関数の値ドメインは、テーブル長の範囲内で計算されたハッシュ・アドレスの分布が均一で、競合を最小限に抑える必要があります.
方法:
①数値解析法——すべてのキーワードの各ビットにおける様々な数字の分布を明確にしなければならない.実際の応用:出版社の図書に同意して、ISBNの上位数位は同じで、デジタル分析法を使う時、ISBNの上位数位を排除します
②二乗中法——キーワードを知らない全ての場合、またはキーワードから直接値を取りにくい分散した数桁の場合に適用
③折りたたみ方法——ハッシュアドレスの桁数が少なく、キーワードの桁数が多く、キーワードから直接値を取るのが難しい分散した数桁
④留去余法——H(key)=key%p pは一般的に表長より小さい最大質量数をとる
実際の適用では、競合の処理方法を完全に回避することは困難です.
①オープンアドレス法Hi=(H(key)+di)%m
I線形検出法di=1,2,3,......,m-1
Ⅱ二次検出法di=1²,-1²,2²,-2²,3²,……,+k²,-k²  (k<=m/2)
III擬似ランダムプローブ法注意表作成時のランダムシーケンスを記録し、表を調べる
②チェーンアドレス法
同じハッシュアドレスを持つレコードを同じ単一チェーンテーブルに置くと、m個のハッシュアドレスにはm個の単一チェーンテーブルがあり、同時にHT[0...m-1]でチェーンテーブルのヘッダポインタが格納され、ハッシュアドレスiのレコードはHT[i]をヘッダノードとする単一チェーンテーブルにノード方式で挿入される
二前回の目標と次の目標
前回は合理的に時間を分配して機に乗る実践を保証することを望んで、今回はもっとよく双方の時間を調整しました
期末が近いので、これからはなるべく締め切りまでにPTAの自測問題を連絡して、宿題問題に限らず復習しないと間に合わないと思います!!!