数据结构查找优秀PPT.ppt

《数据结构查找优秀PPT.ppt》由会员分享，可在线阅读，更多相关《数据结构查找优秀PPT.ppt（97页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第9章章查找查找1查找表查找表(SearchTable)：是由同一类型的数据元素（或记录）构成的集合。是由同一类型的数据元素（或记录）构成的集合。前面已介绍了各种线性或非线性的数据结构，本章探前面已介绍了各种线性或非线性的数据结构，本章探讨另一种在实际应用中大量运用的数据结构讨另一种在实际应用中大量运用的数据结构-查找表。查找表。由于由于“集合集合”中的数据元素之间存在着完全松散的关中的数据元素之间存在着完全松散的关系，因此查找表是一种特别敏捷的数据结构。系，因此查找表是一种特别敏捷的数据结构。2对查找表常常进行的操作：对查找表常常进行的操作：（1）查询某个）查询某个“特定的特定的”数据元素

2、是否在查找表中。数据元素是否在查找表中。（2）检索某个）检索某个“特定的特定的”数据元素的各种属性。数据元素的各种属性。（3）在查找表中插入一个数据元素。）在查找表中插入一个数据元素。（4）从查找表中删去某个数据元素。）从查找表中删去某个数据元素。3查找表可分为两类：查找表可分为两类：若对查找表只作若对查找表只作查询查询和和检索检索操作，则称此类查找表为静态查找表操作，则称此类查找表为静态查找表（StaticSearchTable)。若在查找过程中同时若在查找过程中同时插入插入查找表中不存在的数据元素，或者从查找表查找表中不存在的数据元素，或者从查找表中中删除删除已存在的某个数据元素，则称此类

3、查找表为动态查找表（已存在的某个数据元素，则称此类查找表为动态查找表（DynamicSearchTable）。）。4在各种系统软件或应用软件中，查找表是最常见的结构之一。如编译程序在各种系统软件或应用软件中，查找表是最常见的结构之一。如编译程序中符号表、信息处理系统中信息表等。中符号表、信息处理系统中信息表等。综上所述，所谓综上所述，所谓“查找查找”即为在一个含有众多的数据元素（或记录）的查即为在一个含有众多的数据元素（或记录）的查找表中找出某个找表中找出某个“特定的特定的”数据元素（或记录）。数据元素（或记录）。关于关于“特定的特定的”词的具体含义：词的具体含义：关键字（关键字（Key）：）

4、：是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）。记录）。主关键字（主关键字（PrimaryKey）：）：若此关键字可以惟一地标识一个记录，则称此关键字为主关键字。若此关键字可以惟一地标识一个记录，则称此关键字为主关键字。对不同的记录，其主关键字均不同。对不同的记录，其主关键字均不同。5次关键字（次关键字（SecondaryKey）：）：用以识别若干记录的关键字为次关键字。用以识别若干记录的关键字为次关键字。当数据元素只有一个数据项时，其关键字即为该数据元素的值。当数据元素只有一个数据项时，其关键字即为

5、该数据元素的值。查找（查找（Searching)：依据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素依据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。（或记录）。查找成功：查找成功：若表中存在这样的一个记录，则查找成功，此时查找的结果为给出整个记若表中存在这样的一个记录，则查找成功，此时查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置。录的信息，或指示该记录在查找表中的位置。查找不成功：查找不成功：若表中不存在关键字等于给定值的记录，则查找不成功，此时查找的结果若表中不存在关键字等于给定值的记录，则查找不成功，此时查找的结果可给出一个可给出一

6、个“空空”记录或记录或“空空”指针。指针。6此表为一个查找表。此表为一个查找表。表中每一行为一个记录，学生的学号为记录的关键字。表中每一行为一个记录，学生的学号为记录的关键字。若给定值为若给定值为20010985，则通过查找可得学生王五的各项信息。此时查找是成功的。，则通过查找可得学生王五的各项信息。此时查找是成功的。若给定值为若给定值为20011930，则由于表中没有关键字为，则由于表中没有关键字为20011930的记录，则查找不成功。的记录，则查找不成功。学号学号姓名姓名性别性别入学总分入学总分录取专业录取专业 20010983张三张三女女438计算机计算机20010984李四李四男男43

7、0计算机计算机20010985王五王五女女445计算机计算机 20010998张三张三男男458计算机计算机 招生录用登记表招生录用登记表例：例：7如何进行查找？如何进行查找？在一个结构中查找某个数据元素的过程依靠于这个数据元素在结构中所处在一个结构中查找某个数据元素的过程依靠于这个数据元素在结构中所处的地位。的地位。即：对查找表进行查找的方法取决于表中数据元素依何种关系组织在一起。即：对查找表进行查找的方法取决于表中数据元素依何种关系组织在一起。（这个关系是人为加上的。因为查找表中数据元素之间原本仅存在（这个关系是人为加上的。因为查找表中数据元素之间原本仅存在“同属于一同属于一个集合个集合”

8、的松散关系）。的松散关系）。例：查英文单词。例：查英文单词。字典是按单词的字母在字母表中的次序编排的，则查找时不须要从字典字典是按单词的字母在字母表中的次序编排的，则查找时不须要从字典中第一个单词比较起，中第一个单词比较起，而只要依据待查单词中每个字母在字母表中的位置查而只要依据待查单词中每个字母在字母表中的位置查到该单词。到该单词。字典这种查找表的数据元素之间原本仅存在着字典这种查找表的数据元素之间原本仅存在着“同属于一个集合同属于一个集合”的松的松散散关系，给查找带来不便。关系，给查找带来不便。对字典按单词的字母在字母表中的次序进行编排，就是对字典这种查找对字典按单词的字母在字母表中的次序

9、进行编排，就是对字典这种查找表人为加上的一种关系，以便按某种规则进行查找。表人为加上的一种关系，以便按某种规则进行查找。8总之：总之：查找的方法取决于查找表的结构。查找的方法取决于查找表的结构。由于查找表中的数据元素之间不存在明显的组织规律，由于查找表中的数据元素之间不存在明显的组织规律，因此不便因此不便于查找。于查找。为了提高查找的效率，为了提高查找的效率，须要在查找表中的元素之间人为地附加某须要在查找表中的元素之间人为地附加某种确定的关系，换句话说，种确定的关系，换句话说，用另外一种结构来表示查找表。用另外一种结构来表示查找表。9内查找和外查找：内查找和外查找：若整个查找过程全部在内存进行

10、，则称为内查找；若在查找过程若整个查找过程全部在内存进行，则称为内查找；若在查找过程中还须要访问外存，则称为外查找。本书仅介绍内查找。中还须要访问外存，则称为外查找。本书仅介绍内查找。平均查找长度平均查找长度ASL：查找算法的效率，主要看要查找的值与关键字的比较次数，通常查找算法的效率，主要看要查找的值与关键字的比较次数，通常用平均查找长度来衡量。用平均查找长度来衡量。10 对一个含对一个含n n个数据元素的表，查找成功时：个数据元素的表，查找成功时：其中：其中：P Pi i为找到表中第为找到表中第i i个数据元素的概率，且有：个数据元素的概率，且有：C Ci i为为查查找找表表中中第第i i

11、个个数数据据元元素素所所用用到到的的比比较较次次数数。不不同同的的查查找找方法有不同的方法有不同的C Ci i。查查找找是是许许多多程程序序中中最最消消耗耗时时间间的的一一部部分分。因因而而，一一个个好好的的查查找找方法会大大提高运行速度。方法会大大提高运行速度。119.1 静态查找表静态查找表9.2动态查找表动态查找表9.3 哈希表哈希表本章内容：本章内容：129.1 静态查找表静态查找表131.1.依次表的查找依次表的查找 静态查找表的存储结构可用依次表或线性链表表示。静态查找表的存储结构可用依次表或线性链表表示。本节只探讨在依次存储结构中查找的实现。本节只探讨在依次存储结构中查找的实现。

12、依次查找的基本思想：依次查找的基本思想：从表中最终一个记录起先，逐个进行记录的关键字和给定值从表中最终一个记录起先，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字和给定值比找到所查记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。较都不等，则表明表中没有所查记录，查找不成功。14i例例 012 34567891011 513192137566475808892找找6464监视哨监视哨iiii比较次数比较次数=5

13、比较次数：比较次数：查找第查找第n个元素：个元素：1查找第查找第n-1个元素：个元素：2.查找第查找第1个元素：个元素：n查找第查找第i个元素：个元素：n-i+1查找失败查找失败：n+115例 01234567891011 513192137566475808892找找6464监视哨监视哨#defineM500typedefstructintkey;floatinfo;JD;intseqsrch(JDr,intn,intk)inti=n;r0.key=k;while(ri.key!=k)i-;return(i);16监测哨的作用：监测哨的作用：（1）省去判定循环中下标越界的条件，从而节约比较时

14、间。）省去判定循环中下标越界的条件，从而节约比较时间。（2）保存查找值的副本，查找时若遇到它，则表示查找不成功。这样在从后向）保存查找值的副本，查找时若遇到它，则表示查找不成功。这样在从后向前查找失败时，不必推断查找表是否检测完，从而达到算法统一。前查找失败时，不必推断查找表是否检测完，从而达到算法统一。上述算法中，对于有 n 个数据元素的表，给定值 k与表中第 i 个元素的关键字相等，即定位第 i 个记录时，需进行：ni+1次关键字比较，即 Ci=ni+1。则查找成功时，依次查找的平均查找长度为：依次查找性能分析：依次查找性能分析：对一个含有对一个含有n个数据元素的表，查找成功时有：个数据元

15、素的表，查找成功时有：17设每个数据元素的查找概率相等，即设每个数据元素的查找概率相等，即Pi=，则等概率状况下有：，则等概率状况下有：查找不成功时，关键字的比较次数总是查找不成功时，关键字的比较次数总是n+1次。次。算法中的基本工作就是关键字的比较，因此，查找长度的量级就是查算法中的基本工作就是关键字的比较，因此，查找长度的量级就是查找算法的时间困难度为找算法的时间困难度为O(n)。依次查找缺点是当依次查找缺点是当n很大时，平均查找长度较大，效率低；优点是对很大时，平均查找长度较大，效率低；优点是对表中数据元素的存储没有特殊要求。表中数据元素的存储没有特殊要求。182.2.有序表的查找有序表

16、的查找以有序表表示静态查找表时，可用折半查找法来实现查找。以有序表表示静态查找表时，可用折半查找法来实现查找。折半查找的基本思想：折半查找的基本思想：在有序表中，取中间元素作为比较对象，若给定值与中间元素的在有序表中，取中间元素作为比较对象，若给定值与中间元素的关键字相等，则查找成功；若给定值小于中间元素的关键字，则在中关键字相等，则查找成功；若给定值小于中间元素的关键字，则在中间元素的左半区接着查找；若给定值大于中间元素的关键字，则在中间元素的左半区接着查找；若给定值大于中间元素的关键字，则在中间元素的右半区接着查找。不断重复上述查找过程，直到查找成功，间元素的右半区接着查找。不断重复上述查

17、找过程，直到查找成功，或所查找的区域多数据元素，查找失败。或所查找的区域多数据元素，查找失败。折半查找也叫二分查找，是一种效率较高的查找方法，但前提是折半查找也叫二分查找，是一种效率较高的查找方法，但前提是表中元素必需按关键字有序（按关键字递增或递减）排列。表中元素必需按关键字有序（按关键字递增或递减）排列。19算法实现：算法实现：设表长为设表长为n，low，high和和mid分别指向待查元素所在区间的上界、下界分别指向待查元素所在区间的上界、下界和中点和中点,k为给定值。为给定值。初始时，令初始时，令low=1,high=n,mid=(low+high)/2 让让k与与mid指向的记录比较：

18、指向的记录比较：若若k=rmid.key，则查找成功，则查找成功若若krmid.key，则则low=mid+1重复上述操作，直至重复上述操作，直至lowhigh时，查找失败时，查找失败20算法描述：算法描述：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 92lowhighm

19、id21例例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 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid221 2 3 4 5 6 7 8 9 10 115 13 19 2

20、1 37 56 64 75 80 88 92lowhighintbinsrch(JDr,intn,intk)intlow,high,mid,found;low=1;high=n;found=0;/found为找到标记。值为为找到标记。值为0表示未找表示未找到。到。while(lowrmid.key)low=mid+1;elseif(k=rmid.key)found=1;elsehigh=mid-1;if(found=1)/假如已找到假如已找到return(mid);/找到的记录的下标确定为找到的记录的下标确定为midelsereturn(0);#defineM500typedefstructi

21、ntkey;floatinfo;JD;23折半查找的性能分析：折半查找的性能分析：从折半查找的过程看，每次查找都是以表的中点为比较对象，并以中从折半查找的过程看，每次查找都是以表的中点为比较对象，并以中点将表分割为两个子表，对定位到的子表接着作同样的操作。所以，对表点将表分割为两个子表，对定位到的子表接着作同样的操作。所以，对表中每个数据元素的查找过程，可用二叉树来描述，称这个描述查找过程的中每个数据元素的查找过程，可用二叉树来描述，称这个描述查找过程的二叉树称为判定树。二叉树称为判定树。判定树中每一结点对应表中一个记录，但结点值不是某个记录的关键判定树中每一结点对应表中一个记录，但结点值不是

22、某个记录的关键字，而是某个记录在表中的位置序号。根结点对应当前区间的字，而是某个记录在表中的位置序号。根结点对应当前区间的中间记录中间记录，左子树对应前一子表，右子树对应后一子表。左子树对应前一子表，右子树对应后一子表。241185210741936判定树：1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92从上面判定树可看到，查找第一层的根结点从上面判定树可看到，查找第一层的根结点56，一次比较即可找，一次比较即可找到；到；查找其次层的结点查找其次层的结点19和和80，二次比较即可找到；二次比较即可找到；查找第三层的查找第三层的结点结点

23、5、21、64、88，三次比较即可找到；查找第四层的结点，三次比较即可找到；查找第四层的结点13，37、75、92，四次比较即可找到。，四次比较即可找到。25n个结点的判定树，树高为个结点的判定树，树高为k，则有，则有2k-1-1n2k-1，即，即k-1di.key)&(i=b)/确定要比较的值确定要比较的值k在哪一块在哪一块i+;/kb)printf(nNotfound);return(0);j=di.link;/要比较的值要比较的值k在以在以di.link为起点下标的块中为起点下标的块中while(jn)&(k!=rj.key)&(rj.keydata.key)p=T;returnTRUE

24、;/查找成功查找成功elseif(LT(key,T-data.key)SearchBST(T-lchild,key,T,p);/在左子树中接着查找在左子树中接着查找elseSearchBST(T-rchild,key,T,p);/在右子树中接着查找在右子树中接着查找4230201040352523fT设 key=48fTfT22pfTfTTTTfffp43二叉排序树的查找分析：二叉排序树的查找分析：在二叉排序树上查找其关键字等于给定值结点的过程，恰是走了一条在二叉排序树上查找其关键字等于给定值结点的过程，恰是走了一条从根结点到该结点的路径的过程。从根结点到该结点的路径的过程。含有含有n个结点的

25、二叉树是不唯一的，个结点的二叉树是不唯一的，如如何来进行查找分析呢？何来进行查找分析呢？44例如：上图两棵二叉排序树中，结点的个数和值均相同。例如：上图两棵二叉排序树中，结点的个数和值均相同。但（但（a）的深度）的深度为为3，而（，而（b）的深度为）的深度为6。其等概率平均查找长度分别为：其等概率平均查找长度分别为：ASL(a)=(1*1+2*2+3*3)/6=14/6ASL(b)=(1*1+2*1+3*1+4*1+5*1+6*1)/6=21/6因此，二叉排序树的平均查找长度和二叉树的形态有关。因此，二叉排序树的平均查找长度和二叉树的形态有关。最好状况下，二叉排序树在生成过程中，树的形态比较匀

26、整，其最最好状况下，二叉排序树在生成过程中，树的形态比较匀整，其最终得到的是一颗形态与二分查找的判定树相像的二叉排序树，如图终得到的是一颗形态与二分查找的判定树相像的二叉排序树，如图(a)所示。所示。最坏状况下，二叉排序树通过一个有序表的最坏状况下，二叉排序树通过一个有序表的n个结点依次插入生成个结点依次插入生成的，此时所得的二叉排序树为一颗深度为的，此时所得的二叉排序树为一颗深度为n的单支树，如图的单支树，如图(b)所示。所示。它的平均查找长度和单链表的依次查找相同，也是（它的平均查找长度和单链表的依次查找相同，也是（n+1）/2。对匀整的二叉排序树进行插入或删除结点后，应对其进行调整，使对

27、匀整的二叉排序树进行插入或删除结点后，应对其进行调整，使其照旧保持匀整。其照旧保持匀整。45(3)(3)二叉排序树的插入算法二叉排序树的插入算法依据动态查找表的定义，插入操作在查找不成功时才进行。依据动态查找表的定义，插入操作在查找不成功时才进行。若二叉排序树为空树，则新插入的结点为新的根结点；否则，新若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。4512533372410061907820例如：在右图给定的二叉排例如：在右图给定的二叉排序树中插入结点序树中插入结点20

28、46 Status InsertBST(BiTree&T,ElemType e )/当二叉排序树中不存在关键字等于 e.key 的数据元素时，插入元素值为 e 的结点，并返回 TRUE;否则，不进行插入并返回 FALSE。if(!SearchBST(T,e.key,NULL,p)/假如查找不成功，才进行插入 else /假如查找成功，则不进行插入 return FALSE;47s=(BiTree)malloc(sizeof(BiTNode);/为新结点安排空间为新结点安排空间s-data=e;s-lchild=s-rchild=NULL;if(!p)T=s;/插入插入s为新的根结点为新的根结点

29、elseif(LT(e.key,p-data.key)p-lchild=s;/插入插入*s为为*p的左孩子的左孩子elsep-rchild=s;/插入插入*s为为*p的右孩子的右孩子returnTRUE;/插入成功插入成功48(4)(4)二叉排序树的删除算法二叉排序树的删除算法 和插入相反，删除在查找成功之后进行，并且要求删除二叉排序树上某个结点之后，仍旧保持二叉排序树的特性。可分三种状况探讨：可分三种状况探讨：1）被删除的结点是叶子；）被删除的结点是叶子；2）被删除的结点只有左子树或者只有右子树；）被删除的结点只有左子树或者只有右子树；3）被删除的结点既有左子树，也有右子树。）被删除的结点既

30、有左子树，也有右子树。4950308020908540358832被删除的结点是叶子结点。被删除的结点是叶子结点。例如例如:被删关键字被删关键字=2088其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空”5050308020908540358832被删除的结点只有左子树或者只有右子树被删除的结点只有左子树或者只有右子树其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为“指向被删除结点的左子树指向被删除结点的左子树或右子树或右子树”。被删关键字被删关键字=40805150308020908540358832被删除的结点既有左子树，也有右子树。被删除的结点既有左子树，也

31、有右子树。4040以其前驱替代之，然后再删除该前驱结点。以其前驱替代之，然后再删除该前驱结点。被删结点被删结点前驱结点前驱结点被删关键字被删关键字=5052StatusDeleteBST(BiTree&T,KeyTypekey)/若二叉排序树若二叉排序树T中存在其关键字等于中存在其关键字等于key的数据元素，则删除该数据的数据元素，则删除该数据元素结点，并返回函数值元素结点，并返回函数值TRUE，否则返回函数值，否则返回函数值FALSE。if(!T)/若若T为空为空returnFALSE;/不存在关键字等于不存在关键字等于key的数据元素的数据元素elseif(EQ(key,T-data.ke

32、y)Delete(T);returnTRUE;/找到关键字等于找到关键字等于key的数据元素的数据元素elseif(LT(key,T-data.key)DeleteBST(T-lchild,key);/接着在左子树中进行查找，删除接着在左子树中进行查找，删除elseDeleteBST(T-rchild,key);/接着在右子树中进行查找，删除接着在右子树中进行查找，删除53voidDelete(BiTree&p)/从从二叉排序树中删除结点二叉排序树中删除结点 p，并重接它的左子树或右子树并重接它的左子树或右子树if(!p-rchild)elseif(!p-lchild)else其中删除操作过程

33、如下所描述：其中删除操作过程如下所描述：54/右子树为空树则只需重接它的左子树右子树为空树则只需重接它的左子树q=p;p=p-lchild;free(q);pp55/左子树为空树只需重接它的右子树左子树为空树只需重接它的右子树q=p;p=p-rchild;free(q);pp56q=p;s=p-lchild;/转左转左while(s-rchild)/转左后，到右终点转左后，到右终点q=s;s=s-rchild;/q指向指向s的双亲，的双亲，s指向被删结点的前驱指向被删结点的前驱p-data=s-data;/以以前驱结点的数据替换被删结点的前驱结点的数据替换被删结点的数据数据if(q!=p)q-

34、rchild=s-lchild;/重接重接*q的右子树的右子树elseq-lchild=s-lchild;/重接重接*q的左子树的左子树free(s);/左右子树均不空左右子树均不空pqs57(5)(5)二叉排序树的构造过程二叉排序树的构造过程例：记录的关键字序列为：例：记录的关键字序列为：33，50，42，18，39，9，77，44，2，11，24，则构造一棵二叉排序树的过程如下：则构造一棵二叉排序树的过程如下：从空树起先建立二叉排序树的过程图示从空树起先建立二叉排序树的过程图示58一个无序序列可以通过构造二叉排序树而成为一个有序序列。一个无序序列可以通过构造二叉排序树而成为一个有序序列。每

35、次插入新结点都是二叉排序树上新的叶子结点，不必移动每次插入新结点都是二叉排序树上新的叶子结点，不必移动其它结点，仅需改动某个结点指针，由空变为非空即可。其它结点，仅需改动某个结点指针，由空变为非空即可。59#includetypedefintTElemType;typedefstructBiTNode/结点结构结点结构TElemTypedata;structBiTNode*lchild,*rchild;/左、右指针左、右指针BiTNode,*BiTree;生成二叉排序树的算法：生成二叉排序树的算法：60voidInsBST(BiTree&T,TElemTypeK)BiTNode*f,*p;p=

36、T;while(p)/当当p为空时，即左孩子或右孩子为空时，为空时，即左孩子或右孩子为空时，p不再往下指不再往下指/即即从根结点起先找插入的位置，找到后，从根结点起先找插入的位置，找到后，f为要插入位置的双亲结点的地址为要插入位置的双亲结点的地址if(p-data=K)printf(树中已有树中已有%d，不需插入，不需插入n,K);return;f=p;p=(Kdata)?p-lchild:p-rchild;/p指向自己的左孩子或右孩子指向自己的左孩子或右孩子，f指向指向左右孩子的双亲左右孩子的双亲p=newBiTNode;/申请一个新结点申请一个新结点，把输入的值放入新结点，把输入的值放入新

37、结点p-data=K;p-lchild=p-rchild=NULL;if(T=NULL)/假如根结点为空，新结点为根结点假如根结点为空，新结点为根结点T=p;elseif(Kdata)/假如输入值小于它的根结点，则作为此根结点的左孩子假如输入值小于它的根结点，则作为此根结点的左孩子f-lchild=p;elsef-rchild=p;/假如输入值大于它的根结点，则作为此根结点的右孩子假如输入值大于它的根结点，则作为此根结点的右孩子61BiTreeCreateBST()BiTreeT;/T是是一个指针变量，指向二叉排序树的根结点一个指针变量，指向二叉排序树的根结点TElemTypeK;T=NULL

38、;printf(请输入一个整数关键字请输入一个整数关键字(输入输入0时结束输入时结束输入)：);scanf(%d,&K);while(K)InsBST(T,K);printf(“请输入下一个整数关键字请输入下一个整数关键字(输入输入0时结束输入时结束输入)：);scanf(%d,&K);returnT;voidmain()CreateBST();62例如例如:548254821是平衡树是平衡树不是平衡树不是平衡树平衡二叉树的定义：平衡二叉树的定义：又称又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：树。它或者是一棵空树，或者是具有下列性质的二叉树：1）它的左子树和右子树高度之差的确

39、定值不超过）它的左子树和右子树高度之差的确定值不超过1；2）它的左子树和右子树都是平衡二叉树。）它的左子树和右子树都是平衡二叉树。2.二叉平衡树二叉平衡树63二叉树上结点的平衡因子：二叉树上结点的平衡因子：为该结点的左子树的深度减去它的右子树的深度。为该结点的左子树的深度减去它的右子树的深度。平衡二叉树上全部结点的平衡因子只可能是：平衡二叉树上全部结点的平衡因子只可能是：-1、0、16465在插入过程中，接受平衡旋转技术。在插入过程中，接受平衡旋转技术。例如：依次插入的关键字为例如：依次插入的关键字为 5,4,2,8,6,95,4,2,8,6,95424258665842向右旋转一次先向右旋转

40、再向左旋转构造二叉平衡树构造二叉平衡树的方法：的方法：66426589642895向左旋转一次67当平衡的二叉排序树因插入结点而失去平衡时，仅需对离插入结点当平衡的二叉排序树因插入结点而失去平衡时，仅需对离插入结点最近的最近的最小不平衡子树最小不平衡子树进行平衡旋转处理即可。进行平衡旋转处理即可。平衡旋转处理可分为下列平衡旋转处理可分为下列4种状况：种状况：（1）单向右旋（顺时针）单向右旋（顺时针）（2）单向左旋（逆时针）单向左旋（逆时针）（3）先左后右双向旋转）先左后右双向旋转（4）先右后左双向旋转）先右后左双向旋转68 例：已知一棵平衡二叉排序树如图（a）所示。在A的左子树的左子树上插入1

41、5后，导致失衡，如图（b）所示。为复原平衡并保持二叉排序树的特性，可将A改为B的右子，B原来的右子改为A的左子，如图（c）所示。这相当于以B为轴，对A做了一次顺时针旋转。不平衡二叉树的调整不平衡二叉树的调整(1)69例例：已已知知一一棵棵平平衡衡二二叉叉排排序序树树如如图图（a）所所示示。在在A的的右右子子树树B的的右右子子树树上上插插入入70后后，导导致致失失衡衡，如如图图（b）所所示示。为为复复原原平平衡衡并并保保持持二二叉叉排排序序树树的的特特性性，可可将将A改改为为B的的左左子子，B原原来来的的左左子子改改为为A的的右右子子，如如图图（c）所所示示。这这相相当当于于以以B为轴，为轴，对

42、对A做了一次逆时针旋转。做了一次逆时针旋转。不平衡二叉树的调整不平衡二叉树的调整(2)70例例：已已知知一一棵棵平平衡衡二二叉叉排排序序树树如如图图（a）所所示示。在在A的的左左子子树树B的的右右子子树树上上插插入入45后后，导导致致失失衡衡，如如图图（b）所所示示。为为复复原原平平衡衡并并保保持持二二叉叉排排序序树树的的特特性性，可可首首先先将将B改改为为C的的左左子子，而而C原原来来的的左左子子改改为为B的的右右子子；然然后后将将A改改为为C的的右右子子，C原原来来的的右右子子改改为为A的的左左子子，如如图图（c）所所示示。这这相相当当于于对对C做做了了一一次次逆逆时时针针旋旋转转，对对A

43、做做了了一一次次顺顺时时针针旋旋转。转。71不平衡二叉树的调整不平衡二叉树的调整(3)72 例：已知一棵平衡二叉排序树如图（a）所示。在A的右子树的左子树上插入55后，导致失衡，如图（b）所示。为复原平衡并保持二叉排序树的特性，可首先将B改为C的右子，而C原来的右子改为B的左子；然后将A改为C的左子，C原来的左子改为A的右子，如图（c）所示。这相当于对 C 做了一次顺时针旋转，对 A 做了一次逆时针旋转。73不平衡二叉树的调整不平衡二叉树的调整(4)74 在在二叉二叉平衡树上进行查找的过程和二叉排序树相同，因此，查找过程平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的

44、关键字的个数不超过平衡树的深度。中和给定值进行比较的关键字的个数不超过平衡树的深度。二叉平衡树的查找性能分析：二叉平衡树的查找性能分析：问，含问，含 n n 个关键字的二叉平衡树可能达到的最大深度是多少？个关键字的二叉平衡树可能达到的最大深度是多少？75n=0空树空树最大深度为最大深度为0n=1最大深度为最大深度为1n=2最大深度为最大深度为2n=4最大深度为最大深度为3n=7最大深度为最大深度为4先看几个具体状况先看几个具体状况:76反过来问，深度为反过来问，深度为 h h 的二叉平衡树中所含结点的最小值的二叉平衡树中所含结点的最小值 N Nh h 是多少？是多少？h=0N0=0h=1h=2

45、h=3一般状况下一般状况下N1=1N2=2N3=4Nh=Nh-1+Nh-2+1利用归纳法可证得利用归纳法可证得Nh=Fh+2-177 因此，在二叉平衡树上进行查找时，查找过程中和给定值进行比较的关因此，在二叉平衡树上进行查找时，查找过程中和给定值进行比较的关键字的个数和键字的个数和 log(n)log(n)相当。即：在二叉平衡树上进行查找的时间困难度为相当。即：在二叉平衡树上进行查找的时间困难度为Olog(n)Olog(n)。由此推得，深度为由此推得，深度为 h h 的二叉平衡树中所含结点的最小值的二叉平衡树中所含结点的最小值 N Nh h=h+2h+2/5-1/5-1。反之，含有反之，含有

46、n n 个结点的二叉平衡树能达到的最大深度为：个结点的二叉平衡树能达到的最大深度为：h hn n=log=log(5(n+1)-25(n+1)-2。789.3 哈希表哈希表791.什么是哈希表什么是哈希表以上探讨的查找方法，由于数据元素的存储位置与关键字之间不存在以上探讨的查找方法，由于数据元素的存储位置与关键字之间不存在确定的关系，因此，查找时，须要进行一系列对关键字的查找比较，即查确定的关系，因此，查找时，须要进行一系列对关键字的查找比较，即查找算法是建立在比较的基础上的，查找效率由比较一次缩小的查找范围决找算法是建立在比较的基础上的，查找效率由比较一次缩小的查找范围决定。定。志向的状况是

47、依据关键字干脆得到其对应的数据元素位置，即要求关志向的状况是依据关键字干脆得到其对应的数据元素位置，即要求关键字与数据元素间存在一一对应关系，通过这个关系，能很快地由关键字键字与数据元素间存在一一对应关系，通过这个关系，能很快地由关键字得到对应的数据元素位置。得到对应的数据元素位置。80例：例：11个元素的关键字分别为个元素的关键字分别为18，27，1，20，22，6，10，13，41，15，25。选取关键字与元素位置间的函数为：选取关键字与元素位置间的函数为：f(key)=keymod111.通过这个函数对通过这个函数对11个元素建立查找表如下：个元素建立查找表如下：012345678910

48、102041186271525131222.查找时，对给定值查找时，对给定值kx通过这个函数计算出地址，再将通过这个函数计算出地址，再将kx3.与该地址单元中元素的关键字比较，若相等，查找成功。与该地址单元中元素的关键字比较，若相等，查找成功。81哈希表与哈希方法：哈希表与哈希方法：选取某个函数，依据该函数按关键字计算数据元素的存储地址，并选取某个函数，依据该函数按关键字计算数据元素的存储地址，并按此地址存放数据元素；按此地址存放数据元素；查找时，查找时，由同一个函数对给定值由同一个函数对给定值kx计算出地计算出地址，址，将将kx与该地址单元中数据元素的关键字进行比较，确定查找是否与该地址单元

49、中数据元素的关键字进行比较，确定查找是否成功，这就是哈希方法。成功，这就是哈希方法。哈希方法中运用的转换函数称为哈希函数。哈希方法中运用的转换函数称为哈希函数。哈希方法中计算的存储地址称为哈希地址或散列地址。哈希方法中计算的存储地址称为哈希地址或散列地址。按这个思想构造的查找表称为哈希表。按这个思想构造的查找表称为哈希表。82对于对于n个数据元素的集合，总能找到关键字与存放地址一一对应的个数据元素的集合，总能找到关键字与存放地址一一对应的函数。函数。若最大关键字为若最大关键字为m，可以安排，可以安排m个数据元素存放单元，选取函个数据元素存放单元，选取函数数f(key)=key即可，但这样会造成

50、存储空间的很大奢侈，即可，但这样会造成存储空间的很大奢侈，甚至不行能分甚至不行能分配这么大的存储空间。配这么大的存储空间。通常关键字的集合比哈希地址集合大得多，因而经过哈希函数变换通常关键字的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键字映射到同一个哈希地址上，这种现象称为冲突。后，可能将不同的关键字映射到同一个哈希地址上，这种现象称为冲突。83冲突不行能避开，只能尽可能削减。所以，哈希方法须要解决以冲突不行能避开，只能尽可能削减。所以，哈希方法须要解决以下两个问题：下两个问题：1）构造好的哈希函数）构造好的哈希函数a.所选函数尽可能简洁，以便提高转换速度。所选函数尽可能