数据结构之查找

查找
本章重点：
1、顺序表的查找
2、有序表的查找：折半查找法
3、二叉排序树及其查找过程（动态）
4、二叉排序树的插入（动态）
5、平衡二叉树、B-和B+树的结构
6、哈希表即哈希函数的构造方法了解

查找表：
静态查找表（查询）
动态查找表（查询、插入、删除）
主关键字次关键字

平均查找长度：ASL=sum(Pi*Ci)
为提高ASL，需要人为增加数据元素的关系，以便按照某种规则查找。

    9.1 静态查找表
    9.1.1顺序表的查找
顺序表表示：
typedef int KeyType;
typedef struct
{
    KeyType key;
    InfoTypedata;
}NodeType;
typedef NodeType SeqList[MAXL]

顺序查找
int SeqSearch(SeqList R, int n, KeyType k)
{
    int i = 0;
    while (i <n && R[i].key != k)
        i++;
    if (i >=n)
        return 0;
    else
        return i+ 1;
}

    9.1.2有序表的查找
1、折半查找
int BinSearch(SeqList R, int n, KeyType k)
{
    int low = 0,high = n - 1, mid;
    while (low<= high)
    {
        mid =(low + high) / 2;
        if(R[mid].key == k)
            returnmid + 1;
        if(R[mid].key > k)
            high= mid - 1;
        else
            low =mid + 1;
    }
    return 0;
}

2、斐波那契查找：按照斐波那契数列分段查找
3、插值查找：根据给定值key确定进行比较的关键字R[i].key的查找方法
i=（key-R[i].key）/(R[h].key-R[l].key)*(h-l+1)
适用于关键字均匀分布的表

    9.1.4索引顺序表的查找
1、分块查找，索引顺序查找
int IdxSearch(IDX I,int m,SeqList R,int n,KeyType k)
{
    intlow=0,high=m-1,mid,i;
    intb=n/m;              //b为每块的记录个数
    while(low<=high)       //在索引表中进行二分查找,找到的位置存放在low中
    {
        mid=(low+high)/2;
        if(I[mid].key>=k)
            high=mid-1;
        else
            low=mid+1;
    }
    //应在索引表的high+1块中,再在线性表中进行顺序查找
    i=I[high+1].link;
    while(i<=I[high+1].link+b-1 && R[i].key!=k) i++;
    if(i<=I[high+1].link+b-1)
        return i;
    else
        return-1;
}

    9.2动态查找算法（树表的查找）
    9.2.1二叉排序树和平衡二叉树
1、二叉查找树（二叉排序树）及其查找过程
2、二叉排序树的查找
3、二叉排序树的插入算法（递归算法）
int InsertBST(BSTNode *&p,KeyType k)
{
   if (p==NULL)                        //原树为空,新插入的记录为根结点
    {
        p=(BSTNode*)malloc(sizeof(BSTNode));
        p->key=k;
        p->lchild=p->rchild=NULL;
        return 1;
    }
    else if(k==p->key)                 //树中存在相同关键字的结点,返回0
        return 0;
    else if(k<p->key)
        returnInsertBST(p->lchild,k);  //插入到*p的左子树中
    else
        returnInsertBST(p->rchild,k);  //插入到*p的右子树中
}

4、二叉排序树的生成算法
BSTNode *CreateBST(KeyType A[],int n)   //返回BST树根结点指针

{

    BSTNode*bt=NULL;                   //初始时bt为空树

    int i=0;

    while(i<n)

    {

        InsertBST(bt,A[i]);             //将关键字A[i]插入二叉排序树T中

        i++;

    }

    returnbt;                          //返回建立的二叉排序树的根指针

}

5、二叉排序树的查找算法（递归）
BSTNode *SearchBST(BSTNode *bt,KeyType k)

{

    if (bt==NULL|| bt->key==k)         //递归终结条件

        returnbt;

    if(k<bt->key)

        returnSearchBST(bt->lchild,k);  //在左子树中递归查找

    else

        return SearchBST(bt->rchild,k);  //在右子树中递归查找

}

9.3 哈希表
1、确定的对应关系f
2、对应关系f就是哈希函数
3、哈希函数是一个映象，构造哈希函数的方法：
直接定址法、除留余数法、数字分析法、平方取中法、折叠法
4、冲突现象和解决冲突的方法
当k1!=k2时，f(k1)=f(k2)
开放定址法
（1）线性探测法
（2）平方探测法
拉链法

jtahstu's blogs

数据结构查找

2015/3/11

数据结构之查找