数据结构解析课件

数据结构数据结构第第7 7章查找章查找7.1 7.1 查找的基本概念查找的基本概念查找表查找表:由同一类型的数据元素（或记录）构成的集合由同一类型的数据元素（或记录）构成的集合静态查找表：静态查找表：对查找表没有修改操作对查找表没有修改操作动态查找表：动态查找表：对查找表具有修改操作对查找表具有修改操作关键字关键字记录中某个数据项的值，可用来识别一个记录记录中某个数据项的值，可用来识别一个记录主关键字：主关键字：唯一标识数据元素唯一标识数据元素次关键字：次关键字：可以标识若干个数据元素可以标识若干个数据元素是一种数据结构是一种数据结构关键字的平均比较次数关键字的平均比较次数，也称，也称平均搜索长度平均搜索长度ASLASL(AverageAverage Search Length Search Length)n n：记录的个数：记录的个数pipi：查找第：查找第i i个记录的概率个记录的概率 (通常认为通常认为pi=1/n)pi=1/n)cici：找到第：找到第i i个记录所需的比较次数个记录所需的比较次数查找算法的评价指标查找算法的评价指标7.2 7.2 线性表的查找线性表的查找一、顺序查找（线性查找）一、顺序查找（线性查找）二、折半查找（二分或对分查找）二、折半查找（二分或对分查找）顺序查找顺序查找应用范围：应用范围：顺序表或线性链表表示的静态查找表顺序表或线性链表表示的静态查找表表内元素之间无序表内元素之间无序typedef struct ElemType *R;/表基址表基址 int length;/表长表长SSTable;顺序表的表示顺序表的表示int LocateELem(SqList L,ElemType e)for(i=0;i0;-i)=n;i0;-i)或或 for(ifor(i=1;i=n;i+)=1;i=n;i+)return i;空间复杂度：一个辅助空间。空间复杂度：一个辅助空间。时间复杂度：时间复杂度：1)1)查找成功时的平均查找长度查找成功时的平均查找长度 设表中各记录查找概率相等设表中各记录查找概率相等 ASLASLs s(n(n)=(1+2+.+)=(1+2+.+n)/nn)/n=(n+1)/2=(n+1)/22)2)查找不成功时的平均查找长度查找不成功时的平均查找长度 ASLASLf f =n+1=n+1顺序查找的性能分析顺序查找的性能分析算法简单，对表结构无任何要求（顺序和链式）算法简单，对表结构无任何要求（顺序和链式）n n很大时查找效率较低很大时查找效率较低改进措施：改进措施：非等概率非等概率查找时，可按照查找概率进查找时，可按照查找概率进行排序。行排序。顺序查找算法有特点顺序查找算法有特点n n个数存在一维数组个数存在一维数组A1.nA1.n中，在进行顺序查找时，中，在进行顺序查找时，这这n n个数的排列个数的排列有序或无序有序或无序其平均查找长度其平均查找长度ASLASL不同不同。练习练习:判断对错判断对错查找概率相等时，查找概率相等时，ASL相同；相同；查找概率不等时，如果从前向后查找，则按查找概率查找概率不等时，如果从前向后查找，则按查找概率由大到小排列的有序表其由大到小排列的有序表其ASL要比无序表要比无序表ASL小。小。lowhighmid 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid折半查找折半查找若若k=Rmid.key，查找成功，查找成功若若kRmid.key，则，则low=mid+1 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid若若k=Rmid.key，查找成功，查找成功若若kRmid.key，则，则low=mid+11 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92low highmid直至直至lowhigh时，查找失败时，查找失败折半查找（非递归算法）折半查找（非递归算法）设表长为设表长为n n，lowlow、highhigh和和midmid分别指向待查元素所分别指向待查元素所在区间的上界、下界和中点在区间的上界、下界和中点,k k为给定值为给定值初始时，令初始时，令low=1,high=low=1,high=n,midn,mid=(low+high)/2(low+high)/2 让让k k与与midmid指向的记录比较指向的记录比较若若k=k=Rmid.keyRmid.key，查找成功查找成功若若kkkRmid.keyRmid.key，则则low=mid+1low=mid+1重复上述操作，直至重复上述操作，直至lowhighlowhigh时，查找失败时，查找失败折半查找（递归算法）折半查找（递归算法）int Search_Bin(SSTable ST,keyType key,int low,int high)if(lowhigh)return 0;/查找不到时返回查找不到时返回0 mid=(low+high)/2;if(key=ST.elemmid.key)return mid;else if(key小于小于ST.elemmid.key)./递归递归 else./递归递归 -13-46-79-101-22-34-55-67-88-910-1111-639147102581112h外结点外结点内结点内结点data.key进行比较：进行比较：若若key等于等于T-data.key，则查找成功，返回根结点地，则查找成功，返回根结点地址；址；若若key小于小于T-data.key，则进一步查找左子树；，则进一步查找左子树；若若key大于大于T-data.key，则进一步查找右子树。，则进一步查找右子树。【算法思想算法思想】BSTree SearchBST(BSTree T,KeyType key)if(!T)|key=T-data.key)return T;else if(keydata.key)return SearchBST(T-lchild,key);/在左子树中继续查找在左子树中继续查找 else return SearchBST(T-rchild,key);/在右子树中继续查找在右子树中继续查找/SearchBST【算法描述算法描述】二叉排序树的操作插入二叉排序树的操作插入插入的元素插入的元素一定在一定在叶结点上叶结点上若二叉排序树为空，则插入结点应为若二叉排序树为空，则插入结点应为根结点根结点否则，继续在其左、右子树上查找否则，继续在其左、右子树上查找树中已有，不再插入树中已有，不再插入树树中中没没有有，若若待待插插入入结结点点小小于于根根结结点点，则则插插入其左子树；否则插入其右子树入其左子树；否则插入其右子树4512533372410061907820插入结点插入结点2020二叉排序树的操作插入二叉排序树的操作插入 10，18，3，8，12，2，710101810183101838101838 12101838 122101838 1227从空树出发，经过一系列的查找、插入操作之后，从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树可生成一棵二叉排序树二叉排序树的操作生成二叉排序树的操作生成不同插入次序的序列生成不同形态的二叉排序树不同插入次序的序列生成不同形态的二叉排序树4024551237122437405540，24，12，37，5512，24，37，40，55二叉排序树的操作生成二叉排序树的操作生成二叉排序树的操作删除二叉排序树的操作删除将因删除结点而断开的二叉链表重新链接将因删除结点而断开的二叉链表重新链接起来起来防止重新链接后树的高度增加防止重新链接后树的高度增加 2024年6月25日 北京林业大学信息学院北京林业大学信息学院删除叶结点删除叶结点删除叶结点删除叶结点，只需将其双亲结点指向它的指针清零，只需将其双亲结点指向它的指针清零，只需将其双亲结点指向它的指针清零，只需将其双亲结点指向它的指针清零，再释放它即可。再释放它即可。再释放它即可。再释放它即可。被删结点缺右子树被删结点缺右子树被删结点缺右子树被删结点缺右子树，可以拿它的左子女结点顶替它，可以拿它的左子女结点顶替它，可以拿它的左子女结点顶替它，可以拿它的左子女结点顶替它的位置，再释放它。的位置，再释放它。的位置，再释放它。的位置，再释放它。被删结点缺左子树被删结点缺左子树被删结点缺左子树被删结点缺左子树，可以拿它的右子女结点顶替它，可以拿它的右子女结点顶替它，可以拿它的右子女结点顶替它，可以拿它的右子女结点顶替它的位置，再释放它。的位置，再释放它。的位置，再释放它。的位置，再释放它。被删结点左、右子树都存在被删结点左、右子树都存在被删结点左、右子树都存在被删结点左、右子树都存在，可以在它的右子树中，可以在它的右子树中，可以在它的右子树中，可以在它的右子树中寻找中序下的第一个结点寻找中序下的第一个结点寻找中序下的第一个结点寻找中序下的第一个结点(关键码最小关键码最小关键码最小关键码最小),),),),用它的值填用它的值填用它的值填用它的值填补到被删结点中，再来处理这个结点的删除问题。补到被删结点中，再来处理这个结点的删除问题。补到被删结点中，再来处理这个结点的删除问题。补到被删结点中，再来处理这个结点的删除问题。第第i i层结点需比较层结点需比较i i次。在等概率的前提下，上述次。在等概率的前提下，上述两图的两图的平均查找长度平均查找长度为：为：40245512371224374055查找的性能分析查找的性能分析平均查找长度和二叉树的形态有关，即，平均查找长度和二叉树的形态有关，即，最好：最好：loglog2 2n n（形态匀称，与二分查找的判定树相似）（形态匀称，与二分查找的判定树相似）最坏最坏:（n n+1)/2+1)/2（单支树）（单支树）查找的性能分析查找的性能分析40245512371224374055问题：如何提高二叉排序树的查找效率？问题：如何提高二叉排序树的查找效率？尽量让二叉树的形状均衡尽量让二叉树的形状均衡左、右子树是平衡二叉树；左、右子树是平衡二叉树；所有结点的左、右子树深度之差的绝对值所有结点的左、右子树深度之差的绝对值 1 1平衡二叉树平衡二叉树平衡因子平衡因子:该结点左子树与右子树的高度差该结点左子树与右子树的高度差v任一结点的平衡因子只能取：任一结点的平衡因子只能取：-1-1、0 0 或或 1 1；如果；如果树中任意一个结点的平衡因子的绝对值大于树中任意一个结点的平衡因子的绝对值大于1 1，则这棵二叉树就失去平衡，不再是则这棵二叉树就失去平衡，不再是AVLAVL树；树；v对于一棵有对于一棵有n n个结点的个结点的AVLAVL树，其树，其高度保持在高度保持在O(logO(log2 2n n)数量级，数量级，ASLASL也保持在也保持在O(logO(log2 2n n)量级。量级。7.4 7.4 散列（哈希）表的查找散列（哈希）表的查找基本思想：基本思想：记录的存储位置与关键字之间存在记录的存储位置与关键字之间存在对应关系，对应关系，Loc(iLoc(i)=)=H(keyiH(keyi)优点：优点：查找速度极快查找速度极快O(1),查找效率与元素个数查找效率与元素个数n无关无关哈希函数哈希函数关键字关键字集合集合存储地址存储地址集合集合hash若将学生信息按如下方式存入计算机，如：若将学生信息按如下方式存入计算机，如：将将20010118102200101181020101的所有信息存入的所有信息存入VV0101 单元；单元；将将20010118102200101181020202的所有信息存入的所有信息存入VV0202 单元；单元；将将20010118102200101181023131的所有信息存入的所有信息存入V31V31单元。单元。查找查找20010118102200101181021616的信息，可直接访问的信息，可直接访问V16V16！例例1 1数数据据元元素素序序列列(14(14，2323，3939，9 9，2525，11)11)，若若规规定定每每个个元素元素k k的存储地址的存储地址H H（k k）k k，请画出存储结构图。，请画出存储结构图。141411119 9内容内容地址地址3939252524242323141411119 9232325253939例例2 2根据哈希函数根据哈希函数H（k）k 查找查找key=9,key=9,则访问则访问H(9)=9H(9)=9号地址，若内容为号地址，若内容为9 9则成功；则成功；若查不到，则返回一个特殊值，如空指针或空记录。若查不到，则返回一个特殊值，如空指针或空记录。如何查找如何查找141411119 9内容内容地址地址3939252524242323141411119 9232325253939哈希方法哈希方法(杂凑法杂凑法)选取某个选取某个函数函数，依该函数按关键字计算元素的存储位置，依该函数按关键字计算元素的存储位置，并按此存放；并按此存放；查找时，由同一个函数对给定值查找时，由同一个函数对给定值k k计算地址，计算地址，将将k k与地址与地址单元中元素关键码进行比单元中元素关键码进行比，确定查找是否成功。，确定查找是否成功。哈希函数哈希函数(杂凑函数杂凑函数)：哈希方法中使用的哈希方法中使用的转换函数转换函数有关术语有关术语冲冲 突：突：不同的关键码映射到同一个哈希地址不同的关键码映射到同一个哈希地址哈希表哈希表(杂凑表杂凑表)：按上述思想构造的表按上述思想构造的表有关术语有关术语141411119 9内容内容地址地址3939252524242323141411119 9232325253939同义词：同义词：具有具有相同函数值相同函数值的两个关键字的两个关键字key1 key2，但但H(key1)=H(key2)（14，23，39，9，25，11）哈希函数：哈希函数：H(k)=k mod 72539239146个元素用个元素用7个个地址应该足够地址应该足够!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4同义词同义词有冲突有冲突 0 1 2 3 4 5 6冲突现象举例冲突现象举例冲突是不可能避免的冲突是不可能避免的如何减少冲突如何减少冲突构造好的哈希函数构造好的哈希函数制定一个好的解决冲突方案制定一个好的解决冲突方案哈希函数的构造方法哈希函数的构造方法根据元素集合的特性构造根据元素集合的特性构造地址空间尽量小地址空间尽量小均匀均匀1.1.直接定址法直接定址法 2.2.数字分析法数字分析法3.3.平方取中法平方取中法4.4.折叠法折叠法5.5.除留余数法除留余数法6.6.随机数法随机数法 Hash(key)=akey+b (a、b为常数为常数)优点：优点：以关键码以关键码keykey的某个线性函数值为哈希的某个线性函数值为哈希地址，不会产生冲突。地址，不会产生冲突。缺点：缺点：要占用连续地址空间，空间效率低。要占用连续地址空间，空间效率低。直接定址法直接定址法 例：例：100，300，500，700，800，900，哈希函数哈希函数Hash(key)=key/1000 1 2 3 4 5 6 7 8 9900800700500300100直接定址法直接定址法Hash(key)=key mod p (p是一个整数是一个整数)关键：关键：如何选取合适的如何选取合适的p？技巧：技巧：设表长为设表长为m，取，取pm且为且为质数质数 除留余数法除留余数法（最常用重点掌握）（最常用重点掌握）执行速度（即计算哈希函数所需时间）；执行速度（即计算哈希函数所需时间）；关键字的长度；关键字的长度；哈希表的大小；哈希表的大小；关键字的分布情况；关键字的分布情况；查找频率。查找频率。构造哈希函数考虑的因素构造哈希函数考虑的因素1.开放开放定址法定址法处理冲突的方法处理冲突的方法2.链地址法链地址法基本思想：基本思想：有冲突时就去有冲突时就去寻找下一个空寻找下一个空的哈希地的哈希地址，只要哈希表足够大，空的哈希地址总址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。能找到，并将数据元素存入。1.1.开放定址法（开地址法）开放定址法（开地址法）线性探测法线性探测法二次探测法二次探测法伪随机探测法伪随机探测法Hi=(Hash(key)+di)mod m (1i m)其中：其中：m为哈希表长度为哈希表长度 di 为增量序列为增量序列 1，2，m-1，且，且di=i一旦冲突，就找下一个空地址存入一旦冲突，就找下一个空地址存入线性探测法线性探测法关键码集为关键码集为 47，7，29，11，16，92，22，8，3，设：设：哈希表表长为哈希表表长为m=m=11；哈希函数为哈希函数为Hash(key)=key mod 11 0 1 2 3 4 5 6 7 8 9 10477 291116922283 47、7、11、16、92没有冲突没有冲突 Hash(29)=7，有冲突，由，有冲突，由H1=(Hash(29)+1)mod 11=8，哈希地址哈希地址8为空，因此将为空，因此将29存入存入 3 3 连续移动了两次连续移动了两次连续移动了两次连续移动了两次线性探测法线性探测法线性探测法的特点线性探测法的特点优点：优点：只要哈希表未被填满，只要哈希表未被填满，保证能找到保证能找到一个空一个空地址单元存放有冲突的元素。地址单元存放有冲突的元素。缺点：缺点：可能使第可能使第i个哈希地址的同义词存入第个哈希地址的同义词存入第i+1个个地址，这样本应存入第地址，这样本应存入第i+1个哈希地址的元素个哈希地址的元素变成了第变成了第i+2个哈希地址的同义词，个哈希地址的同义词，产，产生生“聚集聚集”现象，降低查找效率。现象，降低查找效率。解决方案：解决方案：二次探测法二次探测法二次探测法二次探测法关键码集为关键码集为 47，7，29，11，16，92，22，8，3，设：设：哈希函数为哈希函数为Hash(key)=key mod 11 Hi=(Hash(key)di)mod m其中：其中：m为哈希表长度，为哈希表长度，m要求是某个要求是某个4k+3的质数的质数；di为增量序列为增量序列 12，-12，22，-22，q2 0 1 2 3 4 5 6 7 8 9 10829716924732211 Hash(3)=3，哈希地址冲突，由，哈希地址冲突，由H1=(Hash(3)+12)mod 11=4，仍然冲突；，仍然冲突；H2=(Hash(3)-12)mod 11=2，找到空的哈希地址，存入。找到空的哈希地址，存入。伪随机探测法伪随机探测法Hi=(Hash(key)+di)mod m (1i m)其中：其中：m为哈希表长度为哈希表长度 di 为随机数为随机数2.2.链地址法链地址法(拉链法）拉链法）基本思想：基本思想：相同哈希地址的记录链成一单链表，相同哈希地址的记录链成一单链表，m个哈个哈希地址就设希地址就设m个单链表个单链表，然后用用一个数组将，然后用用一个数组将m个单个单链表的表头指针存储起来，形成一个动态的结构链表的表头指针存储起来，形成一个动态的结构0 1 2 3 4 5 6 7 8 9 10 11 12 14127796855198420231011H(k)=k%13链地址法的优点：链地址法的优点：非同义词不会冲突，无非同义词不会冲突，无“聚集聚集”现象现象链链表表上上结结点点空空间间动动态态申申请请，更更适适合合于于表表长长不不确确定的情况定的情况哈希表的查找哈希表的查找给定给定k k值值计算计算H(kH(k)此地址为空此地址为空关键字关键字=k=k查找失败查找失败查找成功查找成功按处理冲突按处理冲突方法计算方法计算HiHiY YN NY YN N给定值与关键字比较给定值与关键字比较 2024年6月25日 北京林业大学信息学院北京林业大学信息学院已知一组关键字已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)(19,14,23,1,68,20,84,27,55,11,10,79)哈希函数为：哈希函数为：H(keyH(key)=key MOD 13,)=key MOD 13,哈希表长为哈希表长为m=16m=16，设每个记录的查找概率相等设每个记录的查找概率相等(1)(1)用线性探测再散列处理冲突，即用线性探测再散列处理冲突，即Hi=(Hi=(H(key)+diH(key)+di)MOD m)MOD m0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1514 1 68 27 55 19 20 84 79 23 11 101 2 1 4 3 1 1 3 9 1 1 3 H(19)=6H(14)=1H(23)=10H(1)=1 冲突，冲突，H1=(1+1)MOD16=2H(68)=3H(20)=7H(27)=1 冲突，冲突，H1=(1+1)MOD16=2 冲突，冲突，H2=(1+2)MOD16=3 冲突，冲突，H3=(1+3)MOD16=4ASL=(1*6+2+3*3+4+9)/12=2.5哈希表的查找哈希表的查找(2)(2)用链地址法处理冲突用链地址法处理冲突0 1 2 3 4 5 6 7 8 9 10 11 12 14127796855198420231011ASL=(1*6+2*4+3+4)/12=1.75关键字关键字(19,14,23,1,68,20,84,27,55,11,10,79)哈希表的查找哈希表的查找使用平均查找长度使用平均查找长度ASLASL来衡量查找算法，来衡量查找算法，ASLASL取决于取决于哈希函数哈希函数处理冲突的方法处理冲突的方法哈希表的装填因子哈希表的装填因子哈希表的查找效率分析哈希表的查找效率分析 越大，表中记录数越多，说明表装得越越大，表中记录数越多，说明表装得越满，发生冲突的可能性就越大，查找时比满，发生冲突的可能性就越大，查找时比较次数就越多。较次数就越多。O(1)?ASLASL与装填因子与装填因子 有关！既不是严格的有关！既不是严格的O(1)O(1)，也不是，也不是O(nO(n)哈希表的查找效率分析哈希表的查找效率分析p对哈希表技术具对哈希表技术具有有很好的平均性能很好的平均性能，优于一优于一些传统的技术些传统的技术p链地址法链地址法优于开地址法优于开地址法p除留余数法除留余数法作哈希函数优于其它类型函数作哈希函数优于其它类型函数几点结论几点结论构造构造Hash函数的方法：函数的方法：p将标识符中的每个字符转换为一个非负整数将标识符中的每个字符转换为一个非负整数p将得到的各个整数组合成一个整数（可以将第一将得到的各个整数组合成一个整数（可以将第一个、中间的和最后一个字符值加在一起，也可以将个、中间的和最后一个字符值加在一起，也可以将所有字符的值加起来）所有字符的值加起来）p将结果数调整到将结果数调整到0M-1范围内，可以利用取模的方范围内，可以利用取模的方法，法，Ki%M（M为素数）为素数）哈希表应用举例哈希表应用举例编译器对标识符的管理编译器对标识符的管理多是采用哈希表多是采用哈希表1.1.熟练掌握顺序表和有序表（熟练掌握顺序表和有序表（折半查找折半查找）的查找算法及其性能）的查找算法及其性能分析方法；分析方法；2.熟练掌握熟练掌握二叉排序树的构造和查找二叉排序树的构造和查找算法及其性能分析方法；算法及其性能分析方法；3.掌握二叉排序树的掌握二叉排序树的插入插入算法，了解二叉排序树的删除算法；算法，了解二叉排序树的删除算法；4.熟练掌握哈希函数熟练掌握哈希函数（除留余数法）（除留余数法）的构造的构造5.熟练掌握哈希函数熟练掌握哈希函数解决冲突的方法解决冲突的方法及其特点及其特点l 开放地址法（开放地址法（线性探测法、二次探测法）线性探测法、二次探测法）l 链地址法链地址法l 给定实例计算平均查找长度给定实例计算平均查找长度ASL，ASL依赖于依赖于装填装填因子因子 小结小结