数据结构复习题.ppt

* * 书虽然摆放整齐了，但是还没有分门别类，具体的书和它们的摆放位置没有关系，因此，我们只能从头到尾一本一本的找，这就是我们现在要介绍的顺序查找法 注意，代码中线性表的元素从1开始存放 * 很显然，这与之前的查找算法基本一致，仅仅在于设置了一个监视哨，这是一个程序设计技巧上的改进 监视哨避免了对 i值 是否越界的判断，在 N 非常大时，对整个算法时间效率的提高有着非常显著的效果 对于查找成功，查找到的元素在所有位置上的概率相同，均为 1/n 对于查找不成功，进行比较的次数是固定值 n+1 假设查找成功和不成功的概率相同，ASL = ?(n+1) 通常在实际应用中，查找不成功的概率非常低，可以忽略不计 * 思考一个小游戏：系统给定一个100以内的正整数，请大家尝试猜到底是哪个数。每次猜，只告诉大了还是小了，请，最快几次可以猜出是什么数字？ * ASL = log2(n+1) – 1 * 图1、4是平衡二叉树 图2、3不是平衡二叉树 * * * * * * 15 18 2 3 18 16 -2 左右双旋 7 3 0 0 0 11 7 14 9 -1 16 15 0 1 11 26 26 14 1 -2 9 散列（哈希）方法 散列方法： 在表项存储位置与其关键码之间建立一个确定的对应函数关系Hash( )，使每个关键码与结构中一个唯一存储位置相对应： Address ＝ Hash ( Rec.key ) 在有哪些信誉好的足球投注网站时, 先对表项的关键码进行函数计算,把函数值当做表项的存储位置, 在结构中按此位置取表项比较。若关键码相等,则有哪些信誉好的足球投注网站成功。否则失败。 在存放表项时, 依相同函数计算存储位置,并按此位置存放。 冲突及解决策略 散列函数是一个压缩映象函数。关键码集合比散列表地址集合大得多。因此有可能经过散列函数的计算，把不同的关键码映射到同一个散列地址上，这就产生了冲突 常用冲突解决策略 开放定址法（线性探测、二次探测、随机探测) 二次散列 链表法 公共溢出区 设一组记录的关键字为： PV1031, TI1104, PV0301, TI0103, PV0012, TI1205 存储表为L[0..9] 定义H(key)为key的后四位之和模除10。 探测序列为：+1, -1, +2, -2, +3, -3, ... H(PV1031)=5 H(TI1104)=6 H(PV0301)=4 H(TI0103)=4 H(PV0012)=3 H(TI1205)=8 0 1 2 3 4 5 6 7 8 9 PV1031 TI1104 PV0301 TI0103 PV0012 TI1205 设一组记录的关键字为： PV1031, TI1104, PV0301, TI0103, PV0012, TI1205 存储表为L[0..9] 定义H1(key)为key的后四位之和模除10， 定义H2(key)为key的后四位的值模除10。 H1(PV1031)=5 H1(TI1104)=6 H1(PV0301)=4 H2(TI0103)=3 H2(PV0012)=2 H1(TI1205)=8 0 1 2 3 4 5 6 7 8 9 PV1031 TI1104 PV0301 TI0103 PV0012 TI1205 设一组记录的关键字为： PV1031, TI1104, PV0301, TI0103, PV0012, TI1205 链式存储表为L[0..9] 定义H(key)为key的后四位之和模除10。 H(PV1031)=5 H(TI1104)=6 H(PV0301)=4 H(TI0103)=4 H(PV0012)=3 H(TI1205)=8 0 1 2 3 4 5 6 7 8 9 PV0012 PV0301 PV1031 TI1104 TI1205 TI0103 PV0301 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 设一组记录的关键字为： PV1031, TI1104, PV0301, TI0103, PV0012, TI1205 存储表为L[0..9] 定义H(key)为key的后四位之和模除10。 探测序列为：+1, -1, +2, -2, +3, -3, ... H(PV1031)=5 H(TI1104)=6 H(PV0301)=4 H(TI0103)=4 H(PV0012)=3 H(TI1205)=8 PV1031 TI1104 PV0301 TI0103 PV0012 TI1205 装填因子 哈希表的装填因子： α=（表中填入的记录数）/（哈希表的长度） α标志哈希表的装满程度 α越小，发生冲突的可能性越小 α越大，发生冲突的可能性越大 不论表的长度有多大, 我们总能选择一个合适的装填因子