8第七章查找.pptVIP

第七章 查找 查找——也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素 关键码——是数据元素中某个数据项的值，它可以标识一个数据元素 主关键码 次关键码 7.2.2 顺序查找 查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较 算法描述 7.2.3 折半查找 查找过程：每次将待查记录所在区间缩小一半 适用条件：采用顺序存储结构的有序表 算法实现 设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值。 初始时,令： Low=0;high=Max-1;mid=(low+high)/2; 让k与mid指向的记录比较 若k==r[mid，查找成功 若kr[mid，则high=mid-1 若k=r[mid，则low=mid+1 重复上述操作，直至lowhigh时，查找失败 算法描述 * * 查找表—— 具有同一类型（属性）的数据元素（记录）组成的集合。 静态查找表——若只对查找表进行如下两种操作： （1）在查找表中查看某个特定的数据元素是否在查找表中， （2）检索某个特定元素的各种属性，则称这类查找表为静态查找表。静态查找表在查找过程中查找表本身不发生变化。对静态查找表进行的查找操作称为静态查找。 动态查找表——若在查找过程中可以将查找表中不存在的数据元素插入，或者从查找表中删除某个数据元素，则称这类查找表为动态查找表。动态查找表在查找过程中查找表可能会发生变化。对动态查找表进行的查找操作称为动态查找。 查找方法评价 查找速度 占用存储空间多少 算法本身复杂程度 平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定值进行比较的关键码的个数的期望值叫查找算法的~ 查找——在数据元素集合中查找满足某种条件的数据元素的过程称为查找。 typedef struct //顺序存储结构 { ElemType *elem； //数组首址 int length； // 表长度 }S_TBL； typedef struct NODE // 链式存储结构结点类型 { ElemType elem； // 结点的值域 struct NODE *next; // 下一个结点指针域 }NodeType； 7.2 静态查找表 7.2.1 静态查找表结构 typedef struct { KeyType key； …… }ElemType i 例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找64 64 监视哨 i i i i 比较次数=5 比较次数： 查找第n个元素： 1 查找第n-1个元素：2 ………. 查找第1个元素： n 查找第i个元素： n+1-i 查找失败： n+1 下面我们给出顺序查找的完整算法。 以顺序存储为例，数据元素从下标为1的数组单元开始存放，0号单元留空。 //在数序表 tab中查找kx int s_search(S_TBL tbl,KeyType kx) { tbl.elem[0].key = kx；//存放监测哨，这样在从 //后向前查找失败时， //不必判表是否检测完。 //从标尾端向前找 for( i = tbl.length ;tbl.elem[i].key kx ;i-- ); return i； //返回找到的下标 } 顺序查找方法的ASL 0 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 8