[教育]数据结构课件9.pptVIP

第八章 查找 60 17 29 60 17 29 38 38 60 17 29 38 60 17 29 H(key)=key mod 11 线性探测再散列 二次探测再散列 伪随机探测再散列 第八章 查找 2、再哈希法 Hi=RHi(key) 3、链地址法 将所有关键字为同义词的记录存储在同一线 性链表中。 附设指针数组。 不产生二次聚焦 4、建立一个公共溢出区 * Data Structure * 数据结构 第一章 绪论 第二章 线性表 第三章 栈和队列 第四章 串 第五章 数组和广义表 第六章 树和二叉树 第七章 图 第八章 查找 第九章 内部排序 第八章 查找 查找表：由同一类型的数据元素（或记录）构成 的集合。 静态查找表—— 1）查找某个“特定的”数据元素是否在查找表中； 2）检索某个“特定的”数据元素的各种属性； 动态查找表—— 3）在查找表中插入一个数据元素； 4）在查找表中删除某个数据元素。 第八章 查找 1、关键字 是数据元素（记录）中某个数据项的值，用 它可以标识（识别）一个数据元素（记录）。 主关键字、次关键字 2、查找 在一个含有众多的数据元素(记录）的查找 表找出某个“特定的” 数据元素(记录）。 查找成功：位置/值 查找不成功：0/空指针 对表进行查找的方法取决于表中数据元素依 何种关系组织在一起。 第八章 查找 8.1 静态查找表 一、顺序表的查找 1、数据结构: 顺序表/线性链表 typedef struct { elemtype ?elem； int length； } sstable； 2、过程 从表中最后一个记录开始，逐个进行记录的关 键字和给定值的比较。若某个记录的关键字和给 定值比较相等，则查找成功，找到所查找记录； 反之，若直至第一个记录，其关键字和给定值比 较都不相等，则表中没有所查记录，查找不成功 第八章 查找 int Search_Seq(SSTable ST , KeyType key) { ST.elem[0].key=key ; for( i=ST.length; !EQ(ST.elem[i].key,key); --I ) ; return i; } 3、性能分析??平均查找长度 为了确定记录在查找表中的位置，需和给定 值进行比较的关键字个数的期望值称为查找算法 在查找成功时的平均查找长度。 第八章 查找 二、有序表的查找 1、数据结构：有序表 2、折半查找 先确定待查找记录所在的范围，然后逐步缩小范围直到找到或找不到该记录为止(区间中间位置记录的关键字等于给定值或查找区间的大小小于零）。 第八章 查找 例： 5，13，19，21，37，56，64，75，80，88，92 Key=85 mid = [(low+high)/2], low=1, high=11 low mid high step1mid=68556 low mid high step2mid=98580 low mid high step3mid=108588 step4mid=10 (high)(low) 查找失败！ low high mid int Search_Bin(SSTable ST, KeyType key) { low=1; high=ST.length; while(low=high) { mid=(low+high)/2; if(EQ(key,ST.elem[mid].key) return mid; else if(L