数据结构上机实验 第8章 查找课件

1、第8章 查找8.1查找的基本概念查找表：(Search Table)是由同一类型的数据元素（或记录）构成的集合。由于“集合”中的数据元素之间存在着完全松散的关系。对查找表的操作：(1)查询某个“特定的”数据元素是否在查找表中；(2)检索某个“特定的”数据元素的各种属性；(3)在查找表中插入一个数据元素；(4)从查找表中删去某个数据元素。静态查找表：做(1),(2)操作动态查找表：做(1),(2),(3),(4)操作。关键字（Key）：是数据元素（或记录）中某个数据项的值，用它可以标识（识别）一个数据元素（或记录）。若此关键字可以惟一标识一个记录，则称此关键字为主关键字(Primary Key)

2、；反之，称用以标识若干记录的关键字为次关键字。当数据元素只有一个数据项时，些关键字即为该数据元素的值。查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在这样的一个记录，称查找成功，此时查找的结果为给出的整个记录的信息。或指示出该记录在查找表中的位置；若表中不存在关键字等于给定的值的数据元素，称查找不成功，查找的结果可给出一个“空”记录或“空”指针。8.2静态查找表1.顺序表的查找 当以顺序表或线性链表表示静态查找表，可用顺序查找来实现。#define MAX_LENGTH 100typedef struct KeyType key; .otheritemE

3、lemtype;typedef struct Elemtype elemMAX_LENGTH; / 0号单元空出 int length;SSTable;顺序查找过程：从表中最后一个记录开始，逐个进行记录的关键字和给定的值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录，反之，直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。int Search_Seq(SSTable ST,KeyType key) ST.elem0.key = key; for(i=ST.length;(ST.elemi.key !=key) ;-i) ; return i;

4、查找性能分析: 平均查找长度（ASL）：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望称为查找算法在查找成功时的平均查找长度。 查找成功时的ASL.2.有序表的查找以有序表表示静态查找表时，可用折半查找来实现。查找key = 19过程 5 13 19 21 37 56 64 low mid highST.elemmid.key key 5 13 19 21 37 56 64 low mid highST.elemmid.key key 5 13 19 21 37 56 64 low high midST.elemmid.key =keyint Search_Bin(SSTab

5、le ST,KeyType key) low = 1;high = ST.length; while(low =high) mid = (low+high)/2; if(key =ST.elemmid.key) return mid; else if(keydata.key) return (T); else if(LT(key,T-data.key) return(SearchBST(T-lchild); else return(SearchBST(T-rchild);2.二叉排序树的插入基本思想是：若二叉排序树为空，将待插入的结点作为根结点。否则，若待插入结点的关键字值和根结点关键字值进行

6、比较。若小于，则作为根结点左子树插入，否则作为右子树插入。63，90，70，55，67，42，98，83，10，45，5863，90，70，55，67，42，98，83，10，45，5863，90，70，55，67，42，98，83，10，45，5863，90，70，55，67，42，98，83，10，45，583.查找分析40,20,50,10,30,90,建立二叉排序树:402050903010ASL=(1+2+2+3+3+3)/6=14/610,20,30,40,50,90,建立二叉排序树:402050903010ASL=(1+2+3+4+5+6)/6=21/63.查找分析随机的情况下,

7、二叉排序树的平均查找长度为对数级.O(logn)4.平衡二叉树(AVL)定义:它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1.平衡因子:结点的左子树的深度减去右子树的深度,平衡因子只能是:-1,0,1.平衡旋转可以归纳为四类 (1)LL平衡旋转 (2)RR平衡旋转 (3)LR平衡旋转 (4)RL平衡旋转(1)LL旋转平衡：由于在A的左子树的左子树中插入结点，使A的平衡因子由1增至2而失去平衡，需要进行一次顺时针旋转操作，如图所示。旋转操作用C语言描述如下： b=a-lch； /* b指向是a的左孩子 */ a-lch=

8、b-rch； /* a的左指针指向b的右孩子 */ b-rch=a； /* a作为b的右孩子 */ a-bf=b-bf=0； /* 调整后的树以b为根 */(2)RR旋转平衡：由于在A的右孩子的右子树中插入结点，使A的平衡因子由-1增至-2而失去平衡，需要进行一次逆时针旋转操作，如图所示。旋转操作用C语言描述如下： b=a-rch ； /* b指向是a的右孩子 */ a-rch=b-lch ； /* a的左指针指向b的左孩子 * b-lch=a ； /* a作为b的左孩子 */ a-bf=b-bf=0 ； /* 调整后的树以b为根 */(3)LR旋转平衡：由于在A的左孩子的右子树中插入结点，使

9、A的平衡因子由1增至2而失去平衡，需要进行两次旋转操作(先逆时针、后顺时针)，如图所示。旋转操作用C语言描述如下： b=a-lch； c=b-rch； /* b指向是a的左孩子，而c指向是b的右孩子 */ a-lch=c-rch； /* a的左指针指向c的右孩子 */ b-rch=c-lch； /* b的右指针指向c的左孩子 */ c-rch=a； /* c的右指针指向a */ c-lch=b； /* c的左指针指向b，c为调整后子树的根 */(4)RL旋转平衡：由于在A的右孩子的左子树中插入结点，使A的平衡因子由-1增至-2而失去平衡，需要进行两次旋转操作(先顺时针、后逆时针)，如图所示。旋

10、转操作用C语言描述如下： b=a-rch； c=b-lch； a-rch=c-lch； b-lch=c-rch； c-lch=a； c-rch=b； 或是空树，或是满足以下条件的m叉树: (1)树中每个结点至多有m棵子树(树的度=m)。 (2)若根结点不是叶子结点，则至少有二棵子树。 (3)除根外的所有非终端结点至少有ceil(m/2)棵子树 (4)所有结点包含信息：(n,A0,K1,A1,Kn,An)，其中Ki为关键字且有序(KiKi+1)，Ai为指向子树根结点的指针，Ai所指子树中所有结点的关键字均小于Ki+1，An所指子树中所有结点的关键字均大于Kn。 (5)所有叶子结点都出现在同一层次

11、上，即：所有为空的指针出现在同一层上。B-树定义 n A0 K1 A1 Kn An8.3 哈希表(散列表) 哈希表存储的基本思想：以数据表中的每个记录的关键字 k为自变量，通过一种函数H(k)计算出函数值。把这个值解释为一块连续存储空间（即数组空间）的单元地址（即下标），将该记录存储到这个单元中。在此称该函数H为哈希函数或散列函数。按这种方法建立的表称为哈希表或散列表。 由于关键字值的某种随机性，使得这种一一对应关系难以发现或构造。因而可能会出现不同的关键字对应一个存储地址。即k1k2，但H(k1)=H(k2)，这种现象称为冲突(collision)。 把这种具有不同关键字值而具有相同哈希地址

12、的对象称“同义词”。 在大多数情况下，冲突是不能完全避免的。这是因为所有可能的关键字的集合可能比较大，而对应的地址数则可能比较少。 对于哈希技术，主要研究两个问题：（1）如何设计哈希函数以使冲突尽可能少地发生。（2）发生冲突后如何解决。1.哈希函数的构造方法(1)直接定址法 取关键字本身或关键字的某个线性函数值为哈希函数. H(key)=key或H(key)=a*key+b 这种哈希函数计算简单，并且不可能有冲突发生。当关键字的分布基本连续时，可使用直接定址法的哈希函数。否则，若关键字分布不连续将造成内存单元的大量浪费。 (2)除留余数法 取关键字被某个不大于哈希表长的m的数p除后所得余数为哈

13、希地址。 H(key)= key mod p p=m; 这是一种最简单，最常用的构造哈希函数的方法，p的选择很重要。一般来说:P为质数或不包含小于20的质因数.2.处理冲突的方法 (1)开放定址法 用开放定址法处理冲突就是当冲突发生时，形成一个地址序列。沿着这个序列逐个探测，直到找出一个“空”的开放地址。将发生冲突的关键字值存放到该地址中去。 如 Hi=(H(key)+di) mod m, i=1，2，k (km-1) 其中H(key)为哈希函数，m为哈希表长，di为增量函数 . 增量序列的取法不同，可得到不同的开放地址处理冲突探测方法。 di=1,2,3,4,5, ,m-1 称为线性探测再散

14、列 di=12,-12,22,-22, 称为二次探测再散列 di=伪随机序列 称为伪随机探测再散列 (2)再哈希法 Hi=RHi(key) RHi均是不同的哈希函数，在同义词冲突时，计算另一个哈希函数，直到冲突不再发生。 (3)链地址法 用链地址法解决冲突的方法是：把所有关键字为同义词的记录存储在一个线性链表中，这个链表称为同义词链表。并将这些链表的表头指针放在数组中.例：已知哈希表地址区间为010，给定关键字序列（20，30，70，15，8，12，18，63，19）。哈希函数为H(k)=k11，采用线性探测法处理冲突，则将以上关键字依次存储到哈希表中。试构造出该哈希表(哈希造表)，并求出等概

15、率情况下的平均查找长度。(1)解决冲突方法采用开放定址法 H(key)=key%p Hi=(H(key)+di)%m 此题中: p=11 m=11(20，30，70，15，8，12，18，63，19)H(20)=20%11=901234567891020(20，30，70，15，8，12，18，63，19)H(30)=30%11=80123456789103020(20，30，70，15，8，12，18，63，19)H(70)=70%11=4012345678910703020(20，30，70，15，8，12，18，63，19)H(15)=15%11=4 -collisionH1=(H(15

16、)+1)%11=501234567891070153020(20，30，70，15，8，12，18，63，19)H(8)=8%11=8 -collisionH1=(H(8)+1)%11=9 -collisionH2=(H(8)+2)%11=10012345678910701530208(20，30，70，15，8，12，18，63，19)H(12)=12%11=101234567891012701530208(20，30，70，15，8，12，18，63，19)H(18)=18%11=70123456789101270151830208(20，30，70，15，8，12，18，63，19)H(

17、63)=63%11=8 -collisionH1=(H(63)+1)%11=9 -collisionH2=(H(63)+2)%11=10 -collisionH3=(H(63)+3)%11=0012345678910631270151830208(20，30，70，15，8，12，18，63，19)H(19)=19%11=8 -collisionH1=(H(19)+1)%11=9 -collisionH2=(H(19)+2)%11=10 -collisionH3=(H(19)+3)%11=0 -collisionH4=(H(19)+4)%11=1 -collisionH5=(H(19)+5)%

18、11=201234567891063121970151830208在等概率情况下成功的平均查找长度为： ASL=（1*5+2+3+4+6）/9 =20/9利用线性探查法处理冲突容易造成关键字的“堆积”问题。这是因为当连续n个单元被占用后，再散列到这些单元上的关键字和直接散列到后面一个空闲单元上的关键字都要占用这个空闲单元，致使该空闲单元很容易被占用，从而发生非同义冲突。造成平均查找长度的增加。(2)若解决冲突采用链地址法: (20，30，70，15，8，12，18，63，19) 在等概率情况下成功的平均查找长度为： ASL=(1*5+2*2+3*1+4*1)9 =169 虽然链地址法要多费一些存储空间，但是彻底解决了“堆积”问题，大大提高了查找效率。 3.哈希查找性能分析哈希法是利用关键字进行计算后直接求出存储地址的。当哈希函数能得到均匀的地址分布时，不需要进行任何比较就可以直接找到所要查的记录。但实际上不可能完全避免冲突，因此查找时还需要进行探测比较。哈希冲突与以下三个因素有关:(1)装填因子有关 所谓装填因子是指哈希表中己存入的元素个数n与哈希表的大小m的比值，即 a=n/m。 当 a 越小时，发生冲突的可能性越小，越