数据结构总复习ppt课件

《数据结构总复习ppt课件》由会员分享，可在线阅读，更多相关《数据结构总复习ppt课件（104页珍藏版）》请在金锄头文库上搜索。

1、第九章第九章查找查找9.1.1 查找表找表9.1 概述概述 查找表找表Search Table：是由同一：是由同一类型的数据元素或型的数据元素或记录构构成的集合。成的集合。 对查找表找表经常常进展的操作通常有：展的操作通常有：1查询某个某个“特定的数据元素能否在特定的数据元素能否在查找表中；找表中；2检索某个索某个“特定的数据元素的各种属性；特定的数据元素的各种属性；3在在查找表中插入一个数据元素；找表中插入一个数据元素；4从从查找表中找表中删去某个数据元素。去某个数据元素。 静静态查找表找表Static Search Table：只：只对查找表作找表作“查找操作的找操作的一一类查找表。找表。

2、 动态查找表找表Dynamic Search Table：对查找表不找表不仅作作“查找操找操作，在作，在查找找过程中程中还同同时插入插入查找表中不存在的数据元素，或者从找表中不存在的数据元素，或者从查找找表中表中删除已存在的某个数据元素的一除已存在的某个数据元素的一类查找表。找表。9.1.2 相关相关术语 关关键字字Key：是数据元素或：是数据元素或记录中某个数据中某个数据项的的值，用，用它可以它可以标识识别一个数据元素或一个数据元素或记录。 主关主关键字字Primary Key：可以独一的：可以独一的标识一个建立的关一个建立的关键字。字。次关次关键字字Secondary Key：用以：用以识

3、别假假设干干记录的关的关键字。字。 查找找Searching：根据：根据给定的某个定的某个值，在，在查找表中确定一个其找表中确定一个其关关键字等于字等于给定定值的的记录或数据元素。或数据元素。 查找找胜利：利：查找表中存在关找表中存在关键字等于字等于给定定值的的记录。此。此时查找的找的结果果为给出整个出整个记录的信息，或指示的信息，或指示该记录在在查找表中的位置。找表中的位置。 查找失找失败：查找表中不存在关找表中不存在关键字等于字等于给定定值的的记录。此。此时查找找的的结果可果可给出一个出一个“空空记录或或“空指空指针。2查找操作的性能分析找操作的性能分析 衡量衡量查找算法好坏的根据：其关找

4、算法好坏的根据：其关键字和字和给定定值进展展过比比较的的记录个个数的平均数的平均值。 平均平均查找找长度度Average Search Length：为确定确定记录在在查找表中找表中的位置，需和的位置，需和给定定值进展比展比较的关的关键字个数的期望字个数的期望值，称，称为查找算法在找算法在查找找胜利利时的平均的平均查找找长度。度。 对于含有于含有n个个记录的表，的表，查找找胜利利时的平均的平均查找找长度度为： 91 其中：其中：Pi为查为查找表中找表中查查找第找第i个个记录记录的概率，且的概率，且；Ci为为找到表中其关找到表中其关键字与给定值相等的第键字与给定值相等的第i个记录时，和给定值已进

5、展过比较的关键字个数。个记录时，和给定值已进展过比较的关键字个数。 查找算法的平均找算法的平均查找找长度度 查找找胜利利时的平均的平均查找找长度度 查找不找不胜利利时的平均的平均查找找长度度9.2.2 顺序表的序表的查找找1顺序存序存储构造的构造的类型定型定义 typedef struct ElemType *elem;/数据元素存数据元素存储空空间基址，建表基址，建表时按按/实践践长度分配，度分配，0号号单元留空元留空int length; /表表长度度 SSTable2顺序序查找的找的实现 顺序序查找找Sequential Search的的查找找过程程为：从表中最后一个：从表中最后一个记录

6、开开始，逐个始，逐个进展展记录的关的关键字和字和给定定值的比的比较，假，假设某个某个记录的关的关键字和字和给定定值比比较相等，那么相等，那么查找找胜利，找到所利，找到所查记录；反之，假；反之，假设直至第一个直至第一个记录，其关，其关键字和字和给定定值比比较都不等，那么都不等，那么阐明表中没有所明表中没有所查记录，查找不找不胜利。利。 int Search_Seq (SSTable ST, KeyType key) /在在顺顺序表序表ST中中顺顺序序查查找其关找其关键键字等于字等于key的数据元素。的数据元素。/假假设设找到，那么函数找到，那么函数值为该值为该元素在表中的位置，否那么元素在表中的

7、位置，否那么为为0。ST.elem0.key = key;/“哨兵哨兵for (i = ST.length; !EQ(ST.elemi.key, key); i);/从后往前找从后往前找return i;/找不到找不到时时i为为0 / Search_Seq算法算法9.1如下：如下：i例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找6464监视哨iiii比较次数=5比较次数：查找第n个元素： 1查找第n-1个元素：2.查找第1个元素： n查找第i个元素： n+1-i查找失败： n+1lP217 监视哨的作用3性能分析性能分析

8、 假假设nST.length，那么，那么顺序序查找的平均找的平均长度度为：ASL = nP1 + (n1)P2 + + 2Pn-1 + Pn 只思索只思索查查找找胜胜利利时时的情况的情况在在顺序序查找的找的过程中，式程中，式91中中Ci取决于所取决于所查记录在表中的位置。在表中的位置。 假假设查找每个找每个记录的概率相等，即的概率相等，即 Pi1/n。那么在等概率情况下。那么在等概率情况下顺序序查找的平均找的平均查找找长度度为： 思索思索查查找找胜胜利和利和查查找不找不胜胜利利时时的情况的情况 顺序序查找中，不找中，不论给定定值key为何何值，查找不找不胜利利时和和给定定值进展比展比较的关的关

9、键字个数均字个数均为n1。 假假设查找找胜利与不利与不胜利的能利的能够性一性一样，对每个每个记录的的查找概率也相等，那么找概率也相等，那么Pi1/(2n)，此，此时顺序序查找的平均找的平均查找找长度度为： 缺陷：平均缺陷：平均查找找长度度较大，特大，特别是当是当n很大很大时，查找效率找效率较低。低。4顺序序查找算法的特点找算法的特点 优点：算法点：算法简单且且顺应面广。它面广。它对表的构造无任何要求，无表的构造无任何要求，无论记录能否按关能否按关键字有序均可运用。字有序均可运用。9.2.3 有序表的有序表的查找找1有序表有序表查找的找的实现 折半折半查找找Binary Search的的查找找过

10、程：先程：先选定待定待查记录所在范所在范围区区间，然后逐，然后逐渐减少范减少范围直到找到或找不到直到找到或找不到该记录为止。止。特点特点:查找找过程：每次将待程：每次将待查记录所在区所在区间减少一半减少一半适用条件：采用适用条件：采用顺序存序存储构造的有序表构造的有序表算法算法实现:设表表长为n，low、high和和mid分分别指向待指向待查元素所在区元素所在区间的上界、下界和中点的上界、下界和中点,k为给定定值初始初始时，令，令low=1,high=n,mid=(low+high)/2 让k与与mid指向的指向的记录比比较假假设k=rmid.key，查找找胜利利假假设krmid.key，那么

11、，那么low=mid+1反复上述操作，直至反复上述操作，直至lowhigh时，查找失找失败 int Search_Bin (SSTable ST, KeyType key) /在有序表在有序表ST中折半中折半查查找其关找其关键键字等于字等于key的数据元素。的数据元素。/假假设设找到，那么函数找到，那么函数值为该值为该元素在表中的位置，否那么元素在表中的位置，否那么为为0。low = 1;/置区置区间间初初值值high = ST.length;/low和和high分分别别指示待指示待查查元素所在范元素所在范围围的下界和上界的下界和上界while (low = high) mid = (low

12、+ high) / 2;/mid指示区指示区间间的中的中间间位置位置 if (EQ(key, ST.elemmid.key)/找到待找到待查查元素元素return mid; else if (LT(key, ST.elemmid.key)/继续继续在前半区在前半区间进间进展展查查找找high = mid1; else low = mid + 1;/继续继续在后半区在后半区间进间进展展查查找找 / whilereturn 0; / Search_Bin算法算法9.2如下：如下：l算法描画lowhighmid例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64

13、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 92lowhighmidCh7_2.c例 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

14、10 115 13 19 21 37 56 64 75 80 88 92low highmid1 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 92lowhigh1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92l二分查找实现时可以用链表吗?3性能分析性能分析查查找算法的断定找算法的断定树树断定断定树：描画：描画查找找过程的二叉程的二叉树。 断定树中圆形结点

15、为内部结点；方形结点为外部结点由内部结点的空指针域链接。树中每个圆形结点标识表中一个记录，结点中的值为该记录在表中的位置。方形结点中的值v为：第i结点的值 v 第i1结点的值；假设i结点为第1个结点那么v 最后一个结点的值。多不超越树的深度，而具有多不超越树的深度，而具有n个结点的断定树的深度为个结点的断定树的深度为 ，所以，所以， 显然，折半查找法在查找胜利或不胜利时进展比较的关键字个数最显然，折半查找法在查找胜利或不胜利时进展比较的关键字个数最折半查找法在查找胜利时和给定值进展比较的关键字个数至多为折半查找法在查找胜利时和给定值进展比较的关键字个数至多为 。 例如，上述例如，上述11个元素

16、的表的例子。个元素的表的例子。查找找21的的过程如程如红线所示，所示，查找找85的的过程如程如蓝线所示。所示。图9.1 断定断定树和和查找找21(红线)，85(蓝线)的的过程程6391471025811-13-46-79-101-22-34-55-67-88-910-1111-折半折半查查找的平均找的平均查查找找长长度度 假定有序表的假定有序表的长度度n2h1反之，反之，hlog2(n+1)，那么描画折，那么描画折半半查找的断定找的断定树是深度是深度为h的的满二叉二叉树。假。假设表中每个表中每个记录的的查找概率相找概率相等等(Pi = 1/n)，那么，那么查找找胜利利时折半折半查找的平均找的平

17、均查找找长度：度：对恣意的恣意的n，当，当n较大大(n50)时，可有以下近似，可有以下近似结果：果：4折半折半查找算法的特点找算法的特点 特点：只适用于有序表，且限于特点：只适用于有序表，且限于顺序存序存储构造构造对线性性链表无法表无法进展展折半折半查找。找。 9.2.4 索引索引顺序表的序表的查找找1分分块查找找 分分块查找又称索引找又称索引顺序序查找，找，这是是顺序序查找的一种改良方法。在此找的一种改良方法。在此查找法中，除表本身以外，尚需建立一个找法中，除表本身以外，尚需建立一个“索引表。如下例所示。索引表。如下例所示。查找找过程：将表分成几程：将表分成几块，块内无序，内无序，块间有序；

18、先确定待有序；先确定待查记录所在所在块，再在，再在块内内查找找适用条件：分适用条件：分块有序表有序表1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表查38最大关键字起始地址 分分块有序：即后一个子表中的一切有序：即后一个子表中的一切记录的关的关键字均大于字均大于前一个子表中的最大关前一个子表中的最大关键字。字。 分分块查找的算法思想：找的算法思想： 确定待确定待查记录所在的所在的块子表；子表； 在在块中中顺序序查找找2性

19、能分析性能分析分分块查找的平均找的平均查找找长度度为： 其中：其中：Lb为查找索引表确定所在找索引表确定所在块的平均的平均查找找长度，度，Lw为在在块中中查找元素的找元素的平均平均查找找长度。度。ASLbsLbLw用用顺顺序序查查找确定所在找确定所在块块；又假定表中每个记录的查找概率相等，那么每；又假定表中每个记录的查找概率相等，那么每 普通情况下，为进展分块查找，可以将长度为普通情况下，为进展分块查找，可以将长度为n的表均匀地分成的表均匀地分成b块，每块，每块含有块含有s个记录，即个记录，即块查找的概率为块查找的概率为1/b，块中每个记录的查找概率为，块中每个记录的查找概率为1/s。那么分块

20、查找的平均长。那么分块查找的平均长度为：度为：用折半用折半查查找确定所在找确定所在块块ASL平均查找长度 最大最小两者之间表构造有序表、无序表 有序表分块有序表存储构造顺序存储构造线性链表顺序存储构造 顺序存储构造线性链表查找方法比较顺序查找折半查找分块查找 特点：表构造本身是在特点：表构造本身是在查找找过程中程中动态生成的，即生成的，即对于于给定定值key，假假设表中存在其关表中存在其关键字等于字等于key的的记录，那么，那么查找找胜利前往，否那么插入关利前往，否那么插入关键字字等于等于key的的记录。动态查找表的特点找表的特点9.3.2 二叉排序二叉排序树和平衡二叉和平衡二叉树1二叉排序二

21、叉排序树 二叉排序二叉排序树Binary Sort Tree：它或者是一棵空：它或者是一棵空树；或者是具有以下性或者是具有以下性质的二叉的二叉树： 1假假设它的左子它的左子树不空，那么左子不空，那么左子树上一切上一切结点的点的值均小于它的根均小于它的根结点的点的值； 2假假设它的右子它的右子树不空，那么右子不空，那么右子树上一切上一切结点的点的值均大于它的根均大于它的根结点的点的值； 3它的左、右子它的左、右子树也分也分别为二叉排序二叉排序树。 定定义义 图图形表示形表示 45125333710024786190图9.3 二叉排序二叉排序树例如例如(a) 二叉排序二叉排序树树的的查查找找 算法

22、思想：二叉排序算法思想：二叉排序树又称二叉又称二叉查找找树，当二叉排序，当二叉排序树不空不空时，首，首先将先将给定定值和根和根结点的关点的关键字比字比较，假，假设相等，那么相等，那么查找找胜利，否那么将根据利，否那么将根据给定定值和根和根结点的关点的关键字之字之间的大小关系，分的大小关系，分别在左子在左子树或右子或右子树上上继续进展展查找。找。算法算法实现：取二叉：取二叉链表作表作为二叉排序二叉排序树的存的存储构造。构造。 BiTree SearchBST (BiTree T, KeyType key) /在根指在根指针针T所指二叉排序所指二叉排序树树中中递归递归地地查查找某关找某关键键字等于

23、字等于key的数据元素，的数据元素，/假假设查设查找找胜胜利，那么前往指向利，那么前往指向该该数据元素数据元素结结点的指点的指针针，否那么前往空指，否那么前往空指针针。if (!T) | | EQ(key, Tdata.key)/查查找找终终了了return (T);else if (LT(key, Tdata.key)/在左子在左子树树中中继续查继续查找找return (SearchBST (Tlchild, key);else return (SearchBST (Trchild, key);/在右子在右子树树中中继续查继续查找找 / SearchBST算法算法9.3(a)如下：如下：二叉

24、排序二叉排序树树的插入和的插入和删删除除1插入算法插入算法i算法思想：根据二叉排序算法思想：根据二叉排序树树的特点，易知，新插入的特点，易知，新插入的的结结点一定是一个新添加的叶子点一定是一个新添加的叶子结结点，并且是点，并且是查查找不找不胜胜利利时查时查找途径上找途径上访问访问的最后一个的最后一个结结点的左孩子或右点的左孩子或右孩子。孩子。 ii算法算法实现实现：为为了在了在查查找不找不胜胜利利时时前往新前往新结结点的插点的插入位置，将上述算法算法入位置，将上述算法算法9.3(a)修正修正为为9.3(b)。插入算。插入算法如算法法如算法9.4所示。所示。 二叉排序二叉排序树树的插入和的插入和

25、删删除除1插入算法插入算法 Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p) /在根指在根指针针T所指二叉排序所指二叉排序树树中中递归递归地地查查找某关找某关键键字等于字等于key的数据元素，假的数据元素，假设设/查查找找胜胜利，那么指利，那么指针针p指向指向该该数据元素数据元素结结点，并前往点，并前往TRUE，否那么指，否那么指针针p指指向向/查查找途径上找途径上访问访问的最后一个的最后一个结结点并前往点并前往FALSE，指，指针针f指向指向T的双的双亲亲，其初，其初/始始调调用用值为值为NULL。if (!T) p

26、= f; return FALSE;/查查找不找不胜胜利利else if EQ(key, Tdata.key) p = T; return TRUE; /查查找找胜胜利利else if LT(key, Tdata.key) /在左子在左子树树中中继续查继续查找找 return (SearchBST (Tlchild, key, T, p); else return (SearchBST (Trchild, key, T, p); /在右子在右子树树中中继续查继续查找找 / SearchBST算法算法9.3(b)如下：如下： Status InsertBST (BiTree T, ElemTyp

27、e e) /当二叉排序树T中不存在关键字等于e.key的数据元素时，插入e并/前往TRUE，否那么前往FALSE。if (!SearchBST (T, e.key, NULL, p) /查找不胜利s = (BiTree) malloc (sizeof (BiTree);sdata = e;slchild = srchild = NULL;if (!p)T = s;/被插结点*s为新的根结点else if LT(e.key, pdata.key)/被插结点*s为左孩子plchild = s;else prchild = s;/被插结点*s为右孩子return TRUE;else return F

28、ALSE;/树中已有关键字一样的结点 / InsertBST算法算法9.4如下：如下：iii例子例子 例如，从空树出发，经过一系列的查找插入操作之后，可生成一棵二叉树。设查找的关键字序列为45, 24, 53, 45, 12, 24, 90，那么删除的二叉排序树如图9.4所示。 45 24 53 12 90 45 24 53 12 45 24 53 45 24 45 (a)(b)(c)(d)(e)(f)图9.4二叉排序二叉排序树的构造的构造过程程二叉排序树查找的性能分析二叉排序树查找的性能分析 在二叉排序树查找中，胜利的查找次数不会超越二叉树的深度，而具有n个结点的二叉排序树的深度，最好为lo

29、g2n，最坏为n。因此，二叉排序树查找的最好时间复杂度为O(log2n)，最坏的时间复杂度为O(n)，普通情形下，其时间复杂度大致可看成O(log2n)，比顺序查找效率要好，但比二分查找要差。2平衡二叉平衡二叉树定定义义 平衡二叉平衡二叉树Balanced Binary Tree 或或Height-Balanced Tree又称又称AVL树。它或者是一棵空。它或者是一棵空树，或者是具有以下性，或者是具有以下性质的二叉的二叉树：它的左子：它的左子树和右子和右子树都是平衡二叉都是平衡二叉树，且左子，且左子树和右子和右子树的深度之差的的深度之差的绝对值不不超越超越1。 平衡因子平衡因子BFBalan

30、ce Factor：二叉：二叉树上上结点的左子点的左子树的深度减去的深度减去它的右子它的右子树的深度的的深度的值。由平衡二叉由平衡二叉树的定的定义易易知，平衡二叉知，平衡二叉树上一切上一切结点的平衡因子只能点的平衡因子只能够 是是1、0和和1。 例如，例如，图9.6(a)所示所示为两棵平衡二叉两棵平衡二叉树，而，而图9.6(b)为两棵不平衡二叉两棵不平衡二叉树，结点中的点中的值为该结点点的平衡因子的平衡因子图图形表示形表示(a) 平衡二叉平衡二叉树树 1 1 0 0 -1 1 -1 0 1 0 0 平衡平衡树查树查找的分析找的分析 平衡二叉平衡二叉树本身就是一棵二叉排序本身就是一棵二叉排序树，

31、故它的，故它的查找与找与二叉排序二叉排序树完全一完全一样。但它的。但它的查找找 性能性能优于二叉排序于二叉排序树，不像二叉排序，不像二叉排序树一一样，会出，会出现最坏的最坏的时间复复杂度度O(n)，它的，它的时间复复杂度与二叉排序度与二叉排序树的最好的最好时间复复杂一一样，都，都为O(log2n)。9.4 哈希表哈希表9.4.1 定定义 哈希哈希Hash函数：在函数：在记录的存的存储位置和它的关位置和它的关键字字之之间建立的一个确定的建立的一个确定的对应关系关系f，使每个关，使每个关键字和构字和构造中一个独一的存造中一个独一的存储位置相位置相对应。称。称这个个对应关系关系f为哈希函数。哈希函数

32、。根本思想：在根本思想：在记录的存的存储地址和它的关地址和它的关键字之字之间建立建立一个确定的一个确定的对应关系；关系；这样，不，不经过比比较，一次存取，一次存取就能得到所就能得到所查元素的元素的查找方法找方法关键字集合存储地址集合hashl哈希表哈希表运用哈希函数，由运用哈希函数，由记录的关的关键字确字确定定记录在表中的地址，并将在表中的地址，并将记录放入此地址，放入此地址，这样构成的表叫构成的表叫l哈希哈希查找找又叫散列又叫散列查找，利用哈希函数找，利用哈希函数进展展查找的找的过程叫程叫例 30个地域的各民族人口统计表编号 地域别 总人口 汉族 回族.1 北京2 上海.以编号作关键字，构造

33、哈希函数：H(key)=keyH(1)=1H(2)=2以地域别作关键字，取地域称号第一个拼音字母的序号作哈希函数：H()=2 H(Shanghai)=19 H(Shenyang)=19从例子可从例子可见： 哈希函数只是一种映象，所以哈希函数的哈希函数只是一种映象，所以哈希函数的设定很灵定很灵敏，只需使任何关敏，只需使任何关键字的哈希函数字的哈希函数值都落在表都落在表长允允许的的范范围之内即可之内即可冲突：冲突：key1key2，但，但H(key1)=H(key2)的景象叫的景象叫 同同义词：具有一：具有一样函数函数值的两个关的两个关键字，叫字，叫该哈希函哈希函数的数的哈希函数通常是一种哈希函数

34、通常是一种紧缩映象，所以冲突不可防止，只映象，所以冲突不可防止，只能尽量减少；同能尽量减少；同时，冲突，冲突发生后，生后，应该有有处置冲突的方置冲突的方法法9.4.2 哈希函数的构造哈希函数的构造1直接定址法直接定址法 取关取关键字或关字或关键字的某个字的某个线性函数性函数值为哈希地哈希地址。即：址。即： H(key) = key 或或H(key) = a * key + b其中其中a和和b为常数常数这种哈希函数叫做本身函数。种哈希函数叫做本身函数。2例子例子 例一，有一个从例一，有一个从1岁到到100岁的人口数字的人口数字统计表。表。 地址地址 01 02 03 25 26 27 100 年

35、年龄 1 2 3 25 26 27 人数人数 300 2000 5000 1050 表表9.1直接定址哈希函数例子一直接定址哈希函数例子一 其中，年其中，年龄作作为关关键字，哈希函数取关字，哈希函数取关键字本身。假字本身。假设要要讯问25岁的人有的人有多少，那么只需多少，那么只需查表的第表的第25项即可。即可。例二：有一个解放后出生的人口例二：有一个解放后出生的人口调查表。表。 地址地址 01 02 03 22 年份年份 1949 1950 1951 1970 人数人数 15000 其中，关其中，关键字是年份，哈希函数取关字是年份，哈希函数取关键字加一常数：字加一常数： H(key) = ke

36、y + (1948)。假假设要要查1970年出生的人，那么只需年出生的人，那么只需查第第(19701948)22项即可。即可。表表9.2 直接定址哈希函数例子二直接定址哈希函数例子二 2数字分析法数字分析法 主要思想：假主要思想：假设关关键字是以字是以r为基的数如：以基的数如：以10为基的十基的十进制数，并且哈希表中能制数，并且哈希表中能够出出现的关的关键字字都是事先知道的，那么可取关都是事先知道的，那么可取关键字的假字的假设干位干位组成哈成哈希地址。希地址。 例如，有例如，有80个个记录，其关，其关键字字为8位十位十进制数。制数。假假设哈希表的表哈希表的表长为10010，那么可取两位十，那么

37、可取两位十进制数制数组成哈希地址。成哈希地址。这两位的取法，原那么是使得到的哈两位的取法，原那么是使得到的哈希地址尽量防止希地址尽量防止产生冲突。假生冲突。假设这80个关个关键字中的一字中的一部分如下所列：部分如下所列： 8 1 3 4 6 5 3 28 1 3 7 2 2 4 8 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 78 1 3 5 4 1 5 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5 对关关键字全体的分析：第字全体的分析：第位都是位都是“8 1，第第位只能位只能够取取1、2、3或或4，第，第

38、位只能位只能够取取2、5或或7，因此，因此这4位都不可取。由于中位都不可取。由于中间4位可看成是近位可看成是近乎随机的，因此可取其中恣意两位，或取其中两位乎随机的，因此可取其中恣意两位，或取其中两位与另两位的叠加求和后舍去与另两位的叠加求和后舍去进位作位作为哈希地址。哈希地址。2例子例子 假假设BASIC言言语中允中允许的的标识符符为一个字母，或一一个字母，或一个字母和一个数字。在个字母和一个数字。在计算机内可用两位八算机内可用两位八进制数制数表示字母和数字表示字母和数字.如如图9.11(a)所示。取表示符在所示。取表示符在计算机中的八算机中的八进制数制数为它的关它的关键字。字。A B C Z

39、 0 1 2 901 02 03 32 60 61 62 713平方取中法平方取中法1定定义义 取关取关键键字平方后的中字平方后的中间间几位几位为为哈希地址。取的哈希地址。取的位数由表位数由表长长决决议议。 (a) 字符的八进制表示对照表2例子例子 假假设表表长为51229，那么可取关，那么可取关键字平方后的字平方后的中中间9位二位二进制数制数为哈希地址。例如，哈希地址。例如，图9.11(b)列出了一些列出了一些标识符及它符及它们的哈希地址。的哈希地址。A 0100 0 010000 000I 1100 1 210000 210J 1200 1 440000 440I0 1160 1 3704

40、00 370P1 2061 4 310541 310P2 2062 4 314704 314Q1 2161 4 734741 734Q2 2162 4 741304 741Q3 2163 4 745651 745记录记录 关键字关键字 (关键字关键字)2 哈希地址哈希地址(21729)(b) 标识标识符及其哈希地址符及其哈希地址 图9.11 4折叠法折叠法 折叠法折叠法folding：将关：将关键字分割成位数一字分割成位数一样的几部分最后一部分的位数可以不同，然后取的几部分最后一部分的位数可以不同，然后取这几部分的叠加和舍去几部分的叠加和舍去进位作位作为哈希地址。哈希地址。移位叠加：将分割后的

41、每一部分的最低位移位叠加：将分割后的每一部分的最低位对齐，然，然后相加。后相加。 间界叠加：从一端向另一端沿分割界来回折叠，然界叠加：从一端向另一端沿分割界来回折叠，然后后对齐相加。相加。 运用前提运用前提 :关关键字位数很多，而且关字位数很多，而且关键字中每一位上数字分布字中每一位上数字分布大致均匀大致均匀时。 4折叠法折叠法3例子例子 例如，每一种西文例如，每一种西文图书馆都有一个国都有一个国际规范范图书编号号ISBN，如国如国际规范范图书馆图书编号号0-442-20586-4的哈希地的哈希地址分址分别如如图9.12(a)和和(b)所示。所示。58645864 4220 0224 ) 04

42、 ) 04 10088 6092 H(key) = 0088 H(key) = 6092(a) 移位叠加移位叠加(b) 间间界叠加界叠加图9.12由折叠法求得哈希地址由折叠法求得哈希地址 l(5)除留余数法除留余数法l构造：取关构造：取关键键字被某个不大于哈希表表字被某个不大于哈希表表长长m的数的数p除后所得余数作哈希地址，即除后所得余数作哈希地址，即H(key)=key MOD p，pml特点特点l简单简单、常用，可与上述几种方法、常用，可与上述几种方法结结合运合运用用lp的的选选取很重要；取很重要；p选选的不好，容易的不好，容易产产生生同同义词义词l(6)随机数法随机数法l构造：取关构造：

43、取关键键字的随机函数字的随机函数值值作哈希地作哈希地址，即址，即H(key)=random(key)l适于关适于关键键字字长长度不等的情况度不等的情况9.4.3 处置冲突的方法置冲突的方法 冲突：指由关冲突：指由关键字得到的哈希地址的位置上已存字得到的哈希地址的位置上已存在在记录。 处置冲突：置冲突：为产生冲突的关生冲突的关键字的字的记录找到另一找到另一个个“空的哈希地址。空的哈希地址。l开放定址法开放定址法l方法：当冲突方法：当冲突发生生时，构成一个探，构成一个探查序序列；沿此序列逐个地址探列；沿此序列逐个地址探查，直到找到，直到找到一个空位置开放的地址，将一个空位置开放的地址，将发生冲生冲

44、突的突的记录放到放到该地址中，即地址中，即Hi=(H(key)+di)MOD m，i=1,2,k(km-1)l其中：其中：H(key)哈希函数哈希函数l m哈希表表哈希表表长l di增量序列增量序列l分分类l线性探性探测再散列：再散列：di=1,2,3,m-1l二次探二次探测再散列：再散列：di=1,-1,2,-2,3,k(km/2)l伪随机探随机探测再散列：再散列：di=伪随机数序列随机数序列例 表长为11的哈希表中已填有关键字为17，60，29的记录， H(key)=key MOD 11,现有第4个记录，其关键字为38， 按三种处置冲突的方法，将它填入表中0 1 2 3 4 5 6 7 8

45、 9 1060 17 29(1) H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5+2) MOD 11=7 冲突 H3=(5+3) MOD 11=8 不冲突 38(2) H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5-1) MOD 11=4 不冲突38(3) H(38)=38 MOD 11=5 冲突 设伪随机数序列为9，那么： H1=(5+9) MOD 11=3 不冲突38l再哈希法再哈希法l方法：构造假方法：构造假设干个哈希函数，当干个哈希函数，当发生冲突生冲突时，计算下一算下一个哈希地址，即：个哈

46、希地址，即：Hi=Rhi(key) i=1,2,kl其中：其中：Rhi不同的哈希函数不同的哈希函数l特点：特点：计算算时间添加添加l链地址法地址法l方法：将一切关方法：将一切关键字字为同同义词的的记录存存储在一个在一个单链表中，表中，并用一并用一维数数组存放存放头指指针建立一个公共溢出区建立一个公共溢出区另另设立向量立向量为溢出表。一切关溢出表。一切关键字和根字和根本表中关本表中关键字字为同同义词的的记录，不，不论它它们由哈希函数得到的哈希地址是什么，由哈希函数得到的哈希地址是什么，一旦一旦发生冲突，都填入溢出表。生冲突，都填入溢出表。例 知一组关键字(19,14,23,1,68,20,84,

47、27,55,11,10,79) 哈希函数为：H(key)=key MOD 13, 用链地址法处置冲突0 1 2 3 4 5 6 7 8 9 10 11 12 141277968551984202310119.4.4 哈希表的哈希表的查找及其分析找及其分析1相关相关术语 查找找过程：程：给定定K值，根据造表，根据造表时设定的哈希函数求得哈希地址，定的哈希函数求得哈希地址，假假设表中此位置上没有表中此位置上没有记录，那么，那么查找不找不胜利；利；(2) 否那么比否那么比较关关键字，假字，假设和和给定定值相等，那么相等，那么查找找胜利；利；(3) 否那么根据造表否那么根据造表时设定的定的处置冲突的方

48、法找置冲突的方法找“下下一地址，直至哈希表中某个位置一地址，直至哈希表中某个位置为“空或者表中所空或者表中所填填记录的关的关键字等于字等于给定定值为止。止。9.4.4 哈希表的哈希表的查找及其分析找及其分析1相关相关术语影响影响查找找过程中需和程中需和给定定值进展比展比较的关的关键字的个字的个数的要素数的要素(p260)：1哈希函数哈希函数2冲突冲突处置方法置方法3哈希表的装填因子哈希表的装填因子装填因子：装填因子：其中，其中，标志哈希表的装志哈希表的装满程度。程度。 直直观的看，的看，越小，越小，发生冲突的能生冲突的能够性就越小；反之，性就越小；反之，越大，表中越大，表中已填入的已填入的记录

49、越多，再填越多，再填记录时，发生冲突的能生冲突的能够性就越大，那么性就越大，那么查找找时，给定定值需与之需与之进展比展比较的关的关键字的个数也就越多。字的个数也就越多。 例 知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：H(key)=key MOD 13, 哈希表长为m=16， 设每个记录的查找概率相等(1) 用线性探测再散列处置冲突，即Hi=(H(key)+di) MOD mH(55)=3 冲突，H1=(3+1)MOD16=4 冲突，H2=(3+2)MOD16=5H(79)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)M

50、OD16=3 冲突，H3=(1+3)MOD16=4 冲突，H4=(1+4)MOD16=5 冲突，H5=(1+5)MOD16=6 冲突，H6=(1+6)MOD16=7 冲突，H7=(1+7)MOD16=8 冲突，H8=(1+8)MOD16=90 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15ASL=(1*6+2+3*3+4+9)/12=2.514 1 68 27 55 19 20 84 79 23 11 10H(19)=6H(14)=1H(23)=10H(1)=1 冲突，H1=(1+1) MOD16=2H(68)=3H(20)=7H(84)=6 冲突，H1=(6+1)MO

51、D16=7 冲突，H2=(6+2)MOD16=8H(27)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4H(11)=11H(10)=10 冲突，H1=(10+1)MOD16=11 冲突，H2=(10+2)MOD16=12这个例子要掌握(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)P262 对对于于预预先知道且先知道

52、且规规模不大的关模不大的关键键字集字集, 有有时时可以找到不可以找到不发发生冲突的哈希函数生冲突的哈希函数第十章 内部排序1相关相关术语 假假设含有含有n个个记录的序列的序列为R1, R2, , Rn10 1其相其相应的关的关键字序列字序列为K1, K2, , Kn需确定需确定1, 2, , n的一种的一种陈列列p1, p2, , pn，使其相，使其相应的关的关键字字满足如下的非足如下的非递减或非减或非递增关系增关系10 2即使式即使式101的序列成的序列成为一个按关一个按关键字有序的序列字有序的序列10 3这样一种操作称一种操作称为排序。排序。10.1 概述概述 假假设Ki = Kj(1in

53、, 1jn, ij)(此此时Ki和和Kj是是记录的次关的次关键字字)，且在排序，且在排序前的序列中前的序列中Ri领先于先于Rj即即i L.r2.key，那么将两个那么将两个记录交交换之之;然后比然后比较第二个第二个记录和第三个和第三个记录的关的关键字。依次字。依次类推，直至第推，直至第n-1个个记录和第和第n个个记录的关的关键字字进展展过比比较为止。止。上述上述过程称做第一趟起泡排序，其程称做第一趟起泡排序，其结果使得关果使得关键字最字最大的大的记录被安被安顿到最后一个到最后一个记录的位置上。的位置上。例38 49 65 76 13 27 30 97第一趟38 49 65 13 27 30 7

54、6第二趟38 49 13 27 30 65第三趟38 13 27 30 49第四趟13 27 30 38第五趟13 27 30第六趟49 38 65 97 76 13 27 303849769713972797309713767676273013652765306513134949304927382738303813 27第七趟起泡排序的效率：起泡排序的效率：假假设设初始序列初始序列为为“正序序列，那么只需正序序列，那么只需进进展一趟排展一趟排序，在排序序，在排序过过程中程中进进展展n-1 次关次关键键字字间间的比的比较较，且不挪，且不挪动记录动记录；假假设设初始序列初始序列为为“逆序序列，那

55、么需求逆序序列，那么需求进进展展n-1趟排序，需趟排序，需进进展展次比次比较，并作数量，并作数量级的的记录挪挪动。总的时间复杂度为总的时间复杂度为O(n2)。2快速排序快速排序快速排序快速排序Quick Sort是是对起泡排序的一种改良。起泡排序的一种改良。 主要思想主要思想经过经过一趟排序将待排序一趟排序将待排序记录记录分割成独立的两部分，分割成独立的两部分，其中一部分其中一部分记录记录的关的关键键字均比另一部分字均比另一部分记录记录的关的关键键字小，字小，那么可分那么可分别对这别对这两部分两部分记录继续进记录继续进展排序，以到达展排序，以到达整个序列有序。整个序列有序。 一趟快速排序一趟快

56、速排序 假假设待排序序列待排序序列为L.rs, L.rs+1, , L.rt,首先首先恣意恣意选取一个取一个记录通常可通常可选为第一个关第一个关键字字L.rs作作为枢枢轴.然后按下述原那么重新然后按下述原那么重新陈列其他列其他记录：将一切关：将一切关键字字较它小的它小的记录都安都安顿在它的位置之前，将一切关在它的位置之前，将一切关键字字较它它大的大的记录都安都安顿在它的位置之后。在它的位置之后。由此可以由此可以该“枢枢轴记录最后落的位置最后落的位置i作分界限，将序作分界限，将序列列L.rs, , L.rt分割成两个子序列分割成两个子序列L.rs, L.rs+1, , L.ri1和和L.ri1,

57、 L.ri+2, , L.rt。这个个过程称做一趟快速排序或一次划分。程称做一趟快速排序或一次划分。 例如，以式例如，以式中关键字为例，一趟快速排序的过程如图中关键字为例，一趟快速排序的过程如图10.7(a)所示。所示。进展进展2次交换后次交换后 27 38 97 76 13 65 49jij进展进展3次交换后次交换后 27 38 13 97 76 65 49jii进展进展1次交换后次交换后 27 38 65 97 76 13 49jii进展进展4次交换后次交换后 27 38 13 76 97 65 49jij完成一趟排序完成一趟排序 27 38 13 49 76 97 65 49(a) 一趟

58、快排一趟快排过过程程pivotkey初始关键字初始关键字 49 38 65 97 76 13 27 49jijP275 图10.7初始形状初始形状 49 38 65 97 76 13 27 49 一次划分之后一次划分之后 27 38 13 49 76 97 65 49分分别进展快速排序展快速排序 13 27 38 终了终了 终了终了 49 65 76 9749 65 终了终了 终了了有序序列有序序列 13 27 38 49 49 65 76 97(b) 排序的全排序的全过过程程图10.7 快速排序例如快速排序例如 快速排序算法快速排序算法实现实现 整个快速排序的整个快速排序的过程可程可递归进展

59、。假展。假设待排序列中只需一个待排序列中只需一个记录，显然已有然已有序，否那么序，否那么进展一趟快速排序后再分展一趟快速排序后再分别对分割所得的两个子序列分割所得的两个子序列进展快速排序，展快速排序，如如图10.7(b)所示。所示。 快速排序的平均快速排序的平均时间时间快速排序的平均时间为：快速排序的平均时间为： 其中，其中，n为待排序序列中待排序序列中记录的个数，的个数，k为某个常数。某个常数。10.4 选择排序排序 选择排序排序Selection Sort的根本思想是：的根本思想是：每一趟每一趟n-i+1(i = 1, 2, , n-1) 个个记录中中选取关取关键字最小的字最小的记录作作为

60、有序序列中第有序序列中第i个个记录10.4.1 简单项选择择排序排序1算法算法实现： 一趟一趟简单项选择择排序的操作排序的操作为：经过n-i次次关关键字字间的比的比较，从，从n-i+1个个记录中中选出关出关键字最字最小的小的记录，并和第，并和第i1in个个记录交交换之。之。2简单项选择择排序的改良排序的改良 选择排序的主要操作是排序的主要操作是进展关展关键字字间的比的比较。因。因此改良此改良简单项选择择排序排序应减少减少“比比较。 显然，在然，在n个关个关键字中字中选出最小出最小值，至少，至少进展展n-1次比次比较. 假假设能利用前能利用前n-1次比次比较所得信息，那么可减少以后各所得信息，那

61、么可减少以后各趟趟选择排序中所用的比排序中所用的比较次数。次数。 例如，在例如，在8个运个运发动中决出前中决出前3名至多需求名至多需求11场竞赛，而不是而不是7+6+5=18场竞赛前提：假前提：假设乙乙胜丙，甲丙，甲胜乙，那乙，那么以么以为甲必能甲必能胜丙。丙。 10.4.2 树形形选择排序排序首先对首先对n个记录的关键字进展两两比较个记录的关键字进展两两比较如此反复，直至选出最小关键字的记录为止。如此反复，直至选出最小关键字的记录为止。然后在其中然后在其中 个较小者之间再进展两两比较个较小者之间再进展两两比较 树形选择排序树形选择排序, 又称锦标赛排序又称锦标赛排序 ，是一种按照锦标赛的思想

62、进，是一种按照锦标赛的思想进展选择排序的方法。展选择排序的方法。10.4.2 树形形选择排序排序上述过程可用一棵有上述过程可用一棵有n个叶子结点的完全二叉树表示。个叶子结点的完全二叉树表示。 图10.8(a)中的二叉中的二叉树表示从表示从8个关个关键字中字中选出最小关出最小关键字字的的过程。程。(a) 选选出最小关出最小关键键字字为为13 13 38 13 38 65 13 27 49 38 65 97 76 13 27 49 27 38 27 38 65 76 27 49 38 65 97 76 27 49 输出输出13之后之后 (b) 选选出次小关出次小关键键字字为为27 在在输出最小关出

63、最小关键字之后，字之后，仅需将叶子需将叶子结点中的点中的最小关最小关键字字13改改为“最大最大值，再从下到上开，再从下到上开场比比较38 38 38 65 76 49 38 65 97 76 49 49 49 输出输出13，27之后之后 (c) 选出居第三的关出居第三的关键字字为38 树树形形选择选择排序的排序的时间时间复复杂杂度：由于含有度：由于含有n个个叶子叶子结结点的完全二叉点的完全二叉树树的深度的深度为为那么在那么在树树形形选择选择排序中，除了最小排序中，除了最小关关键键字之外，每字之外，每选择选择一个次小关一个次小关键键字字仅仅需需进进展展 次比次比较较，因此，因此它的它的时间时间复

64、复杂杂度度为为O(nlog2n)。 l堆排序l堆的定义：n个元素的序列(k1,k2,kn)，当且仅当满足以下关系时，称之为堆或(i=1,2,.n/2)kik2ikik2i+1kik2ikik2i+1例 96，83，27，38，11，9 例 13，38，27，50，76，65，49，97962791138831327384965765097可将堆序列看成完全二叉树，那么堆顶元素完全二叉树的根必为序列中n个元素的最小值或最大值l堆排序：将无序序列建成一个堆，得到关键字最小或最大的记录；输出堆顶的最小大值后，使剩余的n-1个元素重又建成一个堆，那么可得到n个元素的次小值；反复执行，得到一个有序序列，

65、这个过程叫l堆排序需处理的两个问题：l如何由一个无序序列建成一个堆？l如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？l第二个问题处理方法挑选l方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进展比较，并与其中小者进展交换；反复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“挑选例13273849657650979727384965765013输出：132749389765765013输出：139749382765765013输出：13 273849502765769713输出：13 276549502738769713输出

66、：13 27 384965502738769713输出：13 27 387665502738499713输出：13 27 38 495065762738499713输出：13 27 38 499765762738495013输出：13 27 38 49 506597762738495013输出：13 27 38 49 509765762738495013输出：13 27 38 49 50 657665972738495013输出：13 27 38 49 50 659765762738495013输出：13 27 38 49 50 65 769765762738495013输出：13 27 38

67、 49 50 65 76 97算法描画l第一个问题处理方法l方法：从无序序列的第n/2个元素即此无序序列对应的完全二叉树的最后一个非终端结点起，至第一个元素止，进展反复挑选例 含8个元素的无序序列49，38，65，97，76，13，27，5049653827137697504965382713765097491338276576509749133827657650971327384965765097P281 图10.12算法描画l算法评价l时间复杂度：最坏情况下T(n)=O(nlogn)l空间复杂度：S(n)=O(1)Ch8_7.cl8.4 归并排序l归并将两个或两个以上的有序表组合成一个新的

68、有序表，叫l2-路归并排序l排序过程l设初始序列含有n个记录，那么可看成n个有序的子序列，每个子序列长度为1l两两合并，得到n/2个长度为2或1的有序子序列l再两两合并，如此反复，直至得到一个长度为n的有序序列为止例初始关键字： 49 38 65 97 76 13 27一趟归并后： 38 49 65 97 13 76 27二趟归并后： 38 49 65 97 13 27 76三趟归并后： 13 27 38 49 65 76 97算法描画l算法评价l时间复杂度：T(n)=O(nlog2n)l空间复杂度：S(n)=O(n)Ch8_9.cl8.5 基数排序l链式基数排序l基数排序：借助“分配和“搜集

69、对单逻辑关键字进展排序的一种方法l链式基数排序：用链表作存储构造的基数排序P284 而实现 基数排序不需求进展记录关键字间的比较例初始形状：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配930063083184505278008109589269一趟搜集：505008109930063269278083184589二趟搜集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f

70、7f8f9二趟分配008109278930063083184505278008109589269一趟搜集：008063083109184269278505589930三趟搜集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配063083269278505589505008109930063269278083184589二趟搜集：算法描画l算法评价l时间复杂度：l分配：T(n)=O(n)l搜集：T(n)=O(rd)lT(n)=O(d(n+rd)l其中：n记录数l rd关键字取值范围 l d关键字数(分配搜集的趟数)l l空间复杂度：

71、S(n)=2rd个队列指针+n个指针域空间Ch8_10.c10.7 各种内部排序方法的比各种内部排序方法的比较讨论 1算法比算法比较综合比合比较本章内本章内讨论的各种内部排序方法，大致有如下的各种内部排序方法，大致有如下结果：果：基数排序基数排序 O(d(n+rd) O(d(n+rd) O(rd)排序方法排序方法 平均时间平均时间 最坏情况最坏情况 辅助存储辅助存储简单排序简单排序 O(n2) O(n2) O(1)快速排序快速排序 O(nlogn) O(n2) O(nlogn)堆排序堆排序 O(nlogn) O(nlogn) O(1)归并排序归并排序 O(nlogn) O(nlogn) O(n) 从上表易知，本章从上表易知，本章讨论的一切排序方法中，没有哪一种是的一切排序方法中，没有哪一种是绝对最最优的。的。在适用在适用时需根据不同情况适中需根据不同情况适中选用，甚至可将多种方法用，甚至可将多种方法结合起来运用。合起来运用。