07查找01-数据结构课程教学网站.ppt

7 查找(1) ;1、掌握查找的概念，熟练掌握顺序表和有序表（折半查找）的查找算法及其性能分析方法； 2、掌握二叉排序树的概念，熟练掌握二叉排序树的构造和查找算法及其性能分析方法； 3、掌握二叉排序树的插入算法，二叉排序树的删除方法； 4、掌握平衡二叉树的概念，掌握平衡化二叉树的方法； 5、掌握哈希查找的概念，掌握哈希函数（除留余数法）的构造。 6、掌握用线性探测法和链地址法解决冲突的方法，并能进行查找长度的计算。 7、熟悉标准模版库STL中的相关知识。;7.1 静态查找表 7.2 动态查找表 7.3 哈希表（散列表） 7.4 查找与标准模版库STL;问题一;问题二;相关知识;什么是查找表 ？;对查找表经常进行的操作:;静态查找表：仅作查询或检索操作的查找表。; 是数据元素（或记录）中某个数据项的值，用以标识某个数据元素（或记录）。 ; 在查找表中确定是否存在一个数据元素，该元素的关键字等于给定的某个值。 若查找表中存在这样的元素，则“查找成功”。否则“查找失败”。; 查找的方法取决于查找表的结构。采用不同的存储结构将导致不同的查找效率。 因此，采用合适的数据结构来表示查找表是非常重要的。;7.1 静 态 查 找 表;数据对象D：; 通常以顺序表或线性链表表示静态查找表。;静态查找表的顺序存储结构为 struct SSTable{ ElemType *elem; // 元素存储空间基址，0号单元留空 int length; // 表的长度 };;ST.elem;int Location(SSTable ST, KeyType e) // 正向查找 { k = 1; while ( k=ST.length ST.elem[k]!=e) k++; if ( k= ST.length) return k; else return 0; } //Location;ST.elem;int Search_Seq(SSTable ST, KeyType keyV) { // 在顺序表ST中顺序查找其关键字等于key的数据元素。 // 若找到，则返回该元素在表中的位置，否则为0。 ST.elem[0].key = keyV; // “哨兵” // 从后往前找 for (i=ST.length; ST.elem[i].key!=keyV; i--) ; return i; // 找不到时，i为0 } // Search_Seq; 定义： 查找算法的平均查找长度 (Average Search Length) 为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值 其中: n 为表长，Pi 为查找表中第i个记录的概率， 且 　 ， Ci为找到该记录时，已经的比较次数。; 在等概率查找的情况下， 顺序表查找的平均查找长度为： ;若考虑查找不成功时的情况： 查找不成功时的比较次数：n+1 假设有一半情况查找失败，则兼顾查找成功和失败平均查找长度为：; 顺序查找表的查找算法简单，但平均查找长度较大，效率较低。;折半查找的基本思想;ST.elem;int Search_Bin ( SSTable ST, KeyType keyV) { low = 1; high = ST.length; // 置区间初值 while (low = high) { mid = (low + high) / 2; if (keyV == ST.elem[mid].key ) return mid; // 找到待查元素 else if (keyV ST.elem[mid].key) high = mid - 1; // 继续在前半区间进行查找 else low = mid + 1; // 继续在后半区间进行查找 } return 0; // 顺序表中不存在待查元素 } // Search_Bin;先看一个具体的情况，假设：n=11;为讨论方便，设 n=2h-1，且查找概率相等 则 在n50时，可