数据结构(七)——查找的基本概念

七、查找

7.1 查找的基本概念

7.1.1 基本概念

查找 —— 在数据集合中寻找满⾜某种条件的数据元素的过程称为查找
查找表（查找结构）—— ⽤于查找的数据集合称为查找表，它由同⼀类型的数据元素（或记录）组成
关键字 —— 数据元素中唯⼀标识该元素的某个数据项的值，使⽤基于关键字的查找，查找结果应该是唯⼀的

7.1.2 对查找表的常见操作

① 查找符合条件的数据元素
② 插入、删除某个数据元素

7.2.3 查找算法的评价指标

查找长度——在查找运算中，需要对比关键字的次数称为查找长度
平均查找长度(ASL, Average Search Length)——所有查找过程中进行关键字的比较次数的平均值
ASL 的数量级反应了查找算法时间复杂度

”

7.2 顺序查找和折半查找

7.2.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;
}

“哨兵”方式实现

typedef struct{				//查找表的数据结构（顺序表）
    ElemType *elem;			//动态数组基址
    int TableLen;			//表的长度
}SSTable;

//顺序查找
int Search_Seq(SSTable ST,ElemType key){
    ST.elem[0]=key;
    int i;
    for(i=ST.TableLen;ST.elem[i]!=key;--i)
    // 查找成功返回数组下标，否则返回0
	    return i;
}

查找效率：查找成功和查找失败都是O(n)的数量级

一个成功结点的查找长度=自身所在层数
一个失败结点的查找长度=其父节点所在层数
默认情况下，各种失败情况或成功情况都等概率发生

7.2.2 折半查找

折半查找：⼜称“⼆分查找”，仅适⽤于有序的顺序表。（顺序表拥有随机访问的特性，链表没有）

typedef struct{
    ElemType *elem;
    int TableLen;
}SSTable;

// 折半查找
int Binary_Search(SSTable L,ElemType key){
    int low=0,high=L.TableLen,mid;//先让low和high分别指向队头和队尾的位置
    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;                         //查找失败
}

查找效率分析

折半查找的判定树一定是平衡二叉树
折半查找的判定树中(只有最下面一层是不满的，因此，元素个数为n时树高h =[log2(n+1)]

7.2.3 分块查找

分块查找的特点：块内⽆序、块间有序

分块查找，⼜称索引顺序查找，算法过程如下：
①在索引表中确定待查记录所属的分块（可顺序、可折半）
②在块内顺序查找

// 索引表
typedef struct{
    ElemType maxValue;
    int low,high;
}Index;

// 顺序表存储实际元素
ElemType List[100];

若索引表中不包含目标关键字，则折半查找索引表最终停在low>high，要在low所指分块中查找

秒客网