数据结构-用面向对象语言描述-殷人昆-第七章

1、第七章第七章 搜索结构搜索结构杨同峰杨同峰1第七章 搜索结构2搜索搜索(Search)(Search)的概念的概念静态搜索表n所谓所谓搜索搜索，就是在数据集合中寻找满足某种，就是在数据集合中寻找满足某种条件的数据对象。条件的数据对象。n搜索的结果通常有两种可能：搜索的结果通常有两种可能：搜索成功搜索成功，即找到满足条件的数据对象。，即找到满足条件的数据对象。这时，作为结果，可报告该对象在结构中这时，作为结果，可报告该对象在结构中 的位置的位置, 还可给出该对象中的具体信息。还可给出该对象中的具体信息。搜索不成功搜索不成功，或搜索失败。作为结果，应，或搜索失败。作为结果，应报告一些信息报告一些信

2、息, 如失败标志、位置等。如失败标志、位置等。3p通常称用于搜索的数据集合为搜索结构，它是由同一数据类型的对象(或记录)组成。p在每个对象中有若干属性，其中有一个属性，其值可唯一地标识这个对象。称为关键码。使用基于关键码的搜索，搜索结果应是唯一的。但在实际应用时，搜索条件是多方面的，可以使用基于属性的搜索方法，但搜索结果可能不唯一。p实施搜索时有两种不同的环境。u静态环境，搜索结构在插入和删除等操作的前后不发生改变。 静态搜索表 4u动态环境，为保持较高的搜索效率, 搜索结构在执行插入和删除等操作的前后将自动进行调整，结构可能发生变化。 动态搜索表p在静态搜索表中，数据元素存放于数组中，利用数

3、组元素的下标作为数据元素的存放地址。搜索算法根据给定值 k，在数组中进行搜索。直到找到 k 在数组中的存放位置或可确定在数组中找不到 k 为止。 静态搜索表5p顺序搜索主要用于在线性表中搜索。p设若表中有 CurrentSize 个元素，则顺序搜索从表的先端开始，顺序用各元素的关键码与给定值 x 进行比较p若找到与其值相等的元素，则搜索成功，给出该元素在表中的位置。p若整个表都已检测完仍未找到关键码与 x 相等的元素，则搜索失败。给出失败信息。顺序搜索（Sequential Search） 6p顺序搜索的平均搜索长度p在等概率情形，pi = 1/n, i = 1, 2, , n。搜索成功的平均

4、搜索长度为：p在搜索不成功情形，ASLunsucc = n+1。.)()(1- nisuccnnnninASL021211117* *常用的查找算法常用的查找算法9.2 9.2 顺序查找顺序查找struct Recordstruct Record int key; int key; ; ;Record rn;Record rn;无监视哨的顺序查找无监视哨的顺序查找: int SeqSearch(Record r, int n, int k) int i=0;while (in&ri.key!=k) i+;if (in) return i;else return -1;有监视哨的顺序查找

5、有监视哨的顺序查找pint SeqSearch2(Record r, int n, int k)ppint i=0;prn.key=k;pwhile (ri.key!=k) i+;pif (in) return i;pelse return -1;p 顺序查找的平均查找长度为：顺序查找的平均查找长度为：顺序查找的特点：算法简单，但查找效率低。顺序查找的特点：算法简单，但查找效率低。2/ ) 1()/(11nnicpASLniniiisq 二分查找又称为折半查找。二分查找又称为折半查找。 二分查找要求顺序表是有序的。二分查找要求顺序表是有序的。 与中间位置比较，若相等，与中间位置比较，若相等，

6、则找到！则找到！ 如果小，如果小，则在前半段查找，则在前半段查找， 否则在后边段查找。否则在后边段查找。例例: : 05 13 19 21 37 56 64 75 05 13 19 21 37 56 64 75 80 88 9280 88 92 05 13 19 21 3705 13 19 21 37 56 64 75 56 64 75 80 88 9280 88 9205 13 19 05 13 19 21 3721 37 56 64 75 56 64 75 80 88 9280 88 92查找查找K=21K=21的过程（查找成功）的过程（查找成功）05 13 19 21 37 56 64

7、75 05 13 19 21 37 56 64 75 80 88 9280 88 9205 13 19 21 37 56 64 75 05 13 19 21 37 56 64 75 80 88 9280 88 9205 13 19 21 37 56 64 75 05 13 19 21 37 56 64 75 80 88 9280 88 92查找查找K=85K=85的过程（查找失败）的过程（查找失败）05 13 19 21 37 56 64 75 05 13 19 21 37 56 64 75 80 88 92 80 88 92 二分查找算法二分查找算法(非递归非递归)二分查找算法二分查找算法(

8、递归递归) 如果把当前查找位置上的结点作为根，左子如果把当前查找位置上的结点作为根，左子表和右子表的结点分别作为根的左子树和右子树，由表和右子表的结点分别作为根的左子树和右子树，由此得到的二叉树称为描述二分查找的判定树。此得到的二叉树称为描述二分查找的判定树。 借助于判定树很容易求得二分查找的平均查借助于判定树很容易求得二分查找的平均查找长度。查找数据的比较次数最多为该判定树的树高找长度。查找数据的比较次数最多为该判定树的树高. . 二分查找的算法复杂度为：二分查找的算法复杂度为：O(log n)O(log n)即在最坏情况下，二分查找方法查找成功的比较即在最坏情况下，二分查找方法查找成功的比

9、较次数不超过判定树的高度。次数不超过判定树的高度。 虽然二分查找的效率较高，但它要求被虽然二分查找的效率较高，但它要求被查找序列查找序列事先按关键字排好序事先按关键字排好序，而排序本身是一，而排序本身是一种很费时的运算；另外，二分查找只适用于顺序种很费时的运算；另外，二分查找只适用于顺序存储结构，因此，二分查找特别适用于那种一经存储结构，因此，二分查找特别适用于那种一经建立就很少改动、而又需要经常查找的线性表。建立就很少改动、而又需要经常查找的线性表。 二叉排序树的查找二叉排序树的查找二叉排序树的概念二叉排序树的概念二叉排序树的建立二叉排序树的建立二叉排序树的插入二叉排序树的插入二叉排序树的删

10、除二叉排序树的删除二叉排序树的查找二叉排序树的查找查找性能分析查找性能分析1. 1. 二叉排序树的概念二叉排序树的概念 也称为二叉查找树也称为二叉查找树. .(1)(1)左子树的所有结点的值左子树的所有结点的值 根结点的值根结点的值(3)(3)左子树、右子树都是二叉排序树。左子树、右子树都是二叉排序树。举例：举例：性质：性质：中序遍历二叉排序树得到的是有序序列。中序遍历二叉排序树得到的是有序序列。pclass BiSortTreeppBiNode *root;pvoid Insert(BiNode *&ptr, int k); /供插入函数调用供插入函数调用pBiNode* Searc

11、h(BiNode *ptr, int k); /供查找函数调用供查找函数调用pvoid Delete (BiNode *&ptr, int k); /供删除函数调用供删除函数调用p void Free(BiNode *ptr); /供析构函数调用供析构函数调用ppublic:pBiSortTree(int a , int n); /建立二叉排序树建立二叉排序树pBiSortTree(); /析构函数析构函数pvoid Insert(int k); /插入插入pbool Search(int k); /查找查找pvoid Delete (int k); /删除删除p;2 2二叉排序树的插

12、入和建立二叉排序树的插入和建立在一棵二叉排序树中插入值为在一棵二叉排序树中插入值为k k的结点，步骤如的结点，步骤如下：下： 若二叉排序树为空，则生成值为若二叉排序树为空，则生成值为k k的新结点的新结点s s，同时将新结点同时将新结点s s作为根结点插入。作为根结点插入。 若若k k小于根结点的值，则在根的左子树中插小于根结点的值，则在根的左子树中插入值为入值为k k的结点。的结点。 若若k k大于根结点的值，则在根的右子树中插大于根结点的值，则在根的右子树中插入值为入值为k k的结点。的结点。 若若k k等于根结点的值，表明二叉排序树中已等于根结点的值，表明二叉排序树中已有此关键字，则无须

13、插入。有此关键字，则无须插入。 二叉排序树的建立算法二叉排序树的建立算法 BiSortTree:BiSortTree(int a , int n) BiSortTree:BiSortTree(int a , int n) root = NULL;root = NULL; for (int i = 0; i n; i+) for (int i = 0; i key) return ptr; if (k=ptr-key) return ptr; else if (kkey) ptr=ptr-lchild;else if (kkey) ptr=ptr-lchild; else ptr=ptr-rch

14、ild; else ptr=ptr-rchild; return NULL;return NULL; bool BiSortTree:Search2(int k) bool BiSortTree:Search2(int k) /查找查找 return Search2(root,k)!=NULL; return Search2(root,k)!=NULL; p分三种情况分三种情况 :（1）删除叶子结点）删除叶子结点p（2）删除单支结点）删除单支结点p（3）删除双支结点）删除双支结点递归删除算法的步骤如下：递归删除算法的步骤如下：p 若二叉排序树为空，则表明不存在删除的结点，不若二叉排序树为空，则

15、表明不存在删除的结点，不进行删除操作。进行删除操作。p 若给定值若给定值k小于根结点的值，则继续在根的左子树小于根结点的值，则继续在根的左子树中删除。中删除。p 若给定值若给定值k大于根结点的值，则继续在根的右子树大于根结点的值，则继续在根的右子树中删除。中删除。p 若给定值若给定值k等于根结点的值，则根结点即为要删除等于根结点的值，则根结点即为要删除的结点，此时需要根据上述分析的三种结点情况：叶的结点，此时需要根据上述分析的三种结点情况：叶子结点、单支结点或双支结点，执行相应的删除操作。子结点、单支结点或双支结点，执行相应的删除操作。7.3 7.3 平衡二叉树平衡二叉树p问题的提出问题的提出

16、p什么是平衡二叉树什么是平衡二叉树p平衡二叉树的建立平衡二叉树的建立 左子树与右子树高度之差称为结点的左子树与右子树高度之差称为结点的。由平衡二叉树定义可知，平衡二由平衡二叉树定义可知，平衡二叉树所有结点的平衡因子只能取叉树所有结点的平衡因子只能取 1 1，0 0，1 1三个值之一。三个值之一。p如何使建立的一棵二叉排序树是平衡的呢？如何使建立的一棵二叉排序树是平衡的呢？p这就要求当新结点插入二叉排序树时，必须保持所有结点这就要求当新结点插入二叉排序树时，必须保持所有结点的平衡因子满足平衡二叉树的要求，一旦不满足要求，就的平衡因子满足平衡二叉树的要求，一旦不满足要求，就必须进行必须进行调整调整

17、。关键！关键！p从插入位置沿着通向根的路径回溯，逐一检查每个节点的从插入位置沿着通向根的路径回溯，逐一检查每个节点的平衡因子，当发现不平衡时，这个不平衡节点和向下的两平衡因子，当发现不平衡时，这个不平衡节点和向下的两个节点个节点 构成关键的三个节点。构成关键的三个节点。p这三个节点的形状决定了需要采取的操作。这三个节点的形状决定了需要采取的操作。38调整有调整有4 4种情况种情况p（1）LL型型p（2）RR型型p（3）LR型型p（4）RL型型9.7 B9.7 B树与树与B+B+树树p什么是什么是B B树树? ? pB B树的查找树的查找p什么是什么是B+B+树树? ? pB+B+树的查找树的查

18、找9.8 Hash9.8 Hash查找查找1. 1. 基本概念基本概念 Hash, Hash, 哈希哈希, ,也称为也称为散列散列. . HashHash是一种重要的存储方法，也是一种常是一种重要的存储方法，也是一种常见的查找方法。见的查找方法。 它的基本思想是：以数据元素的关键字它的基本思想是：以数据元素的关键字K K为为自变量，通过一个确定的函数关系，计算出对应自变量，通过一个确定的函数关系，计算出对应的函数值的函数值f(K)f(K)，把这个值作为数据元素的存储地，把这个值作为数据元素的存储地址。查找时也是根据这个函数计算其存储位置。址。查找时也是根据这个函数计算其存储位置。 【例】【例】

19、 假设一组记录的关键字分别为假设一组记录的关键字分别为18，27，1，20，22，6，10，13，41，15，25。选取关键字与。选取关键字与记录位置间的函数为记录位置间的函数为f(key)=key %11。pHash函数函数-关键字与记录位置间的函数关键字与记录位置间的函数.pHash地址地址-据据HashHash函数计算出的存储位置函数计算出的存储位置. .pHash表表-存储记录的查找表存储记录的查找表, ,该表中根据该表中根据HashHash函数计算出函数计算出的存储位置的存储位置. .p基于基于Hash表的查找称为表的查找称为Hash查找。查找。在建立在建立HashHash表时，若表

20、时，若HashHash函数是一个一对一的函数，函数是一个一对一的函数， 则在查找时，只需根据散列函数对给定值进行某种运则在查找时，只需根据散列函数对给定值进行某种运 算，即可得到待查数据的存储位置。算，即可得到待查数据的存储位置。在一般情况下，在一般情况下， HashHash表的空间必须比数据的集合大，表的空间必须比数据的集合大， 此时虽然浪费了一定的空间，但换取的是查找效率。此时虽然浪费了一定的空间，但换取的是查找效率。 设散列表的空间大小为设散列表的空间大小为m m，填入表中的数据个数为，填入表中的数据个数为n n，则称则称=n/m=n/m为散列表的为散列表的装填因子装填因子。HashHa

21、sh函数的选取原则是：运算尽可能简单；函数的值函数的选取原则是：运算尽可能简单；函数的值 域必须在表长的范围内；尽可能使得关键字不同时，域必须在表长的范围内；尽可能使得关键字不同时， 其散列函数值亦不相同。其散列函数值亦不相同。若某个若某个HashHash函数对于不相等的关键字计算出了相同的函数对于不相等的关键字计算出了相同的 HashHash地址，则称该现象为地址，则称该现象为hashhash冲突冲突，发生冲突的两个，发生冲突的两个关键字该关键字该HashHash函数的函数的同义词同义词。在实际应用中，不产生冲。在实际应用中，不产生冲突的突的HashHash函数极少存在。函数极少存在。直接定

22、址法直接定址法除留余数法除留余数法数字分析法数字分析法平方取中法平方取中法折叠法折叠法直接定址法直接定址法 Hash Hash函数是关键字的线性函数。即：函数是关键字的线性函数。即： H(key) = aH(key) = akeykeyb例例1 1：已知一个含有：已知一个含有7070个数据的线性表，其关个数据的线性表，其关键字是两位十进制数字组成，则可将线性表存键字是两位十进制数字组成，则可将线性表存储在如下说明的散列表中：储在如下说明的散列表中： int HT100;int HT100;其中，其中，HTiHTi存放关键字为存放关键字为i i的结点，即散列函的结点，即散列函数为：数为： H(k

23、ey)=keyH(key)=key除留余数法除留余数法 选择一个适当的正整数选择一个适当的正整数P，用，用P去除关键字，取去除关键字，取所得得余数作为散列地址，即：所得得余数作为散列地址，即： H(key) = key%P这个方法的关键是选取适当的这个方法的关键是选取适当的P。选择。选择P最好不要是最好不要是偶数，也不要是基数的幂。一般地选偶数，也不要是基数的幂。一般地选P为小于或等于为小于或等于散列表长度散列表长度m的某个最大的某个最大质数质数比较好。例如：比较好。例如： m = 8，16，32，64，128，256，512，1024 P = 7，13，31，61，127，251，503，1

24、019除余法的地址计算公式简单，而且在很多情况下效除余法的地址计算公式简单，而且在很多情况下效果较好，因此是一种常用的构造散列函数的方法。果较好，因此是一种常用的构造散列函数的方法。数字分析法数字分析法 若事先知道关键字集合，且关键字的位数比散列表若事先知道关键字集合，且关键字的位数比散列表的地址位数多，则可选取数字分布比较均匀的若干位作的地址位数多，则可选取数字分布比较均匀的若干位作为散列地址。例如，有一组为散列地址。例如，有一组8位数字组成的关键字：位数字组成的关键字： 经过分析可知，前三位和第五位分布不均匀，所以，经过分析可知，前三位和第五位分布不均匀，所以，若表长为若表长为1000，则

25、可取，则可取4、6、7位的数字作为散列地址，位的数字作为散列地址，若表长为若表长为100，则可取，则可取4、6与与7、8位之和并舍去进位作位之和并舍去进位作为散列地址。为散列地址。平方取中法平方取中法 通常，要预先估计关键字的数字分布并不容易，通常，要预先估计关键字的数字分布并不容易，要找数字均匀分布的位数更难。此时可采用平方取要找数字均匀分布的位数更难。此时可采用平方取中法：即先通过求关键字的平方来扩大差别，再取中法：即先通过求关键字的平方来扩大差别，再取其中的几位或其组合作为散列地址。其中的几位或其组合作为散列地址。 例如：一组关键字：例如：一组关键字： (0100，0110，1010，1

26、001，0111)平方结果为：平方结果为：(0010000，0012100，1020100，1002001，0012321)若表长为若表长为3位，则可取中间三位作为散列地址集：位，则可取中间三位作为散列地址集： (100，121，201，020，123)折叠法折叠法 若关键字位数较多，可将关键字分割成位数相若关键字位数较多，可将关键字分割成位数相同的几段（最后一段的位数可以不同），段的长度同的几段（最后一段的位数可以不同），段的长度取决于散列表的地址位数，然后将各段的迭加和取决于散列表的地址位数，然后将各段的迭加和（舍去进位）作为散列地址。（舍去进位）作为散列地址。 例如，对于例如，对于key

27、=58242324169 582 582 423 423 241 241 + 69 + 69 1315 1315H(key)=315H(key)=315移位迭加移位迭加 582 582 324 324 241 241 + 96 + 96 1243 1243H(key)=243H(key)=243边界迭加边界迭加3. 3. 处理处理hashhash冲突的方法冲突的方法(1)(1)开放地址法开放地址法 线性探察法线性探察法 二次探察法二次探察法 双散列函数法双散列函数法(2)(2)链地址法链地址法 用开放地址法解决冲突的基本思想是：用开放地址法解决冲突的基本思想是：当冲突发生时，使用某种方法在散列

28、表中当冲突发生时，使用某种方法在散列表中形成一个探查序列，按此序列逐个单元的形成一个探查序列，按此序列逐个单元的查找，直到找到一个指定的关键字或碰到查找，直到找到一个指定的关键字或碰到一个开放的地址（单元为空）为止。插入一个开放的地址（单元为空）为止。插入时碰到开放的地址，即可将待插入新结点时碰到开放的地址，即可将待插入新结点放到该地址单元中；查找时碰到开放的地放到该地址单元中；查找时碰到开放的地址，则说明表中没有待查的关键字。址，则说明表中没有待查的关键字。 形成探测的方法不同，所得到的解决形成探测的方法不同，所得到的解决冲突的方法也不同。冲突的方法也不同。线性探测法线性探测法 将散列表看成

29、是一个环形表。若地址为将散列表看成是一个环形表。若地址为d（即（即H(key)=d）的单元发生冲突，则依次探查下述地址）的单元发生冲突，则依次探查下述地址单元：单元： d+1，d+2，.，m-1，0，1，.，d-1直到找到一个空单元或查找到关键字为直到找到一个空单元或查找到关键字为key的结点为的结点为止。当然，若沿着该探查序列查找一遍之后，又回止。当然，若沿着该探查序列查找一遍之后，又回到了地址到了地址d，则无论是做插入操作还是做查找操作，则无论是做插入操作还是做查找操作，都意味着失败。都意味着失败。 例例: 有关键字序列为有关键字序列为3636，7 7，4040，1111，1616，8181，2222，8 8，1414，HashHash表表长为表表长为1111，Hash(key)=key % 11Hash(key)=key % 11，用线性探测法处理冲突，建立的用线性探测法处理冲突，建立的HashHash表。表。 板书板书二次探查法二次探查法 二次探查法的探查序列依次为：二次探查法的探查序列依次为：12，-12，22，-22，.，等，也就是说，发生冲突时，将同义词，等，也就是说，发生冲突时，将同义词来回散列在第一个地址的两端。求下一个开放地来回散列在第一个地址的两端。求下一个开放地址的公式为：址的公式为： d2i