查找算法总结-创新互联

查找
对数值型关键字

#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))

对字符串型关键字

#define EQ(a,b) (!strcmp((a),(b)))
#define LT(a,b) (strcmp((a),(b))<0)
#define LQ(a,b) (strcmp((a),(b))<=0)

一、静态查找表
存储结构

typedef *** KeyType;
typedef struct
{
    KeyType key;
} ElemType;
typedef struct
{
    ElemType *elem;
    int length;
} SSTable;

1.顺序表的查找
1)思路：从前向后逐一比较，找到就返回位序，否则返回0

int Search_Seq(SSTable ST,KeyType x)
{
    for(int i=1; i<=ST.length; i++)
    {
        if(ST.elem[i].key==x)
            return i;
    }
    return 0;
}

2)思路：添加哨兵，从后向前比较，省略每次循环时的越界检查

int Search_Seq(SSTable ST,KeyType x)
{
    ST.elem[0].key=x;
    for(int i=ST.length; ST.elem[i]!=x; i--);
    return i;
}//结构化代码，单入口单出口

2.有序表的查找
折半查找
1)

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

2)

int Search_Bin(SSTable ST,KeyType x)
{
    int low=1,high=ST.length;
    int isDetected=FALSE;
    while(low<=high&&isDetected==FALSE)
    {
        int mid=(low+high)/2;
        if(ST.elem[mid].key==x)
            isDetected=TRUE;
        else if(ST.elem[mid].key>x)
            high=mid-1;
        else
            low=mid+1;
    }
    if(isDetected==FALSE)
        return 0;
    else
        return mid;
}//结构化代码，单入口单出口

二、动态查找表
1.二叉搜索树
存储结构

typedef **** KeyType;
typedef struct
{
    KeyType key;
} ElemType;
typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
typedef BiTree BSTree;
typedef BiTNode BSTNode;

1)查找

递归思路：如果树为空，查找失败，返回NULL
否则，从根节点开始，将x与根节点进行比较
若x小于根节点，递归查找左子树，并返回查找结果
若x大于根节点，递归查找右子树，并返回查找结果
若x等于根节点，查找成功，返回根节点地址

BiTNode *BSTSearch(BSTree T,KeyType x)
{
    if(!T)
        return NULL;
    else
    {
        if(T->data.key>x)
            return BSTSearch(T->lchild,x);
        else if(T->data.keyrchild,x);
        else
            return T;
    }
}

非递归思路：p最初指向根节点，只要p不空且p所指结点不是所求
则根据比较结果令p变为当前结点的左孩子或右孩子。
如此重复则最终p空或者找到

BiTNode *BSTSearch(BSTree T,KeyType x)
{
    BiTNode *p=T;
    while(p&&!EQ(p->data.key,key))
    {
        if(LT(x,p->data.key))
            p=p->lchild;
        else
            p=p->rchild;
    }
    if(!p)
        return NULL;
    else
        return p;
}

查找最小元素:
最左端点
查找大元素:
最右端点

2)插入
非递归思路：先查找是否重复，无重复则插入，插入位置是最后一个所走节点的孩子
查找过程中同时记录所走节点和其父节点f，无重复时新开辟节点放到f孩子上
要注意引用型参数

Status BSTInsert(BSTree &T,ElemType e)
{
    BSTNode *p=T,*f=NULL;
    while(p!=NULL&&!EQ(p->data.key,e.key))
    {
        f=p;
        if(LT(e.key,p->data.key))
            p=p->lchild;
        else
            p=p->rchild;
    }
    if(p==NULL)
    {
        BiTNode *q=new BiTNode;
        q->data=e;
        q->lchild=NULL;
        q->rchild=NULL;
        if(!f)
            T=q;
        if(LT(e.key,f->data.key))
            f->lchild=q;
        else
            f->rchild=q;
        return OK;
    }
    else
        return ERROR;
}

递归思路：与根节点比较，相等则不插入，否则，转换为左或右子树中的插入
递归边界：发现重复不递归，返回ERROR；到达空树不递归，直接开辟节点
T为引用型参数是拼接的关键
S

tatus BSTInsert(BSTree &T,ElemType e)
{
    if(!T)
    {
        BSTNode *p=new BSTNode;
        p->data=e;
        p->rchild=NULL;
        p->lchild=NULL;
        T=p;
        return OK;
    }
    else if(EQ(e.key,T->data.key))
        return ERROR;
    else if(LT(e.key,T->data.key))
        BSTInsert(T->lchild,e);
    else
        BSTInsert(T->rchild,e);
}

3)创建

Status CreateBST(BSTree &T)
{
    T=NULL;
    while(InputElem(e)<=0)
    {
        if(BSTInsert(T,e)==ERROR)
            return ERROR;
        else
            InputElem(e);
    }
}

4)删除
思路：删除叶子节点：直接删除
删除只有一个子树的节点：直接将子树接到被删除节点的双亲指针上
删除有两个子树的节点：将左子树大或右子树最小移至删除位置，
归结为删除左子树大或者右子树最小节点，这两类节点至多有一个孩子

void DeleteBST(BiTree &T,KeyType key)
{
    BSTBode *p=T,*f=NULL;
    while(p!=NULL&&!EQ(key,p->data.key))
    {
        f=p;
        if(LT(key,p->data.key))
            p=p->lchild;
        else
            p=p->rchild;
    }
    if(!p)
        return;
    if(!p->lchild&&!p->rchild)  //p若为叶子节点
    {
        if(!f)     //p为根节点
        {
            free(p);
            p=NULL;
            T=NULL;
        }
        else if(f->lchild==p)
        {
            f->lchild=p;
            free(p);
            p=NULL;
        }
        else
        {
            f->rchild=p;
            free(p);
            p=NULL;
        }
    }
    if(!p->lchild)    //若左孩子为空，p只有右孩子
    {
        if(!f)    //p为根节点
        {
            T=p->rchild;
            free(p);
            p=NULL;
        }
        else if(f->lchild==p)
        {
            f->lchild=p->rchild;
            free(p);
            p=NULL;
        }
        else
        {
            f->rchild=p->rchild;
            free(p);
            p=NULL;
        }
    }
    if(!p->rchild)   //p右孩子为空，只有左孩子
    {
        if(!f)
        {
            T=p->lchild;
            free(p);
            p=NULL;
        }
        else if(f->lchild==p)
        {
            f->lchild=p->lchild;
            free(p);
            p=NULL;
        }
        else
        {
            f->rchild=p->lchild;
            free(p);
            p=NULL;
        }
    }
    if(p->lchild&&p->rchild)
    {
        BSTNode *q=p->lchild;
        f=p;
        while(q->rchild)   //q为p左子树的大值，最多有一个左节点
        {
            f=q;
            q=q->rchild;
        }
        p->data=q->data;
        if(f->lchild==q)
        {
            f->lchild=q->lchild;
            free(q);
            q=NULL;
        }
        else
        {
            f->rchild=q->lchild;
            free(q);
            q=NULL;
        }
    }
}

2.平衡二叉树
任意节点的平衡因子（左右子树深度之差）的绝对值不超过1

3.B-树和B+树
一颗m阶的B树是空树，或是满足下列特性的m叉树：
(1)树中每个结点至多有m棵子树(m-1个关键字)
(2) 根结点或者为叶子结点或者至少有两棵子树
(3)根之外所有非终端结点至少有ceil(m/2)棵子树
(4) 非终端结点包含信息(n, A0,K1,A1,K1,A2,...,Kn ,An)
Ki为关键字,有序; Ai为指向子树根结点的指针,且Ai所指子树中所有结点关键字均介于Ki-1和Ki之间.(n(5)叶结点出现在同一层上,不带信息,相当于查找失败结点

哈希查找

哈希表：根据设定的哈希函数和处理冲突的方法，将一组关键字映象到一组有限的连续的存储空间上，以关键字对应的Hash函数值作存储地址，如此所得的查找表称为哈希表
查找性能：依赖于Hash函数与冲突处理方法的质量
1.哈希函数
2.冲突处理方法
3.哈希表装填因子(饱和度):n/m,n为记录数，m为表长

构建哈希表的方法：
1.线性函数：H(key)=a*key+b
2.除留取余法：H(key)=key%P P通常为大于表长的最小素数
3.数字分析法
4.平方取中法
5.折叠法
6.随机数法

处理冲突方法：
1.开放定址法
2.线性探测再散列
3.二次探测再散列
4.链地址法 冲突的记录构成一个链表，哈希表存其头指针

哈希查找过程：遇空则失败
Step1:对关键字 K, 计算哈希函数值i = Hash(K);
Step2:若 H[i] 为空则查找失败,返回;
Step3:若 H[i].key = K则查找成功,返回i;
Step4:否则 , 据冲突处理方法确定下一地址 Hi
Step5:转到Step2重复

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧