第九章查找 静态查找表 动态查找表 哈希查找表 91基本概念Pae214 >查找表:是由同一类型数据元素构成的集合 构 静态查找表:只做“查询”或“检索”操作 动态查找表:查询、检索、插入、删除。 关键字:是数据元素中某个数据相的值,用 它可以标识一个数据元素。 主关键字、次关键字 查找:根据给定值,在查找表中确定一个其 关键字等于给定值的数据元素。 查找成功返回位置序号、查找不成功返回0
1 第九章 查找 • 静态查找表 • 动态查找表 • 哈希查找表 数 据 结 构 之 查 找 2 9.1 基本概念(Page 214) ¾ 查找表：是由同一类型数据元素构成的集合。 ¾ 静态查找表：只做“查询”或“检索”操作。 ¾ 动态查找表：查询、检索、插入、删除。 ¾ 关键字：是数据元素中某个数据相的值，用 它可以标识一个数据元素。 主关键字、次关键字 ¾ 查找：根据给定值，在查找表中确定一个其 关键字等于给定值的数据元素。 查找成功返回位置序号、查找不成功返回 0
注意 据结构 比较各种查找算法时间 复杂度和空间复杂度, 查找算法的主要时间用 于“关键字的比较”。 92静态查找表 据>顺序表的查找 构 typedef int KT; typedef struct(KT key ;.ET typedef struct{ ET*elem;数据元素存储空间基址 0为空单元 int length;SsT 查 int Search_ Sq(SST ST, Kt key)i St elem0Jkey=key;/设置哨兵 for(i-STlength; key!=STelem(ikey; i--); return 1;
2 数 据 结 构 之 查 找 3 注意 比较各种查找算法时间 复杂度和空间复杂度， 查找算法的主要时间用 于“关键字的比较”。 数 据 结 构 之 查 找 4 9.2 静态查找表 ¾ 顺序表的查找 typedef int KT ; typedef struct{KT key ; ... }ET; typedef struct{ET *elem; //数据元素存储空间基址， 0为空单元 int length;}SST; int Search_Sq(SST ST, KT key){ St.elem[0].key=key;//设置哨兵 for(i=ST.length ; key!=ST.elem[i].key; i--) ; return i; }
>顺序表的查找算法性能分析 据结构 在等概率的情况下:Pi=1/n >查找成功时的平均查找长度:(n+1)/2 查找不成功时的比较次数:n+1 假设查找成功与不成功的可能性相同, 在等概率的情况下:Pi=1/2n,则顺序 查找的平均查找长度为 ASLsS=(n+1)+(n+1)2)/2=3(n+1)/4 有序表的查找折半查找 数据结构 >折半查找(二分查找):经过一次比较将 表分割成两部分,然后只在表的一部分中 继续进行查找的方法。 mid=(low+high)/2 513192158798088 查 ow= /Lmid= high=8
3 数 据 结 构 之 查 找 5 ¾ 顺序表的查找算法性能分析 在等概率的情况下：Pi=1/n ¾查找成功时的平均查找长度： (n+1)/2 ¾查找不成功时的比较次数： n+1 ¾假设查找成功与不成功的可能性相同， 在等概率的情况下：Pi=1/2n , 则顺序 查找的平均查找长度为： ASLss=((n+1)+(n+1)/2)/2=3(n+1)/4 数 据 结 构 之 查 找 6 ¾ 有序表的查找——折半查找 ¾ 折半查找（二分查找）：经过一次比较将 表分割成两部分，然后只在表的一部分中 继续进行查找的方法。 mid=(low+high)/2 key =13
二分算法描述 s int Search_Bin(SST ST, KT key)t 结 low=l: high-ST length; 构 while(ow<=high) mid=(+high)/2 if(key==STelem(mid. key) return mid; else if(key<sTelem mid). key) high=mid-1 else low=mid+1; return 0 时间复杂度:Oogn) 二叉树的性质 数1、在二叉树的第层上至多有2个结点(>=1); 站2、深度为k的二叉树至多有2-1个结点(k>=1); 构3、对任何一棵二叉树T,如果其终端结点数为 n0,度为2的结点数为n,则n=n2+1。 4、具有n个结点的完全二叉树的深度为 t Llog:n+
4 数 据 结 构 之 查 找 7 ¾ 二分算法描述 int Search_Bin(SST ST, KT key){ low=1 ; high=ST. length; while(low<=high){ mid=(low+high)/2; if(key==ST.elem[mid].key) return mid; else if(key<ST.elem[mid].key) high=mid-1; else low=mid+1; } return 0; }//时间复杂度：O(log2 n) 数 据 结 构 之 查 找 8 ¾ 二叉树的性质 1、在二叉树的第 i 层上至多有2 个结点(i>=1); 2、深度为k的二叉树至多有2 -1个结点(k>=1); 3、对任何一棵二叉树T，如果其终端结点数为 n0，度为2的结点数为n2，则n0=n2+1。 4、具有n个结点的完全二叉树的深度为: log2 n +1 k i-1
二叉判定树 查找过程可用二 据结构 叉树来描述。树 中每个结点表示 记录,结点 中的值为该记录 在表中的位置 通常这个描述查 找过程的二叉树 为判定树。 6的的國 在该树中,和给 定值进行比较的 次数恰为该结点 在判定树中的层 次 性能分析 比较次数最多: 数据结构 Llog,n 1 不超过判定树的深度 时间复杂度: O(og,n) 此方法只能适用 于有序表,且限 66 于顺序存储结构
5 数 据 结 构 之 查 找 9 ¾ 二叉判定树 ¾查找过程可用二 叉树来描述。树 中每个结点表示 一个记录，结点 中的值为该记录 在表中的位置， 通常这个描述查 找过程的二叉树 为判定树。 ¾在该树中，和给 定值进行比较的 次数恰为该结点 在判定树中的层 次。 数 据 结 构 之 查 找 10 ¾ 性能分析 比较次数最多： log2 n+1 不超过判定树的深度 时间复杂度： O(log2 n) ¾ 此方法只能适用 于有序表，且限 于顺序存储结构