08 查找

查找的基本概念

线性表的查找

顺序查找

类型定义

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

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

算法

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

改进（哨兵）：

int Search_Seq(SSTable ST, KeyType key){
    ST[0].key = key;
    for (i=ST.length; i>=1; --i);
    return i;
}

折半查找

算法

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 ;//顺序表中不存在待查元素
}// Search_Bin

性能分析

分块查找

折半法：\(log_2(n+1)\)
顺序法：\(\frac {n+1} 2\)

树表的查找

二叉排序树 (BST)

基本概念

递归查找

存储结构：

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

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

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

算法：

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