第九章 查找表课件教学.ppt

开放定址Hash插入StatusInsertHash(HashTableH,HElemTypee){//查找不成功时插入数据元素e到哈希表中，并返回OK；//若冲突次数过大，则重建哈希表intc=0,p=0;if(SearchHash(H,e.key,p,c)==SUCCESS)returnDUPLICATE; //表中已有与e有相同关键字的元素if(cH.cursize){//冲突次数c未达到上限（阀值c可调）H.elem[p]=e;++H.count;returnSUCCESS;//插入e}else{RecreateHashTable(H);//重建哈希表returnUNSUCCESS;}}//InsertHashStatusSearchHash(LHashTableH,KeyTypekval,LHNodeptrp,intc){ //若查到，p指向该结点； //若查不到，p返回最后一个结点待插入 p=H.elem[Hash(kval)]; while(pp-data.key!=kval){q=p;p=p-next;c++;} //q紧随p if(p)returnSUCCESS; else{p=q;returnUNSUCCESS;}}链地址Hash查找StatusInsertHash(HashTableH,ElemTypee){ c=0; if(SearchHash(H,e.key,p,c)==SUCCESS) returnDUPLICATE; if(chashsize[H.sizeindex]/2){ s＝newLHNode; s-data=e;s-next=NULL; p-next=s; H.count++; returnOK; } elserecreateHashTable(H);//重建哈希表}链地址Hash插入if(p)p-next=s;elseH.elem[Hash(kval)]=s;*中国科学技术大学*ypb@ustc.edu.cn第九章查找表9.1静态查找表9.2动态查找表9.3哈希表及其查找查找表：由同一类元素或记录构成的集合。对数据元素间的关系未作限定。对查找表的操作有查找某个“特定”的元素是否在表中。查找某个“特点”的元素的各种属性。在查找表中插入一个元素。在查找表中删除一个元素静态查找表、动态查找表关键字数据元素中的某个数据项值。可以表示一个数据元素，如可以唯一表示，则为主关键字（primarykey）。查找根据给定的某个值，在查找表中确定一个关键字等于给定值的数据元素。若找到表示查找成功，返回该元素详细信息或在查找表中的位置；否则返回NULL9.1静态查找表9.1.1顺序查找typdefstruct{ ElemType*elem;//元素存储空间，0单元保留 int length;//表长度}SSTable;查找成功和失败平均查找长度查找过程中先后和给定值进行比较的关键字的个数的期望值ASL＝∑PiCi∑Pi＝1i＝1，2，……nCi＝n－i＋1Pi＝1/nASLss＝1/n∑（n－i＋1）=(n+1)/29.1.2折半查找折半查找（binarySearch）：二分查找。例8.2利用二分查找在顺序有序表中查找。算法8.2IntSearch_Bin(SStableST,KeyTypekval)ASLbs＝（n＋1）/nlog(n+1)-1二分查找平均查找长度（假设满二叉树）ASLbs＝（n＋1）/nlog(n+1)-1ASLbs=(20+21*2+…+2h-1*h)Pi=又称索引顺序查找介于顺序查和折半查找之间。适合于关键字分块有序typedefstruct{ KeyType key; int stadr;}indexItem;typedefstruct{ indexItem *elem; int length;}indexTable;算法Search_Idx(SSTableST,indexTableID,KeyTkval)设索引长度b，顺序表长度为n，则：ASLidx=ASL(b)+ASL(n/b