ch4_1查找2中国石油大学 {华东} 软件设计基础课件.ppt

4.1 查找;学 号 ;§4.1.1 查找的基本概念;查找表 是由具有同一类型的记录组成的集合。 　 分为静态查找表和动态查找表两类。 1)静态查找表：仅对查找表进行查找操作，而不能改变的表； 2)动态查找表： 除可进行查找操作外，还可进行向表中插入，或删除记录的表。 ? 查找 给定一个值K，在查找表中进行有哪些信誉好的足球投注网站，寻找关键字值等于K的记录，如果找到则输出该记录，否则输出查找不成功的信息。也称为检索。;查找方法评价 平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需进行的关键字比较次数的期望值叫查找算法的~;4.1.2 线性表的查找;线性表查找的存储结构：顺序存储结构 数据结构： typedef struct{ int key; float info; }SSTable;;1、 顺序查找 查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较，直到找到关键字等于K的记录或到达表的另一端。 可以采用从前向后查，也可采用从后向前查的方法。 在下面两种情况下只能采取顺序查找： a. 线性表为无序表（元素排列是无序的）； b. 即使是有序线性表，但采用的是链式存储结构。;int Search_seq(SSTable ST[ ], int n, int key) { int i=n; while( i=1 ST[i].key!=key ) i- -; /*从表尾往前查*/ if ( i=1) return i ; else return 0; }; 改进的顺序查找的算法：;1、 顺序查找 算法描述;顺序查找方法的ASL;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时，查找失败;折半查找 算法描述;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; /*查找成功*/ else if( key ST[mid].key) high=mid-1; /*在前半区间继续查找*/ else low=mid+1; /*在后半区间继续查找*/ } return (0); /*查找不成功*/ };例 ;1 2 3 4 5 6 7 8 9 10 11;算法评价 有n个结点的判定树的深度为?log2n?+1 折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度 折半查找的ASL;3 分块查找（索引顺序查找） 查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找 适用条件：分块有序表 算法实现 用数组存放待查记录,每个数据元素至少含有关键字域 建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针 算法描述;查找38;分块查找方法评价;分块查找;;1 2 3 4 5 6 7 8 9 10 11;二叉排序树 定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值 若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值 它的左、右子树也分别为二叉排序树;?二叉排序树的概念;二叉排序树的查找：;二叉排序树的构造;{ 10、18、3、8、12、2、7、3 };50;从上述二叉排序树的查找过程可见，; 在指针t 所指向的二叉排序树中查找关键字值为K的结点 #define M 100 typedef struc