讲义专业课数据结构课件

1、1第九章 查 找精英专升本23何谓查找表 ？ 查找表是由同一类型的数据元素(或记录)构成的集合。 由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。4对查找表经常进行的操作:1）查询某个“特定的”数据元素是否在查找表中；2）检索某个“特定的”数据元素的各种属性；3）在查找表中插入一个数据元素；4）从查找表中删去某个数据元素。5仅作查询和检索操作的查找表。静态查找表有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。动态查找表查找表可分为两类:6是数据元素（或记录）中某个数据项的

2、值，用以标识（识别）一个数据元素（或记录）。关键字 若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。 若此关键字能识别若干记录，则称之谓“次关键字”。7 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。 查找 若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置； 否则称“查找不成功”。查找结果给出“空记录”或“空指针”。8 由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。 为了提高查找的效率， 需要在查找表中的元素之间人为地 附加某种确定的关系，换句话说， 用另外一种结构来表示查找表。如何进

3、行查找？查找的方法取决于查找表的结构。99.1 静态查找表9.2 动态查找树表9.3 哈希表109.1 静态查找表顺序存储结构链式存储结构顺序表线性链表11typedef struct / 数据元素存储空间基址，建表时 / 按实际长度分配，0号单元留空 int length; / 表的长度 SSTable;假设静态查找表的顺序存储结构为ElemType *elem;声明顺序查找表变量：SSTable ST12数据元素类型的定义为:typedef struct keyType key; / 关键字域 / 其它属性域 ElemType ; , TElemType ;若有顺序查找表ST，则第i个元素

4、的关键字是：ST.elemi.key139.1.1、顺序查找表9.1.2、有序查找表9.1.3、静态查找树表(*)9.1.4、索引顺序表14ST.elem回顾顺序表的查找过程：P26算法2.6假设给定值 e=64,要求 ST.elemk = e, 问: k = ?k一、顺序查找表 以顺序表或线性链表表示静态查找表kk假设给定值 e=91,要求 ST.elemk = e, 问: k = ?15ST.elemST.elem60ikey=64key=6064算法2.6的改进：iii16int Search_Seq(SSTable ST, KeyType key) / 在顺序表ST中顺序查找其关键字等

5、于 / key的数据元素。若找到，则函数值为 / 该元素在表中的位置，否则为0。 ST.elem0.key = key; / “哨兵” for (i=ST.length; ST.elemi.key!=key; -i); / 从后往前找 return i; / 找不到时，i为0 / Search_Seq17关键字的平均比较次数，也称平均搜索长度ASL(Average Search Length)n：记录的个数pi：查找第i个记录的概率 ( 通常认为pi =1/n )ci：找到第i个记录所需的比较次数（n-i+1）查找算法的评价指标18空间复杂度：一个辅助空间。时间复杂度：1) 查找成功时的平均查

6、找长度 设表中各记录查找概率相等 ASLs(n)=(1+2+ . +n)/n =(n+1)/22)查找不成功时的查找长度 ASLf =n+1顺序查找的性能分析19n个数存在一维数组A1.n中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度ASL不同。 练习:判断对错查找概率相等时，ASL相同；查找概率不等时，如果从前向后查找，则按查找概率由小到大排列的顺序表其ASL要比无排列的顺序表ASL小。 20 上述顺序查找表的查找算法简单， 但平均查找长度较大，特别不适用于表长较大的查找表。二、有序查找表 若以有序表表示静态查找表，则查找过程可以基于“折半”进行。21lowhighmid 1

7、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+122 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找701 2 3

8、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+1231 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 92lowhighmid直至lowhigh时，查找失

9、败24int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置区间初值 while (low data.key进行比较： 若key等于T-data.key，则查找成功，返回根结点地址； 若key小于T-data.key，则进一步查找左子树； 若key大于T-data.key，则进一步查找右子树。【算法思想】41BSTree SearchBST(BSTree T,KeyType key) if( (!T) | key=T-data.key ) return T; else if (key data.key)

10、 return SearchBST( T-lchild, key); else return SearchBST( T-rchild, key); / SearchBST【算法描述】T为空树，查找不成功，返回空指针key和树T的根节点关键字相等，查找成功，返回根节点指针T42为方便插入操作，需要在查找时增设指针1、增设指针 p 指向查找路径上访问的最后一个结点2、增设指针 f 指向当前查找过程中树T的双亲3、插入操作在查找不成功时进行，所以在查找成功时返回true，查找不成功时返回false改写的算法描述 P228 算法9.5（b）二叉排序树的操作插入根据动态查找表的定义，“插入”操作在查找不

11、成功时才进行4330201040352523fT设 key = 48fTfT22pfTfTTTTfffp插入的元素一定是P的左孩子或右孩子44二叉排序树的操作插入插入的元素一定在叶结点上若二叉排序树为空，则插入结点应为根结点否则，继续在其左、右子树上查找树中已有，不再插入树中没有，查找直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子45Status Insert BST(BiTree &T, ElemType e ) / 当二叉排序树中不存在关键字等于 e.key 的 / 数据元素时，插入元素值为 e 的结点，并返 / 回 TRUE; 否则，不进行插入并返回F

12、ALSE if (!SearchBST ( T, e.key, NULL, p ) else return FALSE; / Insert BST 46s = (BiTree) malloc (sizeof (BiTNode); / 为新结点分配空间s-data = e; s-lchild = s-rchild = NULL; if ( !p ) T = s; / 插入 s 为新的根结点else if ( LT(e.key, p-data.key) ) p-lchild = s; / 插入 *s 为 *p 的左孩子else p-rchild = s; / 插入 *s 为 *p 的右孩子retu

13、rn TRUE; / 插入成功47 10， 18， 3， 8， 12， 2， 7 10101810183101838101838121018381221018381227从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树二叉排序树的操作生成二叉排序树48不同插入次序的序列生成不同形态的二叉排序树4024551237122437405540，24，12，37，5512，24，37，40，55二叉排序树的操作生成49（1）被删除的结点是叶子；（2）被删除的结点只有左子树或者只有右子树；（3）被删除的结点既有左子树，也有右子树。4二叉排序树的删除算法可分三种情况讨论： 和插入相反，删除

14、在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。5050308020908540358832（1）被删除的结点是叶子结点例如:被删关键字 = 2088其双亲结点中相应指针域的值改为“空”5150308020908540358832（2）被删除的结点只有左子树或者只有右子树 其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。被删关键字 = 40805250308020908540358832（3）被删除的结点既有左子树，也有右子树4040以其前驱替代之，然后再删除该前驱结点被删结点前驱结点被删关键字 = 5053第i层结点需比较i次。在等概

15、率的前提下，上述两图的平均查找长度为：40245512371224374055查找的性能分析54平均查找长度和二叉树的形态有关，即，最好：log2n（形态匀称，与二分查找的判定树相似）最坏: （n+1)/2（单支树）查找的性能分析4024551237122437405555问题：如何提高二叉排序树的查找效率？尽量让二叉树的形状均衡左、右子树是平衡二叉树；所有结点的左、右子树深度之差的绝对值 1平衡二叉树平衡因子:该结点左子树与右子树的高度差56 平衡二叉树（AVL树）是二叉查找树的另一种形式，其特点为： 树中每个结点的左、右子树深度之差的绝对值不大于1 。例如:548254821是平衡树不是平

16、衡树57(a) 平衡树 (b) 不平衡树练习：判断下列二叉树是否AVL树？00011-1-120001-1对于一棵有n个结点的AVL树，其高度保持在O(log2n)数量级，ASL也保持在O(log2n)量级。58 构造二叉平衡（查找）树的方法是：在插入过程中，采用平衡旋转技术。例如:依次插入的关键字为5, 4, 2, 8, 65424258665842向右旋转一次先向右旋转再向左旋转59如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。LL平衡旋转RR平衡旋转LR平衡旋转RL平衡旋转保证二叉排序树的次序不变60若在A的左

17、子树的左子树上插入结点，使A的平衡因子从1增加至2，需要进行一次顺时针旋转。(以B为旋转轴）ABCABC若在A的右子树的右子树上插入结点，使A的平衡因子从-1增加至-2，需要进行一次逆时针旋转。(以B为旋转轴）2）RR平衡旋转：ABCABC1）LL平衡旋转：61若在A的右子树的左子树上插入结点，使A的平衡因子从-1增加至-2，需要先进行顺时针旋转，再逆时针旋转。(以插入的结点C为旋转轴）4）RL平衡旋转：ABCABCABC若在A的左子树的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转。(以插入的结点C为旋转轴）ABCABCABC3）LR平衡旋转：6201303

18、7024练习：请将下面序列构成一棵平衡二叉排序树 （ 13，24，37，90，53）013037-113024-124-213需要RR平衡旋转(绕B逆转，B为根）090-124-137053190-237需要RL平衡旋转(绕C先顺后逆）037090053037090053 63 在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡 树的深度。平衡树的查找性能分析： 问：含 n 个关键字的二叉平衡树可能达到的最大深度是多少？64n = 0空树最大深度为 0n = 1最大深度为 1n = 2最大深度为 2n = 4最大深度为 3n = 7最大深度为 4

19、先看几个具体情况:65反过来问，深度为 h 的二叉平衡树中所含结点的最小值 Nh 是多少？h = 0N0 = 0h = 1h = 2h = 3一般情况下N1 = 1N2 = 2N3 = 4Nh = Nh-1 + Nh-2 + 1利用归纳法可证得Nh = Fh+2 - 1 因此，在二叉平衡树上进行查找时，查找过程中和给定值进行比较的关键字的个数和 log(n) 相当。 总之，含有 n 个结点的二叉平衡树能达到的最大深度 hn = log(5 (n+1) - 2。 66 一、哈希表是什么？二、哈希函数的构造方法 三、处理冲突的方法 四、哈希表的查找 五、哈希表的删除操作9.3 哈 希 表67前述查

20、找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系，一、哈希表是什么？查找的效率取决于和给定值进行比较的关键字个数。用这类方法表示的查找表，其平均查找长度都不为零。对于频繁使用的查找表，希望 ASL = 0。只有一个办法：预先知道所查关键字在表中的位置 即，要求：记录在表中位置和其关键字之间存在一种确定的关系。68若以下标为000 999 的顺序表表示之。例如：为每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围为 xx000 xx999 (前两位为年份)。则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查

21、关键字。69基本思想：记录的存储位置与关键字之间存在对应关系，Loc(i)=H(key) 优点：查找速度极快O(1),查找效率与元素个数n无关哈希函数关键字集合存储地址集合hash70数据元素序列(14，23，39，9，25，11)，若规定每个元素k的存储地址H（k）k，请画出存储结构图。14119内容地址3925242314119232539例271根据哈希函数H（k）k 查找key=9,则访问H(9)=9号地址，若内容为9则成功；若查不到，则返回一个特殊值，如空指针或空记录。 如何查找14119内容地址392524231411923253972哈希方法(杂凑法)选取某个函数，依该函数按关键

22、字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比，确定查找是否成功。哈希函数(杂凑函数)：哈希方法中使用的转换函数有关术语73冲 突：不同的关键码映射到同一个哈希地址哈希表(杂凑表)：按上述思想构造的表有关术语14119内容地址3925242314119232539同义词：具有相同函数值的两个关键字key1key2，但H(key1)=H(key2)74（14，23，39，9，25，11）哈希函数：H(k)=k mod 72539239146个元素用7个地址应该足够!H(14)=14%7=011H(25)=25%7=4H(11)=11%7

23、=4同义词有冲突 0 1 2 3 4 5 6冲突现象举例75冲突是不可能避免的如何减少冲突构造好的哈希函数制定一个好的解决冲突方案76哈希函数的构造方法根据元素集合的特性构造地址空间尽量小均匀直接定址法 数字分析法平方取中法折叠法除留余数法随机数法 77Hash(key) = akey + b (a、b为常数)优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突。缺点：要占用连续地址空间，空间效率低。 直接定址法 例： 100，300，500，700，800，900， 哈希函数Hash(key)=key/1000 1 2 3 4 5 6 7 8 9900800700500300100此

24、法仅适合于：地址集合的大小 = = 关键字集合的大小78除留余数法 设定哈希函数为: H(key) = key MOD p 其中， pm (表长) 并且 p 应为不大于 m 的素数 或是不含 20 以下的质因子79 给定一组关键字为：12, 39, 18, 24, 33, 21，若取 p=9, 则他们对应的哈希函数值将为： 3, 3, 0, 6, 6, 3例如：为什么要对 p 加限制？ 可见，若 p 中含质因子 3， 则所有含质因子 3 的关键字均映射到“3 的倍数”的地址上，从而增加了“冲突”的可能。80三、处理冲突的方法 “处理冲突” 的实际含义是：为产生冲突的地址寻找下一个哈希地址。1.

25、 开放定址法2. 链地址法81基本思想：有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。 1.开放定址法（开地址法）线性探测法二次探测法伪随机探测法82Hi=(Hash(key)+di) mod m ( 1i m ) 其中：m为哈希表长度 di 为增量序列 1，2，m-1，且di=i一旦冲突，就找下一个空地址存入线性探测法83关键码集为 47，7，29，11，16，92，22，8，3，设：哈希表表长为m=11； 哈希函数为Hash(key)=key mod 11 0 1 2 3 4 5 6 7 8 9 10477 291116922283 47、7

26、、11、16、92没有冲突 Hash(29)=7，有冲突，由H1=(Hash(29)+1) mod 11=8，哈希地址8为空，因此将29存入 3 连续移动了两次线性探测法84线性探测法的特点优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素。缺点：可能使第i个哈希地址的同义词存入第i+1个地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，产生“聚集”现象，降低查找效率。解决方案：二次探测法85二次探测法关键码集为 47，7，29，11，16，92，22，8，3，设： 哈希函数为Hash(key)=key mod 11 Hi=(Hash(key)di)

27、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，找到空的哈希地址，存入。 86伪随机探测法Hi=(Hash(key)+di) mod m ( 1i m ) 其中：m为哈希表长度 di 为随机数87将所有哈希地址相同的记录都链接在同一链表中。 2. 链地址法0123456140136198223116855ASL=(61+22+3)/9=13/9例如:同前例的关键字，哈希函数为 H(key)=key MOD 788哈希表的查找给定k值计算H(k)此地