数据结构与算法分析第七章查找.pdfVIP

第七章 查找 • 静态查找表顺序，折半，索引顺序 • 静态查找表顺序，折半，索引顺序 • 动态查找表树表 • 动态查找表树表 • 哈希查找表 • 哈希查找表 7.1 查找概念 7.1 查找概念 查找表(table): 由同类型的DE(或记录)构成的集合. 查找表(table): 由同类型的DE(或记录)构成的集合. 查找表上的基本运算: • 建立查找表create(ST, n) • 查找search(ST, k) • 遍历查找表traverse(ST) 7.1 静态查找表 7.1 静态查找表 查找 : 在查找表中确定与给定值相等的DE 的过程. 查找 : 在查找表中确定与给定值相等的DE 的过程. 查找结果: • 查找成功 (table 中存在给定值的记录) • 查找成功 (table 中存在给定值的记录) • 查找不成功 (table 中不存在给定值的记录) • 查找不成功 (table 中不存在给定值的记录) 查找表分为: 查找表分为: • 静态查找表 (对查找表中的数据元素不进行插入和删 • (对查找表中的数据元素不进行插入和删 除操作) 除操作) • 动态查找表 (对查找表中的数据元素可进行插入和删 • (对查找表中的数据元素可进行插入和删 除操作) 除操作) 7.2 静态查找表 7.2 静态查找表 一. 顺序表的查找 • 查找过程: 从n开始,依次与k进行比较, 若相等则查找 • 查找过程 从n开始,依次与k进行比较, 若相等则查找 成功; 否则, 继续进行,直到与r[0].key 比较为止. 成功; 否则, 继续进行,直到与r[0].key 比较为止. 24 k=24 12 23 1 24 67 11 int serach-seq(sstabel st,keytype k) r[0] r[1] r[2] r[3] r[4] r[5] r[6] { st.elem[0].key=k; For (i=st.length; ! eq(st.elem[I].key, k); --i) Return i; } 7.2 静态查找表 7.2 静态查找表 int serach-seq(sstabel st,keytype k) { st.elem[0].key=k; For (i=st.length; ! eq(st.elem[I].key, k); --i) Return i; } 2. 算法分析: 2. 算法分析 (1) 算法结构应由一个循环构成; (1) 算法结构应由一个循环构成; (2) 循环结束有两种可能： (2) 循环结束有两种可能： • 查找成功 r[i].key = k • 查找成功 r[i].key = k • 查找不成功 i = 0 • 查找不成功 i = 0 3. r[0]起监视哨作用 3. r[0]起监视哨作用 7.2 静态查找表 7.2 静态查找表 平均查找长度(ASL): 平均查找长度(ASL): 查找过程中, 给定值需与关键字比较的次数的期望值. 查找过程中, 给定值需与关键字比较的次数的期望值. n n