9_新教案第九章查找.ppt

* * 9.1 静态查找表 9.1.1 顺序查找 9.1.2 折半查找 9.2 动态查找表 9.2.1 二叉排序树 第九章 查找 9.3 哈希表 9.3.1 哈希表的定义 基本术语 同一类型数据元素构成的集合。 - 查找表 - 静态查找表 动态查找表 关键字 - 查找 ● 基本术语 在查找的过程中插入或删除数据元素。 数据元素中某个数据项的值，可以标识一个数据元素。 根据给定的某个值，在查找表中确定一个关键字等于给定值的数据元素。 只进行查询和检索操作。 9.1 静态查找表 顺序查找 - 创建 - 销毁 - 查找 - 遍历 ● 基本操作 ● 顺序查找 ●查找过程:从表中最后一个记录开始,逐个进行记录的关键字和给定值的比较。 Create(ST,n) Destroy(ST) Search(ST,key) Traverse(ST,Visit()) 9.1 静态查找表 顺序查找 ● 顺序查找 ●算法 typedef struct{ KeyType key; //关键字域 ... //其它域 }ElemType; struct SSTable{ ElemType *elem;//存储空间基址，按实际长度分配，0号空 int length; //表的长度 }; //静态查找表的顺序存储结构 int Search_Seq（SSTable ST，KeyType key）{ return i; } ST.elem[0].key=key; for(i=ST.length;!EQ(ST.elem[i].key,key);--i); 9.1 静态查找表 顺序查找性能分析 ● 顺序查找 ●性能分析 - 平均查找长度(ASL):为了确定记录在查找表中的位置,需要和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度. - 顺序查找的ASL: - 特点:算法简单且适应面广,查找效率低 9.1 静态查找表 折半查找 ● 折半查找 ●查找过程： 先确定待查记录的范围,然后逐步缩小范围直到找到或找不到该记录为止。 05 13 19 21 37 56 64 75 80 88 92 low mid high 05 13 19 21 37 56 64 75 80 88 92 low high mid 查找key=21的过程： 05 13 19 21 37 56 64 75 80 88 92 high low mid 折半查找 05 13 19 21 37 56 64 75 80 88 92 low mid high 05 13 19 21 37 56 64 75 80 88 92 high low mid 查找key=85的过程： 05 13 19 21 37 56 64 75 80 88 92 high low mid 05 13 19 21 37 56 64 75 80 88 92 high low 9.1 静态查找表 折半查找 ● 折半查找 ●算法 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 LT(key,ST.elem[mid].key) high=mid-1