数据结构第9章-1.ppt

int binsrch(SqList st, KeyType k, int low, int high) { if (lowhigh) return(0)； mid= (low + high) / 2； switch { case st.elem[[mid].key == k：return(mid)； case st.elem[mid].key k： return(binsrch(st, k, low, mid-1)； case st.elem[mid].key k： return(binsrch(st, k, mid+1, high)； } } //bisrch * * 9.1 静态查找表 9.2 动态查找树表 9.3 哈希表 查找：在不同的表结构中查找指定元素。 查找到指定元素— 返回该元素在表中的位置。 若找不到满足条件的元素— 查找失败，返回特定值。 元素(记录)的关键字：可以标识一个元素(记录)的数据项值 不同的表结构(查找表)采用不同的查找方法 查找表： 同一类型的数据元素的存储结构 基本操作：查找，插入，删除。 静态查找表：对表只作查找操作。 动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素。 typedef struct { KeyType key； //关键字成员 …… ； //其它成员 } ElemType 本章以后各节中涉及的数据元素类型统一定义为： 静态查找表的类型描述： typedef struct{ ElemType * elem；//数据元素存储空间的首地址，建表时按实际长度分配，0号单元不存记录。 int length； // 静态查找表的长度 } SqList ； int seqsrch(SqList st， KeyType k){ //在静态表st中，查找key域为k的记录的位置，若不存在返回0 i=st.length； while (st.elem[i].key≠k i0) i-- ； return(i) } // seqsrch 9.1.1 顺序查找 如果数组中关键字的排列是无序的，只能进行逐个查找。可采用顺查或逆查。 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 i i 60 i kval = 64 kval = 60 i 改进： 在st.elem[0]处设立监视哨，可以减少查找时间 64 int seqsrch(SqList st，KeyType k){ st.elem[0].key= k； // 监视哨 i= st.length； while (st.elem[i].key≠k) i--； return(i) } //seqsrch 0 1 2 3 4 … st.length st.elem …… k 改进： 在st.elem[0]处设立监视哨。 查找方法评价 算法本身复杂程度 占用存储空间多少 查找速度 —— 平均查找长度ASL ( Average Search Length ) 为确定记录在查找表中的位置，需要和给定值 进行比较的关键字个数的期望值 其中: n 为表长 Pi ——查找第i个记录的概率且 Ci ——为找到该记录和关键字比较过的次数 顺序表查找的平均查找长度为： 对顺序表查找方法而言，Ci = n-i+1 在等概率查找的情况下， ASLunsucc = n + 1 查找不成功时： 2 1 1 1 1 + = + - = ? = n ) i (n n n i ? = = n i i i C P ASL 1 ? = = n i 1 n 1 (n -i+1) 9.1.2 有序表的查找 有序表：表中的记录按关键字有序排列。 即： st.elem[i].key≤ st.elem[i+1].key； (i=1，2，……，n-1) 可使用折半（二分）查找来实现。 折半查找算法： 假设有一序列存在数组 r 中，指针low和high分