第8章 查找.pptVIP

第8章 查找;第8章 查找;平均查找长度ASL(Average Search Length);8.1 顺序查找;i;;8.2 折半查找;折半查找算法描述P220 算法9.2;low;例 ;1 2 3 4 5 6 7 8 9 10 11;算法评价 判定树：描述查找过程的二叉树叫~ 有n个结点的判定树的深度为?log2n?+1 折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度 折半查找的ASL;8.3 分块查找-索引顺序表的查找;1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18;分块查找方法评价;定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值 若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值 它的左、右子树也分别为二叉排序树 二叉排序树的插入 插入原则：若二叉排序树为空，则插入结点应为新的根结点；否则，继续在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子 二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树;插入算法P228 算法9.5(b)+9.6;BiTree SearchBST (BiTree T, KeyType key) { // 算法9.5(a) // 在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素， // 若查找成功，则返回指向该数据元素结点的指针，否则返回空指针 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); // 在右子树中继续查找 } // SearchBST ;Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree p) { // 算法9.5(b) // 在根指针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 TRUE; } // 查找成功 else if (LT(key, T-data.key)) return SearchBST(T-lchild, key, T, p); // 在左子树中继续查找 else return SearchBST(T-rchild, key, T, p); // 在右子树中继续查找 } // SearchBST ;Status InsertBST(BiTree T, ElemType e) { // 算法9.6 // 当二叉排序树T中不存在关键字等于e.key的数据元素时， // 插入e并返回TRUE，否则返回FALSE BiTree p,s; 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;