文档介绍：第13讲查找() 赵英良西安交通大学 2015 大学计算机基础II 查找的重要性?近代大量文献资料?中海量信息?日常办公中的信息检索……查找过程往往是知识发现和智能决策的基础。查找、查找表?查找就是在给定的数据结构中找出满足某种条件的元素?一组待查数据元素的集合,被称作查找表。查找表的结构可以是线性或非线性的?仅仅进行查询元素,不改变查找表中数据元素的内容和彼此的逻辑关系,称为静态查找?若除了查找,还可能添加、删除元素,改变元素间逻辑关系,则称为动态查找关键字?一个数据元素往往包含多种信息,查找往往是根据数据元素的某个属性进行的?学生信息: 班级、学号、姓名、性别、课程、分数?图书信息书名、作者、出版社、出版年代你、定价、书号?例如根据学号查找一个学生的全部信息, 根据作者查找相关书籍的全部信息。这种被用于查找的数据元素的属性一般称为关键字。平均查找长度(ASL) ?为了确定元素的位置,需要将被查找的给定值和表中的元素的关键字进行比较。比较的平均次数称为平均查找长度(ASL,Averagesearch length)。?ASL的计算方法为: 等概率时?其中:n 为表长,Pi为查找第i个元素的概率,Ci为找到该记录时,曾和给定值比较过的数据元素的个数。本节讨论的查找算法?顺序查找?二分(折半)查找?哈希查找?树表查找 1、顺序查找?算法思想: 已知一个线性序列L,为在L中寻找某个数据key,可以从前至后逐个对比 key和L中的元素的关键字?该方法适用于所有线性结构,包括顺序结构、链式结构 0 1 2 3 4 5 6 7 8 9 L 12,10,17,20,15,11, 5,21,23 设列表L中存有若干数据,算法描述如下: SqSearch(L, key) : 设初始查找位置k 为0 当( k<len(L)且L[k]≠key ) : k++ //逐个对比若(k<len(L)) : return k //返回数据元素位置否则: return-1 //没找到,返回-1 顺序查找算法顺序查找的python程序#顺序查找 def sqsearch(L,key): N=len(L) k=0 while(k<N and L[k]!=key): k=k+1 if k<N: return k else: return -1 #主程序 list=[21,34,6,4,7,2,84,3,7,5,33] print(list) 西安交通大学计算机教学实验中心2013 9 SqSearch(L, key) : 设初始查找位置k 为0 当( k<len(L)且 L[k]≠key ) : k++ 若(k<len(L)) : return k 否则: return-1 // 执行结果[21, 34, 6, 4, 7, 2, 84, 3, 7, 5, 33] the position of 6 is 2 106 is not in the list 西安交通大学计算机教学实验中心2013 10 x=6 K=sqsearch(list,x) if K==-1: print(x,' is not in the list') else: print('the position of ',x,'is',K) x=106 K=sqsearch(list,x) if K==-1: print(x,' is not in the list') else: print('the position of ',x,'is',K)