数据结构课件09

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

2、两类查找表可分为两类:是数据元素（或记录）中某个数据项数据项的值，用以标识标识（识别）一个数据元素（或记录）。关键字关键字 若此关键字可以识别唯一的唯一的一个记录，则称之谓“主关键字主关键字”。 若此关键字能识别若干若干记录，则称之谓“次关键字次关键字”。 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。 查找查找 若查找表中存在这样一个记录，则称“查找成功查找成功”。查找结果； 否则称“查找不成功查找不成功”。查找结果。 由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。 为了提高查找的效率， 需要在查找表中的元素之间人为地 附加某种确定的关系，换句

3、话说， 。如何进行查找？如何进行查找？查找的方法取决于查找表的结构。查找的方法取决于查找表的结构。9.1 静态查找表静态查找表9.2 动态查找树表动态查找树表9.3 哈希表哈希表9.1 静态查找表静态查找表顺序存储结构顺序存储结构链式存储结构链式存储结构顺序表顺序表线性链表线性链表typedef struct / 数据元素存储空间基址，建表时 / 按实际长度分配，0号单元留空 int length; / 表的长度 SSTable;假设静态查找表静态查找表的顺序存储结构顺序存储结构为ElemType *elem;数据元素类型的定义为数据元素类型的定义为:typedef struct keyTyp

4、e key; / 关键字域 / 其它属性域 ElemType ; , TElemType ;9.1.1、顺序查找表、顺序查找表9.1.2、有序查找表、有序查找表9.1.3、静态查找树表、静态查找树表(*)21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elemkkk21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elem21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5

5、6 7 8 9 10 11 ST.LengthST.elem60ikey=64key=6064算法2.6的改进：iiiint Search_Seq(SSTable ST, KeyType key) / 在顺序表ST中顺序查找其关键字等于 / key的数据元素。若找到，则函数值为 / 该元素在表中的位置，否则为0。 for (i=ST.length; -i); / 从后往前找 return i; / 找不到时，i为0 / Search_Seq关键字的平均比较次数关键字的平均比较次数，也称，也称平均搜索长度平均搜索长度ASLASL( (Average Search LengthAverage Se

6、arch Length) )n n：记录的个数：记录的个数pipi：查找第：查找第i i个记录的概率个记录的概率 ( ( 通常认为通常认为pi =1/n )pi =1/n )cici：找到第：找到第i i个记录所需的比较次数个记录所需的比较次数niiicpASL1 空间复杂度：一个辅助空间。空间复杂度：一个辅助空间。 时间复杂度：时间复杂度：1) 查找成功时的查找成功时的 设表中各记录查找概率相等设表中各记录查找概率相等 ASLs(n)=(1+2+ . +n)/n =(n+1)/22)查找不成功时的查找长度查找不成功时的查找长度 ASLf =n+1n n个数存在一维数组个数存在一维数组A1.n

7、A1.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、 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 1 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 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lo

9、whighmid若若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 highmidint Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置区间初值 while (low data = e; s-lchild = s-rchild =

10、 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 的右孩子return TRUE; / 插入成功 10， 18， 3， 8， 12， 2， 7 10101810183101838101838121018381221018381227从空树出发，经过一系列的查找、插入操作之后，从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树可生成一棵二叉排序树不同插入次序的序列生成

11、不同形态的二叉排序树不同插入次序的序列生成不同形态的二叉排序树4024551237122437405540，24，12，37，5512，24，37，40，55 （1）被删除的结点是叶子； （2）被删除的结点只有左子树或者只有右子树； （3）被删除的结点既有左子树，也有右子树。4二叉排序树的删除算法二叉排序树的删除算法可分三种情况讨论： 和插入相反，删除在查找成功查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍仍然保持二叉排序树的特性然保持二叉排序树的特性。50308020908540358832（1）被删除的结点是叶子结点叶子结点例如例如:被删关键字被删关键字 = 2088其双亲结

12、点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空”50308020908540358832（2）被删除的结点只有左子树只有左子树或者只有右子树只有右子树 其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树指向被删除结点的左子树或右子树”。被删关键字被删关键字 = 408050308020908540358832（3）被删除的结点既有左子树，也有右子树既有左子树，也有右子树4040以其前驱替代之，然以其前驱替代之，然后再删除该前驱结点后再删除该前驱结点被删结点前驱结点被删关键字被删关键字 = 50fPLPRPFfp(a) P的左右子树均不空Q

13、LSLCFfp(d) 将原P结点的值改为 S结点的值 ， 删 除原S结 点并将原S的左子树改为 Q的右子树QqCLSPRcSLPRCf(c) 将P的 左子树改为 F的左 子 树 ，将P的右子树改为 S的右子树SCLFcQLSLCFpQqCLPPRcSs(b) S为P的直接前驱第第i i层结点需比较层结点需比较i i次。在等概率的前提下，上述次。在等概率的前提下，上述两图的两图的为：为：)(35/ )54321 ()(2 . 25/ )23221 (11右图左图niiiniiicpcp40245512371224374055平均查找长度和二叉树的形态有关，即，平均查找长度和二叉树的形态有关，即，

14、最好：最好：loglog2 2n n（形态匀称，与二分查找的判定树相似）（形态匀称，与二分查找的判定树相似）最坏最坏: : （n n+1)/2+1)/2（单支树）（单支树）40245512371224374055)( 35/ ) 54321 ()( 2 . 25/ ) 23221 (11右图左图niiiniiicpcp问题：如何提高二叉排序树的查找效率？问题：如何提高二叉排序树的查找效率？尽量让二叉树的形状均衡尽量让二叉树的形状均衡 平衡二叉树（平衡二叉树（AVL树）树）是二叉查找树的另一种形式，其特点为： 树中每个结点的树中每个结点的左、右子树深度左、右子树深度之差的绝对值不大于之差的绝对值

15、不大于1 。例如例如:1RLhh548254821是平衡树是平衡树不是平衡树不是平衡树(a) (a) 平衡树平衡树 (b) (b) 不平衡树不平衡树练习：判断下列二叉树是否练习：判断下列二叉树是否AVLAVL树？树？0 00 00 01 11 1-1-1-1-10 00 00 01 1-1-1v对于一棵有对于一棵有n n个结点的个结点的AVLAVL树，其树，其高度保持在高度保持在O(logO(log2 2n n) )数量级，数量级，ASLASL也保持在也保持在O(logO(log2 2n n) )量级。量级。 构造二叉平衡（查找）树的方法是：在插入过程中，采用平衡旋转技术。在插入过程中，采用平

16、衡旋转技术。例如:依次插入的关键字为5, 4, 2, 8, 65424258665842向右旋转一次先向右旋转再向左旋转如果在一棵如果在一棵AVLAVL树中插入一个新结点，就有可能造树中插入一个新结点，就有可能造成失衡，此时必须成失衡，此时必须重新调整树的结构重新调整树的结构，使之恢复，使之恢复平衡。我们称调整平衡过程为平衡。我们称调整平衡过程为平衡旋转平衡旋转。LLLL平衡旋转平衡旋转RRRR平衡旋转平衡旋转LRLR平衡旋转平衡旋转RLRL平衡旋转平衡旋转保证二叉排序树保证二叉排序树的次序不变的次序不变若在若在A A的的左子树的左子树上插入左子树的左子树上插入结点，使结点，使A A的平衡因子

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

18、的子树的右右子树上插入子树上插入结点，使结点，使A的平衡因子从的平衡因子从1增加至增加至2，需要，需要先进行先进行逆逆时针旋转，再时针旋转，再顺顺时针旋转。时针旋转。(以插入的结点以插入的结点C为旋转轴）为旋转轴）0 013130 037370 02424练习：练习：请将下面序列构成一棵请将下面序列构成一棵平衡二叉排序树平衡二叉排序树 （ 1313，2424，3737，9090，5353）0 013130 03737-1-113130 02424-1-124241313需要需要RR平衡旋转平衡旋转(绕绕B逆转，逆转，B为根）为根）0 09090-1-12424-1-137370 053531

19、190903737需要需要RL平衡旋转平衡旋转(绕绕C先顺后逆）先顺后逆）0 037370 090900 053530 037370 090900 05353 在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数进行比较的关键字的个数不超过平衡 树的深度。平衡树的查找性能分析：平衡树的查找性能分析： 问：含 n 个关键字的二叉平衡树可能达到的最大深度最大深度是多少？n = 0空树空树最大深度为最大深度为 0n = 1最大深度为最大深度为 1n = 2最大深度为最大深度为 2n = 4最大深度为最大深度为 3n = 7最大深度为最大深度为 4反过来问，深度为深

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

21、冲突的方法处理冲突的方法 四、哈希表的查找哈希表的查找 五、哈希表的删除操作哈希表的删除操作9.3 哈哈 希希 表表前述查找表的各种结构结构的共同特点特点：记录在表中的位置位置和它的关键字关键字之间不存在不存在一个确定的关系，查找的效率查找的效率取决于和给定值进行比较进行比较的关键字个数个数。对于频繁使用的查找表，希望 。只有一个办法：预先知道所查关键字在表中的位置例如：为每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围为 xx000 xx999 (前两位为年份)。则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较不需要经过比较便可直接从顺序表中找到待查关键

22、字。 基本思想：基本思想：记录的存储位置与关键字之间存在记录的存储位置与关键字之间存在对应关系，对应关系，Loc(i)=Loc(i)= 优点：优点：查找速度极快查找速度极快O(1),查找效率与元素个数查找效率与元素个数n无关无关关键字关键字集合集合存储地址存储地址集合集合数据元素序列数据元素序列(14(14，2323，3939，9 9，2525，11)11)，若规定每个，若规定每个元素元素k k的存储地址的存储地址H H（k k）k k，请画出存储结构图。，请画出存储结构图。141411119 9内容内容地址地址3939252524242323141411119 9232325253939根据

23、哈希函数根据哈希函数H（k）k 查找查找key=9,key=9,则访问则访问H(9)=9H(9)=9号地址，若内容为号地址，若内容为9 9则成功；则成功；若查不到，则返回一个特殊值，如空指针或空记录。若查不到，则返回一个特殊值，如空指针或空记录。 141411119 9内容内容地址地址3939252524242323141411119 9232325253939哈希方法哈希方法( (杂凑法杂凑法) )选取某个选取某个函数函数，依该函数按关键字计算元素的存储位置，依该函数按关键字计算元素的存储位置，并按此存放；并按此存放；查找时，由同一个函数对给定值查找时，由同一个函数对给定值k k计算地址，计

24、算地址，将将k k与地址与地址单元中元素关键码进行比单元中元素关键码进行比，确定查找是否成功。，确定查找是否成功。哈希函数哈希函数( (杂凑函数杂凑函数) )：哈希方法中使用的哈希方法中使用的转换函数转换函数冲冲 突：突：不同的关键码映射到同一个哈希地址不同的关键码映射到同一个哈希地址哈希表哈希表( (杂凑表杂凑表) )：按上述思想构造的表按上述思想构造的表141411119 9内容内容地址地址3939252524242323141411119 9232325253939同义词：同义词：具有具有相同函数值相同函数值的两个关键字的两个关键字key1 key2，但但H(key1)=H(key2)（

25、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冲突是不可能避免的冲突是不可能避免的构造好的哈希函数构造好的哈希函数制定一个好的解决冲突方案制定一个好的解决冲突方案根据元素集合的特性构造根据元素集合的特性构造地址空间尽量小地址空间尽量小均匀均匀 直接定址法直接定址法 数字分析法数字分析法 平方取中法平方取中法 折叠法折叠法 随机数法随机数法 Hash(key) = akey + b

26、( (a、b为常数为常数) )优点：优点：以关键码以关键码keykey的某个线性函数值为哈希的某个线性函数值为哈希地址，地址，不会产生冲突不会产生冲突。缺点：缺点：要占用连续地址空间，空间效率低。要占用连续地址空间，空间效率低。 例：例： 100，300，500，700，800，900， 哈希函数哈希函数Hash(key)=key/1000 1 2 3 4 5 6 7 8 9900800700500300100此法仅适合于：此法仅适合于：地址集合的大小地址集合的大小 = = 关键字集合的大小关键字集合的大小除留余数法除留余数法 设定哈希函数为设定哈希函数为: H(key) = key MOD

27、p 其中其中， pm ( (表长表长) ) 并且并且 p 应为不大于应为不大于 m 的的 或是不含或是不含 给定一组关键字为：12, 39, 18, 24, 33, 21，若取 p=9, 则他们对应的哈希函数值将为： 3, 3, 0, 6, 6, 3例如：例如：为什么要对 p 加限制？ 可见，若 p 中含质因子 3， 则所有含质则所有含质因子因子 3 的关键字均映射到的关键字均映射到“3 的倍数的倍数”的的地址上地址上，从而增加了“冲突”的可能。 “处理冲突处理冲突” 的实际含义是：为产生冲突的地址寻找下一个寻找下一个哈希地址。1. 开放定址法开放定址法2. 链地址法链地址法基本思想：基本思想

28、：有冲突时就去有冲突时就去寻找下一个空寻找下一个空的哈希地的哈希地址，只要哈希表足够大，空的哈希地址总址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。能找到，并将数据元素存入。 线性探测法线性探测法二次探测法二次探测法伪随机探测法伪随机探测法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； 哈

29、希函数为哈希函数为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存入存入 优点：优点：只要哈希表未被填满，只要哈希表未被填满，保证能找到保证能找到一个空一个空地址单元存放有冲突的元素。地址单元存放有冲突的元素。缺点：缺点：可能使第可能使第i个哈希地址的同义词存入第个哈希地址的同义词存入第i+1个个地址，这样本应存入第地址，这样本应存入第i+

30、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，哈希地址冲突

31、，由，哈希地址冲突，由H1=(Hash(3)+12) mod 11=4，仍然冲突；，仍然冲突；H2=(Hash(3)-12) mod 11=2，找到空的哈希地址，存入。找到空的哈希地址，存入。 Hi=(Hash(key)+di) mod m ( 1i m ) 其中：其中：m为哈希表长度为哈希表长度 di 为随机数为随机数0123456ASL=(61+22+3)/9=13/9例如:同前例的关键字，哈希函数为 H(key)=key MOD 7给定给定k k值值计算计算H(k)H(k)此地址为空此地址为空关键字关键字=k=k查找失败查找失败查找成功查找成功按处理冲突按处理冲突方法计算方法计算HiHiY YN NY YN N给定值与关键字比较给定值与关键字比较已知一组关键字已知一组关键字(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(key)=key MOD 13, H(key)=key MOD 13, 哈希表长为哈希表长为m=16m=16， 设每个记录的查找概率相等设每个记录的查找概率相等(1) (1) 用线性