八章 查找.pptVIP

第八章 查找 查找的概念 查找表 是由同一类型的数据元素(或记录)构成的集合,由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的数据结构。 对查找表的操作: 查询某个“特定的”数据元素是否在查找表中; 检索某个“特定的”数据元素的各种属性； 在查找表中插入一个数据元素； 从查找表中删去某个数据元素 查找表的分类 静态查找表 仅作查询和检索操作的查找表。 动态查找表 在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素,此类表为动态查找表。 关键字 是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。 若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。 若此关键字能识别若干记录，则称之谓“次关键字”。 查找 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。 若查找表中存在这样一个记录,则称“查找成功” 查找结果：给出整个记录的信息，或指示该记录在查找表中的位置； 否则称“查找不成功” 查找结果：给出“空记录”或“空指针”。 如何进行查找 查找的方法取决于查找表的结构。 由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。 为了提高查找的效率， 需要在查找表中的元素之间人为地 附加某种确定的关系，换句话说， 用另外一种结构来表示查找表。 查找方法评价 查找速度 占用存储空间多少 算法本身复杂程度 平均查找长度ASL(Average Search Length) 为确定记录在表中的位置，需要和给定值进行比较的关键字的个数的期望值 静态查找表 顺序表的查找 以顺序表表示静态查找表，则Search函数可用顺序查找来实现。 顺序存储结构 typedef struct { ElemType *elem; // 数据元素存储空间基址，建表时按实际长度分配，0号单元留空，预备做哨兵 int length; // 表的长度 } SSTable; 查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较。 算法实现 int Search_Seq(SSTable ST, KeyType kval) { /* 在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。 */ ST.elem[0].key = kval; // 设置“哨兵” for (i=ST.length; ST.elem[i].key!=kval; --i) ; // 从后往前找 return i; // 找不到时，i为0，哨兵 } // Search_Seq 有序表的查找 顺序表的查找算法简单，但平均查找长度较大，不适用于表长较大的查找表。 若以有序表表示静态查找表，则查找过程可以基于“折半”进行。 折半查找 查找过程：每次将待查记录所在区间缩小一半。 适用条件：采用顺序存储结构的有序表。 折半查找算法描述 1.设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值。 2.初始时，令 low=1,high=n,mid=?(low+high)/2? 3.让k与mid指向的记录比较 若k==r[mid].key，查找成功 若kr[mid].key，则high=mid-1 若kr[mid].key，则low=mid+1 mid=?(low+high)/2? 4.重复3操作，直至lowhigh时，查找失败。 折半查找算法 int Search_Bin ( SSTable ST, KeyType kval ) { low = 1; high = ST.length; // 置区间初值 while (low = high) { mid = (low + high) / 2; if (kval == ST.elem[mid].key ) return mid; // 找到待查元素 else if ( kval ST.elem[mid].key) ) high = mid - 1; // 继续在前半区间进行查找 else low = mid + 1; // 继续在后半区间进行查找 } return 0; // 顺序表中不存在待查元素 } // Search_Bin 查找成功时顺序表查找的平均查找长度 查找成功时折半查找的平均查找长度 当n50时，ASL≈log2(n+1)-1