计算机软件技术基础课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,计算机软件技术基础,查找与排序,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算机软件技术基础,教 师：曾晓东,电 话：,13679007201,E_mail:,计算机软件技术基础教 师：曾晓东,5.1,查找,一、概念和术语,二、顺序表查找,三、散列查找,四、各种查找算法的比较,计算机软件技术基础,查找与排序,5.1 查找一、概念和术语计算机软件技术基础查找与排序,5.1,查找,访问与查找都是数据结构中的重要操作，访问数据结构中数据元素的访问算法都是与具体数据结构的特性紧密相关的。,如根据下标访问数组中的数据元素，沿指针指向访问线性链表中的结点、遍历一棵二叉树等。在这一节中，我们将讨论各种查找算法，并对查找算法进行分析。,计算机软件技术基础,查找与排序,5.1 查找访问与查找都是数据结构中的重要操作，访问数据结构,一、概念和术语,记录,(record),：它是由若干个数据项,(,或称为域,),组成的数据元素，它和结点、顶点的意义完全相同。,文件,(file),：它是由若干记录组成的集合，即含有若干记录的表称为文件。,关键字,1,）,主关键字,：在数据处理中，被查找的元素通常是以记录形式出现的，即每一个数据元素（记录）由若干个数据项组成，其中能用来唯一标识该记录的数据项称为主关键字。,2,）,次关键字,：用来标识若干记录的数据项称为次关键字。,计算机软件技术基础,查找与排序,一、概念和术语记录(record)：它是由若干个数据项(或称,一、概念和术语,查找,给定一个值,K,，在含有,n,个记录的文件中进行查找，寻找一个关键字值等于,K,的记录，如果找到则输出该记录，否则输出查找不成功的信息。,动态查找与静态查找,查找的同时对表作修改操作的表称为动态查找表，否则称之为静态查找表。,计算机软件技术基础,查找与排序,一、概念和术语查找计算机软件技术基础查找与排序,一、概念和术语,平均查找长度,由于待查记录在文件中的位置随意性很大，因此通常用比较次数的平均值，即统计意义上的数学期望值来评估查找算法，称为平均查找长度（,ASL,）：,其中，,n,是文件中记录的个数，,P,i,是查找第,i,个记录的查找概率，通常我们认为每个记录的查找概率相等，即,P,i,=1/n,；,C,i,是找到第,i,个记录时所经历的比较次数。,计算机软件技术基础,查找与排序,一、概念和术语平均查找长度其中，n是文件中记录的个数，Pi,二、顺序表查找,1,、顺序查找,顺序查找又称线性查找，是一种最简单的查找方法。,1,）基本思想,从第一个记录开始，逐个比较记录的关键字，直到和给定的,K,值相等，则查找成功；若比较结果与文件中所有关键字都不等，则查找失败。,2,）算法描述,顺序表的类型定义,const int MAXSIZE=100;,typedef struct,struct elemtype dataMAXSIZE;,int length;,listtype;,结点的类型定义,typedef struct,keywordtype key;,datatype elemdata;,elemtype;,计算机软件技术基础,查找与排序,二、顺序表查找1、顺序查找顺序表的类型定义结点的类型定义计算,二、顺序表查找,int seqSearch(listtype*a,keywordtype k),/,在顺序表,a,中查找关键字,k,，若成功则返回记录号，否则返回,-1,int i;,a-dataa-length=k;/,设置监视哨,for(i=0;a-datai.key!=k;i+);,if(i=a-length)return(-1);/,查找不成功,else return(i);/,查找成功,3),性能分析,等概率情况下，,P,i,=1/n,，,C,i,=i,，所以：,计算机软件技术基础,查找与排序,二、顺序表查找int seqSearch(listtype,二、顺序表查找,2,、折半查找,又称对分查找，是对有序表进行的一种查找。,1),基本思想,先找到“中间记录”，比较其关键字，,如果关键字与给定值,K,相等，则查找成功；,如果关键字,x,小于给定值,K,，则说明被查找记录必在前半区间内；,反之则在后半区间内。这样把查找区间缩小了一半，继续进行查找。,计算机软件技术基础,查找与排序,二、顺序表查找2、折半查找计算机软件技术基础查找与排序,二、顺序表查找,5 13 17 42 46 55 70 94,low mid hig,k=55,5 13 17 42 46 55 70 94,low mid hig,5 13 17 42 46 55 70 94,low mid hig,k=12,5 13 17 42 46 55 70 94,low mid hig,5 13 17 42 46 55 70 94,hig low,查找成功,查找失败,计算机软件技术基础,查找与排序,二、顺序表查找5 13 17 42 46,二、顺序表查找,2),算法描述,int binSearch(listtype*a,keywordtype,k),/*,在有序顺序表,a,中查找关键字,k,，若成功则返回记录号，否则返回,-1*/,int mid,low=0,，,high=a-length-1;while(low datamid.key)return(mid);if(k datamid.key)high=mid-1;if(k a-datamid.key)low=mid+1;return(-1);,计算机软件技术基础,查找与排序,二、顺序表查找2)算法描述计算机软件技术基础查找与排序,二、顺序表查找,3),性能分析,对分查找的判定树：在查找过程中，各记录的比较次数与待查记录在文件中的相对位置有关，我们把比较次数相同的记录关键字放在同一层次，各层次之间用分支相连，可得到一棵二叉树，称为,判定树,。,42,94,55,70,46,13,17,5,序列：,5,13,17,42,46,55,70,94,的判定树,等概率下的平均查找长度为：,计算机软件技术基础,查找与排序,二、顺序表查找3)性能分析429455704613175序列,二、顺序表查找,3,、分块查找,1,）概念,分块查找又称,索引顺序查找,，把关键字分成若干块，且后一块中的所有关键字均大于前一块中最大的关键字。而每一块中的关键字则不一定有序。,2,）基本思想,先将各块中的最大关键字构成一个递增有序的索引表，查找分两步：,对索引表对分或顺序查找,以确定所在块。,在所在块中进行顺序查找。,计算机软件技术基础,查找与排序,二、顺序表查找3、分块查找计算机软件技术基础查找与排序,二、顺序表查找,图例,11 9 30 4 38 40 60 65 84 70 75 66,65 84,0 4 8,第,1,块 第,2,块 第,3,块,索引表,最大关键字,起始地址,计算机软件技术基础,查找与排序,二、顺序表查找图例11 9 30 4 38,二、顺序表查找,3),算法分析,分块查找的平均查找次数包括两部分,查找索引表,(Lb),在块中查找,(Lw),ASL=Lb+Lw,设共有,n,个记录，分成,b,块，每块有,s,个记录，则,b=n/s,设在索引表和块中都进行顺序查找，则,ASL=(b/2+s/2)=(n/s+s)/2+1,当,b=s=sqrt(n),时，,ASL,最小，为,sqrt(n)+1,其查找效率界于折半查找和顺序查找之间,计算机软件技术基础,查找与排序,二、顺序表查找3)算法分析计算机软件技术基础查找与排序,三、散列查找,1,、散列表,又称哈希表,1,）基本思想：通过对给定值作某种运算，直接求得关键字等于给定值的记录的位置。,2,）,概念,：设关键字,key,与存储位置间的对应关系为,H(key),，若用一维数组来存放文件，则,H(key),即为数组的下标。我们称,函数,H,为哈希,(Hash),函数,，,H(key),为哈希地址（或散列地址）,，这个一维数组,称为哈希表,。,计算机软件技术基础,查找与排序,三、散列查找1、散列表计算机软件技术基础查找与排序,三、散列查找,3,）有关问题,哈希查找是对给定的关键字按哈希函数直接求得记录位置的，不需进行比较。,为提高查找效率，哈希表的空间,m,要比记录个数,n,大，定义,a=n/m,为装填系数,(,有时也叫装填因子,),，实际应用中一般取：,0.65,0.85,。,计算机软件技术基础,查找与排序,三、散列查找3）有关问题计算机软件技术基础查找与排序,三、散列查找,为求得哈希地址，有时须对关键字进行算术或逻辑运算，若关键字为非数值型，可先转化为数值，称为,关键字的内部码,。而且求得的哈希地址的值域必须在哈希表长的范围内。,若某个哈希函数对不同的关键字得到相同的哈希地址，这种现象称为,冲突,，这些关键字称为,同义词,。实际应用中，冲突一般不可避免，应寻找解决冲突的方法。,所以，运用哈希技术进行查找，要解决两个问题：哈希函数的构造和解决冲突。,计算机软件技术基础,查找与排序,三、散列查找 为求得哈希地址，有时须对关键字进行算术或逻辑,三、散列查找,2,、构造散列函数,构造散列函数的原则,散列函数应是简单的，能在较短的时间内计算出结果。,散列函数的定义域必须包括需要存储的全部关键码,如果散列表允许,m,个地址时,其值域必须在,0,到,m,-1,之间。,散列函数计算出来的地址应能均匀分布在整个地址空间中。,计算机软件技术基础,查找与排序,三、散列查找2、构造散列函数计算机软件技术基础查找与排序,三、散列查找,1,）折叠移位法,将关键字分为几段，除了最后一段外，其余各段都须等长，然后将各段相加作为哈希地址。,折叠时有两种方法：移位折叠和边界折叠。如关键字值为：,12320324111220,，分为,5,段：,123,203,241,112,20,，两种折叠法分别如下：,123321203203241142112112 20 02,879780,计算机软件技术基础,查找与排序,三、散列查找1）折叠移位法计算机软件技术基础查找与排序,三、散列查找,2),平方取中法,先将关键字平方，再选取其中几位作为哈希地址。例如有一组关键字为：,(0100,1100,1200,1160,2060,2061,2163,2261,2262),设存储空间为,1000,将关键字平方后再取第,2,3,4,位构成哈希地址为：,(010,210,440,345,243,247,678,112,116)。,计算机软件技术基础,查找与排序,三、散列查找2)平方取中法计算机软件技术基础查找与排序,三、散列查找,3,),除留余数法,对关键字取模（余数）作为哈希地址，即：,H(key)=key%p,。,如果将,m,取为某个偶数，则奇数关键字值被转换为奇地址，偶数关键字值被转换成偶地址。显然，这很容易造成散列冲突。另外，如果用较小的质数或含有小质数因子的合数作为除数,m,，也会导致散列地址不均匀的结果。为了获得比较均匀的地址分布，最好选择,个较大的质数作为除数。,计算机软件技术基础,查找与排序,三、散列查找3)除留余数法计算机软件技术基础查找与排序,三、散列查找,注意：经验证明模数,m,取为超过,20,的质因子的合数，散列地址分布将比较均匀。,也可以使用此方法，作附加处理，将散列地址限制在一个范围内。,如允许的地址空间限制在,000,499,之间，则将,H%500,即可。,计算机软件技术基础,查找与排序,三、散列查找注意：经验证明模数m取为超过20的质因子的合数，,三、散列查找,4,）数字分析法,适合静态数据，关键字已知,分析数字的分布，删除不均匀的数字，再根据存储空间的大小决定数字的数目。例如有,7,个学生的学号为：,542422241542813678542228171542389671542541577542885376542