基本概念

线性表的查找

基本概念

根据给定的一个值，在查找表中确定一个关键字等于给定值的数据元素或（记录）

关键字：用来标识一个数据元素（或记录）的某个数据项的值

主关键字：可唯一地标识一个记录的关键字是主关键字

次关键字：用以标识若干记录的关键字是次关键字

线性表的查找

顺序查找（线性查找）

应用范围

顺序表或线性链表表示的静态查找表
表内元素之间无序

顺序表的数据元素类型定义

typedef struct{
    KeyType key;    //关键字域
    ……              //其他域
}ElemType;

顺序表的表示

typedef struct{    //顺序表结构类型定义
    ElemType *R;    //基地址
    int length;     //表长
}SSTable;
SSTable ST;  //定义顺序表ST

顺序查找算法 O(n)

int Search_Seq(SSTable ST,KeyType key){
    //若成功返回其位置信息，否则返回0
    for(i=ST.length;i>=1;--i)
        if(ST.R[i].key == key)    return i;    
    return 0;
}

设置监视哨的顺序查找 O(n)

int Search_Seq(SSTable ST,KeyType key){
    //在顺序表ST中顺序查找其关键字等于key的数据元素
    ST.R[0].key=key;        //"哨兵"
    for(i=ST.length;ST.R[i].key!=key;--i);
    return i;
}

查找第i个元素，需要比较n-i+1次；查找失败，需比较n+1次。

平均查找长度(n+1)/2

空间复杂度为O(1)

顺序查找的优缺点

优点：算法简单，对表结构无任何要求，既适用于顺序结构，也适用于链式结构，无论记录是否按关键字有序均可应用。

缺点：平均查找长度较大，查找效率较低，所以当n很大时，不宜采用顺序查找

折半查找（二分查找） O（log2n）

mid = (low + high)/2

折半查找的算法

int Search_Bin(SSTable ST,KeyType key){
    low = 1;high = ST.length;    //置区间初值
    while(low <= high){
        mid = (low+high)/2;
        if(ST.R[mid].key == key)    return mid;
        else if(key < ST.R[mid].key)
            high = mid-1;
        else low = mid+1;
    }
    return 0;
}

折半查找的递归算法

int Search_Bin(SSTable ST,keyType key, int low,int high){
    if(low > high)    return 0;
    mid = (low + high)/2;
    if(key == ST.elem[mid].key)    return mid;
    else if(key < ST.elem[mid].key)
        Search_Bin(SSTable ST,keyType key, int low,int mid-1);
    else    
        Search_Bin(SSTable ST,keyType key, int mid+1,int high);
}

折半查找的判定树

时间复杂度为O(log2n)

平均查找长度ASL=log2(n+1)-1

折半查找的优缺点

优点：效率比顺序查找高

缺点：只适用于有序表，且限于顺序存储结构（对线性链表无效）

分块查找

优点：插入和删除比较容易，无需进行大量移动

缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算

适用情况：如果线性表既要快速查找又经常动态变化，则可采用分块查找

查找方法比较

树表的查找

动态查找表–对于给定值key,若表中存在，则成功返回；否则，插入关键字等于key的记录

二叉排序树

二叉排序树或是空树，或是满足以下性质的二叉树

若其左子树非空，则左子树上所有结点的值均小于根结点的值
若其右子树非空，则右子树上所有结点的值均大于等于根结点的值
其左右子树本身又是一棵二叉排序树

中序遍历非空的二叉排序树是一个按关键字排列的递增有序的序列

比较的关键字次数=此结点所在层次数

最多的比较次数=树的深度

二叉排序树的存储结构

typedef struct{
    KeyType key;    //关键字项
    InfoType otherinfo;    //其他数据域
}ElemType;

typedef struct BSTNode{
    ElemType data;        //数据域
    struct BSTNode *lchild,*rchild;    //左右孩子指针
}BSTNode,*BSTree;

BSTree T;    //定义二叉排序树T

二叉排序树的查找操作 O(log2n)

BSTree SearchBST(BSTree T,KeyType key){
    if((!T)|| key == T->data.key)    return T;
    else if(key < T->data.key)
        return SearchBST(T->lchild,key);    //在左子树中继续查找
       else return SearchBST(T->rchild,key);    //在右子树中继续查找
}

含有n个结点的平均查找长度最好情况：O(log2n)

最坏情况：O(n)

二叉排序树的插入操作 O(log2n)

插入的元素一定在叶结点上

void InsertBST(BSTree &T,ElemType e){
    //当二叉排序树T中不存在关键字等于e.key的数据元素时，则插入该元素
    if(!T){
        S = new BSTNode;                    //生成新结点*S
        S -> data = e;
        S -> lchild = S -> rchild = NULL;    //新结点*S作为叶子结点
        T = S;
    }
    else if(e.key < T -> data.key)
        InsertBST(T -> lchild,key);
    else if(e.key < T -> data.key)
        InsertBST(T -> lchild,key);
}

二叉排序树的创建操作 O(nlog2n)

不同插入次序的序列生成不同形态的二叉排序树

void CreateBST(BSTree &T){
    //依次读入一个关键字为key的结点，将结点插入二叉排序树T中
    T = NULL；
    cin >> e;
    while(e.key != ENDFLAG){    //ENDFLAG为自定义常量，作为输入结束标志
        Insert(T,e);
        cin >> e;
    }
}