数据结构 | 第八章查找

朱雀 2021-11-22 13:24 372阅读 0赞

**(一) 查找的基本概念**

*  静态查找：只查找特定元素或其属性
 *  动态查找：除以上外还有插入删除操作。
 *  关键字：主关键字、次关键字。

**(二) 顺序查找法**

*  从表最后一个记录开始，逐个进行记录的关键字和给定值的比较，若相等则查找成功，若直至第一条记录都不相等则查找失败。

//静态查找表的顺序存储结构
    typedef struct{ 
    	EkemType *elem;//数据元素存储空间基址
    	int  length;//表长度
    }SSTable;

int Search_Seq(SSTable ST,KeyType key){ 
    	//在顺序表ST中顺序查找其关键字等于key的数据元素。
    	//若找到，则函数值为该元素在表中的位置，否则为0
    	ST.elem[0].key=key; //哨兵
    	for(i=ST.length; !EQ(ST.elem[i].key,key);--i);//从后往前找
    	return i；//找不到时，i为0
    }//Search.Seq

*  平均查找长度ASL=3/4（n+1）

**(三) 折半查找法**

*  先确定待查记录所在的范围，然后逐个缩小范围直到找到或者找不到为止

int Search_Bin(SSTable ST,KeyType key)
    { 
    	low=1;high=ST.length;//置区间初值
    	while(low<=high)
    	{ 
    		mid=(low+high)/2;
    		if(EQ(key,ST.elem[mid].key)) high=mid-1;
    		else low=mid+1;
    	}
    	return 0; //顺序表中不存在待查元素
    }

*  折半查找成功/不成功的比较关键字个数最多为![在这里插入图片描述][20190802103700584.png]
 *  平均查找长度为![在这里插入图片描述][20190802103827261.png]
 *  折半查找效率比顺序查找高，但折半查找只使用于有序表，且限于顺序存储结构（对线性链表无法折半查找）

**(四) 动态查找表**

*  二叉排序树（也叫二叉查找树）  
    空树；或者左子树小于根节点，右子树大于根节点，左右子树的左右子树均符合以上条件。  
    存储结构为二叉链表。

BiTree SearchBST(BiTree T,KeyType key, BiTree f, BiTree &p)
    { 
    	//在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素
    	//若成功，则指针p指向该元素结点，并返回TRUE，否则指针p指向查找路径上访问的
    	//最后一个结点并返回False，指针f指向T的双亲，其初始调用值为NULL
    	if (!T) { p=f;return FALSE;} //查找不成功
    	else if EQ(key,T->data.key){ P=t;return TURE;} //查找成功
    	else if LT(key,T->data.key) return(SearchBST(T->lchild,key));//左子树中继续查找
    	else return(SearchBST(T->rchild,key));//右子树中继续查找
    }

//插入

Status InsertBST(BiTree &T, ElemType e)
    { 
    	//当二叉排序树T中不存在关键字等于e.key的数据元素时
    	//插入e并返回TRUE，否则返回FALSE
    	if(!SearchBST(T,e.key,NULL,p){    //查找不成功
    	s=(BiTree)malloc(sizeof(BiTNode));
    	s->data=e; s->lchild=s->rchild=NULL;
    	if(!p) T=s;//被插结点*s为新的根结点
    	else if LT(e.key,p->data.key) p->lchild=s; //被插结点*s为左孩子
    	else p->rchild=s;
    	return TRUE;
    })
    else return FALSE;//树中已有关键字相同的结点，不再插入。
    }

//删除

Status DeleteBST(BiTree &T,KeyType key)
    { 
    	//若二叉排序树T中存在关键字等于key的数据元素结点，
    	//并返回True，否则返回FALSE
    	if(!T) return FALSE;//不存在关键字等于key的元素
    	else{ 
    		if(EQ(key,T->data.key)){ return Delete(T)};//找到关键字等于key的数据元素
    		else if （LT(key，T->data.key)）return DeleteBST(T->lchild,key);
    		else return DeleteBST(T->rchild,key);
    }
    }

Status Delete(BiTree &p)
    { 
    	//从二叉排序树中删除结点p并重接它的左或右子树
    	if（！p->rchild）//右子树空则只需重接它的左子树
    	{ 
    		q=p;p=p->lchild;free(q);
    	}
    	else if(!p->lchild)
    	{ 
    		q=p;p=p->rchild;free(q);
    	}
    	else{ //左右子树均不空
    		q=p;s=p->lchild;
    		while(s->rchild){ q=s;s=s->rchild}//左转，然后向右到尽头
    		p->data=s->data;//s指向被删结点的“前驱”
    		if(q!=p)q->rchild=s->lchild;//重新*q的右子树
    		else q->lchild=s->lchild;
    		delete s;
    }
    return TRUE;
    }

*  平衡二叉树  
    又叫AVL树。空树或者，左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差（平衡因子：-1、0、1）的绝对值不超过1。  
    （画图题）二叉排序树转成平衡二叉树。
 *  B-树及其基本操作  
    一棵m阶的B-树，或为空树，或为满足下列特性的m叉树：  
    1 树中每个结点至多有m棵子树；  
    2 若根结点不是叶子结点，则至少有两颗子树  
    3 除根之外的所有非终端结点至少有\[m/2\]棵子树  
    4 所有的非终端结点中包含下列信息数据，其中k为关键字，且ki<ki+1；A为指向子树根结点的指针，且指针指针Ai-1所指子树中所有结点的关键字均小于Ki，An所指子树中所有结点的关键字均大于Kn，n为关键字的个数，n+1为子树个数  
    ![在这里插入图片描述][20190802115917155.png]5 所有叶子结点都出现在同一层次上，并且不带信息  
    B-树主要用作文件的索引，因此它的查找涉及外村的存取。
 *  B树的插入和删除咋做？  
    图文演示：[https://www.cnblogs.com/nullzx/p/8729425.html][https_www.cnblogs.com_nullzx_p_8729425.html]

**(五) 哈希(Hash)表**  
存储地址与存储的值有一定的对应关系。存储位置叫哈希地址或散列地址。  
**(六) 查找算法的分析及应用**

[20190802103700584.png]: /images/20211122/96829fa11139404f91429fee41627e52.png
[20190802103827261.png]: /images/20211122/04dbb677484e4f55b2cff57a867aca93.png
[20190802115917155.png]: /images/20211122/556a8b522a2a47d5b527f9a4a7478468.png
[https_www.cnblogs.com_nullzx_p_8729425.html]: https://www.cnblogs.com/nullzx/p/8729425.html