数据结构查找.ppt

第第9章章查找查找1查找表查找表(SearchTable)：是由同一类型的数据元素（或记录）构成的集合。是由同一类型的数据元素（或记录）构成的集合。前面已介绍了各种线性或非线性的数据结构，本章讨论另一种在前面已介绍了各种线性或非线性的数据结构，本章讨论另一种在实际应用中大量使用的数据结构实际应用中大量使用的数据结构-查找表。查找表。由于由于“集合集合”中的数据元素之间存在着完全松散的关系，因此中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构。查找表是一种非常灵便的数据结构。2对查找表经常进行的操作：对查找表经常进行的操作：（1）查询某个）查询某个“特定的特定的”数据元素是否在查找表中。数据元素是否在查找表中。（2）检索某个）检索某个“特定的特定的”数据元素的各种属性。数据元素的各种属性。（3）在查找表中插入一个数据元素。）在查找表中插入一个数据元素。（4）从查找表中删去某个数据元素。）从查找表中删去某个数据元素。3查找表可分为两类：查找表可分为两类：若对查找表只作若对查找表只作查询查询和和检索检索操作，则称此类查找表为静态查找表操作，则称此类查找表为静态查找表（StaticSearchTable)。若在查找过程中同时若在查找过程中同时插入插入查找表中不存在的数据元素，或者从查找表查找表中不存在的数据元素，或者从查找表中中删除删除已存在的某个数据元素，则称此类查找表为动态查找表（已存在的某个数据元素，则称此类查找表为动态查找表（DynamicSearchTable）。）。4在各种系统软件或应用软件中，查找表是最常见的结构之一。如编译程序在各种系统软件或应用软件中，查找表是最常见的结构之一。如编译程序中符号表、信息处理系统中信息表等。中符号表、信息处理系统中信息表等。综上所述，所谓综上所述，所谓“查找查找”即为在一个含有众多的数据元素（或记录）的查即为在一个含有众多的数据元素（或记录）的查找表中找出某个找表中找出某个“特定的特定的”数据元素（或记录）。数据元素（或记录）。关于关于“特定的特定的”词的具体含义：词的具体含义：关键字（关键字（Key）：）：是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）。记录）。主关键字（主关键字（PrimaryKey）：）：若此关键字可以惟一地标识一个记录，则称此关键字为主关键字。若此关键字可以惟一地标识一个记录，则称此关键字为主关键字。对不同的记录，其主关键字均不同。对不同的记录，其主关键字均不同。5次关键字（次关键字（SecondaryKey）：）：用以识别若干记录的关键字为次关键字。用以识别若干记录的关键字为次关键字。当数据元素只有一个数据项时，其关键字即为该数据元素的值。当数据元素只有一个数据项时，其关键字即为该数据元素的值。查找（查找（Searching)：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。（或记录）。查找成功：查找成功：若表中存在这样的一个记录，则查找成功，此时查找的结果为给出整个记若表中存在这样的一个记录，则查找成功，此时查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置。录的信息，或指示该记录在查找表中的位置。查找不成功：查找不成功：若表中不存在关键字等于给定值的记录，则查找不成功，此时查找的结果若表中不存在关键字等于给定值的记录，则查找不成功，此时查找的结果可给出一个可给出一个“空空”记录或记录或“空空”指针。指针。6此表为一个查找表。此表为一个查找表。表中每一行为一个记录，学生的学号为记录的关键字。表中每一行为一个记录，学生的学号为记录的关键字。若给定值为若给定值为20010985，则通过查找可得学生王五的各项信息。此时查找是成功的。，则通过查找可得学生王五的各项信息。此时查找是成功的。若给定值为若给定值为20011930，则由于表中没有关键字为，则由于表中没有关键字为20011930的记录，则查找不成功。的记录，则查找不成功。学号学号姓名姓名性别性别入学总分入学总分录取专业录取专业 20010983张三张三女女438计算机计算机20010984李四李四男男430计算机计算机20010985王五王五女女445计算机计算机 20010998张三张三男男458计算机计算机 招生录取登记表招生录取登记表例：例：7如何进行查找？如何进行查找？在一个结构中查找某个数据元素的过程依赖于这个数据元素在结构中所处在一个结构中查找某个数据元素的过程依赖于这个数据元素在结构中所处的地位。的地位。即：对查找表进行查找的方法取决于表中数据元素依何种关系组织在一起。即：对查找表进行查找的方法取决于表中数据元素依何种关系组织在一起。（这个关系是人为加上的。因为查找表中数据元素之间原本仅存在（这个关系是人为加上的。因为查找表中数据元素之间原本仅存在“同属于一同属于一个集合个集合”的松散关系）。的松散关系）。例：查英文单词。例：查英文单词。字典是按单词的字母在字母表中的次序编排的，则查找时不需要从字典字典是按单词的字母在字母表中的次序编排的，则查找时不需要从字典中第一个单词比较起，中第一个单词比较起，而只要根据待查单词中每个字母在字母表中的位置查而只要根据待查单词中每个字母在字母表中的位置查到该单词。到该单词。字典这种查找表的数据元素之间原本仅存在着字典这种查找表的数据元素之间原本仅存在着“同属于一个集合同属于一个集合”的松的松散散关系，给查找带来不便。关系，给查找带来不便。对字典按单词的字母在字母表中的次序进行编排，就是对字典这种查找对字典按单词的字母在字母表中的次序进行编排，就是对字典这种查找表人为加上的一种关系，以便按某种规则进行查找。表人为加上的一种关系，以便按某种规则进行查找。8总之：总之：查找的方法取决于查找表的结构。查找的方法取决于查找表的结构。由于查找表中的数据元素之间不存在明显的组织规律，由于查找表中的数据元素之间不存在明显的组织规律，因此不便因此不便于查找。于查找。为了提高查找的效率，为了提高查找的效率，需要在查找表中的元素之间人为地附加某需要在查找表中的元素之间人为地附加某种确定的关系，换句话说，种确定的关系，换句话说，用另外一种结构来表示查找表。用另外一种结构来表示查找表。9内查找和外查找：内查找和外查找：若整个查找过程全部在内存进行，则称为内查找；若在查找过程若整个查找过程全部在内存进行，则称为内查找；若在查找过程中还需要访问外存，则称为外查找。本书仅介绍内查找。中还需要访问外存，则称为外查找。本书仅介绍内查找。平均查找长度平均查找长度ASL：查找算法的效率，主要看要查找的值与关键字的比较次数，通常查找算法的效率，主要看要查找的值与关键字的比较次数，通常用平均查找长度来衡量。用平均查找长度来衡量。10 对一个含对一个含n n个数据元素的表，查找成功时：个数据元素的表，查找成功时：其中：其中：P Pi i为找到表中第为找到表中第i i个数据元素的概率，且有：个数据元素的概率，且有：C Ci i为为查查找找表表中中第第i i个个数数据据元元素素所所用用到到的的比比较较次次数数。不不同同的的查查找找方法有不同的方法有不同的C Ci i 。查查找找是是许许多多程程序序中中最最消消耗耗时时间间的的一一部部分分。因因而而，一一个个好好的的查查找找方法会大大提高运行速度。方法会大大提高运行速度。119.1 静态查找表静态查找表9.2动态查找表动态查找表9.3 哈希表哈希表本章内容：本章内容：129.1 静态查找表静态查找表131.1.顺序表的查找顺序表的查找 静态查找表的存储结构可用顺序表或线性链表表示。静态查找表的存储结构可用顺序表或线性链表表示。本节只讨论在顺序存储结构中查找的实现。本节只讨论在顺序存储结构中查找的实现。顺序查找的基本思想：顺序查找的基本思想：从表中最后一个记录开始，逐个进行记录的关键字和给定值从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字和给定值比找到所查记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。较都不等，则表明表中没有所查记录，查找不成功。14i例例 012 34567891011 513192137566475808892找找6464监视哨监视哨iiii比较次数比较次数=5 比较次数：比较次数：查找第查找第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）省去判定循环中下标越界的条件，从而节约比较时间。）省去判定循环中下标越界的条件，从而节约比较时间。（2）保存查找值的副本，查找时若遇到它，则表示查找不成功。这样在从后向）保存查找值的副本，查找时若遇到它，则表示查找不成功。这样在从后向前查找失败时，不必判断查找表是否检测完，从而达到算法统一。前查找失败时，不必判断查找表是否检测完，从而达到算法统一。上述算法中，对于有上述算法中，对于有n 个数据元素的表，给定值个数据元素的表，给定值k与表中第与表中第i 个元素的关键个元素的关键字相等，即定位第字相等，即定位第i 个记录时，需进行：个记录时，需进行：n i+1次关键字比较，即次关键字比较，即Ci=n i+1。则查找成功时，顺序查找的平均查找长度为：则查找成功时，顺序查找的平均查找长度为：顺序查找性能分析：顺序查找性能分析：对一个含有对一个含有n 个数据元素的表，查找成功时有：个数据元素的表，查找成功时有：17设每个数据元素的查找概率相等，即设每个数据元素的查找概率相等，即Pi=，则等概率情况下有：，则等概率情况下有：查找不成功时，关键字的比较次数总是查找不成功时，关键字的比较次数总是n+1次。次。算法中的基本工作就是关键字的比较，因此，查找长度的量级就是查算法中的基本工作就是关键字的比较，因此，查找长度的量级就是查找算法的时间复杂度为找算法的时间复杂度为O(n)。顺序查找缺点是当顺序查找缺点是当n很大时，平均查找长度较大，效率低；优点是对很大时，平均查找长度较大，效率低；优点是对表中数据元素的存储没有特殊要求。表中数据元素的存储没有特殊要求。182.2.有序表的查找有序表的查找以有序表表示静态查找表时，可用折半查找法来实现查找。以有序表表示静态查找表时，可用折半查找法来实现查找。折半查找的基本思想：折半查找的基本思想：在在有有序序表表中中，取取中中间间元元素素作作为为比比较较对对象象，若若给给定定值值与与中中间间元元素素的的关关键键字字相相等等，则则查查找找成成功功；若若给给定定值值小小于于中中间间元元素素的的关关键键字字，则则在在中中间间元元素素的的左左半半区区继继续续查查找找；若若给给定定值值大大于于中中间间元元素素的的关关键键字字，则则在在中中间间元元素素的的右右半半区区继继续续查查找找。不不断断重重复复上上述述查查找找过过程程，直直到到查查找找成成功功，或所查找的区域无数据元素，查找失败。或所查找的区域无数据元素，查找失败。折半查找也叫二分查找，是一种效率较高的查找方法，但前提是折半查找也叫二分查找，是一种效率较高的查找方法，但前提是表中元素必须按关键字有序（按关键字递增或递减）排列。表中元素必须按关键字有序（按关键字递增或递减）排列。19算法实现：算法实现：设表长为设表长为n，low，high和和mid分别指向待查元素所在区间的上界、下界分别指向待查元素所在区间的上界、下界和中点和中点,k为给定值为给定值。初始时，令初始时，令low=1,high=n,mid=(low+high)/2 让让k与与mid指向的记录比较指向的记录比较：若若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 92lowhighmid21例例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 21 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);#defineM500typedefstructintkey;floatinfo;JD;23折半查找的性能分析：折半查找的性能分析：从折半查找的过程看，每次查找都是以表的中点为比较对象，并以中从折半查找的过程看，每次查找都是以表的中点为比较对象，并以中点将表分割为两个子表，对定位到的子表继续作同样的操作。所以，对表点将表分割为两个子表，对定位到的子表继续作同样的操作。所以，对表中每个数据元素的查找过程，可用二叉树来描述，称这个描述查找过程的中每个数据元素的查找过程，可用二叉树来描述，称这个描述查找过程的二叉树称为判定树。二叉树称为判定树。判定树中每一结点对应表中一个记录，但结点值不是某个记录的关键判定树中每一结点对应表中一个记录，但结点值不是某个记录的关键字，而是某个记录在表中的位置序号。根结点对应当前区间的字，而是某个记录在表中的位置序号。根结点对应当前区间的中间记录中间记录，左子树对应前一子表，右子树对应后一子表。左子树对应前一子表，右子树对应后一子表。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，二次比较即可找到；二次比较即可找到；查找第三层的查找第三层的结点结点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;/查找成功查找成功elseif(LT(key,T-data.key)SearchBST(T-lchild,key,T,p);/在左子树中继续查找在左子树中继续查找elseSearchBST(T-rchild,key,T,p);/在右子树中继续查找在右子树中继续查找4230201040352523fT设 key=48fTfT22pfTfTTTTfffp43二叉排序树的查找分析：二叉排序树的查找分析：在二叉排序树上查找其关键字等于给定值结点的过程，恰是走了一条在二叉排序树上查找其关键字等于给定值结点的过程，恰是走了一条从根结点到该结点的路径的过程。从根结点到该结点的路径的过程。含有含有n个结点的二叉树是不唯一的，个结点的二叉树是不唯一的，如如何来进行查找分析呢？何来进行查找分析呢？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因此，二叉排序树的平均查找长度和二叉树的形态有关。因此，二叉排序树的平均查找长度和二叉树的形态有关。最好情况下，二叉排序树在生成过程中，树的最好情况下，二叉排序树在生成过程中，树的形态比较均匀形态比较均匀，其最，其最终得到的是一颗形态与二分查找的判定树相似的二叉排序树，如图终得到的是一颗形态与二分查找的判定树相似的二叉排序树，如图(a)所示。所示。最坏情况下，二叉排序树通过一个有序表的最坏情况下，二叉排序树通过一个有序表的n个结点依次插入生成个结点依次插入生成的，此时所得的二叉排序树为一颗深度为的，此时所得的二叉排序树为一颗深度为n的的单支树单支树，如图，如图(b)所示。它所示。它的平均查找长度和单链表的顺序查找相同，也是（的平均查找长度和单链表的顺序查找相同，也是（n+1）/2。对均匀的二叉排序树进行插入或删除结点后，应对其进行调整，使对均匀的二叉排序树进行插入或删除结点后，应对其进行调整，使其依然保持均匀。其依然保持均匀。45(3)(3)二叉排序树的插入算法二叉排序树的插入算法根据动态查找表的定义，插入操作在查找不成功时才进行。根据动态查找表的定义，插入操作在查找不成功时才进行。若二叉排序树为空树，则新插入的结点为新的根结点；否则，新若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。4512533372410061907820例如：在右图给定的二叉排例如：在右图给定的二叉排序树中插入结点序树中插入结点2046 StatusInsertBST(BiTree&T,ElemTypee)/当二叉排序树中不存在关键字等于当二叉排序树中不存在关键字等于 e.key 的数据元素时，插入元素值为的数据元素时，插入元素值为 e的结点，并返回的结点，并返回 TRUE;否则，不进行插入并返回否则，不进行插入并返回 FALSE。if(!SearchBST(T,e.key,NULL,p)/如果查找不成功，才进行插入如果查找不成功，才进行插入else/如果查找成功，则不进行插入如果查找成功，则不进行插入returnFALSE;47s=(BiTree)malloc(sizeof(BiTNode);/为新结点分配空间为新结点分配空间s-data=e;s-lchild=s-rchild=NULL;if(!p)T=s;/插入插入s为新的根结点为新的根结点elseif(LT(e.key,p-data.key)p-lchild=s;/插入插入*s为为*p的左孩子的左孩子elsep-rchild=s;/插入插入*s为为*p的右孩子的右孩子returnTRUE;/插入成功插入成功48(4)(4)二叉排序树的删除算法二叉排序树的删除算法 和插入相反，删除在查找成功之后进行，并且要求删除二叉排序树和插入相反，删除在查找成功之后进行，并且要求删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。上某个结点之后，仍然保持二叉排序树的特性。可分三种情况讨论：可分三种情况讨论：1）被删除的结点是叶子；）被删除的结点是叶子；2）被删除的结点只有左子树或者只有右子树；）被删除的结点只有左子树或者只有右子树；3）被删除的结点既有左子树，也有右子树。）被删除的结点既有左子树，也有右子树。4950308020908540358832被删除的结点是叶子结点。被删除的结点是叶子结点。例如例如:被删关键字被删关键字=2088其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空”5050308020908540358832被删除的结点只有左子树或者只有右子树被删除的结点只有左子树或者只有右子树其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为 “指向被删除结点的左子树指向被删除结点的左子树或右子树或右子树”。被删关键字被删关键字=40805150308020908540358832被删除的结点既有左子树，也有右子树。被删除的结点既有左子树，也有右子树。4040以其前驱替代之，然后再删除该前驱结点。以其前驱替代之，然后再删除该前驱结点。被删结点被删结点前驱结点前驱结点被删关键字被删关键字=5052StatusDeleteBST(BiTree&T,KeyTypekey)/若二叉排序树若二叉排序树 T T 中存在其关键字等于中存在其关键字等于 key key 的数据元素，则删除该数据的数据元素，则删除该数据 元素结点，并返回函数值元素结点，并返回函数值 TRUETRUE，否则返回函数值否则返回函数值 FALSEFALSE。if(!T)/若若 T T为空为空returnFALSE;/不存在关键字等于不存在关键字等于 key key 的数据元素的数据元素 elseif(EQ(key,T-data.key)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其中删除操作过程如下所描述：其中删除操作过程如下所描述：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-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一个无序序列可以通过构造二叉排序树而成为一个有序序列。一个无序序列可以通过构造二叉排序树而成为一个有序序列。每次插入新结点都是二叉排序树上新的叶子结点，不必移动每次插入新结点都是二叉排序树上新的叶子结点，不必移动其它结点，仅需改动某个结点指针，由空变为非空即可。其它结点，仅需改动某个结点指针，由空变为非空即可。59#includetypedefintTElemType;typedefstructBiTNode/结点结构结点结构TElemTypedata;structBiTNode*lchild,*rchild;/左、右指针左、右指针BiTNode,*BiTree;生成二叉排序树的算法：生成二叉排序树的算法：60voidInsBST(BiTree&T,TElemTypeK)BiTNode*f,*p;p=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;/申请一个新结点申请一个新结点，把输入的值放入新结点，把输入的值放入新结点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;printf(请输入一个整数关键字请输入一个整数关键字(输入输入0时结束输入时结束输入)：);scanf(%d,&K);while(K)InsBST(T,K);printf(“请输入下一个整数关键字请输入下一个整数关键字(输入输入0时结束输入时结束输入)：);scanf(%d,&K);returnT;voidmain()CreateBST();62例如例如:548254821是平衡树是平衡树不是平衡树不是平衡树平衡二叉树的定义：平衡二叉树的定义：又称又称AVL树树。它或者是一棵空树，或者是具有下列性质的二叉树：。它或者是一棵空树，或者是具有下列性质的二叉树：1）它的左子树和右子树高度之差的绝对值不超过）它的左子树和右子树高度之差的绝对值不超过1；2）它的左子树和右子树都是平衡二叉树。）它的左子树和右子树都是平衡二叉树。2.二叉平衡树二叉平衡树63二叉树上结点的平衡因子：二叉树上结点的平衡因子：为该结点的左子树的深度减去它的右子树的深度。为该结点的左子树的深度减去它的右子树的深度。平衡二叉树上所有结点的平衡因子只可能是：平衡二叉树上所有结点的平衡因子只可能是：-1、0、16465在插入过程中，采用平衡旋转技术。在插入过程中，采用平衡旋转技术。例如：依次插入的关键字为例如：依次插入的关键字为 5,4,2,8,6,95,4,2,8,6,95424258665842向右旋转一次先向右旋转再向左旋转构造二叉平衡树构造二叉平衡树的方法：的方法：66426589642895向左旋转一次67当平衡的二叉排序树因插入结点而失去平衡时，仅需对离插入结点当平衡的二叉排序树因插入结点而失去平衡时，仅需对离插入结点最近的最近的最小不平衡子树最小不平衡子树进行平衡旋转处理即可。进行平衡旋转处理即可。平衡旋转处理可分为下列平衡旋转处理可分为下列4种情况：种情况：（1）单向）单向右右旋（顺时针）旋（顺时针）（2）单向）单向左左旋（逆时针）旋（逆时针）（3）先左后右先左后右双向旋转双向旋转（4）先右后左先右后左双向旋转双向旋转68 例例：已已知知一一棵棵平平衡衡二二叉叉排排序序树树如如图图（a）所所示示。在在A的的左左子子树树的的左左子子树树上上插插入入15后后，导导致致失失衡衡，如如图图（b）所所示示。为为恢恢复复平平衡衡并并保保持持二二叉叉排排序序树树的的特特性性，可可将将A改改为为B的的右右子子，B原原来来的的右右子子改改为为A的的左左子子，如如图图（c）所所示示。这这相相当当于于以以B为轴，对为轴，对A做了一次顺时针旋转做了一次顺时针旋转。不平衡二叉树的调整不平衡二叉树的调整(1)69例例：已已知知一一棵棵平平衡衡二二叉叉排排序序树树如如图图（a）所所示示。在在A的的右右子子树树B的的右右子子树树上上插插入入70后后，导导致致失失衡衡，如如图图（b）所所示示。为为恢恢复复平平衡衡并并保保持持二二叉叉排排序序树树的的特特性性，可可将将A改改为为B的的左左子子，B原原来来的的左左子子改改为为A的的右右子子，如如图图（c）所所示示。这这相相当当于于以以B为轴，为轴，对对A做了一次逆时针旋做了一次逆时针旋转。转。不平衡二叉树的调整不平衡二叉树的调整(2)70例例：已已知知一一棵棵平平衡衡二二叉叉排排序序树树如如图图（a）所所示示。在在A的的左左子子树树B的的右右子子树树上上插插入入45后后，导导致致失失衡衡，如如图图（b）所所示示。为为恢恢复复平平衡衡并并保保持持二二叉叉排排序序树树的的特特性性，可可首首先先将将B改改为为C的的左左子子，而而C原原来来的的左左子子改改为为B的的右右子子；然然后后将将A改改为为C的的右右子子，C原原来来的的右右子子改改为为A的的左左子子，如如图图（c）所所示示。这这相相当当于于对对C做做了了一一次次逆逆时时针针旋旋转转，对对A做做了了一一次次顺顺时时针针旋旋转。转。71不平衡二叉树的调整不平衡二叉树的调整(3)72 例例：已已知知一一棵棵平平衡衡二二叉叉排排序序树树如如图图（a）所所示示。在在A的的右右子子树树的的左左子子树树上上插插入入55后后，导导致致失失衡衡，如如图图（b）所所示示。为为恢恢复复平平衡衡并并保保持持二二叉叉排排序序树树的的特特性性，可可首首先先将将B改改为为C的的右右子子，而而C原原来来的的右右子子改改为为B的的左左子子；然然后后将将A改改为为C的的左左子子，C原原来来的的左左子子改改为为A的的右右子子，如如图图（c）所所示示。这这相相当于对当于对C做了一次顺时针旋转，做了一次顺时针旋转，对对A做了一次逆时针旋转。做了一次逆时针旋转。73不平衡二叉树的调整不平衡二叉树的调整(4)74 在在二叉二叉平衡树上进行查找的过程和二叉排序树相同，因此，查找过程平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡树的深度。中和给定值进行比较的关键字的个数不超过平衡树的深度。二叉平衡树的查找性能分析：二叉平衡树的查找性能分析：问，含问，含 n n 个关键字的二叉平衡树可能达到的最大深度是多少？个关键字的二叉平衡树可能达到的最大深度是多少？75n=0空树空树最大深度为最大深度为0n=1最大深度为最大深度为1n=2最大深度为最大深度为2n=4最大深度为最大深度为3n=7最大深度为最大深度为4先看几个具体情况先看几个具体情况:76反过来问，深度为反过来问，深度为 h h 的二叉平衡树中所含结点的最小值的二叉平衡树中所含结点的最小值 N Nh h 是多少？是多少？h=0N0=0h=1h=2h=3一般情况下一般情况下N1=1N2=2N3=4Nh=Nh-1+Nh-2+1利用归纳法可证得利用归纳法可证得Nh=Fh+2-177 因此，在二叉平衡树上进行查找时，查找过程中和给定值进行比较的关因此，在二叉平衡树上进行查找时，查找过程中和给定值进行比较的关键字的个数和键字的个数和 log(n)log(n)相当。即：在二叉平衡树上进行查找的时间复杂度为相当。即：在二叉平衡树上进行查找的时间复杂度为Olog(n)。由此推得，深度为由此推得，深度为 h h 的二叉平衡树中所含结点的最小值的二叉平衡树中所含结点的最小值 N Nh h =h+2h+2/5-1/5-1。反之，含有反之，含有 n n 个结点的二叉平衡树能达到的最大深度为：个结点的二叉平衡树能达到的最大深度为：h hn n=log=log(5(n+1)-25(n+1)-2。789.3 哈希表哈希表791.什么是哈希表什么是哈希表以上讨论的查找方法，由于数据元素的存储位置与关键字之间不存在以上讨论的查找方法，由于数据元素的存储位置与关键字之间不存在确定的关系，因此，查找时，需要进行一系列对关键字的查找比较，即查确定的关系，因此，查找时，需要进行一系列对关键字的查找比较，即查找算法是建立在比较的基础上的，查找效率由比较一次缩小的查找范围决找算法是建立在比较的基础上的，查找效率由比较一次缩小的查找范围决定。定。理想的情况是依据关键字直接得到其对应的数据元素位置，即要求关理想的情况是依据关键字直接得到其对应的数据元素位置，即要求关键字与数据元素间存在一一对应关系，通过这个关系，能很快地由关键字键字与数据元素间存在一一对应关系，通过这个关系，能很快地由关键字得到对应的数据元素位置。得到对应的数据元素位置。80例：例：11个元素的关键字分别为个元素的关键字分别为18，27，1，20，22，6，10，13，41，15，25。选取关键字与元素位置间的函数为：选取关键字与元素位置间的函数为：f(key)=keymod111.通过这个函数对通过这个函数对11个元素建立查找表如下：个元素建立查找表如下：012345678910102041186271525131222.查找时，对给定值查找时，对给定值kx通过这个函数计算出地址，再将通过这个函数计算出地址，再将kx3.与该地址单元中元素的关键字比较，若相等，查找成功。与该地址单元中元素的关键字比较，若相等，查找成功。81哈希表与哈希方法：哈希表与哈希方法：选取某个函数，依据该函数按关键字计算数据元素的存储地址，并选取某个函数，依据该函数按关键字计算数据元素的存储地址，并按此地址存放数据元素；按此地址存放数据元素；查找时，查找时，由同一个函数对给定值由同一个函数对给定值kx计算出地计算出地址，址，将将kx与该地址单元中数据元素的关键字进行比较，确定查找是否与该地址单元中数据元素的关键字进行比较，确定查找是否成功，这就是哈希方法。成功，这就是哈希方法。哈希方法中使用的转换函数称为哈希函数。哈希方法中使用的转换函数称为哈希函数。哈希方法中计算的存储地址称为哈希地址或散列地址。哈希方法中计算的存储地址称为哈希地址或散列地址。按这个思想构造的查找表称为哈希表。按这个思想构造的查找表称为哈希表。82对于对于n个数据元素的集合，总能找到关键字与