数据结构总复习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：可以独一的标

3、识一个建立的关键字。：可以独一的标识一个建立的关键字。次关键字次关键字Secondary Key：用以识别假设干记录的关键字。：用以识别假设干记录的关键字。查找查找Searching：根据给定的某个值，在查找表中确定一个其：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。关键字等于给定值的记录或数据元素。查找胜利：查找表中存在关键字等于给定值的记录。此时查找的查找胜利：查找表中存在关键字等于给定值的记录。此时查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置。结果为给出整个记录的信息，或指示该记录在查找表中的位置。查找失败：查找表中不存在关键字等于给定值的记录

4、。此时查找查找失败：查找表中不存在关键字等于给定值的记录。此时查找的结果可给出一个的结果可给出一个“空记录或空记录或“空指针。空指针。2查找操作的性能分析查找操作的性能分析 衡量查找算法好坏的根据：其关键字和给定值进展过比较的记录个衡量查找算法好坏的根据：其关键字和给定值进展过比较的记录个数的平均值。数的平均值。平均查找长度平均查找长度Average Search Length：为确定记录在查找表中：为确定记录在查找表中的位置，需和给定值进展比较的关键字个数的期望值，称为查找算法在的位置，需和给定值进展比较的关键字个数的期望值，称为查找算法在查找胜利时的平均查找长度。查找胜利时的平均查找长度。

5、对于含有对于含有n个记录的表，查找胜利时的平均查找长度为：个记录的表，查找胜利时的平均查找长度为：niiiCPASL191 其中：其中：Pi为查找表中查找第为查找表中查找第i个记录的概率，且个记录的概率，且niiP11；Ci为找到表中其关为找到表中其关键字与给定值相等的第键字与给定值相等的第i个记录时，和给定值已进展过比较的关键字个数。个记录时，和给定值已进展过比较的关键字个数。查找算法的平均查找长度查找算法的平均查找长度 查找胜利时的平均查找长度查找胜利时的平均查找长度 查找不胜利时的平均查找长度查找不胜利时的平均查找长度9.2.2 顺序表的查找顺序表的查找1顺序存储构造的类型定义顺序存储构

6、造的类型定义 typedef struct ElemType *elem;/数据元素存储空间基址，建表时按数据元素存储空间基址，建表时按/实践长度分配，实践长度分配，0号单元留空号单元留空int length;/表长度表长度 SSTable2顺序查找的实现顺序查找的实现 顺序查找顺序查找Sequential Search的查找过程为：从表中最后一个记录开的查找过程为：从表中最后一个记录开始，逐个进展记录的关键字和给定值的比较，假设某个记录的关键字和给定值始，逐个进展记录的关键字和给定值的比较，假设某个记录的关键字和给定值比较相等，那么查找胜利，找到所查记录；反之，假设直至第一个记录，其关键比较

7、相等，那么查找胜利，找到所查记录；反之，假设直至第一个记录，其关键字和给定值比较都不等，那么阐明表中没有所查记录，查找不胜利。字和给定值比较都不等，那么阐明表中没有所查记录，查找不胜利。int Search_Seq(SSTable ST,KeyType key)/在顺序表在顺序表ST中顺序查找其关键字等于中顺序查找其关键字等于key的数据元素。的数据元素。/假设找到，那么函数值为该元素在表中的位置，否那么为假设找到，那么函数值为该元素在表中的位置，否那么为0。ST.elem0.key=key;/“哨兵哨兵for(i=ST.length;!EQ(ST.elemi.key,key);i);/从后往

8、前找从后往前找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性能分析性能分析 假设假设nST.length，那么顺序查找的平均长度为：，那么顺序查找的平均长度为：ASL=nP1+(n1)P2+2Pn-1+Pn niiiSSCPASL1niinn1)1(121

9、nASLSS只思索查找胜利时的情况只思索查找胜利时的情况在顺序查找的过程中，式在顺序查找的过程中，式91中中Ci取决于所查记录在表中的位置。取决于所查记录在表中的位置。假设查找每个记录的概率相等，即假设查找每个记录的概率相等，即 Pi1/n。那么在等概率情况下顺序查。那么在等概率情况下顺序查找的平均查找长度为：找的平均查找长度为：思索查找胜利和查找不胜利时的情况思索查找胜利和查找不胜利时的情况 顺序查找中，不论给定值顺序查找中，不论给定值key为何值，查找不胜利时和给定值进展比较的关为何值，查找不胜利时和给定值进展比较的关键字个数均为键字个数均为n1。假设查找胜利与不胜利的能够性一样，对每个记

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

11、序表查找的实现 折半查找折半查找Binary Search的查找过程：先选定待查记录所在范的查找过程：先选定待查记录所在范围区间，然后逐渐减少范围直到找到或找不到该记录为止。围区间，然后逐渐减少范围直到找到或找不到该记录为止。特点特点:查找过程：每次将待查记录所在区间减少一半查找过程：每次将待查记录所在区间减少一半适用条件：采用顺序存储构造的有序表适用条件：采用顺序存储构造的有序表算法实现算法实现:设表长为设表长为n，low、high和和mid分别指向待查元素所在分别指向待查元素所在区间的上界、下界和中点区间的上界、下界和中点,k为给定值为给定值初始时，令初始时，令low=1,high=n,m

12、id=(low+high)/2 让让k与与mid指向的记录比较指向的记录比较假设假设k=rmid.key，查找胜利，查找胜利假设假设krmid.key，那么，那么low=mid+1反复上述操作，直至反复上述操作，直至lowhigh时，查找失败时，查找失败 int Search_Bin(SSTable ST,KeyType key)/在有序表在有序表ST中折半查找其关键字等于中折半查找其关键字等于key的数据元素。的数据元素。/假设找到，那么函数值为该元素在表中的位置，否那么为假设找到，那么函数值为该元素在表中的位置，否那么为0。low=1;/置区间初值置区间初值high=ST.length;/

13、low和和high分别指示待查元素所在范围的下界和上界分别指示待查元素所在范围的下界和上界while(low=high)mid=(low+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算法描画lowhig

14、hmid例 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 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

15、 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 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性能分析性能分析查

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

17、展比较的关键字个数至多为折半查找法在查找胜利时和给定值进展比较的关键字个数至多为 。1log2n 例如，上述例如，上述11个元素的表的例子。查找个元素的表的例子。查找21的过程如红线所示，查找的过程如红线所示，查找85的过程如蓝线所示。的过程如蓝线所示。图图9.1 断定树和查找断定树和查找21(红线红线)，85(蓝线蓝线)的过程的过程6391471025811-13-46-79-101-22-34-55-67-88-910-1111-折半查找的平均查找长度折半查找的平均查找长度 假定有序表的长度假定有序表的长度n2h1反之，反之，hlog2(n+1)，那么描画折，那么描画折半半查找的断定树是深

18、度为查找的断定树是深度为h的满二叉树。假设表中每个记录的查找概率相的满二叉树。假设表中每个记录的查找概率相等等(Pi=1/n)，那么查找胜利时折半查找的平均查找长度：，那么查找胜利时折半查找的平均查找长度：1)1(log1212111nnnjnCPASLhjjniiibs对恣意的对恣意的n，当，当n较大较大(n50)时，可有以下近似结果：时，可有以下近似结果：1)1(log2nASLbs4折半查找算法的特点折半查找算法的特点 特点：只适用于有序表，且限于顺序存储构造对线性链表无法进展特点：只适用于有序表，且限于顺序存储构造对线性链表无法进展折半查找。折半查找。9.2.4 索引顺序表的查找索引顺

19、序表的查找1分块查找分块查找 分块查找又称索引顺序查找，这是顺序查找的一种改良方法。在此分块查找又称索引顺序查找，这是顺序查找的一种改良方法。在此查找法中，除表本身以外，尚需建立一个查找法中，除表本身以外，尚需建立一个“索引表。如下例所示。索引表。如下例所示。查找过程：将表分成几块，块内无序，块间有序；先确定待查查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找记录所在块，再在块内查找适用条件：分块有序表适用条件：分块有序表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

20、24 48 60 58 74 57 86 5322 48 861 7 13索引表查38最大关键字起始地址 分块有序：即后一个子表中的一切记录的关键字均大于分块有序：即后一个子表中的一切记录的关键字均大于前一个子表中的最大关键字。前一个子表中的最大关键字。分块查找的算法思想：分块查找的算法思想：确定待查记录所在的块子表；确定待查记录所在的块子表；在块中顺序查找在块中顺序查找2性能分析性能分析分块查找的平均查找长度为：分块查找的平均查找长度为：其中：其中：Lb为查找索引表确定所在块的平均查找长度，为查找索引表确定所在块的平均查找长度，Lw为在块中查找元素的为在块中查找元素的平均查找长度。平均查找长

21、度。1)(2121211111ssnsbisjbLLASLsibjwbbsASLbsLbLw用顺序查找确定所在块用顺序查找确定所在块snb/；又假定表中每个记录的查找概率相等，那么每；又假定表中每个记录的查找概率相等，那么每 普通情况下，为进展分块查找，可以将长度为普通情况下，为进展分块查找，可以将长度为n的表均匀地分成的表均匀地分成b块，每块，每块含有块含有s个记录，即个记录，即块查找的概率为块查找的概率为1/b，块中每个记录的查找概率为，块中每个记录的查找概率为1/s。那么分块查找的平均长。那么分块查找的平均长度为：度为：用折半查找确定所在块用折半查找确定所在块2)1(log2ssnLAS

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

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

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

25、二叉排序树中递归地查找某关键字等于所指二叉排序树中递归地查找某关键字等于key的数据元素，的数据元素，/假设查找胜利，那么前往指向该数据元素结点的指针，否那么前往空指针。假设查找胜利，那么前往指向该数据元素结点的指针，否那么前往空指针。if(!T)|EQ(key,Tdata.key)/查找终了查找终了return (T);else if(LT(key,Tdata.key)/在左子树中继续查找在左子树中继续查找return (SearchBST(Tlchild,key);else return (SearchBST(Trchild,key);/在右子树中继续查找在右子树中继续查找 /Search

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

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

28、ULL。if(!T)p=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,ElemType e)/当二叉排序树T中

29、不存在关键字等于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 FALSE;/树中已有关键字一样的结点 /InsertBST算法算法9.4如下：

30、如下：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个结点的二叉排序树的深度，最好为log2n，最坏为n。因此，二叉排序树查找的最好时间复杂度为O(log2n)，最坏的时间复杂度

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

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

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

34、的存储位置相对应。称这个对应关系f为为哈希函数。哈希函数。根本思想：在记录的存储地址和它的关键字之间建立根本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法就能得到所查元素的查找方法关键字集合存储地址集合hashl哈希表哈希表运用哈希函数，由记录的关键字确运用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，定记录在表中的地址，并将记录放入此地址，这样构成的表叫这样构成的表叫l哈希查找哈希查找又叫散列查找，利用哈希函数进又叫散列查找，利用哈希函数进展查找的过程叫展查找

35、的过程叫例 30个地域的各民族人口统计表编号 地域别 总人口 汉族 回族.1 北京2 上海.以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2以地域别作关键字，取地域称号第一个拼音字母的序号作哈希函数：H()=2 H(Shanghai)=19 H(Shenyang)=19从例子可见：从例子可见：哈希函数只是一种映象，所以哈希函数的设定很灵哈希函数只是一种映象，所以哈希函数的设定很灵敏，只需使任何关键字的哈希函数值都落在表长允许的敏，只需使任何关键字的哈希函数值都落在表长允许的范围之内即可范围之内即可冲突：冲突：key1key2，但，但H(key1)=H(key2)的景象

36、叫的景象叫 同义词：具有一样函数值的两个关键字，叫该哈希同义词：具有一样函数值的两个关键字，叫该哈希函数的函数的哈希函数通常是一种紧缩映象，所以冲突不可防止，只哈希函数通常是一种紧缩映象，所以冲突不可防止，只能尽量减少；同时，冲突发生后，应该有处置冲突的方能尽量减少；同时，冲突发生后，应该有处置冲突的方法法9.4.2 哈希函数的构造哈希函数的构造1直接定址法直接定址法 取关键字或关键字的某个线性函数值为哈希地取关键字或关键字的某个线性函数值为哈希地址。即：址。即：H(key)=key 或或H(key)=a*key+b其中其中a和和b为常数这种哈希函数叫做本身函数。为常数这种哈希函数叫做本身函数

37、。2例子例子 例一，有一个从例一，有一个从1岁到岁到100岁的人口数字统计表。岁的人口数字统计表。地址地址 01 02 03 25 26 27 100 年龄年龄 1 2 3 25 26 27 人数人数 300 2000 5000 1050 表表9.1直接定址哈希函数例子一直接定址哈希函数例子一 其中，年龄作为关键字，哈希函数取关键字本身。假设要讯问其中，年龄作为关键字，哈希函数取关键字本身。假设要讯问25岁的人有岁的人有多少，那么只需查表的第多少，那么只需查表的第25项即可。项即可。例二：有一个解放后出生的人口调查表。例二：有一个解放后出生的人口调查表。地址地址 01 02 03 22 年份年

38、份 1949 1950 1951 1970 人数人数 15000 其中，关键字是年份，哈希函数取关键字加一常数：其中，关键字是年份，哈希函数取关键字加一常数：H(key)=key+(1948)。假设要查假设要查1970年出生的人，那么只需查第年出生的人，那么只需查第(19701948)22项即可。项即可。表表9.2 直接定址哈希函数例子二直接定址哈希函数例子二 2数字分析法数字分析法 主要思想：假设关键字是以主要思想：假设关键字是以r为基的数如：以为基的数如：以10为基的十进制数，并且哈希表中能够出现的关键为基的十进制数，并且哈希表中能够出现的关键字都是事先知道的，那么可取关键字的假设干位组成

39、字都是事先知道的，那么可取关键字的假设干位组成哈希地址。哈希地址。例如，有例如，有80个记录，其关键字为个记录，其关键字为8位十进制数。位十进制数。假设哈希表的表长为假设哈希表的表长为10010，那么可取两位十进制数，那么可取两位十进制数组成哈希地址。这两位的取法，原那么是使得到的组成哈希地址。这两位的取法，原那么是使得到的哈希地址尽量防止产生冲突。假设这哈希地址尽量防止产生冲突。假设这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

40、 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，第位只能够取，第位只能够取2、5或或7，因此这，因此这4位都不可取。由于中间位都不可取。由于中间4位可看成是近位可看成是近乎随机的，因此可取其中恣意两位，或取其中两位乎随机的，因此可取其中恣意两位，或取其中两位与另两位的叠加求和后舍去进位作为哈希地址。与另两位的叠加求和后舍去进位作为哈希地址。2例子例子 假设假设BASIC言语中允许的标识符为一个字母，或言语中允许的标识

41、符为一个字母，或一个字母和一个数字。在计算机内可用两位八进一个字母和一个数字。在计算机内可用两位八进制数表示字母和数字制数表示字母和数字.如图如图9.11(a)所示。取表示符在计算机中的八进制数所示。取表示符在计算机中的八进制数为它的关键字。为它的关键字。A B C Z 0 1 2 901 02 03 32 60 61 62 713平方取中法平方取中法1定义定义 取关键字平方后的中间几位为哈希地址。取的取关键字平方后的中间几位为哈希地址。取的位数由表长决议。位数由表长决议。(a)字符的八进制表示对照表2例子例子 假设表长为假设表长为51229，那么可取关键字平方后的，那么可取关键字平方后的中间

42、中间9位二进制数为哈希地址。例如，图位二进制数为哈希地址。例如，图9.11(b)列出了一些标识符及它们的哈希地址。列出了一些标识符及它们的哈希地址。A 0100 0 010000 000I 1100 1 210000 210J 1200 1 440000 440I0 1160 1 370400 370P1 2061 4 310541 310P2 2062 4 314704 314Q1 2161 4 734741 734Q2 2162 4 741304 741Q3 2163 4 745651 745记录记录 关键字关键字 (关键字关键字)2 哈希地址哈希地址(21729)(b)标识符及其哈希地址

43、标识符及其哈希地址 图图9.11 4折叠法折叠法 折叠法折叠法folding：将关键字分割成位数一样：将关键字分割成位数一样的几部分最后一部分的位数可以不同，然后取的几部分最后一部分的位数可以不同，然后取这几部分的叠加和舍去进位作为哈希地址。这几部分的叠加和舍去进位作为哈希地址。移位叠加：将分割后的每一部分的最低位对齐，然移位叠加：将分割后的每一部分的最低位对齐，然后相加。后相加。间界叠加：从一端向另一端沿分割界来回折叠，然间界叠加：从一端向另一端沿分割界来回折叠，然后对齐相加。后对齐相加。运用前提运用前提:关键字位数很多，而且关键字中每一位上数字分布关键字位数很多，而且关键字中每一位上数字分

44、布大致均匀时。大致均匀时。4折叠法折叠法3例子例子 例如，每一种西文图书馆都有一个国际规范图书例如，每一种西文图书馆都有一个国际规范图书编号编号ISBN，如国际规范图书馆图书编号如国际规范图书馆图书编号0-442-20586-4的哈希地的哈希地址分别如图址分别如图9.12(a)和和(b)所示。所示。58645864 4220 0224 )04 )04 10088 6092 H(key)=0088 H(key)=6092(a)移位叠加移位叠加(b)间界叠加间界叠加图图9.12由折叠法求得哈希地址由折叠法求得哈希地址 l(5)除留余数法除留余数法l构造：取关键字被某个不大于哈希表表构造：取关键字被

45、某个不大于哈希表表长长m的数的数p除后所得余数作哈希地址，即除后所得余数作哈希地址，即H(key)=key MOD p，pml特点特点l简单、常用，可与上述几种方法结合运简单、常用，可与上述几种方法结合运用用lp的选取很重要；的选取很重要；p选的不好，容易产生选的不好，容易产生同义词同义词l(6)随机数法随机数法l构造：取关键字的随机函数值作哈希地构造：取关键字的随机函数值作哈希地址，即址，即H(key)=random(key)l适于关键字长度不等的情况适于关键字长度不等的情况9.4.3 处置冲突的方法处置冲突的方法 冲突：指由关键字得到的哈希地址的位置上已存冲突：指由关键字得到的哈希地址的位

46、置上已存在记录。在记录。处置冲突：为产生冲突的关键字的记录找到另一处置冲突：为产生冲突的关键字的记录找到另一个个“空的哈希地址。空的哈希地址。l开放定址法开放定址法l方法：当冲突发生时，构成一个探查序方法：当冲突发生时，构成一个探查序列；沿此序列逐个地址探查，直到找到列；沿此序列逐个地址探查，直到找到一个空位置开放的地址，将发生冲一个空位置开放的地址，将发生冲突的记录放到该地址中，即突的记录放到该地址中，即Hi=(H(key)+di)MOD m，i=1,2,k(km-1)l其中：其中：H(key)哈希函数哈希函数l m哈希表表长哈希表表长l di增量序列增量序列l分类分类l线性探测再散列：线性

47、探测再散列：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 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)=3

48、8 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方法：构造假设干个哈希函数，当发生冲突时，计算下方法：构造假设干个哈希函数，当发生冲突时，计算下一个哈希地址，即：一个哈希地址，即：Hi=Rhi(key)i=1,2,kl其中：其中：Rhi不同的哈希函数不同的哈希函数l特点：计算时间添加特点：计算时间添加l链地址法链地址法l方法：将一切关键字为同义词的记录存储在一个单链表方法：将一切关键字为同义词的

49、记录存储在一个单链表中，并用一维数组存放头指针中，并用一维数组存放头指针建立一个公共溢出区建立一个公共溢出区另设立向量为溢出表。一切关键字和根另设立向量为溢出表。一切关键字和根本表中关键字为同义词的记录，不论它本表中关键字为同义词的记录，不论它们由哈希函数得到的哈希地址是什么，们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。一旦发生冲突，都填入溢出表。例 知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函数为：H(key)=key MOD 13,用链地址法处置冲突0 1 2 3 4 5 6 7 8 9 10 11 12 1412779685

50、51984202310119.4.4 哈希表的查找及其分析哈希表的查找及其分析1相关术语相关术语 查找过程：查找过程：给定给定K值，根据造表时设定的哈希函数求得哈希地址，值，根据造表时设定的哈希函数求得哈希地址，假设表中此位置上没有记录，那么查找不胜利；假设表中此位置上没有记录，那么查找不胜利；(2)否那么比较关键字，假设和给定值相等，那么查找否那么比较关键字，假设和给定值相等，那么查找胜利；胜利；(3)否那么根据造表时设定的处置冲突的方法找否那么根据造表时设定的处置冲突的方法找“下下一地址，直至哈希表中某个位置为一地址，直至哈希表中某个位置为“空或者表中所空或者表中所填记录的关键字等于给定值

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

52、填记录时，发生冲突的能够性就越大，那么查找时，给定值需与之进展比较的关键字的个数也就越多。时，给定值需与之进展比较的关键字的个数也就越多。例 知一组关键字(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)MOD16=3 冲突，H3=(1+3)MOD

53、16=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)MOD16=7 冲突，H2=(6+2)MOD16

54、=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 对于预先知道且规模不大的关键字集对于预先知道且规模不大的关键字集,有时可

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

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

57、 30 97第一趟38 49 65 13 27 30 76第二趟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 次关键字间的比较，且不次关键字间的比较，且不挪动

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

59、，以到达那么可分别对这两部分记录继续进展排序，以到达整个序列有序。整个序列有序。一趟快速排序一趟快速排序 假设待排序序列为假设待排序序列为L.rs,L.rs+1,L.rt,首先首先恣意选取一个记录通常可选为第一个关键字恣意选取一个记录通常可选为第一个关键字L.rs作作为枢轴为枢轴.然后按下述原那么重新陈列其他记录：将一切关键字较然后按下述原那么重新陈列其他记录：将一切关键字较它小的记录都安顿在它的位置之前，将一切关键字较它它小的记录都安顿在它的位置之前，将一切关键字较它大的记录都安顿在它的位置之后。大的记录都安顿在它的位置之后。由此可以该由此可以该“枢轴记录最后落的位置枢轴记录最后落的位置i作

60、分界限，将序作分界限，将序列列L.rs,L.rt分割成两个子序列分割成两个子序列L.rs,L.rs+1,L.ri1和和L.ri1,L.ri+2,L.rt。这个过程称做一趟快速排序或一次划分。这个过程称做一趟快速排序或一次划分。例如，以式例如，以式),94(),27(),13(),76(),97(),65(),38(),49(RRRRRRRR中关键字为例，一趟快速排序的过程如图中关键字为例，一趟快速排序的过程如图10.7(a)所示。所示。进展进展2次交换后次交换后 27 38 97 76 13 65 49jij进展进展3次交换后次交换后 27 38 13 97 76 65 49jii进展进展1次

61、交换后次交换后 27 38 65 97 76 13 49jii进展进展4次交换后次交换后 27 38 13 76 97 65 49jij完成一趟排序完成一趟排序 27 38 13 49 76 97 65 49(a)一趟快排过程一趟快排过程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 终了终了

62、 终了终了有序序列有序序列 13 27 38 49 49 65 76 97(b)排序的全过程排序的全过程图图10.7 快速排序例如快速排序例如 快速排序算法实现快速排序算法实现 整个快速排序的过程可递归进展。假设待排序列中只需一个记录，显然已有整个快速排序的过程可递归进展。假设待排序列中只需一个记录，显然已有序，否那么进展一趟快速排序后再分别对分割所得的两个子序列进展快速排序，序，否那么进展一趟快速排序后再分别对分割所得的两个子序列进展快速排序，如图如图10.7(b)所示。所示。快速排序的平均时间快速排序的平均时间快速排序的平均时间为：快速排序的平均时间为：nknTavgln其中，其中，n为待

63、排序序列中记录的个数，为待排序序列中记录的个数，k为某个常数。为某个常数。10.4 选择排序选择排序 选择排序选择排序Selection Sort的根本思想是：的根本思想是：每一趟每一趟n-i+1(i=1,2,n-1)个记录中选取关键个记录中选取关键字最小的记录作为有序序列中第字最小的记录作为有序序列中第i个记录个记录10.4.1 简单项选择择排序简单项选择择排序1算法实现：算法实现：一趟简单项选择择排序的操作为：经过一趟简单项选择择排序的操作为：经过n-i次次关键字间的比较，从关键字间的比较，从n-i+1个记录中选出关键字最个记录中选出关键字最小的记录，并和第小的记录，并和第i1in个记录交

64、换之。个记录交换之。2简单项选择择排序的改良简单项选择择排序的改良 选择排序的主要操作是进展关键字间的比较。因选择排序的主要操作是进展关键字间的比较。因此改良简单项选择择排序应减少此改良简单项选择择排序应减少“比较。比较。显然，在显然，在n个关键字中选出最小值，至少进展个关键字中选出最小值，至少进展n-1次比次比较较.假设能利用前假设能利用前n-1次比较所得信息，那么可减少以后次比较所得信息，那么可减少以后各趟选择排序中所用的比较次数。各趟选择排序中所用的比较次数。例如，在例如，在8个运发动中决出前个运发动中决出前3名至多需求名至多需求11场竞赛，场竞赛，而不是而不是7+6+5=18场竞赛前提

65、：假设乙胜丙，甲胜乙，那场竞赛前提：假设乙胜丙，甲胜乙，那么以为甲必能胜丙。么以为甲必能胜丙。10.4.2 树形选择排序树形选择排序首先对首先对n个记录的关键字进展两两比较个记录的关键字进展两两比较如此反复，直至选出最小关键字的记录为止。如此反复，直至选出最小关键字的记录为止。然后在其中然后在其中 个较小者之间再进展两两比较个较小者之间再进展两两比较 树形选择排序树形选择排序,又称锦标赛排序又称锦标赛排序，是一种按照锦标赛的思想进，是一种按照锦标赛的思想进展选择排序的方法。展选择排序的方法。2n10.4.2 树形选择排序树形选择排序上述过程可用一棵有上述过程可用一棵有n个叶子结点的完全二叉树表

66、示。个叶子结点的完全二叉树表示。图图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 在输出最小关键字之后，仅需将叶子结点中的在输出最小关键字之后，仅需将叶子结点中的最小关键字最小关键字13改为改为“最大值，再从下到上开最大值，再从下到上开场比较场比较38 38 38 65 76 49 38 65 97 76 49 49 49 输出输出13，27之后之后 (c)选出居第三的关键字为选出居第三的关键字为38 树形选择排序的时间复杂度：由于含有树形选择排序的时间复杂度：由于含有n个个叶子结点的完全二叉树的深度为叶子结点的完全二叉树的深度为1log2n那么在树形选择排序中，除了最小那么在树形选择排序中，除了最小关键字之外，每选择一个次小关键关键字之外，每