搜索
第8章查找查找的基本概念静态查找表动态查找表哈希表主要知识点8.1查找的基本概念查找:查询某个关键字是否在(数据元素集合）表中的过程。也称作检索。主关键字:能够惟一区分各个不同数据元素的关键字次关键字:通常不能惟一区分各个不同数据元素的关键字查找成功:在数据元素集合中找到了要查找的数据元素查找不成功:在数据元素集合中没有找到要查找的数据元素静态查找:只查找，不改变数据元素集合内的数据元素动态查找:既查找，又改变（增减）集合内的数据元素静态查找表:静态查找时构造的存储结构动态查找表:动态查找时构造的存储结构平均查找长度:查找过程所需进行的关键字比较次数的平均值,是衡量查找算法效率的最主要标准,其数学定义为：其中，Pi是要查找数据元素出现的概率，Ci是查找相应数据元素的比较次数。定义要查找数据元素的结构体为：typedefstruct{KeyTypekey;}DataType;=×=niiiCPASL18.2静态查找表静态查找表主要有三种结构：顺序表有序顺序表索引顺序表1.顺序表在顺序表上查找的基本思想是：从顺序表的一端开始，用给定数据元素的关键字逐个和顺序表中各数据元素的关键字比较，若在顺序表中查找到要查找的数据元素，则查找成功，函数返回该数据元素在顺序表中的位置；否则查找失败，函数返回-1。查找函数设计如下：intSeqSearch(DataTypea[],intn,KeyTypekey)//在a[0]--a[n-1]中顺序查找关键码为key的数据元素//查找成功时返回该元素的下标序号；失败时返回-1{inti=0;while(in&&a[i].key!=key)i++;if(a[i].key==key)returni;elsereturn-1;}算法分析查找成功时的平均查找长度ASL成功为：=====niiniininCPASL112/)1(1成功查找失败时的平均查找长度ASL失败为2/)1(111=====ninCPASLniinii失败2.有序顺序表有序顺序表上的查找算法主要有顺序查找和折半查找两种方法。一、顺序查找有序顺序表上的顺序查找算法和顺序表上的查找算法方法类同二、二分查找（又称折半查找）算法的基本思想：先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至前半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。反之，如果key大，则缩小至后半部内查找。二分查找算法如下：intBiSearch(DataTypea[],intn,KeyTypekey)//在有序表a[0]--a[n-1]中二分查找关键码为key的数据元素//查找成功时返回该元素的下标序号；失败时返回-1{intlow=0,high=n-1;//确定初始查找区间上下界intmid;while(low=high){mid=(low+high)/2;//确定查找区间中心下标if(a[mid].key==key)returnmid;//查找成功elseif(a[mid].keykey)low=mid+1;elsehigh=mid-1;}return-1;//查找失败}算法分析查找成功时的平均查找长度ASL成功为：查找失败时的平均查找长度ASL失败为nnnninCPASLnikiiii22111log1)1(log112=====成功)1(log)1(log12211=====nnnCPASLniniii失败3.索引顺序表当顺序表中的数据元素个数非常大时，采用在顺序表上建立索引表的办法提高查找速度。把要在其上建立索引表的顺序表称作主表。主表中存放着数据元素的全部信息，索引表中只存放主表中要查找数据元素的主关键字和索引信息。8146910223418193140385466467178688085140034516610285153keylink下标索引表012345678910111213141516171819key其它域位置主表索引表结构图索引表中的数据元素由两个域构成，key域为被索引的若干个数据元素中关键字的最大值，link域为被索引的若干个数据元素中第一个数据元素的位置编号。完全索引表:和主表项完全相同，但只包含索引关键字和该数据元素在主表中位置信息的索引表二级索引表:当主表中的数据元素个数非常庞大时，按照建立索引表的同样方法对索引表再建立的索引表。二级以上的索引结构称作多级索引结构等长索引表:索引表中的每个索引项对应主表中的数据元素个数相等;反之称为不等长索引表。不等长索引表中的索引长度可随着动态插入和动态删除过程改变,因此不仅适用于静态查找问题，而且也适用于动态查找问题。相关术语假设索引表的长度为m，主表中每个子表的长度为s，并假设在索引表上和在主表上均采用顺序查找算法，则索引顺序表上查找算法的平均查找长度为：122121==smsmASL算法分析8.3动态查找表动态查找表主要有二叉树结构和树结构两种类型。二叉树结构有二叉排序树、平衡二叉树等。树结构有B-树、B+树等。1.二叉排序树一、基本概念----或是一棵空树；或者是具有如下性质的非空二叉树：（1）左子树的所有结点均小于根的值；（2）右子树的所有结点均大于根的值；（3）它的左右子树也分别为二叉排序树。二叉排序树中结点的结构体定义如下：typedefstructnode{DataTypedata;structnode*leftChild;structnode*rightChild;}BiTreeNode;3811241094039454035190146476760445600800下图所示就是一棵二叉排序树二、二叉排序树的查找算法intSearch(BiTreeNode*root,DataTypeitem){BiTreeNode*p;if(root!=NULL){p=root;while(p!=NULL){if(p-data.key==item.key)return1;if(item.keyp-data.key)p=p-rightChild;elsep=p-leftChild;}}return0;}三、插入算法插入操作要求首先查找数据元素是否在二叉排序树中存在，若存在则返回；若不存在，插入查找失败时结点的左指针或右指针上。所插新结点一定在叶结点上。插入算法设计如下:intInsert(BiTreeNode**root,DataTypeitem){BiTreeNode*current,*parent=NULL,*p;current=*root;while(current!=NULL){if(current-data.key==item.key)return0;parent=current;if(current-data.keyitem.key)current=current-rightChild;elsecurrent=current-leftChild;}/*生成新结点*/p=(BiTreeNode*)malloc(sizeof(BiTreeNode));p-data=item;p-leftChild=NULL;p-rightChild=NULL;if(parent==NULL)*root=p;elseif(item.keyparent-data.key)parent-leftChild=p;elseparent-rightChild=p;return1;}下图是调用上述插入函数依次插入数据元素4,5,7,2,1,9,8,11,3的过程。41152791384115279184527918452791452714527457454(d)(c)(b)(a)(g)(f)(e)(i)(h)五、删除算法删除操作要求首先查找数据元素是否在二叉排序树中存在，若不存在则结束；存在的情况及相应的删除方法有如下四种：(1)要删除结点无孩子结点，直接删除该结点。(2)要删除结点只有左孩子结点，删除该结点且使被删除结点的双亲结点指向被删除结点的左孩子结点。(3)要删除结点只有右孩子结点，删除该结点且使被删除结点的双亲结点指向被删除结点的右孩子结点。(4)要删除结点有左右孩子结点，分如下三步完成：首先寻找数据元素的关键字值大于要删除结点数据元素关键字的最小值，即寻找要删除结点右子树的最左结点；然后把右子树的最左结点的数据元素值拷贝到要删除的结点上；最后删除右子树的最左结点。删除过程分别如图所示1814245162038710303518142451620387303518142451620387103035181424516203071035ptrptr(a)无孩子结点(b)有左孩子结点18142451620387103035181424716203810303518142451620387103035181430516207103538ptrptr(c)有右孩子结点(d)有左右孩子结点测试程序例10-2设计一个测试二叉排序树的主函数。#includestdio.h#includestdlib.h#includemalloc.htypedefintKeyType;typedefstruct{KeyTypekey;}DataType;typedefstructnode{DataTypedata;structnode*leftChild;structnode*rightChild;}BiTreeNode;#include“BiSortTree.h”voidInTraverse(BiTreeNode*root)/*中序遍历显示二叉排序树结点信息函数*/{if(root==NULL)return;if(root-leftChild!=NULL)InTraverse(root-leftChild);printf(%d,root-data.key);if(root-rightChild!=NULL)InTraverse(root-rightChild);}voidmain(void){DataTypetest[]={4,5,7,2,1,9,8,11,3},x={9};intn=9,i,s;BiTreeNode*root=NULL;for(i=0;in;i++)Insert(&root,test[i]);InTraverse(root);s=Search(root,x);if(s==1)printf(\n数据元素%d存在！,x.key);elseprintf(\n数据元素不存在！);}程序运行建立的二叉排序树如图10-5（i）所示。程序运行结果如下：1234578911数据元素9存在！六、二叉排序树的性能分析一棵二叉排序树的平均查找长度为：其中：ni是每层结点个数；Ci是结点所在层次数；m为树深。当二叉排序树是一棵单分支退化树时，查找成功的平均查找长度和有序顺序表的平均查找长度相同，即为：===nininASL12/)1(1成功若每个数据元素的查找概率相等，则二叉排序树查找成功的平均查找长度为：)1(log)2(1211==ninASLkii成功=×=miiiCnnASL113456781064835710(a)(b)（a）满二叉排序树时，k=log2(7+1)=3，所以查找成功的平均查找长度为：717)34221(71)2(111====inASLiki成功（b）左分支退化二叉排序树时，k=n=7，所以查找成功的平均查找长度为：42/)17(2/)1(11=====nininASL成功在最坏情况下，二叉排序树的平均查找长度为O(n)。在一般情况下，二叉排序树的平均查找长度为O(log2n)。2.B_树B_树是一种平衡多叉排序树。平衡是指所有叶结点都在同一层上，从而可避免出现像二叉排序树那样的分支退化现象。因此B_树的动态查找效率更高。B_树中所有结点的孩子结点的最大值称为B_树的阶，一棵m阶的B_树或者是