数据结构 查找

1、1数数 据据 结结 构构8.1 查找的基本概念查找的基本概念第第 8 章章 查找查找8.2 基于线性表的查找法基于线性表的查找法8.3 基于树的查找基于树的查找法法8.4 计算式查找法计算式查找法哈希表哈希表2数数 据据 结结 构构8.1 查找的基本概念查找的基本概念第第 8 章章 查找查找查找表是由查找表是由同一类型的数据元素同一类型的数据元素( (或记录或记录) )构构成的成的集合集合。由于由于“集合集合”中的数据元素之间存在着中的数据元素之间存在着松散松散的关系，因此查找表是一种的关系，因此查找表是一种应用灵便应用灵便的结构。的结构。3数数 据据 结结 构构8.1 查找的基本概念查找的基

2、本概念第第 8 章章 查找查找对查找表常进行的操作对查找表常进行的操作: :1 1）查询查询某个某个“特定的特定的”数据元素是否在查找表中数据元素是否在查找表中静态静态查找查找动态查找动态查找3 3）在查找表中）在查找表中插入插入一个数据元素一个数据元素2 2）检索检索某个某个“特定的特定的”数据元素的各种属性数据元素的各种属性4 4）从查找表中）从查找表中删去删去某个数据元素某个数据元素4数数 据据 结结 构构8.1 查找的基本概念查找的基本概念第第 8 章章 查找查找查找表的分类查找表的分类仅作仅作查询查询和和检索检索操作操作静态查找表静态查找表“不在查找表中不在查找表中”的数据元素的数据

3、元素插入插入到查找表中；到查找表中；删除删除其其“查询查询”结果为结果为“在查找表中在查找表中”的数据元的数据元素。素。动态查找表动态查找表查找还可分为：查找还可分为：内查找和外查找。内查找和外查找。5数数 据据 结结 构构8.1 查找的基本概念查找的基本概念第第 8 章章 查找查找关键字：关键字：是数据元素（或记录）中是数据元素（或记录）中某个数据项某个数据项的值，的值，用以用以标识标识（识别）（识别）一个数据元素一个数据元素（或记录）。（或记录）。主关键字：主关键字：可以识别可以识别唯一唯一的一个记录的关键字。的一个记录的关键字。次关键字：次关键字：可以识别可以识别若干若干记录的关键字记录

4、的关键字。6根据给定的某个值，在查找表中根据给定的某个值，在查找表中确定一个确定一个其关键字等于给定值的数据元素其关键字等于给定值的数据元素（记录）。（记录）。 查找查找 若查找表中若查找表中存在存在这样一个记录，则称这样一个记录，则称“查查找成功找成功”。查找结果。查找结果给出整个记录的信息给出整个记录的信息，或或指示该记录在查找表中的位置；指示该记录在查找表中的位置； 否则称否则称“查找不成功查找不成功”。查找结果给出。查找结果给出“空空记录记录”或或“空指针空指针”。数数 据据 结结 构构8.1 查找的基本概念查找的基本概念第第 8 章章 查找查找7 由于查找表中的数据元素之间不存在明显

5、的由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。组织规律，因此不便于查找。 为了提高查找的效率，为了提高查找的效率， 需要在查找表中的元需要在查找表中的元素之间人为地附加某种确定的关系，换句话说素之间人为地附加某种确定的关系，换句话说,用用另外一种结构另外一种结构来表示查找表。来表示查找表。如何进行查找？如何进行查找？查找的方法取决于查找表的结构。查找的方法取决于查找表的结构。数数 据据 结结 构构8.1 查找的基本概念查找的基本概念第第 8 章章 查找查找8数数 据据 结结 构构8.2 基于线性表的查找基于线性表的查找 第第 8 章章 查找查找顺序查找顺序查找折半查找折半查

6、找分块查找分块查找9数数 据据 结结 构构8.2 基于线性表的查找基于线性表的查找 第第 8 章章 查找查找顺序查找顺序查找key=64key=6021 37 88 19 92 05 64 56 80 72 13012345678910 11 12iiiiiiiiiii结果：查找成功，返回位置结果：查找成功，返回位置7结果：查找不成功结果：查找不成功int SeqSearch(RecordList l, KeyType k) int i; i=l.length; while (i=1&l.ri.key!=k) i-; if (i=1) return(i); else return(0)

7、; 10数数 据据 结结 构构8.2 基于线性表的查找基于线性表的查找 第第 8 章章 查找查找顺序查找顺序查找key=64key=60结果：查找成功，返回位置结果：查找成功，返回位置7结果：查找不成功结果：查找不成功6460int SeqSearch(RecordList l, KeyType k) int i; l.r0.key=k; /*标识边界标识边界*/ i=l.length; while (l.ri.key!=k) i-; return(i); 技巧：技巧： r0起到监视哨兵的作用起到监视哨兵的作用,可免去检查表是可免去检查表是否查完否查完, ,且提高算法的执行效率且提高算法的执行

8、效率, ,但并不是但并不是真正的待查找记录。真正的待查找记录。21 37 88 19 92 05 64 56 80 72 13012345678910 11 12iiiiiiiiiiii11数数 据据 结结 构构8.2 基于线性表的查找基于线性表的查找 第第 8 章章 查找查找顺序查找顺序查找分析查找的时间性能分析查找的时间性能: :查找算法的平均查找长度查找算法的平均查找长度( (A Averageverage S Search earch L Length)ength)为确定记录在查找表中的位置，需和给定值为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值进行比较的关键字个

9、数的期望值( (查找成功查找成功时）时）ASL=PiCii=1n其中其中: : n n为表长；为表长；P Pi i为查找表中第为查找表中第i i个记录的概率，且个记录的概率，且 ; ;C Ci i为找到该记录时，曾和给定值比较过的关键字的次数。为找到该记录时，曾和给定值比较过的关键字的次数。Pi=1i=1n12在在等概率等概率查找的情况下，顺序表查找成功的平均查查找的情况下，顺序表查找成功的平均查找长度为：找长度为：Pi=1/n对对顺序表顺序表而言而言，Ci = n-i+1ASL = nP1 +(n-1)P2 + +2Pn-1+Pn8.2 基于线性表的查找基于线性表的查找 第第 8 章章 查找

10、查找数数 据据 结结 构构21111+=+-=n)i(nnASLniSUCC若查找概率无法事先测定，则查找过程采取的改进若查找概率无法事先测定，则查找过程采取的改进办法是，附设一个办法是，附设一个访问频度域访问频度域或者在每次查找之后，或者在每次查找之后，将将刚刚查找到的记录直接移至表尾的位置上刚刚查找到的记录直接移至表尾的位置上。顺序查找顺序查找138.2 基于线性表的查找基于线性表的查找 第第 8 章章 查找查找数数 据据 结结 构构折半查找折半查找顺序查找的查找算法简单，但平均查找长顺序查找的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。度较大，特别不适用于表长较大的查

11、找表。若以若以有序表有序表表示查找表，则查找过程表示查找表，则查找过程可以基于可以基于“折半折半”进行。进行。148.2 基于线性表的查找基于线性表的查找 第第 8 章章 查找查找数数 据据 结结 构构折半查找折半查找1.1.首先确定查找表的首先确定查找表的中间中间位置；位置；2.2.然后将然后将待查的值与中间位置的值待查的值与中间位置的值进行比较，进行比较，若相等，则查找成功并返回此位置若相等，则查找成功并返回此位置，否则须否则须确定新的查找区间，继续二分查找确定新的查找区间，继续二分查找。基本思想基本思想:158.2 基于线性表的查找基于线性表的查找 第第 8 章章 查找查找数数 据据 结

12、结 构构折半查找折半查找例例1: key= 64 的查找过程如下：的查找过程如下：lowmidhighlowmidmidhigh low=11211109876543219288807564563721191305low 指示查找区间的下界指示查找区间的下界high=11mid=(1+11)/2=6 keymid指向的记录值指向的记录值low=mid+1=7 mid=(7+11)/2=9 keymid指向的记录值指向的记录值high=mid-1=8mid=(8+7)/2=7key=mid所指向的记录值所指向的记录值 查找成功查找成功举例举例:high 指示查找区间的上界指示查找区间的上界mid

13、 = (low+high)/270lowmidhighhighlow 查找不成功查找不成功168.2 基于线性表的查找基于线性表的查找 第第 8 章章 查找查找数数 据据 结结 构构折半查找折半查找算法算法int BinSrch(RecordList l, KeyType k) int low = 1, high = l.length, mid; while (low = high) mid = (low + high) / 2; if (k=l.rmid. key) return mid; else if (k50n50时，可得近似结果时，可得近似结果 log2(n+1)-1折半查找折半查找

14、只适用于只适用于有序有序表，且限于表，且限于顺序存储顺序存储结构结构198.2 基于线性表的查找基于线性表的查找 第第 8 章章 查找查找数数 据据 结结 构构分块查找分块查找 （索引顺序查找）（索引顺序查找）基本思想：基本思想：1 1、把线性表分成若干块，每块包含若干个记、把线性表分成若干块，每块包含若干个记录，在每一块中记录的存放是任意的，但块录，在每一块中记录的存放是任意的，但块与块之间必须有序。与块之间必须有序。（分块有序）（分块有序）2 2、建立一个索引表，把每块中的、建立一个索引表，把每块中的最大关键字最大关键字值及每块的第值及每块的第一一个记录在表中的位置和个记录在表中的位置和最

15、后最后一一个记录在表中的个记录在表中的位置位置存放在存放在索引项索引项中。中。20索索 引引 表表141186106485122key start finish012322 12 13 22 12 13 8 8 9 9 33 42 38 24 48 58 74 49 86 33 42 38 24 48 58 74 49 8614131211109876543218.2 基于线性表的查找基于线性表的查找 第第 8 章章 查找查找数数 据据 结结 构构分块查找分块查找 （索引顺序查找）（索引顺序查找）218.2 基于线性表的查找基于线性表的查找 第第 8 章章 查找查找数数 据据 结结 构构分块查

16、找分块查找 （索引顺序查找）（索引顺序查找）索引顺序表的查找过程：索引顺序表的查找过程：1）由索引确定记录所在区间（块）；）由索引确定记录所在区间（块）；2）在某个区间（块）内进行顺序查找。）在某个区间（块）内进行顺序查找。注意：索引可以根据查找表的特点来构造。注意：索引可以根据查找表的特点来构造。可见，可见， 分块查找分块查找的过程也是一个的过程也是一个“缩小区间缩小区间”的查找过程。的查找过程。分块查找分块查找的平均比较次数的平均比较次数 = = 查找查找“索引索引”的平均比较次数的平均比较次数 + + 查找查找“块内块内”的平均比较次数的平均比较次数22第第 8 章章 查找查找数数 据据

17、 结结 构构8.2 基于线性表的查找基于线性表的查找 线性表的三种查找方法比较线性表的三种查找方法比较 因此，对于不同的表长因此，对于不同的表长n、不同的表结构和表存、不同的表结构和表存储结构，应采用不同的查找方法。储结构，应采用不同的查找方法。顺序查找顺序查找折半查找折半查找分块查找分块查找表的结构表的结构有序、无序有序、无序有序有序表间有序表间有序表的存储表的存储顺序、链式顺序、链式顺序顺序顺序、链式顺序、链式ASLASL最大最大最小最小次之次之23第第 8 章章 查找查找数数 据据 结结 构构8.3 基于树的查找基于树的查找 二叉排序树二叉排序树二叉平衡树二叉平衡树B B- -树树B B

18、+ +树树键树键树24第第 8 章章 查找查找数数 据据 结结 构构8.3 基于树的查找基于树的查找 二叉排序树二叉排序树定义：定义：二叉排序树二叉排序树或者是一棵或者是一棵空空树；或者树；或者是具有如下特性的二叉树：是具有如下特性的二叉树：1. 若它的左子树不空，则若它的左子树不空，则左子树上所有左子树上所有 结点的值均小于根结点的值结点的值均小于根结点的值；3. 它的它的左、右子树也都分别是二叉排序树左、右子树也都分别是二叉排序树。2. 若它的右子树不空，则若它的右子树不空，则右子树上所有右子树上所有 结点的值均大于根结点的值结点的值均大于根结点的值；25第第 8 章章 查找查找数数 据据

19、 结结 构构8.3 基于树的查找基于树的查找 503080209010854035252388例如例如:是二叉排序树。是二叉排序树。66不不二叉排序树二叉排序树26第第 8 章章 查找查找数数 据据 结结 构构8.3 基于树的查找基于树的查找 二叉排序树二叉排序树查找算法查找算法n若给定值若给定值等于根结点等于根结点的关键字，则的关键字，则查找成功查找成功；n若给定值若给定值小于根结点小于根结点的关键字，则继续在的关键字，则继续在左左子树子树上进行查找；上进行查找；n若给定值若给定值大于根结点大于根结点的关键字，则继续在的关键字，则继续在右右子树子树上进行查找。上进行查找。否则，否则，若二叉排

20、序树为若二叉排序树为空空，则，则查找不成功查找不成功；在二叉排序树上进行查找，类似在二叉排序树上进行查找，类似折半查找折半查找2750308020908540358832第第 8 章章 查找查找数数 据据 结结 构构8.3 基于树的查找基于树的查找 例如例如: 二叉排序树二叉排序树查找关键字查找关键字= 50 ,35 , 90 , 953080209085403588325050304035508090二叉排序树二叉排序树查找算法查找算法失败失败28第第 8 章章 查找查找数数 据据 结结 构构8.3 基于树的查找基于树的查找 从上述查找过程可见，从上述查找过程可见，在查找过程中，生成了一条查

21、在查找过程中，生成了一条查找路径：找路径： 从根结点出发，沿着左分支或右分支逐层从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点向下直至关键字等于给定值的结点; 从根结点出发，沿着左分支或右分支逐层从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。向下直至指针指向空树为止。 查找成功查找成功 查找不成功查找不成功二叉排序树二叉排序树查找算法查找算法29BSTree SearchBST(BSTree bst, KeyType key) if (!bst) return NULL; else if (bst- key=key) return bst； else if

22、(key key) return SearchBST(bst-lchild, key); else return SearchBST(bst-rchild, key); 第第 8 章章 查找查找数数 据据 结结 构构8.3 基于树的查找基于树的查找 二叉排序树二叉排序树查找算法查找算法-递归递归30二叉排序树二叉排序树查找算法查找算法-非递归非递归第第 8 章章 查找查找数数 据据 结结 构构8.3 基于树的查找基于树的查找 BSTree SearchBST(BSTree bst, KeyType key) BSTree q; q=bst; while(q) if (q-key=k) retu

23、rn q; if (key data.key) q=q-lchild; else q=q-rchild; return NULL; 31二叉排序树二叉排序树插入算法插入算法第第 8 章章 查找查找数数 据据 结结 构构8.3 基于树的查找基于树的查找 根据动态查找表的定义，根据动态查找表的定义，“插入插入”操作操作在在查找不成功查找不成功时才进行；时才进行；若二叉排序树为若二叉排序树为空空树，则新插入的结点为树，则新插入的结点为新新的根结点的根结点；否则，新插入的结点必为一个；否则，新插入的结点必为一个新新的叶子结点的叶子结点，其，其插入位置插入位置由由查找过程查找过程得到。得到。324830

24、103523402025二叉排序树二叉排序树插入算法插入算法第第 8 章章 查找查找数数 据据 结结 构构8.3 基于树的查找基于树的查找 设设 key = 30304833二叉排序树二叉排序树插入算法插入算法第第 8 章章 查找查找数数 据据 结结 构构8.3 基于树的查找基于树的查找 void InsertBST(BSTree *bst, KeyType key) BiTree s; if (*bst=NULL) s=(BSTree)malloc(sizeof(BSTNode); s- key=key; s-lchild=NULL; s-rchild=NULL; *bst=s; else

25、if (key key) InsertBST(&(*bst)-lchild), key); else if (key (*bst)-key) InsertBST(&(*bst)-rchild), key); 34二叉排序树二叉排序树生成算法生成算法第第 8 章章 查找查找数数 据据 结结 构构8.3 基于树的查找基于树的查找 例如：设关键字输入顺序为：例如：设关键字输入顺序为： 45，24，53，12，28，90 28125324459024，45，53，90，12，28 289045122453所以，二叉排序树的所以，二叉排序树的形态形态完全由一个完全由一个输入输入序序列决定

26、，一个列决定，一个无序序列无序序列可以通过构造一棵二可以通过构造一棵二叉排序树而得到一个叉排序树而得到一个有序序列有序序列。35void CreateBST(BSTree *bst) KeyType key; *bst=NULL; scanf(%d, &key); while (key!=ENDKEY) InsertBST(bst, key); scanf(%d, &key); 二叉排序树二叉排序树生成算法生成算法第第 8 章章 查找查找数数 据据 结结 构构8.3 基于树的查找基于树的查找 364830103523402025二叉排序树特点二叉排序树特点:1.中序遍历中序遍历

27、二叉排序树可得到二叉排序树可得到关键字有序序列关键字有序序列。2.在构造二叉排序树时，每次插入的新结点都是新在构造二叉排序树时，每次插入的新结点都是新的叶子结点，则进行插入时，不必移动其它结点。的叶子结点，则进行插入时，不必移动其它结点。3.二叉排序树不但拥有类似于二叉排序树不但拥有类似于折半查找折半查找的特性，又采的特性，又采用了用了链表链表作存储结构，因此是作存储结构，因此是动态查找动态查找表的一种表的一种适宜适宜表示。表示。中序遍历：中序遍历：10，20，23，25，30，35，40，48第第 8 章章 查找查找数数 据据 结结 构构8.3 基于树的查找基于树的查找 37二叉排序树二叉排

28、序树删除算法删除算法第第 8 章章 查找查找数数 据据 结结 构构8.3 基于树的查找基于树的查找 和插入相反，删除在和插入相反，删除在查找成功查找成功之后进行，并且要求之后进行，并且要求在删除二叉排序树上某个结点之后，在删除二叉排序树上某个结点之后，仍然保持二叉仍然保持二叉排序树的特性。排序树的特性。可分三种情况讨论：可分三种情况讨论：（1）被删除的结点是）被删除的结点是叶子叶子；（2）被删除的结点）被删除的结点只有左子树或者只有右子树只有左子树或者只有右子树；（3）被删除的结点）被删除的结点既有左子树，也有右子树既有左子树，也有右子树。38二叉排序树二叉排序树删除算法删除算法第第 8 章章

29、 查找查找数数 据据 结结 构构8.3 基于树的查找基于树的查找 50802090403588328530（1）被删除的结点是）被删除的结点是叶子叶子结点结点例如例如:被删关键字被删关键字 = 20 88其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空”39二叉排序树二叉排序树删除算法删除算法第第 8 章章 查找查找数数 据据 结结 构构8.3 基于树的查找基于树的查找 50802090403588328530（2）被删除的结点）被删除的结点只有左子树只有左子树或或只有右子树只有右子树例如例如:被删关键字被删关键字 = 40 80其双亲结点的相应指针域的值改为其双亲结点的相应

30、指针域的值改为“指向被删除结点的左子树或右子树指向被删除结点的左子树或右子树”。40二叉排序树二叉排序树删除算法删除算法第第 8 章章 查找查找数数 据据 结结 构构8.3 基于树的查找基于树的查找 50802090403588328530（3）被删除的结点）被删除的结点既有左子树也有右子树既有左子树也有右子树例如例如:被删关键字被删关键字 = 50以其前驱或后继替代之，然后再删除该前驱或后继结点以其前驱或后继替代之，然后再删除该前驱或后继结点4041二叉排序树二叉排序树删除算法删除算法第第 8 章章 查找查找数数 据据 结结 构构8.3 基于树的查找基于树的查找 BSTNode * DelB

31、ST(BSTree t, KeyType k) BSTNode *p, *f,*s ,*q; p=t; f=NULL; while(p) if(p-key=k ) break; f=p; if（p-keyk） p=p-lchild; else p=p-rchild; 42if(p=NULL) return t；if(p-lchild=NULL) if(f=NULL) t=p-rchild; else if(f-lchild=p) f-lchild=p-rchild ； else f-rchild=p-rchild ; free(p);数数 据据 结结 构构二叉排序树二叉排序树删除算法删除算法第

32、第 8 章章 查找查找8.3 基于树的查找基于树的查找 43 else q=p; s=p-lchild; while(s-rchild) q=s; s=s-rchild; if(q=p) q-lchild=s-lchild ; else q-rchild=s-lchild; p-key=s-key; free(s); return t; 数数 据据 结结 构构二叉排序树二叉排序树删除算法删除算法第第 8 章章 查找查找8.3 基于树的查找基于树的查找 44数数 据据 结结 构构二叉排序树二叉排序树性能分析性能分析第第 8 章章 查找查找8.3 基于树的查找基于树的查找 由关键字序列由关键字序列

33、 1，2，3，4，5 构造而得的二叉排序树构造而得的二叉排序树例如：例如：ASLsucc =（1+2+3+4+5）/ 5 = 3ASLsucc =（1+2 2+2 3）/ 5 = 2.24321514352最最好好情况是与情况是与折半查找判定树折半查找判定树相同相同最最差差情况蜕化为单支树与情况蜕化为单支树与顺序顺序查找相同查找相同3，1，4，2，545含有值相同的含有值相同的n个关键字，构造的二叉排序树个关键字，构造的二叉排序树 中，中，ASL和树的形态有关和树的形态有关；2.最最差差的情况：当关键字有序时的情况：当关键字有序时,树的深度为树的深度为n， 其平均查找次数为其平均查找次数为（n

34、+1）/2。3.最最好好的情况：二叉排序树的的情况：二叉排序树的形态和折半查找的形态和折半查找的 判定树相同判定树相同，平均查找次数，平均查找次数和和log2n成正比。成正比。数数 据据 结结 构构二叉排序树二叉排序树性能分析性能分析第第 8 章章 查找查找8.3 基于树的查找基于树的查找 46数数 据据 结结 构构第第 8 章章 查找查找8.4 计算式查找法计算式查找法哈希表哈希表以上两节讨论的表示查找表的各种结构的以上两节讨论的表示查找表的各种结构的共同特点：共同特点：哈希表是什么？哈希表是什么？2.查找的过程为给定值依次和关查找的过程为给定值依次和关 键字集合中各个关键字进行比较键字集合

35、中各个关键字进行比较;3.查找的查找的效率效率取决于和给定值进取决于和给定值进 行行比较的比较的关键字关键字个数个数。1.记录在表中的位置和它的关键记录在表中的位置和它的关键 字之间字之间不不存在一个确定的关系；存在一个确定的关系；47 用这类方法表示的查找表，其用这类方法表示的查找表，其 平均查找长度都不为零平均查找长度都不为零。 不同的表示方法，其差别仅在于：不同的表示方法，其差别仅在于： 关键字和给定值进行比较的顺序不同关键字和给定值进行比较的顺序不同。数数 据据 结结 构构第第 8 章章 查找查找8.4 计算式查找法计算式查找法哈希表哈希表 只有一个办法：只有一个办法： 预先知道所查关

36、键字在表中的位置预先知道所查关键字在表中的位置。 对于频繁使用的查找表，希望对于频繁使用的查找表，希望 ASL = 0。 即要求：即要求：记录在表中位置和其关键字之间存在一种确定的关系。记录在表中位置和其关键字之间存在一种确定的关系。48数数 据据 结结 构构第第 8 章章 查找查找8.4 计算式查找法计算式查找法哈希表哈希表若以若以下标为下标为000 999 的顺序表的顺序表表示之。表示之。例如：为每年招收的例如：为每年招收的 1000 名新生建立一张查找表，名新生建立一张查找表，其关键字为学号，其值的范围为其关键字为学号，其值的范围为 xx000 xx999 (前前两位为年份两位为年份)。

37、则查找过程可以简单进行：则查找过程可以简单进行：取给定值（学号）的后取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待三位，不需要经过比较便可直接从顺序表中找到待查关键字。查关键字。49数数 据据 结结 构构第第 8 章章 查找查找8.4 计算式查找法计算式查找法哈希表哈希表但是，对于但是，对于动态查找表动态查找表而言，而言，因此在一般情况下，需在关键字与记录在表中的存因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以储位置之间建立一个函数关系，以 f(key) 作为关键作为关键字为字为 key 的记录在表中的位置，通常称这个函数的记录在表中的位置，通常称

38、这个函数 f(key) 为哈希函数。为哈希函数。1）表长不确定；）表长不确定；2）在设计查找表时，只知道关键字所）在设计查找表时，只知道关键字所 属范围，而不知道确切的关键字。属范围，而不知道确切的关键字。50数数 据据 结结 构构第第 8 章章 查找查找8.4 计算式查找法计算式查找法哈希表哈希表Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dei 例如：对于如下例如：对于如下 9 个关键字个关键字设设 哈希函数哈希函数 f(key) = (Ord(第一个字母第一个字母) -Ord(A)+1)/2 问题问题: 若添加关键字若添加关键字 Zhou , 怎么办？

39、怎么办？能否找到另一个哈希函数？能否找到另一个哈希函数？012345678910111213ChenZhaoQian SunLiWuHanYeDei51数数 据据 结结 构构第第 8 章章 查找查找8.4 计算式查找法计算式查找法哈希表哈希表1）哈希函数是一个哈希函数是一个映象映象，即将关键字的集合映即将关键字的集合映 射到某个地址集合上射到某个地址集合上， 它的设置很灵活，只它的设置很灵活，只 要这个地址集合的要这个地址集合的 大小不超出允许范围即可；大小不超出允许范围即可；从这个例子可见：从这个例子可见：2）由于哈希函数是一个）由于哈希函数是一个压缩映象压缩映象，因此，在一，因此，在一 般

40、情况下，很容易产生般情况下，很容易产生“冲突冲突”现象，现象， 即：即： key1 key2，而，而 f(key1) = (key2)。52数数 据据 结结 构构第第 8 章章 查找查找8.4 计算式查找法计算式查找法哈希表哈希表3) 很难找到一个很难找到一个不不产生冲突的哈希函数。产生冲突的哈希函数。 一般情况下，只能选择一般情况下，只能选择恰当恰当的哈希函数，的哈希函数， 使冲突尽可能少地产生使冲突尽可能少地产生。 因此，在构造这种特殊的因此，在构造这种特殊的“查找表查找表” 时，除时，除了需要选择一个了需要选择一个“好好”(尽可能少产生冲突尽可能少产生冲突)的的哈希函数之外；还需要找到一

41、种哈希函数之外；还需要找到一种“处理冲突处理冲突” 的方法。的方法。53数数 据据 结结 构构第第 8 章章 查找查找8.4 计算式查找法计算式查找法哈希表哈希表哈希表的定义：哈希表的定义： 根据设定的哈希函数根据设定的哈希函数 H(key) 和所选中的处和所选中的处理冲突的方法，将理冲突的方法，将一组关键字映象到一个有一组关键字映象到一个有限的、地址连续的地址集限的、地址连续的地址集 (区间区间) 上，并以关上，并以关键字在地址集中的键字在地址集中的“象象”作为相应记录在表作为相应记录在表中的存储位置中的存储位置，如此构造所得的查找表称之，如此构造所得的查找表称之为为“哈希表哈希表”。54数

42、数 据据 结结 构构第第 8 章章 查找查找8.4 计算式查找法计算式查找法哈希表哈希表 构造哈希函数的方法构造哈希函数的方法 对对数字数字的关键字可有下列构造方法：的关键字可有下列构造方法： 若是若是非数字非数字关键字，则需先对其进行关键字，则需先对其进行数字化数字化处理。处理。1. 直接定址法直接定址法3. 平方取中法平方取中法5. 除留余数法除留余数法4. 折叠法折叠法6. 随机数法随机数法2. 数字分析法数字分析法55数数 据据 结结 构构第第 8 章章 查找查找8.4 计算式查找法计算式查找法哈希表哈希表哈希函数为关键字的线性函数哈希函数为关键字的线性函数 H(key) = key

43、或者或者 H(key) = a key + b.直接定址法直接定址法此法仅适合于：此法仅适合于：地址集合的大小地址集合的大小 = = 关键字集合的大小关键字集合的大小构造哈希函数的方法构造哈希函数的方法56数数 据据 结结 构构第第 8 章章 查找查找8.4 计算式查找法计算式查找法哈希表哈希表 构造哈希函数的方法构造哈希函数的方法此方法仅适合于：此方法仅适合于：能预先估计出全体关键字的每能预先估计出全体关键字的每一位上各种数字出现的频度。一位上各种数字出现的频度。.数字分析法数字分析法 假设关键字集合中的每个关键字都是由假设关键字集合中的每个关键字都是由 s 位数字组成位数字组成 (u1,

44、u2, , us)，分析关键字集中的全体，分析关键字集中的全体， 并从中提取分并从中提取分布均匀的若干位或它们的组合作为地址。布均匀的若干位或它们的组合作为地址。8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 78 1 3 3 8 9 6 71 2 3 4 5 6 7 857数数 据据 结结 构构第第 8 章章 查找查找8.4 计算式查找法计算式查找法哈希表哈希表 构造哈希函数的方法构造哈希函数的方法 以以关键字的平方值的中间几位关键字的平方值的中间几位作为存储地址。求作为存储地址。求“关键字的

45、平方值关键字的平方值” 的目的是的目的是“扩大差别扩大差别” ，同时，同时平方值的中间各位又能受到整个关键字中各位的影响。平方值的中间各位又能受到整个关键字中各位的影响。. 平方取中法平方取中法 此方法适合于此方法适合于: 关键字中的每一位都有某些关键字中的每一位都有某些 数字重复出现频度很高的现象。数字重复出现频度很高的现象。58数数 据据 结结 构构第第 8 章章 查找查找8.4 计算式查找法计算式查找法哈希表哈希表 构造哈希函数的方法构造哈希函数的方法 将关键字分割成若干部分，然后取它们的将关键字分割成若干部分，然后取它们的叠加和为哈希地址。叠加和为哈希地址。. 折叠法折叠法 此方法适合

46、于此方法适合于: 关键字的数字位数特别多。关键字的数字位数特别多。有两种叠加处理的方法：有两种叠加处理的方法：移位叠加和间界叠加移位叠加和间界叠加。59. 除留余数法除留余数法 设定哈希函数为设定哈希函数为: H(key) = key MOD p 其中其中， pm (表长表长) 并且并且 p 应为不大于应为不大于 m 的素数的素数 或是或是 不含不含 20 以下的质因子以下的质因子数数 据据 结结 构构第第 8 章章 查找查找8.4 计算式查找法计算式查找法哈希表哈希表 构造哈希函数的方法构造哈希函数的方法60 给定一组关键字为：给定一组关键字为：12, 39, 18, 24, 33, 21，

47、 若取若取 p=9, 则他们对应的哈希函数值将为：则他们对应的哈希函数值将为： 3, 3, 0, 6, 6, 3例如：例如：为什么要对为什么要对 p 加限制？加限制？ 可见，若可见，若 p 中含质因子中含质因子 3， 则所有含质因子则所有含质因子 3 的的 关键字均映射到关键字均映射到“3 的倍数的倍数”的地址上，从而增加的地址上，从而增加 了了“冲突冲突”的可能。的可能。数数 据据 结结 构构第第 8 章章 查找查找构造哈希函数的方法构造哈希函数的方法8.4 计算式查找法计算式查找法哈希表哈希表61数数 据据 结结 构构第第 8 章章 查找查找8.4 计算式查找法计算式查找法哈希表哈希表 构

48、造哈希函数的方法构造哈希函数的方法.随机数法随机数法设定哈希函数为设定哈希函数为: H(key) = Random(key)其中，其中，Random 为伪随机函数为伪随机函数 此方法适合于：此方法适合于：关键字的长度不等关键字的长度不等62数数 据据 结结 构构第第 8 章章 查找查找8.4 计算式查找法计算式查找法哈希表哈希表 构造哈希函数的方法构造哈希函数的方法 实际造表时，实际造表时，采用何种采用何种构造哈希函数的构造哈希函数的方法方法取决于建表的关键字集合的情况取决于建表的关键字集合的情况(包括关包括关键字的范围和形态键字的范围和形态)，总的，总的原则是使产生冲突原则是使产生冲突的可能

49、性降到尽可能地小的可能性降到尽可能地小。63数数 据据 结结 构构第第 8 章章 查找查找8.4 计算式查找法计算式查找法哈希表哈希表处理冲突的方法处理冲突的方法 “处理冲突处理冲突” 的实际含义是：的实际含义是：为产生冲突的地址寻找下一个哈希地址。为产生冲突的地址寻找下一个哈希地址。1. 开放定址法开放定址法2. 链地址法链地址法3. 再哈希法再哈希法64数数 据据 结结 构构第第 8 章章 查找查找8.4 计算式查找法计算式查找法哈希表哈希表处理冲突的方法处理冲突的方法. 开放定址法开放定址法为产生冲突的地址为产生冲突的地址 H(key)求得一个地址序列：求得一个地址序列： H0, H1, H2, , Hs 1 sm-1其中：其中：H0 = H(key) Hi