第九章-查找.ppt

查找 9.1 静态查找表 9.1.1 顺序表的查找 9.1.2 有序表的查找 9.2 动态查找表 9.2.1 二叉排序树和二叉平衡树 9.2.2 B-树和B+树 9.3 哈希表(散列表) 查找 查找表 (search table): 同一类型数据元素构成的集合。 查找操作: (1)查询某个“特定的”数据元素是否在查找表中; (2)检索某个“特定的”数据元素的各种属性; (3)在查找表中插入一个数据元素; (4)从查找表中删除某个数据元素. 静态查找表:对查找表只作(1)(2)操作； 动态查找表:可以对查找表作(1)-(4)操作 有关查找的“词”的含义 关键字(KEY): 数据元素(或记录)的某个数据项的值,用以标识一个数据元素(或记录). 可以唯一标识一个记录的关键字称为主关键字(Primary Key); 否则称为次关键字(Secondary Key). 查找(Searching) 根据给定的值,在查找表中确定一个关键字等于给定值的记录或数据元素. 9.1 静态查找表 可以用顺序表，也可以用线性链表来表示静态查找表。 顺序表的查找 //静态查找表的顺序存储结构 typedef struct{ ElemType *elem; int length; }SSTable; 顺序查找 int Search_Seq(SSTable ST, KeyType key){ ST.elem[0].key = key;// “哨兵” for(i=ST.length;!EQ(ST.elem[i].key,key); --i); return i; } 有序表的查找:折半查找 确定待查记录的区间，逐步缩小范围直到找到或找不到该记录为止。 例： 数据元素有序表如下,查找关键字key=21的数据元素。 (1) key=ST.elem[mid].key查找成功; (2)当keyST.elem[mid].key时,下一个待查区间为[low,mid-1] (3)当keyST.elem[mid].key时下一个待查区间为[mid+1,high] 折半查找的性能分析 索引顺序表 索引项：包括关键字项和指针项 分块有序 确定块的查找可以用顺序查找或折半查找 块中顺序查找 9.2 动态查找表 动态查找表:表结构是在查找过程中动态生成的,即对于给定值key,若表中存在关键字为key的记录,则查找成功并返回;否则插入关键字等于key的记录。 动态查找表的实现 二叉排序树 平衡二叉树 B-和B+树 9.2.1 二叉排序树 二叉排序树(Binary Sort Tree): 二叉排序树是空树,或者是具有以下性质的二叉树: (1)若左子树非空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树非空,则右子树上所有结点的值均大于它的根结点的值; (3)它的左、右子树也分别为二叉排序树 二叉排序树举例 二叉排序树的查找操作 Status SearchBST(BiTree T, KeyType key) { // f指向T的父结点，初始值为NULL if(!T||EQ(key,T-data.key) return (T) ; else if (LT(key,T-data.key)) return SearchBST(T-lchild,key) ; else return SearchBST(T-rchild,key) ; } 二叉排序树的生成(插入结点) 插入操作：新插入结点是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点 例如:对{45,24,53,45,12,24,90}关键字序列的二叉排序树生成过程如下: 二叉排序树的查找操作 Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree p ) { // f指向T的父结点，初始值为NULL if(!T) { p = f ; return FALSE ; } else if (EQ(key,T-data.key)) { p=T; return TRUE;} else if (LT(key,T-data.key)) return SearchBST(T-lchild,key,T,p) ; else return SearchBST(T-rchild,key,T,p) ; } 二叉树的插入操作 Status InsertBST(BiTree T, ElemType e ) { if(!SearchBST(T,e.key,NULL,p)) { s = (BiTree)malloc(sizeof