第四章查找与排序技术 41基本的查找技术 查找:查找是在一个给定的数据结构中,根据给定的 条件查找满足条件的结点。 不同的数据结构采用不同的查找方法。 查找的效率直接影响数据处理的效率 查找的结果: 查找成功:找到满足条件的结点 查找失败:找不到满足条件的结点
第四章 查找与排序技术 4.1 基本的查找技术 查找：查找是在一个给定的数据结构中，根据给定的 条件查找满足条件的结点。 不同的数据结构采用不同的查找方法。 查找的效率直接影响数据处理的效率。 查找的结果： 查找成功：找到满足条件的结点 查找失败：找不到满足条件的结点
411顺序查找(线性查找) 查找过程: 对给定的一关键字K,从线性表的一端开始,逐个进 行记录的关键字和K的比较,直到找到关键字等于K的记 录或到达表的另一端。 可以采用从前向后查,也可采用从后向前查的方法。 在平均情况下,大约要与表中一半以上元素进行比较,效 率较低。平均查找长度较大。 在下面两种情况下只能采取顺序查找: a.线性表为无序表(元素排列是无序的) b.即使是有序线性表,但采用的是链式存储结构
·可以采用从前向后查，也可采用从后向前查的方法。 ·在平均情况下，大约要与表中一半以上元素进行比较，效 率较低。平均查找长度较大。 ·在下面两种情况下只能采取顺序查找： a. 线性表为无序表（元素排列是无序的）； b. 即使是有序线性表，但采用的是链式存储结构。 4.1.1 顺序查找（线性查找） 查找过程： 对给定的一关键字K，从线性表的一端开始，逐个进 行记录的关键字和K的比较，直到找到关键字等于K的记 录或到达表的另一端
1.顺序查找(线性表在顺序存储结构下的顺序查找) 数据结构: typedef struct( 每个结点包含两部分 Int key, 内容:Key和info float info: ISSTable 其他 信
1 . 顺序查找 (线性表在顺序存储结构下的顺序查找） 数据结构： typedef struct{ int key; float info; }SSTable; 每个结点包含两部分 内容：Key 和info 其他 信息
顺序查找的算法: 使用了监视哨, int Search seq( ssTable ST,intn, int key))在查找过程中, i int i=n; 不用每一步都去 判断是否查找结 stio. key=key; 束。 while(sti. key!=key)i-;/从表尾往前查找到:返回元素 return i 01234在线性表中的存 10|204080储位置; (a)初乱未找到:返回0 314567 8010204080306025 ○ 监视哨 (b)K-80 (return i=4) 0123456 9010204080306025 (c)K=90 (return i=0)
0 1 2 3 4 5 6 7 （a） 初态 10 20 40 80 30 60 25 (b) K=80 (return i=4) 80 10 20 40 80 30 60 25 0 1 2 3 4 5 6 7 (c) K=90 (return i=0 ) 0 1 2 3 4 5 6 7 90 10 20 40 80 30 60 25 顺序查找的算法： int Search_seq(SSTable ST[ ], int n, int key) { int i=n; ST[0].key=key; while(ST[i].key!=key) i- -; /*从表尾往前查*/ return i; } 监视哨 使用了监视哨， 在查找过程中， 不用每一步都去 判断是否查找结 束。 找到：返回元素 在线性表中的存 储位置； 未找到：返回0
根据上述算法可知: 查找成功时的平均查找次数为: ASL=(1+2+3+4+…+n)/n=(n+1)/2 查找不成功时的比较次数为:n+1 则顺序查找的平均查找长度为: AsL==(n+1)2+n+1)/2=(n+1)3/4 顺序查找的优点:算法简单,无需排序,采用顺序 和链式存储均可。 缺点:平均查找长度较大
根据上述算法可知： 查找成功时的平均查找次数为： ASL=(1+2+3+4+……+n)/n=(n+1)/2 查找不成功时的比较次数为： n+1 则顺序查找的平均查找长度为： ASL==((n+1)/2+n+1)/2=(n+1)3/4 顺序查找的优点：算法简单，无需排序，采用顺序 和链式存储均可。 缺点：平均查找长度较大
41.2折半查找(二分法查找) 思想:先确定待査找记录所在的范围,然后逐步缩小范 围,直到找到或确认找不到该记录为止。 前提:必须在具有顺序存储结构的有序表中进行。 分三种情况 1)若中间项的值等于x则说明已查到。 2)若x小于中间项的值,则在线性表的前半部分查找 3)若x大于中间项的值,则在线性表的后半部分查找 特点:比顺序查找方法效率高。最坏的情况下,需要比 较|og2n次
4.1.2 折半查找（二分法查找） 思想：先确定待查找记录所在的范围，然后逐步缩小范 围，直到找到或确认找不到该记录为止。 前提：必须在具有顺序存储结构的有序表中进行。 分三种情况： 1）若中间项的值等于x,则说明已查到。 2）若x小于中间项的值，则在线性表的前半部分查找； 3）若x大于中间项的值，则在线性表的后半部分查找。 特点：比顺序查找方法效率高。最坏的情况下，需要比 较 log2n次
查找23和79的过程如下图:mid=(ow+high)/2不进位取整 (08,14,23,37,46,55,68,79,91) (08,14,23,37,46,55,68,79,91) mid high 23 6,55,68,79,91) high=mid-1 (08,14,23,37,46,55,68,79,91) low=mid+1 high d (08,14,23,37,46,55,68,79,91) mid Ow high (08,14,23,37,46,55,68,79,91) low mid high (08,14,23, 46,55,68,79 91) low high mid
查找23和79的过程如下图： mid=(low+high)/2不进位取整 ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) low mid high ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) low mid high=mid-1 ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) low=mid+1 high mid ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) low high mid ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) low mid high ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) low high mid
折半查找的c语言算法程序: int Search Bin( SSTable Sti, int n, int key Rint low, high, mid; low=l: high=n: while(low<=high) i mid=(lowthigh)/2; if( TIMid. key==key) return(mid;查找成功 else if((key< TIMid]. key)high=mid-1;/在前半区间继续查找* else ow=mid+l /在后半区间继续查找* return(O); 查找不成功*
折半查找的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); /*查找成功*/ else if( key< ST[mid].key) high=mid-1; /*在前半区间继续查找*/ else low=mid+1; /*在后半区间继续查找*/ } return (0); /*查找不成功*/ }
41.3分块查找(索引顺序查找) 是顺序查找的一种改进方法,就是把被查找的表 分成若干块,每块中记录的存放顺序是无序的,但块 与块之间必须按关键字有序。即第一块中任一记录的 关键字都小于第二块中任一记录的关键字,而第二块 中任一记录的关键字都小于第三块中任一记录的关键 字,依此类推。 该法要为被查找的表建立一个索引表,索引表中 的一项对应于表中的一块,索引表中含有这一块中的 最大关键字和指向块内第一个记录位置的指针,索引 表中各项关键字有序
是顺序查找的一种改进方法，就是把被查找的表 分成若干块，每块中记录的存放顺序是无序的，但块 与块之间必须按关键字有序。即第一块中任一记录的 关键字都小于第二块中任一记录的关键字，而第二块 中任一记录的关键字都小于第三块中任一记录的关键 字，依此类推。 该法要为被查找的表建立一个索引表，索引表中 的一项对应于表中的一块，索引表中含有这一块中的 最大关键字和指向块内第一个记录位置的指针，索引 表中各项关键字有序。 4.1.3分块查找（索引顺序查找）
块中的最大 索引表 关键字 20 53 89 块内第 6 11 个记录位 置的指针 1812852051362229538960726676
索引表 20 53 89 1 6 11 18 12 8 5 20 51 36 22 29 53 89 60 72 66 76 块中的最大 关键字 块内第一 个记录位 置的指针