第七查找PPT课件

1、1typedef struct KeyType key； / 关键字字段，可以是整型，字符串型、构造类型等 / 其它字段 ElemType；第1页/共105页2 查找速度 占用存储空间多少 算法本身复杂程度 平均查找长度ASL(Average Search Length) 为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的个元素所需比较次数为找到表中第个元素的概率，为查找表中第其中：个记录的表，对含有icpipcpASLniniiiniii111第2页/共105页3第3页/共105页4 顺序存储结构 typedef struct ElemType *elem； /数组

2、基址 int length； /表长度 S_TBL； 第4页/共105页5 链式存储结构 typedef struct NODE ElemType elem； / 结点的值域 struct NODE *next； /下一个结点指针域 NodeType； 第5页/共105页6查找过程从表的一端开始逐个进行记录的关键字和给定值的比较第6页/共105页7212) 1(11111nnnnincpASLnpniniiii则概率相等设表中每个元素的查找niiicpASLn1个记录的表，对含有第7页/共105页8 条件 有序表表中数据元素按关键字升序或降序排列 折半查找的思想 每次将待查记录所在区间缩小一半

3、第8页/共105页9 05，13，19，21，37，56，64，75，80，88，92 05，13，19，21，37，56，64，75，80，88，92 05，13，19，21，37，56，64，75，80，88，92lowlowmidhighhighmidlowhigh第9页/共105页10high)/2(low 条件 (1)确定查找区间的中点位置mid (2)将待查的K值与seqlistmid.key比较 (3)若相等，查找成功并返回此位置 (4) 若不相等，确定新的查找区间,返回(1), 重新开始二分法查找 (5) 当上下界相等时,结束查找过程第10页/共105页11lowhighmid

4、1 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 92lowhighmid例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找21第11页/共105页121 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

5、56 64 75 80 88 92lowhighmid例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找70第12页/共105页131 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92low highmid第13页/共105页14 第14页/共105页15第15页/共105页16第16页/共105页17 查找过程 将表分成几块，块内无序

6、，块间有序 先确定待查记录所在块，再在块内查找 适用条件 分块有序表是后一个子表中所有记录的关键字均大于前一个子表中的最大关键字 算法实现 用数组存放待查记录,每个数据元素至少含有关键字域 建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针第17页/共105页18第18页/共105页19第19页/共105页20第20页/共105页21第21页/共105页22 以二叉链表作为二叉排序树的存储结构 typedef struct NODE ElemTypeelem; /数据元素字段 struct NODE *lc,*rc;/左、右指针字段 NodeType; /二叉树结点类型第22

7、页/共105页23第23页/共105页24第24页/共105页25第25页/共105页26 原则 从二叉排序树中删除一个结点之后，使其仍能保持二叉排序树的特性即可。第26页/共105页27 p为叶子结点，只需修改p双亲f的指针 f- lc=NULL ,f-rc=NULL p只有左子树或右子树 p只有左子树，用p的左孩子代替p (1)(2) p只有右子树，用p的右孩子代替p (3)(4) p左、右子树均非空 沿p左子树的根C的右子树分支找到S，S的右子树为空，将S的左子树成为S的双亲Q的右子树，用S取代p (5) 若C无右子树，用C取代p (6)第27页/共105页28第28页/共105页29第

8、29页/共105页30第30页/共105页31第31页/共105页32 对给定序列建立二叉排序树 若左右子树均匀分布，则其查找过程类似于有序表的折半查找。 若给定序列原本有序，则建立的二叉排序树就蜕化为单链表，其查找效率同顺序查找一样 需对均匀的二叉排序树进行插入或删除结点后，应对其调整，使其依然保持均匀。 第32页/共105页33 平衡二叉树或者是一棵空树，或者是具有下列性质的二叉排序树 它的左子树和右子树都是平衡二叉树 左子树和右子树高度之差的绝对值(平衡因子)不超过1第33页/共105页34 5 2 3 4 16 7 一棵平衡二叉树 6 1 2 3 4 8 5 7 一棵非平衡二叉树 第3

9、4页/共105页35第35页/共105页36 左单旋转（ LL型的处理） 右单旋转（ RR型的处理） 先左后右双向旋转（ LR型的处理） 先右后左双向旋转（ RL型的处理）第36页/共105页37 1 A B C 0 2 C B A 0 0 0 第37页/共105页38 第38页/共105页39 第39页/共105页40 第40页/共105页41第41页/共105页42 第42页/共105页43第43页/共105页44 第44页/共105页45 第45页/共105页46第46页/共105页47 4 2 3 1 5 7 6 第47页/共105页48第48页/共105页49动态查找表 B-树 B-

10、树是一种平衡的多路查找树，它在文件系统中很有用。 下图为阶B-树 root 50 15 71 84 3 8 20 26 43 56 62 78 89 96第49页/共105页50第50页/共105页51Ki（i=1,2,n）为关键字，且KiKi+1Ai为指向子树根结点的指针(i=0,1,n)，且指针Ai-1所指子树中所有结点的关键字均小于Ki (i=1,2,n)An所指子树中所有结点的关键码均大于Kn，m/2 1nm 1 ，n为关键字的个数(或n+1为子树的个数) 。第51页/共105页52第52页/共105页53第53页/共105页54 第54页/共105页55第55页/共105页5650

11、20 40 80 插入关键字 = 60, 60 80 90,60809090 50 806030, 40 20 30 50 808030 50第56页/共105页57 分两种情况 (1)删除最底层结点中关键字 (2)删除为非底层结点中关键字 若所删除关键字非底层结点中的Ki，则可以指针Ai所指子树中的最小关键字X替代Ki，然后，再删除关键字X，直到这个X在最底层结点上，即转为(1)的情形。 第57页/共105页58第58页/共105页59第59页/共105页60第60页/共105页61第61页/共105页62第62页/共105页63第63页/共105页64第64页/共105页65第65页/共1

12、05页66第66页/共105页67 B+树是应文件系统所需而产生的一种B-树的变形树 m阶的B+树和m阶的B-树的差异在于 有n棵子树的结点中含有n个关键字 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 第67页/共105页68 第68页/共105页69第69页/共105页70 哈希函数是一个映象， 即：将关键字的集合映射到某个地址集合上。 由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象， 即：key1 key2

13、，而 f(key1) = f(key2)。 很难找到一个不产生冲突的哈希函数第70页/共105页71 第71页/共105页72第72页/共105页73 哈希方法需要解决以下两个问题 构造好的哈希函数 所选函数尽可能简单,以便提高转换速度。 所选函数对关键字计算出的地址，应在哈希地址集中大致均匀分布，以减少空间浪费。 制定解决冲突的方案。 第73页/共105页74 第74页/共105页75 构造哈希函数的方法第75页/共105页76 第76页/共105页77 第77页/共105页78 第78页/共105页79 第79页/共105页80 第80页/共105页81 第81页/共105页82 第82页

14、/共105页83 第83页/共105页84 选取哈希函数，考虑以下因素： 计算哈希函数所需时间 关键字长度 哈希表长度（哈希地址范围） 关键字分布情况 记录的查找频率第84页/共105页85第85页/共105页86第86页/共105页87第87页/共105页88第88页/共105页89第89页/共105页90Hash(3)=3哈希地址上冲突由H1=(Hash(3)+12) mod 11=4 仍然冲突；H2=(Hash(3)-12) mod 11=2 找到空的哈希地址，存入。第90页/共105页91第91页/共105页92 第92页/共105页930 1 2 3 4 5 6 7 8 9 10 11 12 14127796855198420231011第93页/共105页94第94页/共105页95第95页/共105页96第96页/共105页97第97页/共105页98第98页/共105页99第99页/共105页100第100页/共105页101哈希表的装填因子 第101页/共105页102几种不同处理冲突方法的平均查找长度的比较第102页/共105页103第七章 查找 查找的基本概念 顺序表、有序表和索引表的查找 二叉平衡树 B-树、B+树的查找 散列表的查找 第103页/共105页