数据结构 查找PPT课件

1,华中科技大学计算机学院,数据结构,2,第九章查找查找表:由同一类型的数据元素（记录）组成的集合。记作：ST=a1,a2,.,an,序号,1234n,关键字:可以标识一个记录的数据项主关键字:可以唯一地标识一个记录的数据项次关键字:可以识别若干记录的数据项,学生成绩表,数据项1(主关键字),数据项2,数据项5,3,查找表的操作:生成查找表查找元素(记录)x在是否在表ST中查找元素(记录)x的属性插入新元素(记录)x删除元素(记录)x.,4,查找-根据给定的某个关键字值，在查找表中确定一个其关键字等于给定值的记录或数据元素。设k为给定的一个关键字值，R1.n为n个记录的表,若存在Ri.key=k,1in,称查找成功；否则称查找失败。静态查找:查询某个特定的元素，检查某个特定的数据元素的属性,不插入新元素或删除元素(记录)。动态查找:在查找过程中，同时插入查找表中不存在的数据元素(记录)。,5,查找表的类型及其查找方法(1)静态查找表顺序表，用顺序查找法线性链表，用顺序查找法有序的顺序表，用：折半查找法；*斐班那契查找法；插值查找法；索引顺序表/分块表，用分块查找法。(2)动态查找表二叉排序树,平衡二叉树(AVL树）*B树,B+树,键树(3)哈希(Hash)表,6,平均查找长度-查找一个记录时比较关键字次数的平均值。nASL=PiCii=1Pi-查找ri的概率Ci-查找ri所需比较关键字的次数,7,0123maxsize,elemkeyname.,监视哨,9.1静态查找表9.1.1顺序表与顺序查找法1.顺序表的描述,8,例1元素类型为记录(结构)#definemaxsize100/表长100typedefstructnodekeytypekey；/关键字类型charname6；/姓名./其它ElemType；typedefstructElemTypeelemmaxsize+1；/maxsize+1个记录,/elem0为监视哨intlength;SSTable;SSTableST1,ST2;,9,0123456maxsizelength,监视哨,例2元素类型为整型#definemaxsize100/表长100typedefintElemType；typedefstructElemTypeelemmaxsize+1；/maxsize+1个记录,/elem0为监视哨intlength;SSTable;SSTableST1,ST2;,10,2.顺序查找法(sequentialsearch)算法设计算法1：假定不使用监视哨elem0基本思想：将关键字k依次与记录的关键字:elemn.key,elemn-1.key，.,elem1.key比较。如果找到一个记录elemi,有:elemi.keyk(1in)，则查找成功，停止比较,返回记录的下标i；否则,查找失败,返回0。,11,输入：查找表ST，查找条件（关键字）k输出：成功时：记录序号，失败时：0intsequsearch(SSTableST,keytypek)inti=ST.length；/从第n个记录开始查找while(i=1,35,(5)二叉排序树的查找算法(返回值失败：NULL成功：非NULL，结点指针）a)递归算法structnode*search_tr(structnode*t,keytypek)if(t=NULL)returnNULL；/查找失败elseif(k=t-data.key)returnt；/查找成功elseif(kdata.key)returnsearch_tr(t-lchild,k)；/查左子树elsereturnsearch_tr(t-rchild,k)；/查右子树,36,b)非递归算法structnode*search_tree(structnode*t,keytypek)while(t!=NULL)if(k=t-data.key)returnt；/查找成功elseif(kdata.key)t=t-lchild；/查左子树elset=t-rchild；/查右子树returnt；/查找失败,37,(6)二叉排序树的删除,在二叉排序树中删除一个结点时，必须将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会失去。为保证在删除节点后二叉排序树的性质不会丢失:删除叶结点，只需将其双亲结点指向它的指针置空，再释放它即可。被删结点缺左子树（或右子树），可以用被删节点的右子树（或左子树）顶替它的位置，再释放它。,38,被删结点左、右子树都存在，可以在它的右子树中寻找中序下的第一个结点(关键值最小),用它的值填补到被删结点中，再来处理这个结点的删除问题。,53,78,65,17,87,09,23,45,删除45,缺右子树,用左子树顶替,53,78,65,17,87,09,23,39,88,53,78,88,17,94,09,23,删除78,缺左子树,用右子树顶替,53,94,88,17,09,23,53,78,81,17,94,09,45,删除78,在右子树上找中序下第一个结点填补,23,65,53,81,88,17,94,09,45,23,65,40,(7)查找性能分析最好情况(为满二叉树）n+1ASL=-log2(n+1)-1=O(log2n)n最坏情况(为单枝树):ASL=(1+2+.+n)/n=(n+1)/2平均值:ASLO(log2n),58,28,49,30,45,58,15,19,10,18,11,4,88,69,79,64,75,65,60,满二叉树,单枝树,ASL=(15+1)/15*log2(15+1)-13.3ASL=(1+2+3+4)/4=2.5,41,2.平衡二叉树(高度平衡二叉树）AVL树：由G.M.Adelson-Velskii和E.M.Landis提出。结点的平衡因子：结点的左右子树的深度之差。平衡二叉树：任意结点的平衡因子的绝对值小于等于1的二叉树。,T1T2T3T4,T5,0,1,0,2,-1,0,0,0,-1,1,2,1,0,0,-2,（1）AVL树的定义,42,（2）AVL树的存储结构：,typedefintDataType;/结点数据类型typedefstructnode/AVL树结点定义DataTypedata;/结点数据域intbalance;/结点平衡因子域structnode*leftChild,*rightChild;/结点左、右子树指针域AVLNode;typedefAVLNode*AVLTree;/AVL树,43,如果在一棵平衡的二叉搜索树中插入一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化。平衡化旋转有两类：单旋转(左旋和右旋)双旋转(左平衡和右平衡)每插入一个新结点时,AVL树中相关结点的平衡状态会发生改变。因此,在插入一个新结点后，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子。,（3）平衡化旋转,44,如果在某一结点发现高度不平衡，停止回溯。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。如果这三个结点处于一条直线上，则采用单旋转进行平衡化。单旋转可按其方向分为左单旋转和右单旋转,其中一个是另一个的镜像，其方向与不平衡的形状相关。如果这三个结点处于一条折线上，则采用双旋转进行平衡化。双旋转分为先左后右和先右后左两类。,45,右单旋转,左单旋转,左右双旋转,右左双旋转,46,在子树E中插入新结点，该子树高度增1导致结点A的平衡因子变成-2，出现不平衡。沿插入路径检查三个结点A、C和E。它们处于方向为“”的直线上，需做左单旋转。以结点C为旋转轴，让结点A逆时针旋转。,（a）左单旋转(RotateLeft),h,h,h,A,C,E,B,D,h,h,h+1,B,A,C,E,D,h,h,h+1,C,E,A,B,D,-1,-2,0,-1,0,0,47,在子树D中插入新结点，该子树高度增1导致结点A的平衡因子变成+2，出现不平衡。沿插入路径检查三个结点A、B和D。它们处于方向为“/”的直线上，需做右单旋转。以结点B为旋转轴，让结点A顺时针旋转。,（b）右单旋转(RotateRight),h,h,h,A,C,E,B,D,h,h+1,B,A,C,E,D,h,h,h+1,C,E,A,B,D,h,0,0,0,+1,+1,+2,48,在子树F或G中插入新结点，该子树的高度增1。结点A的平衡因子变为+2，发生了不平衡。,（c）先左后右双旋转(RotationLeftRight),插入,0,0,+1,+2,-1,+1,h,h,A,C,E,D,h-1,h,h,A,h,B,C,E,D,B,左单旋转,F,G,F,G,h-1,h-1,49,插入,0,0,+1,+2,-1,+1,h,h,A,C,E,D,h-1,h,h,A,h,B,C,E,D,B,左单旋转,F,G,F,G,从结点A起沿插入路径选取3个结点A、B和E，它们位于一条形如“”的折线上，因此需要进行先左后右的双旋转。以结点E为旋转轴，将结点B逆时针旋转。,h-1,h-1,50,0,0,+2,0,0,-1,h,h,A,C,E,D,+2,h,h,h,A,h,B,C,E,D,B,右单旋转,F,G,F,G,h-1,h-1,再以结点E为旋转轴，将结点A顺时针旋转。,51,右左双旋转是左右双旋转的镜像在子树F或G中插入新结点，该子树高度增1，A的平衡因子变为+2，发生了不平衡。,（d）先右后左双旋转(RotationRightLeft),插入,右单旋转,-1,0,0,0,+1,0,h,h,A,C,E,D,B,F,G,-2,0,0,0,h,h,A,C,E,h,B,F,G,D,h-1,h-1,h-1,52,从结点A起沿插入路径选取3个结点A、C和D，它们位于一条形如“”的折线上，因此需要进行先右后左的双旋转。以结点D为旋转轴，将结点C顺时针旋转。,插入,右单旋转,-1,0,0,0,+1,0,h,h,A,C,E,D,B,F,G,-2,0,0,0,h,h,A,C,E,h,B,F,G,D,h-1,h-1,h-1,53,再以结点D为旋转轴，将结点A逆时针旋转。,0,0,-2,0,+1,0,h,h,A,C,E,-2,h,h,h,A,h,B,C,E,D,B,左单旋转,F,G,F,G,D,h-1,h-1,54,在向一棵本来是高度平衡的AVL树中插入一个新结点时，如果树中某个结点的平衡因子的绝对值|balance|1，则出现了不平衡，需要做平衡化处理。算法从一棵空树开始，通过输入一系列对象关键码，逐步建立AVL树。在插入新结点时使用平衡旋转方法进行平衡化处理。,（3）AVL树的插入,55,16,16,例，输入关键码序列为16,3,7,11,9,26,18,14,15，插入和调整过程如下。,0,3,16,3,+1,0,7,0,-1,+2,左右双旋,7,3,16,0,0,0,7,3,11,0,+1,-1,7,3,16,16,11,9,0,+1,+2,右单旋,3,7,16,9,0,0,0,-1,3,7,11,26,9,16,11,0,-1,-1,-2,-2,56,18,18,0,3,16,3,+1,0,16,0,-2,右左双旋,7,3,9,0,0,0,18,26,11,+1,7,3,26,16,11,9,+1,左单旋,9,7,16,14,0,0,-1,7,11,26,26,9,-1,-1,11,57,15,18,-2,3,18,16,+2,左右双旋,7,3,0,0,0,11,7,14,9,+1,16,15,0,-1,11,26,26,14,-1,+2,9,从空树开始的建树过程,58,平衡二叉树、二叉排序树、平衡二叉排序树的区别：,48,50,35,10,20,41,45,60,平衡二叉排序树,68,70,65,10,20,41,45,80,平衡二叉树,68,80,75,10,41,45,85,二叉排序树,-2,-1,-1,0,1,-1,-1,1,-1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,59,静态和动态查找表查找方法静态查找表和动态查找表通过比较关键字进行查找：（1）顺序表，对数据元素的存储一般有两种形式：(a)是按到来次序连续存放，查找时顺序比较查找；(b)按关键字的相对关系整理后以递增或递减形式连续存放，则查找时使用顺序法或二分法比较查找。（2）二叉排序树，从根开始进行比较查找。不足：查找时无法根据关键字的值估计数据元素可能在的位置。,60,9.3哈希(Hash)表和哈希法存储数据元素时，利用一个Hash函数根据数据元素的关键字计算出该数据元素的存储位置，查找时，也是根据给定的数据元素的关键字计算出该数据元素可能存储位置，这样一来，存储和查找的效率相当高，哈希表也称为散列表，其数据元素的存储一般是不连续的。通过Hash函数计算出的地址称为哈希地址或散列地址。,61,9.3.1哈希表相关术语Hash函数实现的是将一组关键字映象到一个有限的地址区间上，理想的情况是不同的关键字得到不同的地址。设K1和K2为关键字,若K1K2,H(K1)=H(K2),则称K1,K2为同义词,K2与K1发生了冲突例设H(k)=k%17k1=5k2=22H(5)=5%17=5H(22)=22%17=5H(5)=H(22)=55和22是同义词,5和22发生冲突,62,9.3.1哈希表相关术语采用哈希表进行存储和查找需要着重考虑两个问题：（a）选择一个好的哈希（散列）函数；（b）选择一种解决冲突（碰撞）的方法。,63,例1人口统计表,序号(地址)年龄人数(万),1234150,H(key)=key=地址H(年龄）=年龄,key,9.3.2构造哈希函数的方法1.直接定址法取关键字或关键字的某个线性函数值为哈希地址H(key)=keyH(key)=a.key+b,64,例2学生成绩表,1234n,key,序号(地址)学号姓名性别数学外语,H(key)=key-200040=地址H(学号)=学号-200040,65,例3标识符表,1234562526,序号标识符(key),H(key)=key的第一个字母在字母表中的序号key=ABCCADDATFOXYABZOOH(key)=13462526,66,2.除留余数法设哈希表HT0.m-1的表长为m，哈希地址为key除以p所的的余数：H(key)=keyMODp/PASCAL语言H(key)=key%p/C语言其中：MOD,%为“取模”或“求余”p=m，p为接近m的质数(素数),如：3,5,7,11,13,17,19,23,29,31,37.或不包含小于20的质因子的合数，如：713(=23*31),67,例1设m=130,取p=127,H(key)=key%127,012.129,例2设m=256取p=251H(key)=key%251,012.255,68,例设哈希表的地址范围为020,哈希函数为H(K)=K%19输入关键字序列：39,22,21,37,36,38,19,解决冲突的方法为线性探测再散列(哈希),构造哈希表HT0.20。,关键字KH(K)=K%193939%19=12222%19=32121%19=23737%19=183636%19=173838%19=01919%19=019与38冲突,再与39,21,22冲突,存入HT4,01234517181920,HT0.20,39,22,21,37,38,36,19,69,再输入17,56,5517%19=1717与36冲突,再与37冲突,存入HT19。56%19=1856与37冲突,再与17冲突,存入HT20。55%19=1755与36冲突,再与37,17,56冲突,再与38,39,21,22,19冲突,存入HT5。对于H(k)=k%19，所有的19a+b为同义词,0b19如：5,24,43,62,81,.,01234517181920,HT0.20,key,70,3.平方取中法-取关键字平方后的中间某几位为哈希地址,即：H(k)=取k2的中间某几位数字,例.设哈希表为HT0.99,哈希函数为：H(K)=取k2的中间2位数,输入关键字序列：39,21,6,36,38,13,用线性探测再散列法解决冲突,构造HT0.99。Kk2H(K)39152152210441446003603361296293814444413016916,03162944455299,key,71,4.折叠法将关键字分割成位数相同的几部分,然后取这几部分的叠加和作为哈希地址。,(1)边界折叠法设表地址范围为0999k1=056439527650+439+725=1814H(k1)=814k2=123486790321+486+097=907H(k2)=907k3=300600007003+600+700=1303H(k2)=303,01303814907999,HT0.999,72,4.折叠法将关键字分割成位数相同的几部分,然后取这几部分的叠加和作为哈希地址。,(2)移位折叠法(移位法)设表地址范围为0999k1=056439527056+439+527=1022H(k1)=022k2=123486790123+486+790=1399H(k2)=399k3=300600007300+600+007=907H(k2)=907,0122399907999,HT0.999,73,5.数字分析法设哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干分布均匀的位组成哈希地址。,kH(k)902006720690443134319013456145904432643290532435249061791679,145206431432524679,HT0.999,74,6.随机数法H(key)=random(key)random(key)为产生伪随机数的函数7.灵活构造哈希函数,例.设哈希表为HT0.40,哈希函数为：H(K)=取k2的中间2位数*40/99其中40/99将其0099压缩到0040之内，输入关键字序列：39,21,6,36,38,13,用线性探测再散列法解决冲突。Kk2H(K)39152152*40/99=2121044144*40/99=176003603*40/99=177592992*40/99=3738144444*40/99=1713016916*40/99=6,01361718213740,key,75,9.3.3如何解决冲突1.开放地址法(开式寻址法)假定记录Ri,RX的关键字Ki,KX为同义词，散列地址为q,Ri已存入HT0.m-1中的HTq中，则RX存入HT中的某个空位上。依次在地址:q+1,q+2,.,m-1,0,1,.,q-1中寻找一个空位，叫做线性探测再散列。(1)线性探测再散列,HT0.m-1,01q-1qq+1m-1,Ri,RX,76,课堂练习：设H(k)=k的首字母在字母表中的序号,用线性探测再散列法解决冲突，依次用下列关键字，构造哈希表HT0.28。,kH(k)A1DEC4ZMN26DAB4ZE26ANT1YY25ZOO26CAD3YES25ZY26LL12DE4,01234567121325262728,HT0.28,12345678910111213,77,例设H(k)=k的首字母在字母表中的序号，用线性探测再散列法解决冲突，依次用下列关键字，构造哈希表HT0.28。,kH(k)1A12DEC43ZMN264DAB45ZE266ANT17YY258ZOO269CAD310YES2511ZY2612LL1213DE4,012345671225262728,HT0.28,78,(2)二次探测再散列假定记录Ri和Rj的关键字Ki和Kj为同义词，散列地址为q,Ri已存入HT0.m-1中的HTq中。若依次在地址q+12,q-12,q+22,q-22,.,q+i2,q-i2,.中寻找一个空位，叫做二次探测再散列。例:设记录X和A为同义词，散列地址为50,二次探测再散列的地址序列为：51,49,54,46,59,41,66,34,75,.,HT0.99,03441464950515459667599,X,X,X,X,X,X,X,X,03441464950515459667599,79,2.链地址法将关键字为同义词的所有记录存入同一链表中。（表头插入）例设H(k)=k的首字母在字母表中的序号,用下列关键字造哈希表HT1.26,kH(k)A1DEC4ZMN26DAB4ZE26ANT1YY25ZOO26CAD3YES25ZY26LL12DE4,12345678910111213,HT1.2