数据结构第五章查找教材课件

数据结构第五章查找徐晓晖制查找是为了得到某个信息而进行的工作，也称检索p基本概念与术语p静态查找表p动态查找表p哈希表查找数据结构第五章查找徐晓晖制基本概念u关键码 关键码关键码是数据元素(或记录)中某个数据项的值，用它可以标识一个数据元素。主关键码主关键码：能唯一确定一个数据元素的关键码。次关键码次关键码：不能唯一确定一个数据元素的关键码。数据结构第五章查找徐晓晖制u查找表查找表是一种以集合为逻辑结构、以查找为核心的数据结构。查找表的基本操作：建表、查找、读表元、插入与删除静态查找表：指一经建立就基本保持不变的查找表，主要操作是检索。动态查找表：经常需要改动的查找表，常进行插入删除操作。数据结构第五章查找徐晓晖制u平均查找长度查找查找是给定一个值key，在查找表中找出关键码等于key的元素，如果找到，则查找成功成功；否则查找失败失败（主关键字）。查找效率的标准查找效率的标准是指查找过程中和关键码的平均比较次数，即平均查找长度平均查找长度ASL，定义为：数据结构第五章查找徐晓晖制5-1 线性表查找u表结构将数据元素组织为一个线性表，可以是基于数组的顺序存储或以线性链表存储Typedef int KeyType;typedef struct KeyType key;DataType other;ElemType;首先，关键码类型和数据元素类型约定如下描述：数据结构第五章查找徐晓晖制typedef struct ElemType *data;int length;SeqTable;静态查找表的顺序存储结构描述如下：静态查找表的链式存储结构及其结点类型描述如下：typedef struct node ElemType data;struct node *next;NodeType;数据结构第五章查找徐晓晖制u顺序查找基本思想是从查找表的一端开始顺序扫描，将查找表中元素的关键码同给定的值比较，如果相等，则查找成功；当扫描结束时，还未找到关键码等于给定值的元素，则查找失败。顺序查找算法顺序查找算法结束时，返回查找成功或失败的标志，若查找成功，指出找到元素的位置，否则，给出失败信息。顺序查找既适合于顺序存储的静态查找表，又适合于链式存储的静态查找。数据结构第五章查找徐晓晖制typedef int KeyType;typedef struct KeyType key;DataType other;ElemType;typedef struct ElemType *elem;int length;SeqTable;数据结构第五章查找徐晓晖制u顺序查找算法int S_Search(SeqTable*t,KeyType kx)int i;t-elem0=kx;for(i=t-length;t-elemi.key!=kx;i-);return i;int seqSearch(SeqTable*t,KeyType kx,int*p)int i；for(i=0；ilength；i+)if(t-elemi.key=kx)*p=i；return(1)；*p=i；return(0)；数据结构第五章查找徐晓晖制若找到的是第一个元素data1，则比较次数c1=n；若找到的是第i个元素datai，则比较次数ci=n-i+1；在不考虑检索失败的情况下，顺序检索的平均检索长度为 ASL=1*pn+2*pn-1+n*p1 =(1+2+n)/n (pi=1/n)=(n+1)/2 T（n)=O(n)优点是算法简单且适应面广，无论查找表中元素是否有序均可使用。缺点是平均检索长度较大，特别是当n很大时，检索效率较低。数据结构第五章查找徐晓晖制u有序表的查找l二分查找基本思想是设查找表中的元素从小到大有序，首先将给定值key与表中间位置上元素的关键码比较，如果相等，则检索成功；否则，若key小，则在查找表前半部分中继续进行二分法查找，若key大，则在查找表后半部分中继续进行二分法查找。这样，经过一次比较就缩小一半的查找区间，如此进行下去，直到检索成功或检索失败。效率较高的查找方法数据结构第五章查找徐晓晖制71418212329313538424649520123456789101112lowmidhighhigh midhighmid lowmid数据结构第五章查找徐晓晖制status BinSearch(SeqTable t,KeyType kx)int low,high,mid;int flag;low=0;high=t-length-1;while(low=high)mid=(low+high)/2;if(kxelemmid)high=mid-1;else if(kxt-elemmid)low=mid+1;else flag=mid;break;return flag;数据结构第五章查找徐晓晖制若表中元素个数n为：有 则最大检索长度为j;若则最大检索长度为j+1，所以设检索每个元素的概率相同，则平均检索长度为：T(n)=O(log2n)数据结构第五章查找徐晓晖制l插值查找类似于查英文字典的方法，在查找一个C开头的英文单词时，从字典中间的一页开始，这就是插值查找的基本思想。查找表顺序存储，数据元素的关键字在查找表中均匀分布。mid=low+kx-t.datalow.keyt.datahigh.key-t.datalow.key(high-low)时间效率为T(n)=O(log2n)数据结构第五章查找徐晓晖制l斐波纳契查找（黄金分割法）斐波纳契数列定义：设n个数据元素的有序表，且n正好是某个斐波纳契数。可用此查找方法基本思想：对于表长为F(k)-1的有序表，以相对low偏移量F(k-1)-1取中点，即mid=low+F(k-1)-1,对表进行分割，则左子表表长为F(k-1)-1，右子表表长为F(k)-1-F(k-1)-1F(k-2)-1。一直分割到查找成功或查找失败。数据结构第五章查找徐晓晖制u分块查找分块检查找（索引顺序查找），是顺序查找的一个改进方法。数据结构第五章查找徐晓晖制索引表索引表的整个表分成三个子表，对每个子表建立一个索引项，其中包括两项内容：关键字项(其值为该子表内的最大关键字)和指针项(指示该子表的第一个记录在表中的位置)。索引表按关键字有序，表或者有序或者分块有序。分块有序指的是后一个子表中所有记录的关键字均大于前一个子表中的最大关键字。设n个数据元素查找表分为m个子表，分块检索的平均检索长度为数据结构第五章查找徐晓晖制5-2 哈希表查找哈希表查找法哈希表查找法即即散列法散列法又称为杂凑法杂凑法或关键码关键码地址转换法地址转换法。用散列法表示的查找表称为（哈希表）散列表散列表。散列函数使每个关键码都和结构中存储位置对应,这样的一个对应关系称为散列散列(哈希哈希Hash)函数函数。关键码关键码 存储地址存储地址h22113251527618412010012345678910例18,27,1,20,22,6,10,13,41,15,25h(key)=key mod 11u哈希表与哈希方法数据结构第五章查找徐晓晖制哈希表与哈希方法：选取某个函数，依该函数按关键码计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值kx计算地址，将kx与地址单元中元素关键码进行比较，确定查找是否成功。若key1key2，有h(key1)=h(key2)，这种现象称为冲突（碰撞）。key1和key2称为同义词。h(key)的值域所对应的地址空间称为基本区域。发生碰撞时，同义词可以存放在基本区域中未被占用的单元，也可以存放到另外的区域中数据结构第五章查找徐晓晖制负载因子负载因子：其中1时冲突不可避免。(1)构造好的哈希函数哈希方法的两个问题：(2)制定解决冲突的方案所选函数尽可能简单，以便提高转换速度。转制换出来的地址要大致均匀分布，减少空间浪费。数据结构第五章查找徐晓晖制u常用的哈希函数1.直接定址法取关键码的某个线性函数值为哈希函数。Hash(key)=a.key+b例：100,300,500,700,800,9001003005007008009000123456789Hash(key)=1/100*key数据结构第五章查找徐晓晖制2.除余法除余法除余法是取关键码被某个不大于散列表长度m的数P除后所得余数为散列地址。数p的选取，一般可选P为小于基本区域长度m的最大素数比较好。22113251527618412010012345678910例18,27,1,20,22,6,10,13,41,15,25h(key)=key mod 11数据结构第五章查找徐晓晖制3.乘余取整法Hash(key)=取上式的整数部分作为哈希地址。a一般取值为：4.中平方法 先求出关键码的平方，然后取中间几位作为地址。例如，关键码key=4731 (4731)2=22382361 h(key)=382 数据结构第五章查找徐晓晖制5.数字分析法 数字分析法数字分析法是关键码位数比存储区的地址码的位数多,这时可以对关键码的各位进行分析,丢掉分布不均匀的位留下均匀位作为地址。例如:对下列关键码集合进行关键码到地址的转换。关键码是9位的，地址是3位的，需要经过分析丢掉6位。Key h(key)000319426 326 000718309 709 000629443 643 000758615 715 000919697 997 000310329 329 数据结构第五章查找徐晓晖制6.折叠法 折叠法折叠法是将关键码分割成倍数相等的几部分，最后一部分的倍数可以短点，将这几部分叠加求和，取后几位为哈希地址。例：key=25346358705移位叠加法：将各部分的最后一位对齐相加；间界叠加法：从一端向另一端沿各部分分界来回折叠，最后一位对齐相加。分割：253 463 587 05253463587+051308253364587 50+1254Hash(key)=308Hash(key)=254数据结构第五章查找徐晓晖制例如，关键码为key=582422241，要求转换为4位的地址码。58|2422|241 移位折叠相加 移位相加 8 5 5 8 1 4 2 2 4 1 2 4 2 2 2 4 2 2 1 1 0 6 4 2 7 2 1 h1(key)=1064 h2(key)=2721折叠法折叠法是将关键码分割成几部分，其中一部分的长度等于地址码的长度，再加上其余部分，舍弃进位作为地址。+补充：数据结构第五章查找徐晓晖制u处理冲突的方法1.开放定址法开放定址法开放定址法解决碰撞的方法是在基本区域内形成一个探查序列，沿探查序列进行检索，直到找到该元素或碰到一个未被占用的地址为止。插入时，直到找到一个空单元；检索时，或检索到关健码为key的元素或检索到达一个空单元。Hi=(Hash(key)+di)MOD mi=1,2,k(km-1)其中：m为表长，di为增量序列，可有多种取法；数据结构第五章查找徐晓晖制di=1,2,3,m-1,di=i称线性探查序列线性探查序列；线性探查法线性探查法由线性探查序列,解决碰撞,称为线性探查法线性探查法。关键码集：47,7,29,11,16,92,22,8,3哈希表长为11，Hash(key)=key mod 11477012345678910291116922283数据结构第五章查找徐晓晖制二次探测法二次探测法di=12,-12,22,-22,k2,-k2(km/2)称为二次探查序列；80123456789101647,7,29,11,16,92,22,8,3477291192223数据结构第五章查找徐晓晖制双哈希函数探测法双哈希函数探测法di=i*ReHash(key),ReHash(key)是另一个散列函数，称双散列探查序列双散列探查序列；Hi=(Hash(key)+i*ReHash(key)MOD m例如:K=18,73,10,05,68,99,27,41,51,32,25,Hash(key)=key%13，ReHash(key)=key%11+118731001234567891011125689927 41513225数据结构第五章查找徐晓晖制.拉链法设基本区域长度为m，建立m条链表，将所有关键字为同义词的记录存储在同一条线性链表中。如果某个基本区域地址中没有存放查找表元素，则对应的链表为空链表；发生冲突的同组同义词存放在同一条链表中。给定元素的关键码为key，首先计算出h(key)，即确定是在第h(key)条链表中，在链表中进行插入及检索操作。数据结构第五章查找徐晓晖制K=18,73,10,05,68,99,27,41,51,32,25，h(key)=key%13 5,8,10,5,3,8,1,2,12,6,12数据结构第五章查找徐晓晖制结点类型：typedef struct Node keytype dey;struct Node *next;NodeType;哈希表：typedef NodeType *OpenHashm;数据结构第五章查找徐晓晖制#define m int CreateHashT(OpenHash l_t;DataType *eptr)int I;int d,finished;for(i=0;ikey!=0;eptr+)d=Hash(eptr-key);finished=MovElemToHashT(eptr,l_t,d);if(!finished)break;return finished;数据结构第五章查找徐晓晖制3.建立一个公共溢出区基本表溢出表数据结构第五章查找徐晓晖制5-4 动态查找表u二叉排序树查找表采用二叉排序树作为存储结构，既有较高的查找效率，又具有链式存储时元素插入、删除操作的灵活性。l二叉排序树的定义二叉排序树二叉排序树(Binary Sort Tree)或者是一棵空二叉树；或者具有下列性质的二叉树：(1).若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；(2).若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；(3).它的左右子树也分别为二叉排序树。数据结构第五章查找徐晓晖制6355425890706310456783一棵二叉排序树数据结构第五章查找徐晓晖制l二叉排序树的查找过程(1)若查找树为空，查找失败。(2)查找树为非空，将给定值kx与查找树的根结点关键码比较；(3)若相等，查找成功，结束，否则有以下两种情况：当小于根结点关键码，查找将在左子树上进行，转(1)；当大于根结点关键码，查找将在右子树上进行，转(1)；typedef struct Node KeyType key;struct Node *lchild,*rchild;BinTNode,*BiTree;数据结构第五章查找徐晓晖制int BSTSearch(BinTNode*T,BinTNode *C,BinTNode*F,KeyType x)int flag;C=T;flag=0;while(C)if(xC-key)F=C;C=C-rchild;else if(xkey)F=C;C=C-lchild;else flag=1;break;return flag;二叉排序树查找算法数据结构第五章查找徐晓晖制假设二叉排序树共有n个结点，高度是h()，算法的执行时间代价最坏为O(h)。数据结构第五章查找徐晓晖制l二叉排序树的插入操作和构造一棵二叉排序树在二叉排序树中插入新结点，要保证插入后仍是二叉排序树。插入新结点的方法是：(1).如果二叉排序树为空，则新结点为根结点。(2).如果二叉排序树为非空，则将新结点的关键码与根结点的关键码比较，若相等表示该结点已在二叉排序树中；若小于根结点的关键码，则将新结点插入到根结点的左子树中；否则，插入到根结点的左子树中。(3).子树中的插入过程和树中的插入过程相同，如此进行下去，直到找到该结点，或者直到新结点成为叶子结点为止。数据结构第五章查找徐晓晖制635542589070631045678343数据结构第五章查找徐晓晖制二叉排序树插入一个结点的算法Int InsertNode(BinTNode *T,KeyType x)BinTNode *p,*q,*s;int flag=0;p=*t;if(!BSTSearch(T,q,p,x)s=new BinTNode;s-key=kx;s-lchild=s-rchild=NULL;flag=1;if(!p)T=s;else if(xp-key)p-rchild=s;else p-lchild=s;return flag;数据结构第五章查找徐晓晖制例如：已知关键码集合K=18,73,10,05,68,99,27,41,51,32,25，写出二叉排序树的构造过程1873100568992741513225数据结构第五章查找徐晓晖制Status CreatBST(BinTNode*T)KeyType x;T=NULL;cinx;while(x!=-1)InsertNode(T,x);cinx;return success;数据结构第五章查找徐晓晖制l二叉排序树的删除操作二叉排序树的删除操作在二叉排序树中删除一个指定结点，删除结点后的二叉树还是一棵二叉排序树。设待删除结点为p，其双亲结点为f，分以下三种情况：(1)p是叶结点。(2)p是单分支结点，即只有左子树pl或右子树pr,只需用子树根结点代替p结点。(3)p有左右子树时,按中序遍历保持有序进行调整。FPfpPL数据结构第五章查找徐晓晖制两种调整方法：直接令p结点的右孩子p1为f相应的子树，将p的 原左子树pL作为以pr为根的子树中序遍历的第一 个结点的左子树。用p结点的直接后继pr(或直接前驱)替换p结点。再用(2)方法删去pr。数据结构第五章查找徐晓晖制FPfpPLP1P2PJPRS1S2SJSRFPpPLP1P2PJPRS1S2SJSRfPR数据结构第五章查找徐晓晖制二叉排序树删除算法int DeleteNode(BinTNode *T,KeyType x)BinTNode *p,*q,*s,*f;int flag=0;p=T;if(BSTSearch(T,q,p,x)if(q)if(q-lchild=NULL&q-rchild=NULL)if(p)if(p-lchild=q)p-lchild=NULL;else p-rchild=NULL;else T=NULL;free(q);数据结构第五章查找徐晓晖制else if(q-lchild=NULL)if(p)if(p-lchild=q)p-lchild=q-rchild;else p-rchild=q-rchild;else T=q-rchild;free(q);else if(q-rchild=NULL)if(p)if(p-lchild=q)p-lchild=q-lchild;else p-rchild=q-lchild;else T=q-lchild;free(q);数据结构第五章查找徐晓晖制else child=q-rchild;while(child-lchild)child=child-lchild;child-lchild=q-lchild;if(p)if(p-lchild=q)p-lchild=q-rchild;else p-rchild=q-rchild;else T=q-rchild;free(q);return success;return failure;数据结构第五章查找徐晓晖制在二叉排序树上查找关键字实际上是走了一条从根结点到某个结点的路径的过程，比较的次数等于路径长度加1。因此，比较的次数不超过树的深度。但是具有n个结点的二叉树可以有不同的形态，因此，对于不同形态的二叉排序树，其平均查找长度也是不同的。最坏的情况下蜕变为单支树，此时的平均查找长度为（n+1)/2。数据结构第五章查找徐晓晖制u平衡二叉树（AVL树）l平衡二叉树的定义是一棵空树或是具有下列性质的二叉排序树：它的左子树和右子树都是平衡二叉树，且左子树和右子树高度之差的绝对值不超过1.72418530607891426550477241853060789142非平衡二叉树平衡二叉树3-30000000002-2011-101数据结构第五章查找徐晓晖制平衡因子：结点左右子树高度之差的数字称为结点的平衡因子在平衡二叉树上插入或删除结点后，得进行平衡调整左单旋转（RR型）aBhDhEhcxaBhDhEhcx数据结构第五章查找徐晓晖制27510-1BA27510-1BA73-2735100BA27051270-1BA1007341099730BA510274101000-10990-1-1-2数据结构第五章查找徐晓晖制acDhEhB hxacDhEhB hx右单旋转（LL型）数据结构第五章查找徐晓晖制271001BA271001BA052271000BA050512701BA10005180003011251270BA1000518003010数据结构第五章查找徐晓晖制先左后右双向旋转（LR型）先右后左双向旋转（RL型）数据结构第五章查找徐晓晖制uB树和树和B树树B树和B树用于外存文件的索引。一棵m阶的B树，或为空树，或是满足下列特性的m叉树：（1）树中每个结点至多有m棵子树；（2）除根之外的所有分支结点至少有m/2棵子树；（3）若根结点不是叶子结点，则至少有两棵子树；（4）有j个子女的非叶结点中恰好有j-1个关键码，且 按递增顺 序排列，结点中包含的信息为 (p0,k1,p1,k2,kj-1,pj)lB树的定义数据结构第五章查找徐晓晖制其中ki(i=1,.,j-1)为关键码，且ki ki+1(i=1,j-2);pi(i=0,j-1)为指向子树根结点的指针，且pi-1所指子树中所有结点的关键码均小于ki(i=1,j-1),pj-1所指子树中所有结点的关键码均大于kj-1,j（m/2=j elem=*e_addr;q-next=*(l_t+h_addr);*(l_t+h_addr)=q;status=1;return status;数据结构第五章查找徐晓晖制设有100个数据元素，采用折半搜索时，最大比较次数为()。A.6 B.7 C.8 D.10 假设有K个关键字互为同义词，若用线性探查法把这K个关键字存入散列表中，至少需要进行（）次探测。AK-1 BK CK+1 DK(K+1)/2 在采用线性探查法处理冲突所构成的散列表上进行查找，可能要探测到多个位置，在查找成功的情况下，所探测的这些位置上的值（）。A一定是同义词 B一定都不是同义词C都相同 D不一定都是同义词数据结构第五章查找徐晓晖制在各种检索方法中，平均检索长度与结点个数n无关的检索方法是 。数据结构第五章查找徐晓晖制设有一组关键字3,5,7,9,11,13,15,17采用哈希函数:H(key)=key mod 7表长为10,用开放地址法的线性探测再散列方法Hi=(H(key)+di)mod 10(di=1,2,3,)解决冲突。对该关键字序列构造哈希表并计算其平均查找长度。数据结构第五章查找徐晓晖制设散列表长度为设散列表长度为1111，散列函数，散列函数。给定关键码序列为：。给定关键码序列为：1 1，1313，1212，3434，3838，3333，2727，2222。试画出用拉链法解决冲突时所构造的散列表。试画出用拉链法解决冲突时所构造的散列表。