C/C++メモ(二)2015/8/15

スタック

VS2013             1M   //  ：    ->  ->   ->  
    

        ，         ，      
  ，        

static

補間ルックアップ

int  serch2(double *p, int n, int key)
{
    int tou, wei, zhong;
    tou = 0;
    wei = n - 1;
    while (tou <= wei)
    {
        //zhong = (tou + wei) / 2;      //    
        zhong = tou + (wei - tou)*(key - p[tou]) / (p[wei] - p[tou]);   //    

        if (p[zhong] == key)
            return zhong;
        else if (key > p[zhong])
            tou = zhong + 1;
        else
            wei = zhong - 1;
    }
    return -1;
}

zhong = tou + (wei - tou)*(key - p[tou])/(p[wei] - p[tou]);//補間検索式(wei-tou)は、合計何個の要素(key-p[tou])/(p[wei]-p[tou])/スケールの決定
二分検索はzhong=(wei+tou)*1/2=tou+(wei-tou)*1/2//補間検索の固定形式と見なすことができ、割合は1/2に固定されている