查找算法总结-创新互联
查找
对数值型关键字
#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
哈希查找
哈希表：根据设定的哈希函数和处理冲突的方法，将一组关键字映象到一组有限的连续的存储空间上，以关键字对应的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元起，快前往官网查看详情吧
新闻名称：查找算法总结-创新互联
标题来源：http://cdiso.cn/article/dpegej.html
