第9章查找9.1静态查找表9.2动态查找表9.3哈希表1.查找表是由同一类型的数据元素(或记录)构成的集合，由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的数据结构。对查找表经常进行的操作有：查询、检索、插入、删除。分类：静态查找表动态查找表查找的基本概念2.关键字在实际应用问题中，每个记录一般包含有多个数据域，查找是根据其中某一个指定的域进行的，这个作为查找依据的域称关键字（key）。主关键字可唯一标识一个记录的关键字。例：学号次关键字可识别若干记录的关键字。例：性别3.查找根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在这样的一个记录，则称查找是成功的，若表中不存在关键字等于给定值的记录，则称查找不成功。静态查找只查找，不改变数据元素集内的数据元素。动态查找既查找，又改变(增减)集合内的数据元素。4.平均查找长度(AverageSearchLength)为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度（ASL）。对于含有n个记录的表，查找成功时的平均查找长度为：ASL=niiipc1查找表中第i个记录的概率，且nii=1p1找表中关键字与给定值相等的第i个记录时，和给定值已进行过比较的关键字个数第9章查找9.1静态查找表9.1.1顺序表的查找9.1.2有序表的查找9.1.4索引顺序表的查找9.2动态查找表9.3哈希表9.1.1顺序表的查找也称线性查找。1.查找过程：对给定的一关键字K，从线性表的一端开始，逐个进行记录的关键字和K的比较，直到找到关键字等于K的记录或到达表的另一端。2.实现顺序查找的数据结构typedefstruct{intkey;//关键字域……//其他域}SSTable;3.顺序查找的算法intseqsearch(SSTableST[],intn,intkey){inti=n;while(ST[i].key!=key)&&(i>=1)i--;returni;}（returni=4）Key=804080306010202501234567(returni=0)01234567（a）初态40803060102025(b)K=757540803060102025012345673.顺序查找的算法intSearch_seq(SSTableST[],intn,intkey){inti=n;ST[0].key=key;while(ST[i].key!=key)i--;returni;//找不到时，i为0}监视哨作用：避免每步都去判断是否查找结束监视哨4.算法分析查找成功时的平均查找次数为：ASL=(1+2+3+4+……+n)/n=(n+1)/2①查找不成功时的比较次数为：ASL=(n(n+1))/n=n+1②则顺序查找的平均查找长度为：ASL==(①+②)/2=3(n+1)/4优点：算法简单，无需排序，采用顺序和链式存储均可。缺点：平均查找长度较大。第9章查找9.1静态查找表9.1.1顺序表的查找9.1.2有序表的查找9.1.4索引顺序表的查找9.2动态查找表9.3哈希表可用折半查找（二分法查找）来实现。1.查找思想先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。前提条件：必须在具有顺序存储结构的有序表中进行。9.1.2有序表的查找查找23和79的过程如下图：mid=「(low+high)/2」(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)lowhighmid(08,14,23,37,46,55,68,79,91)lowhigh=mid-1mid(08,14,23,37,46,55,68,79,91)low=mid+1highmid(08,14,23,37,46,55,68,79,91)lowhighmid(08,14,23,37,46,55,68,79,91)lowhighmid(08,14,23,37,46,55,68,79,91)lowhighmid2.折半查找的算法intSearch_Bin(SSTableST[],intn,intkey){intlow,high,mid;low=1;high=n;while(low<=high){mid=(low+high)/2;if(ST[mid].key==key)returnmid;elseif(key
VIP
