电子科技大学：《软件技术基础 Fundamental of Software Technology》课程教学资源（课件讲稿）第三章 数据结构 3.7.1 查找（一）

电子斜技大学 软件技术基础 3.7.1查找算洁（) 主讲教师：刘民岷 航空航天学院 a口2 软件技术基础课程组

软件技术基础 主讲教师：刘民岷 航空航天学院 软件技术基础课程组

查找与排序 口查找的功能是从大量数据在寻找出所需的数据来 ▣排序是将一组记录按其关键字的递增或递减的次 序排列，以便进行数据查找、数据处理。 电子科技大学刘民岷 查找算法 2

电子科技大学 刘民岷 查找算法 2 查找与排序  查找的功能是从大量数据在寻找出所需的数据来  排序是将一组记录按其关键字的递增或递减的次 序排列，以便进行数据查找、数据处理

查找的基本概念 关键字：可以唯一标识一个数据元素的数据项。 查找表：一组待查数据元素的集合。 显然，查找运算依赖于查找表中各数据元素在计算机存 储系统的组织与存储结构。数据元素的组织与存储方式决定 了采用什么样的查找方法； 反过来，为了提高查找方法的效率，又要求数据元素采 用某些特殊的存储方式。 电子科技大学刘民岷 查找算法 3

电子科技大学 刘民岷 查找算法 3 关键字：可以唯一标识一个数据元素的数据项。 查找表：一组待查数据元素的集合。 显然，查找运算依赖于查找表中各数据元素在计算机存 储系统的组织与存储结构。数据元素的组织与存储方式决定 了采用什么样的查找方法； 反过来，为了提高查找方法的效率，又要求数据元素采 用某些特殊的存储方式

顺序查找 ·基本思想：从第一个元素开始，逐个把数据元素的关键字与给定值 进行比较。适用于顺序结构组织的查找表，也适用于链式存储结构组织 的查找表的查找。 [算法]顺序查找的算法。（查找表的数据元素存储在顺序表$ 中，类型说明为：elemtype S[MAXNUM) 00001: 00002:int seq_search(elemtype S[],keytype k,int n) 00003: {inti 00004: S[n].key=k; 00005 i=0; 00006: while(S[i].key!=k) 00007: i++; 00008: if(i<n) 00009 { printf(" searching success") 00010: return(i); 00011: } 00012 else 00013: printf(" searching failed") 00014: return(-1); 00015: 00016: } 电子科技大学刘民岷 查找算法 4

电子科技大学 刘民岷 查找算法 4 • 基本思想：从第一个元素开始，逐个把数据元素的关键字与给定值 进行比较。适用于顺序结构组织的查找表，也适用于链式存储结构组织 的查找表的查找。 [算法]顺序查找的算法。(查找表的数据元素存储在顺序表S 中，类型说明为：elemtype S[MAXNUM])

2、顺序查找（续） 算法评估 平均查找长度 对于含n个数据元素的查找表，查找成功时的平均查找长度为： ASL=∑PC i=l 其中：P为查找第I个元素的概率，C为查到第I个元素时进行比较的次数 假设查找表中每个数据的查找概率相同，即P,=1/n,查找第I个元素 的比较次数为C=I,则顺序查找算法成功查找的平均查找长度为： ASLg=∑PC,=∑（日×）=n+1) i=1 i=1 对结点的逻辑次序（不必有序）和存储结构（顺序、链表均可）无要求 ;当序列中的记录“基本有序”或N值较小时，是较好的算法。但平 均查找时间长。 电子科技大学刘民岷 查找算法 5

电子科技大学 刘民岷 查找算法 5 • 算法评估 ➢ 平均查找长度 对于含n个数据元素的查找表，查找成功时的平均查找长度为： 其中：Pi为查找第I个元素的概率，Ci为查到第I个元素时进行比较的次数 ➢ 假设查找表中每个数据的查找概率相同，即Pi ＝1/n，查找第I个元素 的比较次数为Ci ＝I，则顺序查找算法成功查找的平均查找长度为： ➢ 对结点的逻辑次序(不必有序)和存储结构(顺序、链表均可）无要求 ；当序列中的记录“基本有序”或N值较小时，是较好的算法。但平 均查找时间长。 = = n i ASL Pi Ci 1   = = = =  = + n i n n i S q i i ASL PC i n 1 2 1 1 1 ( ) ( 1)

二分查找 基本思想：如果查找表中的数据元素按关键字有序（假设递增有 序)，则在查找时可不必逐个顺序比较，而采用跳跃的方式一一先 与“中间位置”的数据元素的关键字比较，若相等，则查找成功； 若给定值大于“中间位置”的关键字，则在查找表的后半部继续进 行二分查找，否则在前半部进行二分查找。 查找的过程： 设：待查元素所在区域的下界为low,上界为hig,则中 间位置mid=(low+hig)/2, >若此元素关键字值等于给定值，则查找成功； > 若此元素关键字值大于给定值，则在区域mid+1~hig内进行二 分查找。 > 若此元素关键字值小于给定值，则在区域low~mid-1内进行二 分查找。 电子科技大学刘民岷 查找算法 6

电子科技大学 刘民岷 查找算法 6 • 基本思想：如果查找表中的数据元素按关键字有序（假设递增有 序），则在查找时可不必逐个顺序比较，而采用跳跃的方式――先 与“中间位置”的数据元素的关键字比较，若相等，则查找成功； 若给定值大于“中间位置”的关键字，则在查找表的后半部继续进 行二分查找，否则在前半部进行二分查找。 • 查找的过程： 设：待查元素所在区域的下界为low，上界为hig，则中 间位置mid=(low+hig)/2， ➢ 若此元素关键字值等于给定值，则查找成功； ➢ 若此元素关键字值大于给定值，则在区域mid+1～hig内进行二 分查找。 ➢ 若此元素关键字值小于给定值，则在区域low～mid-1内进行二 分查找

3、二分查找（续） 。二分查找的平均查找长度ASL~log.(n+1)-1 但是要求数据元素按关键字的大小进行排序； ·适合用于数表建立后很少改动，可以事先进行排序，且经 常需要查找的场合。 电子科技大学刘民岷 查找算法 7

电子科技大学 刘民岷 查找算法 7 • 二分查找的平均查找长度 ASL≈log2 (n+1)-1 • 但是要求数据元素按关键字的大小进行排序； • 适合用于数表建立后很少改动，可以事先进行排序，且经 常需要查找的场合