电子斜技大学 软件技术基础 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)