7、查找

1、顺序查找

  • 顺序存储

  • 链式存储

typedef struct{
    ELemType *elem;	//动态数组基址
    int TableLen;	//表的长度
}SSTable

//顺序查找
int Search_ Seq (SSTable ST, ElemType key){
    int i;
    for(i=0;i<ST. TableLen && ST.elem[i] !=key; ++i);
    //查找成功,则返回元素下标;查找失败,则返回-1
    return i== =ST. TableLen? -1 : i;
}

无序表的ASL:n+12\frac{n+1}{2}

有序表的ASL:n2+nn+1\frac{n}{2}+\frac{n}{n+1}

2、折半查找

  • 顺序存储(有序)

typedef struct{
    ELemType *elem;	//动态数组基址
    int TableLen;	//表的长度
}SSTable
    
//折半查找
int Binary_Search(SSTable L, ElemType key){
    int low=0 , high=L.TableLen-1, mid;
    while(low<=high){
        mid=(low+high)/2;	//取中间位置
        if(L.elem[mid]==key)
        	return mid;		//查找成功则返回所在位置
        else if(L.elem[mid]>key)
        	high=mid-1;		//从前半部分继续查找
        else
        	low=mid+1;		//从后半部分继续查找
    }
    return -1;//查找失败,返回-1
}

判定树高:log2(n+1)\log_{2}(n+1)

查找成功的ASL:log2(n+1)1\log_2(n+1)-1

3、分块查找

用折半查找找分块索引表(low>high时查找失败,则取现在low所指向的分块)

在分块内用顺序查找

设共有n条记录,则分块长度最理想应为n\sqrt n

4、B树

  • 树结构

    • 顺序存储

    • 链式存储

定义

B树
  • B树中所有结点的孩子个数的最大值称为B树的阶,对于m阶B树

  • 树中每个结点至多有m棵子树,即至多含有m-1个关键字

  • 若根结点不是终端结点,则至少有两棵子树

  • 除根结点外的所有非叶结点至少有m/2\lceil m/2\rceil棵子树,即至少含有m/21\lceil m/2\rceil-1个关键字

  • 所有的叶结点都出现在同一层次上,并且不带信息(可以视为外部结点或类似于折

计算

设树的阶数为m,有n个关键字,树高记为h

  • 最大树高n+12(m/2)h1Hmaxlogm/2((n+1)/2)+1n+1\geq2(\lceil m/2\rceil)^{h-1} \Rightarrow \text{H}_{max}\leq\log_{\lceil m/2\rceil}((n+1)/2)+1

  • 最小树高nmh1hminlogm(n+1)n\leq m ^h -1 \Rightarrow \text h_{min}\geq \log_m(n+1)

插入

设为m阶B树,即每个节点中最多只能插入m-1个关键字

  • 当节点不满时,直接插入关键字

  • 节点已满

    • 将当前节点的中间的关键字提为父节点

    • 将原节点中剩下的关键字拆分为两个

删除

  • 非终端节点:用直接前驱代替删除的节点

  • 终端节点

    • 节点中关键字没有低于下限:直接删除

    • 节点中关键字数量低于下限

      • 兄弟够借

        • 从兄弟中借一个变成父节点

        • 原父节点拉下来补充

      • 兄弟不够借

        • 将两个节点合并

        • 将两个节点中间的父节点也合并进来

        • 此时若父节点不够,则继续按照此逻辑处理

B+树

  • 记录数=叶子节点数

  • 类似于索引分块查找

  • B+树支持顺序查找

5、散列表

  • 顺序存储

  • 链式存储

散列函数

  • 直接定址法:H(key)=a×key+bH(key)= a\times key+b

  • 除留余数法:H(key)=key%pH(key)=key\%p

  • 数字分析法

  • 平方取中法

冲突处理

  • 开放定址法

    • 线性探测法:向后推移

    • 平方探测法(二次探测法):推移的距离变为021212k2k20^2、1^2、-1^2……k^2、-k^2

    • 双散列法(再散列法):使用另一个散列函数再次计算

    • 伪随机序列法:推移的距离是伪随机序列

  • 拉链法:直接挂在链表后面

参数

表长为m,p为不大于m的质数。

  • 装填因子:记录数表长\frac{记录数}{表长}

  • 成功的平均查找长度:每个元素的查找长度元素数量\frac{每个元素的查找长度}{元素数量}

  • 失败查找长度:可能取值范围内的元素查找失败长度可能的取值范围\frac{可能取值范围内的元素查找失败长度}{可能的取值范围}

    • 可能的取值范围取决于p的值,即[0, p-1]

Last updated