[小学教育]第八章 查找.ppt

第八章 查找 8.1 基本概念 8.2 静态查找表 8.3 动态查找表 8.4 哈希表 查找——也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素 关键字——是数据元素中某个数据项的值，它可以标识一个数据元素 查找方法评价 查找速度 占用存储空间多少 算法本身复杂程度 平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的~ 8.2.1 顺序表的查找 查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较 #define MAXSIZE 100 #define KEYTYPE int typedef struct {KEYTYPE key; otherdata ……; // 记录的其余数据部分 }SSELEMENT; typedef struct { SSELEMENT r［MAXSIZE］; int len; }SSTABLE; 查找过程：每次将待查记录所在区间缩小一半 适用条件：采用顺序存储结构的有序表 算法实现: 设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值 初始时，令low=1,high=n,mid=?(low+high)/2? 让k与mid指向的记录比较 若k==r[mid].key，查找成功 若kr[mid].key，则high=mid-1 若kr[mid].key，则low=mid+1 重复上述操作，直至lowhigh时，查找失败 算法描述： 8.2.3 索引顺序表查找（分块查找） 查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找 适用条件：分块有序表 算法实现 用数组存放待查记录,每个数据元素至少含有关键字域 建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针 8.2　动态查找表 　　　动态查找表的特点：表结构本身是在查找过程中动态生成的，即对给定值key，若表中存在则查找成功，否则插入关键字等于key的记录． 定义：二叉排序树或是一棵空树，或 是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值 若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值 它的左、右子树也分别为二叉排序树 二叉排序树的插入： 插入原则：若二叉排序树为空，则插入结点应为新的根结点；否则，继续在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子 二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树 插入算法 数据结点类型： #define KEYTYPE int; typedef struct node {KEYTYPE key; otherdata ……; // 结点的其余数据部分struct node *lchild, *rchild; } BSTNODE 插入算法： void insert_btree_onenode(KEYTYPE k, BSTNODE *p) { if(p == NULL) // 如果二叉排序树空 {p = malloc(sizeof(BSTNODE)); p-lchild = NULL; p-rchild = NULL; p-key = k;} else if(k p-key) insert_btree_onenode(k,p-rchild else insert_btree_onenode(k,p-lchild } } 要删除二叉排序树中的p结点，分三种情况： p为叶子结点，只需修改p双亲f的指针 f-lchild=NULL f-rchild=NULL p只有左子树或右子树 p只有左子树，用p的左孩子代替p (1)(2) p只有右子树，用p的右孩子代替p (3)(4) p左、右子树均非空 沿p左子树的根C的右子树分支找到S，S的右子树为空，将S的左子树成为S的双亲Q的右子树，用S取代p (5) 若C无右子树，用C取代p (6) 查找性能的分析： 对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的ASL值，显然，由值相同