第九章查找表查找表•同一类型的数据元素的集合对查找表进行的操作•查询某个特定的数据元素•检索特定的某个元素的属性•在查找表中插入一个数据元素•删除某个数据•静态查找表–仅查询和检索•动态查找表–查找到了要删除或者查找不到要插入查找定义•根据给定的某个值，在查找表中查找关键字•是数据元素的某个值，用于识别一个数据元素•若此关键字可以识别唯一的记录称主关键字•若此关键字可以识别多个记录则称次关键字•若查找表中存在这样一个待查记录，则称查找成功，给出结果，查找不成功，给出空记录或空指针•查找方式，取决查找表的结构•如：查字典和查电话不同•为了提高查找效率需要在查找表加一些人为的关系–字典按笔画建立索引，根据字的笔画到指定的页面顺序查。–电话按用户性质、地区划分，要到所属区域查。9.1静态查找表•表数据在查找过程中不变定义•数据对象D–具有相同特性的数据元素集合（无线性表特征）–每个元素含有类型相同的关键字，可唯一识别数据元素•数据关系R–数据元素同属一个集合静态查找表基本操作•create(&st,n)//构造含n个元素的查找表•destroy(&st)•search(st,key)//返回等于关键字key的元素位置•Traverse(st,visit())//遍历查找表静态查找表使用顺序结构的存储typedefstruct{ElemType*elem;//动态定义intlength;//元素个数}SSTable;•查找过程，数据不需移动静态查找表表示方法•顺序查找表（无序）•有序查找表•静态查找树表•索引顺序表1）.顺序查找表•以顺序表或线性链表表示静态查找表st.elem2137881992564568075st..length=10012345678910st.elem602137881992564568075st..length=10012345678910待找的数据放在0位置就可以减少一种比较0项不用按规则查找intlocation(SqListlElemTypee,Status(*compare)(ElemType,ElemType)){k=1;p=l.elem;while(k<=l.length&&!(*compare)(*p++,e))；if(k<=l.length)returnk；//返回位置>0elsereturn0;}//从前往后找按关键字查找intsearch_Seq(SSTablest,keyTypekey){st.elem[0].key=key;//设置哨兵//从后往前找，终能找到，不用判断越界for(i=st.length;st.elem[i].key!=key;--i);returni;//i==0找不到,i>0找到}//search_Seq例：search_Seq.c分析顺序查找的时间性能•查找算法的平均查找长度•平均查找长度定义–为确定记录在查找表中的位置，需和给定值进行比较的平均次数–ASL=∑pici•pi查找某数的概率•ci查找某数的次数例•10个数，每个数查1次，查10次–等概率pi=1/10–查第1个数1次，查第2个数2次，…–ASL=(1+2+3+…+10)*(1/10)=5.5–一般等概率情况：ASL=(n+1)/2•顺序查找–ci=n-i+1:从后开始查，当i=n查1次，i=1查n次–ASL=np1+(n-1)p2+…..+pn•等概率情况：p*(n+1)*n/2=(n+1)/2•在不等概率时，计算ASL,p取最小值•为了减少查找次数，可将查找概率大的靠近表尾•如果查找的数不在查找表内，则每次要查n次，此时的平均查找长度要大大增加2）.有序查找表•查找表内的数据有序•折半查找例查75m第1次后51319213756647580889201234567891011lowhighm初始51319213756647580889201234567891011lowhigh51319213756647580889201234567891011lowhighm第2次后51319213756647580889201234567891011lowhighm第3次后查76则low+1>high查找结束intsearch_Bin(SSTables,KeyTypekey){low=1;high=st.length;while(low<=high){mid=(low+high)/2;if(EQ(key,st.elem[mid].key))returnmid;elseif(LT(key,st.elem[mid].key))high=mid-1;elselow=mid+1;}return0;}•例：search_BIN.c折半查找的平均查找长度•折半查找判定树–折半查找过程可用二叉判定树描述i1234567891011Ci34234134234631425971011812个区域不成功查找ASL=(1*1+2*2+3*4+4*4)/11=3二叉排序树•一般情况下，表长为n的折半查找的判定树和含有n个结点的完全二叉树的深度相同•假设n=2h-1,并且查找概率相同则•ASL=(1/n)∑i*2i-1=(n+1)/n*log2(n+1)-1在n>50•ASL=log2(n+1)-1=log2n3）.静态查找树表•不等概率查找情况下，折半查找不是最好的查找方法，如：ABCDEPi0.20.30.050.30.15Ci23123折半查找：ASL=0.2*2+0.3*3+0.05*1+0.3*2+0....
