CHAP009_查寻.pptVIP

第九章 查找;学 号 ;查找的基本概念;查找表 是由具有同一类型的记录组成的集合。 　 分为静态查找表和动态查找表两类。 1)静态查找表：仅对查找表进行查找操作，而不能改变的表； 2)动态查找表： 除可进行查找操作外，还可进行向表中插入，或删除记录的表。 ? 查找 给定一个值K，在查找表中进行有哪些信誉好的足球投注网站，寻找关键字值等于K的记录，如果找到则输出该记录，否则输出查找不成功的信息。也称为检索。;对查找表经常进行的操作:;查找方法评价 查找速度 占用存储空间多少 算法本身复杂程度 平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需进行的关键字比较次数的期望值叫查找算法的~;如何进行查找？;9.1 静态查找表;9.1 静 态 查 找 表;数据对象D：; Create(ST, n);; 构造一个含n个数据元素 的静态查找表ST。 ;销毁表ST。;若 ST 中存在其关键字等于 key 的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。 ;按某种次序对ST的每个元素调用函数Visit()一次且仅一次，一旦Visit()失败，则操作失败。;typedef struct { // 数据元素存储空间基址，建表时 // 按实际长度分配，0号单元留空 int length; // 表的长度 } SSTable;;数据元素类型的定义为:;一、顺序查找表; 以顺序表或线性链表表示静态查找表;1、 顺序查找 查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较，直到找到关键字等于K的记录或到达表的另一端。 可以采用从前向后查，也可采用从后向前查的方法。;ST.elem;int location( SqList L, ElemType e, Status (*compare)(ElemType, ElemType)) { k = 1; p = L.elem; while ( k=L.length !(*compare)(*p++,e))) k++; if ( k= L.length) return k; else return 0; };1、 顺序表查找 算法描述;0 1 2 3 4 5 6 7;int Search_Seq(SSTable ST, KeyType key) { // 在顺序表ST中顺序查找其关键字等于 // key的数据元素。若找到，则函数值为 // 该元素在表中的位置，否则为0。 ST.elem[0].key = key; // “哨兵” for (i=ST.length; ST.elem[i].key!=key; --i); // 从后往前找 return i; // 找不到时，i为0 }; 在等概率查找的情况下， 顺序表查找的平均查找长度为： ;顺序表查找; 上述顺序查找表的查找算法简单， 但平均查找长度较大，特别不适用于表长较大的查找表。;2 折半查找 查找过程：每次将待查记录所在区间缩小一半 适用条件：采用顺序存储结构的有序表 算法实现 设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点，k为给定值 初始时，令low=1, high=n, mid=?(low+high)/2? 让k与mid指向的记录比较 若k==r[mid].key，查找成功 若kr[mid].key，则high=mid-1 若kr[mid].key，则low=mid+1 重复上述操作，直至lowhigh时，查找失败;折半查找 算法描述;例 ;1 2 3 4 5 6 7 8 9 10 11;折半查找的c语言算法程序： int Search_Bin( SSTable ST[ ], int n, int key) {int low, high,mid; low=1; high=n; while(low=high) { mid=(low+high)/2; if(ST[mid].key= = key) return (mid); /*查找成功*/