内容纲要

1.名词解释

  • 平均查找长度(ASL)不是AWSL
    查找过程中比较次数的平均值:

    ASL = \sum_{\mathclap{1\le i\le n}} P_1C_i

    其中,n为文件记录个数,Pi为第i个记录的查找概率,Ci是找到第i个记录时经历的比较次数。

2.顺序查找

  • 简介
    从顺序表一端开始,逐个比较,直到查找成功。若失败,则返回-1.
  • 实现
    int srh(int* a,int target)
    {
    a[0] = target; //将没有利用的数组第0位设为监视哨,这样查找失败会返回0
    for(int i = len;;i--) //len为序列中元素个数
        if(a[i] == target)
            return i;
    }
  • 性能
    查找第i个元素比较次数为 n-i+1,可计算其ASL:

    ASL = \sum_{\mathclap{1\le i\le n}} P_1C_i = \frac {1}{n}\sum_{\mathclap{1\le i\le n}} (n - 1 + 1) = \frac {n + 1}{2}

3.二分

  • 简介
    对一个升序序列,先比较其中间值,如果比中间值小,则对其左端序列进行同样的操作,否则对其右边的序列进行同样的操作。注意,序列必须有序
  • 实现
    int bin_srh(int* a,int target,int l,int r)
    {
    while(l <= r)
    {
        int m = (l + r) / 2;
        if(a[m] == target)
            return m;
        if(a[m] < target)
            l = m + 1;
        else
            r = m - 1;
    }
    return -1;
    }
  • 性能
    ASL = \sum_{\mathclap{1\le i\le n}} P_1C_i = \frac {1}{n} \sum_{\mathclap{1\le j\le h}} 2^{j-1} j = \frac {n+1}{n}log_2(n+1)-1

4.索引查找

  • 简介
    分块查找要求把一个大的线性表分解成若干块,每块中的节点可以任意存放,但块与块之间必须排序。假设是按关键码值非递减的,那么这种块与块之间必须满足已排序要求,实际上就是对于任意的i,第i块中的所有节点的关键码值都必须小于第i+1块中的所有节点的关键码值。此外,还要建立一个索引表,把每块中的最大关键码值作为索引表的关键码值,按块的顺序存放到一个辅助数组中,显然这个辅助数组是按关键码值费递减排序的。查找时,首先在索引表中进行查找,确定要找的节点所在的块。由于索引表是排序的,因此,对索引表的查找可以采用顺序查找或折半查找;然后,在相应的块中采用顺序查找,即可找到对应的节点。(代码教材未给出不做要求,目前没用到过,故本文目前不贴代码)
  • 性能
    log_2{n} \le ASL_bs \le \frac{n+1}{2}

总提纲:《数据结构》期末提纲小结

发表评论

电子邮件地址不会被公开。 必填项已用*标注