(一) 查找的基本概念
静态查找：只查找特定元素或其属性动态查找：除以上外还有插入删除操作。关键字：主关键字、次关键字。(二) 顺序查找法
从表最后一个记录开始，逐个进行记录的关键字和给定值的比较，若相等则查找成功，若直至第一条记录都不相等则查找失败。 //静态查找表的顺序存储结构 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; //顺序表中不存在待查元素 } 折半查找成功/不成功的比较关键字个数最多为平均查找长度为折半查找效率比顺序查找高，但折半查找只使用于有序表，且限于顺序存储结构（对线性链表无法折半查找）(四) 动态查找表
二叉排序树（也叫二叉查找树） 空树；或者左子树小于根节点，右子树大于根节点，左右子树的左右子树均符合以上条件。 存储结构为二叉链表。 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为子树个数 5 所有叶子结点都出现在同一层次上，并且不带信息 B-树主要用作文件的索引，因此它的查找涉及外村的存取。B树的插入和删除咋做？ 图文演示：https://www.cnblogs.com/nullzx/p/8729425.html(五) 哈希(Hash)表 存储地址与存储的值有一定的对应关系。存储位置叫哈希地址或散列地址。 (六) 查找算法的分析及应用
