回 帖 发 新 帖 刷新版面

主题:[讨论]折半查找插入的小问题。

折半查找插入算法中,折半查找插入位置,是不是查找到插入位置后low=high+1 ?

下面是具体算法.
typedef int KeyType;         //定义关键字类型为整数类型
typedef struct {
    KeyType key;           //关键字项
    InfoType otherinfo;       //其他数据项
}RedType;                  //记录类型
typedef struct {
    RedType r[MAXSIZE+1];  //r[0]闲置或用作哨兵单元
    int length;               //顺序表长度
}SqList;  

void BinsertSort (SqList &L)    {
    for (i=2;i<=L.length; ++i)     {
        L.r[0]=L.r[i];                //将L.r[i]暂存到L.r[0]
        low=1; high=i-1;
        while(low<high)    {        //在r[low..high]中折半查找有序插入的位置
            m=(low+high)/2;        //折半
            if (LT(L.r[0].key, L.r[m].key)) high=m-1;  //插入点在低半区
            else low=m+1;                       //插入点在高半区
        }//while
        for (j=i-1; j>=high+1; --j ) L.r[j+1]=L.r[j];    //记录后移
        L.r[high+1]=L.r[0];                      //插入
}//for
}//BInsertSort


我个人看来查到到位置以后low=high+1的,所以for (j=i-1; j>=high+1; --j )也可以把high+1用low代替.但不知道有没有遗漏什么..

求教了...

回复列表 (共2个回复)

沙发

怎么没头文件,看起来很累的哈。。基本上同意你说的,再做过测试程序,这样会比较好。

板凳


没有遗漏!很正确。

我来回复

您尚未登录,请登录后再回复。点此登录或注册