查找-数据结构.ppt

静态查找表 动态查找表 哈希表 查找的基本概念和术语 查找表：由同一类型的数据元素（或记录）构成的集合。 静态查找表：若对查找表只作查找操作，则称此类查找表为静态查找表。 动态查找表：若在查找过程中同时插入表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素，则称此类查找表为动态查找表。 关键字：数据元素中某个数据项的值，用它可以标识一个数据元素。若此关键字可以唯一的标识一个记录，则称此关键字为主关键字。反之，称用以识别若干记录的关键字为次关键字。当数据元素只有一个数据项时，其关键字即为该数据元素的值。 查找：根据给定的某个值，在查找表中确定一个其关键字等于给顶值的记录或数据元素。若表中存在这样的一个记录，则称查找是成功的，此时查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可给出一个“空”记录或“空”指针。 平均查找长度：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度，简称ASL。 对于含有n个记录的表，查找成功时的平均查找长度为： 顺序查找的基本思想： 从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值K相比较， 若相等，则查找成功， 若整个表扫描完毕，仍末找到关键字等于K的元素，则查找失败。 顺序表的类型描述 #define max 1024 typedef int ElemType; typedef struct{ ElemType data[max];/*0号单元留空*/ int length; }SSTable; 算法实现 性能分析 对于含有n个记录的顺序表，在等概率情况下进行顺序查找的查找成功的平均查找长度为 假设查找成功和查找不成功的可能性相同，对每个记录的查找概率也相同，则此时顺序查找的平均查找长度为 有序表的查找 折半查找的查找过程 将待查的 key值和有序表ST.data[low..high] 的中间位置mid上的结点的关键字进行比较，若相等，则查找成功，返回该结点的下标mid 否则，若keyST.data[mid]，则在左子表ST.data[low..mid-1]中继续进行折半查找 若keyST.data[mid]，则在右子表ST.data[mid+1..high]中继续进行折半查找。 这样，经过一次关键字比较就缩小一半的查找区间。如此进行下去，直到找到关键字为key的结点，或者当前的查找区间为空，查找失败。 例如：已知如下11个数据元素的有序表： {05,13,19,21,37,56,64,75,80,88,92} 现要查找关键字为21和85的数据元素。 假设指针low和high分别指示待查元素所在区间的下界和上界，指针mid指示区间的中间位置，mid= ?(low+high)/2 ? 查找21 查找85 算法实现 int Search_bin (SSTable ST,KeyType key){ 　 　low=1; high=ST.length; 　while(low=high){ 　　mid=(low+high)/2; 　　if(key==ST.elem[mid].key) return(mid); else if(keyST.elem[mid].key) high=mid-1; 　　　 else low=mid+1; 　} return(0); } 性能分析 二分查找的查找过程可以用一棵二叉树来描述。其中，树中的每个结点表示一个记录，结点中的值为该记录在表中的位置，通常称这个描述查找过程的二叉树为判定树。 判定树的构造过程：把整个查找区间的中间位置作为根结点，左子表或右子表的中间位置作为根的左孩子或右孩子，依此类推，得到的二叉树即为描述二分查找的判定树。 由此可见，二分查找过程恰好是走了一条从判定树的根到被查结点的路径，比较的关键字个数恰为该结点在判定树中的层数。 如果在二分查找的判定树中的所有结点的空指针域上加上一个指向一个方形结点的指针并称这些方形结点为外部结点（与之相对，称那些圆形结点为内部结点），那么折半查找时查找不成功的过程就是走了一条从根结点到外部结点的路径，和给定值进行比较的关键字的个数等于路径上内部结点的个数。 判定树非完全二叉树，但它的叶子结点所在的层次之差最多为1，则n个结点的判定树的深度和n个结点的完全二叉树的深度相同。 这般查找在查找成功和查找失败时进行比较的关键字个数最多不超过树的深度，而具有n个结点的判定树的深度为?log2n ?+1 ，因此折半查找的平均时间复杂度为O(log2n )。 顺序查找与折半查找