6种查找方法

大家好，欢迎来到IT知识分享网。

1.顺序查找

2.折半查找

3.分块查找

4.二叉排序树

左子树关键字<根关键字<右子树关键字

非递归：

typedef struct BiTNode{ 
    ElemType key; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; BiTNode* BSTSearch(BiTree p,int key) { 
    while(p!=null) { 
    if(p==p->key) { 
    return p; } else if(key<p->key) { 
    return p->lchild; } else { 
    return p->rchild; } } return null; } 

递归

typedef struct BiTNode{ 
    ElemType key; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; BiTNode* BSTSearch(BiTree p,int key) { 
    if(p==null) { 
    return null; } else { 
    if(p==p->key) { 
    return p; } else if(key<p->key) { 
    return BSTSearch(p->lchild,key) } else { 
    return BSTSearch(p->rchild,key); } } } 

5.B树和B+树

一个关键字的空位子对应一个分支

B+树特性：
1.n个关键字n个分支；
2.m阶B+树每个结点至多有m个分支；
3.叶结点包含信息，非叶结点只是索引作用
4.可以顺序查找

一个关键字对应一个分支

6.散列表

解决冲突的方法
1.开放定地址法
其中的线型探测法：冲突发生时顺序探测下一个单元。
2.拉链法
把所有的同义词存储在一个线性链表中。