《第10章查找.ppt》由会员分享,可在线阅读,更多相关《第10章查找.ppt(55页珍藏版)》请在三一文库上搜索。
1、第10章 查找,查找的基本概念 静态查找表 动态查找表 哈希表,主要知识点,10.1 查找的基本概念,查找:查询关键字是否在(数据元素集合)表中的过程。也称作检索。 主关键字:能够惟一区分各个不同数据元素的关键字 次关键字:通常不能惟一区分各个不同数据元素的关键字 查找成功:在数据元素集合中找到了要查找的数据元素 查找不成功:在数据元素集合中没有找到要查找的数据元素 静态查找:只查找,不改变数据元素集合内的数据元素 动态查找:既查找,又改变(增减)集合内的数据元素 静态查找表:静态查找时构造的存储结构 动态查找表:动态查找时构造的存储结构,平均查找长度:查找过程所需进行的关键字比较次数的平均值
2、,是衡量查找算法效率的最主要标准,其数学定义为:,其中,Pi是要查找数据元素出现的概率,Ci是查找相应数据元素的比较次数。,定义要查找数据元素的结构体为: typedef struct KeyType key; DataType;,10.2 静态查找表,静态查找表主要有三种结构: 顺序表 有序顺序表 索引顺序表,1.顺序表,在顺序表上查找的基本思想是:从顺序表的一端开始,用给定数据元素的关键字逐个和顺序表中各数据元素的关键字比较,若在顺序表中查找到要查找的数据元素,则查找成功,函数返回该数据元素在顺序表中的位置;否则查找失败,函数返回-1。,查找函数设计如下: int SeqSearch(Da
3、taType a, int n, KeyType key) /在a0-an-1中顺序查找关键码为key的数据元素 /查找成功时返回该元素的下标序号;失败时返回-1 int i = 0; while(i n ,算法分析,查找成功时的平均查找长度ASL成功为:,查找失败时的平均查找长度ASL失败为,时间效率为 O(n),2.有序顺序表,有序顺序表上的查找算法主要有顺序查找和折半查找两种方法。,一、顺序查找 有序顺序表上的顺序查找算法和顺序表上的查找算法方法类同,二、二分查找(又称折半查找),算法的基本思想:先给数据排序(例如按升序排好),形成有序表,然后再将key与正中元素相比,若key小,则缩小
4、至前半部内查找;再取其中值比较,每次缩小1/2的范围,直到查找成功或失败为止。反之,如果key大,则缩小至后半部内查找。,二分查找算法如下: int BiSearch(DataType a, int n, KeyType key) /在有序表a0-an-1中二分查找关键码为key的数据元素 /查找成功时返回该元素的下标序号;失败时返回-1 int low = 0, high = n - 1; /确定初始查找区间上下界 int mid; while(low = high) mid = (low + high)/2; /确定查找区间中心下标 if(amid.key = key) return mi
5、d; /查找成功 else if(amid.key key) low = mid + 1; else high = mid - 1; return -1; /查找失败 ,算法分析,查找成功时的平均查找长度ASL成功为:,查找失败时的平均查找长度ASL失败为,3.索引顺序表,当顺序表中的数据元素个数非常大时,采用在顺序表上建立索引表的办法提高查找速度。把要在其上建立索引表的顺序表称作主表。主表中存放着数据元素的全部信息,索引表中只存放主表中要查找数据元素的主关键字和索引信息。,索引表结构图,索引表中的数据元素由两个域构成,key域为被索引的若干个数据元素中关键字的最大值,link域为被索引的若干
6、个数据元素中第一个数据元素的位置编号。,完全索引表:和主表项完全相同,但只包含索引关键字和该数据元素在主表中位置信息的索引表 二级索引表:当主表中的数据元素个数非常庞大时,按照建立索引表的同样方法对索引表再建立的索引表。二级以上的索引结构称作多级索引结构 等长索引表:索引表中的每个索引项对应主表中的数据元素个数相等;反之称为不等长索引表。不等长索引表中的索引长度可随着动态插入和动态删除过程改变,因此不仅适用于静态查找问题,而且也适用于动态查找问题。,相关术语,假设索引表的长度为m,主表中每个子表的长度为s,并假设在索引表上和在主表上均采用顺序查找算法,则索引顺序表上查找算法的平均查找长度为:,
7、算法分析,10.3 动态查找表,动态查找表主要有二叉树结构和树结构两种类型。二叉树结构有二叉排序树、平衡二叉树等。树结构有B-树、B+树等。,1.二叉排序树,一、基本概念,-或是一棵空树;或者是具有如下性质的非空二叉树: (1)左子树的所有结点均小于根的值; (2)右子树的所有结点均大于根的值; (3)它的左右子树也分别为二叉排序树。 二叉排序树中结点的结构体定义如下: typedef struct node DataType data; struct node *leftChild; struct node *rightChild; BiTreeNode;,下图所示就是一棵二叉排序树,二、二
8、叉排序树的查找算法,int Search(BiTreeNode *root, DataType item) BiTreeNode *p; if(root != NULL) p = root; while(p != NULL) if(p-data.key = item.key) return 1; if(item.key p-data.key) p = p-rightChild; else p = p-leftChild; return 0; ,三、插入算法,插入操作要求首先查找数据元素是否在二叉排序树中存在,若存在则返回;若不存在,插入查找失败时结点的左指针或右指针上。 插入算法设计如下:,i
9、nt Insert(BiTreeNode *root, DataType item) BiTreeNode *current, *parent = NULL, *p; current = *root; while(current != NULL) if(current-data.key = item.key) return 0; parent = current; if(current-data.key rightChild; else current = current-leftChild; ,/*生成新结点*/ p = (BiTreeNode *)malloc(sizeof(BiTreeN
10、ode); p-data = item; p-leftChild = NULL; p-rightChild = NULL; if(parent = NULL) *root = p; else if(item.key data.key) parent-leftChild = p; else parent-rightChild = p; return 1; ,下图是调用上述插入函数依次插入数据元素 4,5,7,2,1,9,8,11,3的过程。,五、删除算法,删除操作要求首先查找数据元素是否在二叉排序树中存在,若不存在则结束;存在的情况及相应的删除方法有如下四种: (1)要删除结点无孩子结点,直接删
11、除该结点。 (2)要删除结点只有左孩子结点,删除该结点且使被删除结点的双亲结点指向被删除结点的左孩子结点。 (3)要删除结点只有右孩子结点,删除该结点且使被删除结点的双亲结点指向被删除结点的右孩子结点。 (4)要删除结点有左右孩子结点,分如下三步完成:首先寻找数据元素的关键字值大于要删除结点数据元素关键字的最小值,即寻找要删除结点右子树的最左结点;然后把右子树的最左结点的数据元素值拷贝到要删除的结点上;最后删除右子树的最左结点。,删除过程分别如图所示,测试程序 例10-2 设计一个测试二叉排序树的主函数。 #include #include #include typedef int KeyTy
12、pe; typedef struct KeyType key; DataType; typedef struct node DataType data; struct node *leftChild; struct node *rightChild; BiTreeNode; #include “BiSortTree.h”,void InTraverse(BiTreeNode *root) /*中序遍历显示二叉排序树结点信息函数*/ if(root = NULL) return; if(root-leftChild != NULL) InTraverse(root-leftChild); pri
13、ntf(“%d “, root-data.key); if(root-rightChild != NULL) InTraverse(root-rightChild); ,void main(void) DataType test = 4,5,7,2,1,9,8,11,3, x = 9; int n = 9, i, s; BiTreeNode *root = NULL; for(i = 0; i n; i+) Insert( 程序运行建立的二叉排序树如图10-5(i)所示。程序运行结果如下: 1 2 3 4 5 7 8 9 11 数据元素9存在!,六、二叉排序树的性能分析,一棵二叉排序树的平均查
14、找长度为:,其中: ni 是每层结点个数; Ci 是结点所在层次数; m 为树深。,当二叉排序树是一棵单分支退化树时,查找成功的平均查找长度和有序顺序表的平均查找长度相同,即为:,若每个数据元素的查找概率相等,则二叉排序树查找成功的平均查找长度为:,(a)满二叉排序树时,k = log2(7+1)=3,所以查找成功的平均查找长度为:,(b)左分支退化二叉排序树时,k = n=7,所以查找成功的平均查找长度为:,在最坏情况下,二叉排序树的平均查找长度为O(n)。在一般情况下,二叉排序树的平均查找长度为O(log2n)。,2.B_树,B_树是一种平衡多叉排序树。平衡是指所有叶结点都在同一层上,从而
15、可避免出现像二叉排序树那样的分支退化现象。因此B_树的动态查找效率更高。,B_树中所有结点的孩子结点的最大值称为B_树的阶,一棵m阶的B_树或者是一棵空树,或者是满足下列要求的m叉树: (1)树中每个结点至多有m个孩子结点。 (2)除根结点外,其他结点至少有m/2个孩子结点(符号“ ”表示上取整)。 (3)若根结点不是叶结点,则根结点至少有两个孩子结点; (4)每个结点的结构为:,(5)所有叶结点都在同一层上。,一棵4阶B_树,1. 查找算法,在B_树上查找数据元素x的方法为:将 x.key与根结点的Ki逐个进行比较: (1)若x.key=Ki则查找成功。 (2)若keyKn则沿着指针Pn所指
16、的子树继续查找。,2. 插入算法,插入过程分两步完成: (1)利用查找算法找出该关键字的插入结点(B_树的插入结点一定是叶结点)。 (2)判断该结点是否还有空位置,即判断该结点是否满足nm-1,若该结点满足nm-1,说明该结点还有空位置,直接把关键字x.key插入到该结点的合适位置上;若该结点有n=m-1,说明该结点已没有空位置,要插入就要分裂该结点。,在3阶B_树上进行插入操作如下图示:,3.删除,删除分两步完成: (1)利用查找算法找出该关键字所在的结点。 (2)在结点上删除关键字x.key分两种情况: 一种是在叶结点上删除关键字,共有以下三种情况: (a)假如要删除关键字结点的关键字个数
17、n大于m/2+1,说明删去该关键字后该结点仍满足B_树的定义,则可直接删去该关键字。其过程如下图(b)所示,(b)假如要删除关键字结点的关键字个数n等于m/2+1,说明删去该关键字后该结点将不满足B_树的定义,此时若该结点的左(或右)兄弟结点中关键字个数n大于m/2+1,则把该结点的左(或右)兄弟结点中最大(或最小)的关键字上移到双亲结点中,同时把双亲结点中大于(或小于)上移关键字的关键字下移到要删除关键字的结点中,这样删去关键字后该结点以及它的左(或右)兄弟结点都仍旧满足B_树的定义。其过程如图(c)所示,(c)假如要删除关键字结点的关键字个数n等于m/2+1并且该结点的左和右兄弟结点(如果
18、存在的话)中关键字个数n均等于m/2+1,这时需把要删除关键字的结点与其左(或右)兄弟结点以及双亲结点中分割二者的关键字合并成一个结点。其过程如图(d)所示,另一种是在非叶结点上删除关键字。在非叶结点上删除关键字时,假设要删除关键字Ki(1in),在删去该关键字后,以该结点Pi所指子树中的最小关键字Kmin来代替被删关键字Ki所在的位置(Pi所指子树中的最小关键字Kmin一定是在叶结点上),然后再以指针Pi所指结点为根结点查找并删除Kmin(在非叶结点上删除问题就转化成了叶结点上的删除问题)。其过程如图(e)所示,10.4 哈希表,哈希函数:数据元素的关键字和该数据元素的存放位置之间的映射函数
19、 哈希表:通过哈希函数来确定数据元素存放位置的一种特殊表结构。,1.哈希表的基本概念,构造方法:设要存储的数据元素个数为n,设置一个长度为m(mn)的连续内存单元,分别以每个数据元素的关键字Ki(0in-1)为自变量,通过哈希函数h(Ki),把Ki映射为内存单元的某个地址h(Ki),并把该数据元素存储在这个内存单元中。哈希函数h(Ki)实际上是关键字Ki到内存单元的映射,因此,h(Ki)也称为哈希地址,哈希表也称作散列表。,构造哈希表时出现KiKj(ij),但h(Ki)=h(Kj)的现象称作哈希冲突。这种具有不同关键字而具有相同哈希地址的数据元素称作“同义词”,由同义词引起的冲突称作同义词冲突
20、。,解决哈希冲突的基本思想是:通过哈希冲突函数(设为hl(K)(l=1,2,m-1)产生一个新的哈希地址使hl(Ki)hl(Kj)。把要存储的n个数据元素通过哈希函数映射到了m个连续内存单元中,从而完成了哈希表的构造。 可见,构造哈希表一定要使用主关键字,不能使用次关键字。 为什么?,例10-1 建立数据元素集合a的哈希表, a = 180,750,600,430,541,900,460,并比较m取值不同时的哈希冲突情况。 分析:数据元素集合a中共有7个数据元素,数据元素的关键字为三位整数,如果我们取内存单元个数m为1000,即内存单元区间为000999,则第一,在m个内存单元中可以存放下n个
21、数据元素,第二,若取h(K)=K,则当KiKj(ij)时一定有h(Ki) h(Kj)。但是,在1000个内存单元中只存储7个数据元素其空间存储效率太低。,我们可适当减少内存单元个数。若取内存单元个数m为13,取哈希函数h(K)为:h(K) = K mod m,即哈希地址h(K)为关键字K除m所得的余数,则有: h(180) = 11 h(750) = 9 h(600) = 2 h(430) = 1 h(541) = 8 h(900) = 3 h(460) = 5 若取内存单元个数m为11,仍取哈希函数h(K)为:h(K) = K mod m,则有: h(180) = 4 h(750) = 2
22、h(600) = 6 h(430) = 1 h(541) = 3 h(900) = 9 h(460) = 9 此时h(460) =h(900) = 9,因此存在哈希冲突。 若取第一次哈希冲突函数h1(K)为哈希地址加1后模m,即:h1(K) = h(K+1) = (K+1) mod m,则有: h1(460) = 10,构造哈希表时 ,冲突是不可避免的,有关因素主要有如下三个:,(1)装填因子。装填因子是指哈希表中已存入的数据元素个数与哈希地址空间大小的比值,即/,越小,冲突的可能性就越小,但哈希表中空闲单元的比例就越大; 越大(最大可取1)时,冲突的可能性就越大,但哈希表中空闲单元的比例就越
23、小,存储空间的利用率就越高。 (2)与所采用的哈希函数有关。 (3)与解决哈希冲突的哈希冲突函数有关。,2.哈希函数的构造方法,常用的哈希函数构造方法有:,1.除留余数法 2.直接定址法 3.数字分析法,函数设计目标:使通过哈希函数得到的n个数据元素的哈希地址尽可能均匀地分布在m个连续内存单元上,同时使计算过程尽可能简单,以达到尽可能高的时间效率。,h(K) = K mod m 优点:计算简单,适用范围广 关键:选好哈希表长度m 技巧:哈希表长m取素数时效果较好,一、除留余数法,二、直接定址法,h(K) = K + C 优点:计算简单,不会发生冲突 缺点:有可能造成内存单元的大量浪费,特点:取
24、数据元素关键字中某些取值较均匀的数字位作为哈希地址,只适合于所有关键字值已知的情况,三、数字分析法,3.哈希冲突解决方法,常见的冲突处理方法有:,一、开放定址法 二、链表法,一、开放定址法,设计思路:以发生哈希冲突的哈希地址为自变量、通过某种哈希冲突函数得到一个新的空闲的内存单元地址。,具体实现方法:,(1)线性探查法,优点:只要哈希表未被填满,保证能找到一个空地址单元存 放有冲突的元素; 缺点:容易产生“堆积” ,大大降低了查找效率。,(2)平方探查法,(3)伪随机数法,平方探查法的探查跨步很大,所以可避免出现堆积问题,伪随机数法的探查跨步是随机的,也可避免出现堆积问题 非同义词冲突:这种由
25、于解决同义词冲突而引起冲突称作非同义词冲突。,二、链表法,基本思想:如果没有发生哈希冲突,则直接存放该数据元素;如果发生了哈希冲突,则把发生哈希冲突的数据元素另外存放在单链表中。,例10-2建立数据元素集合a的哈希表。a = 16, 74, 60, 43, 54, 90, 46, 31, 29, 88, 77, 66, 55。要求哈希函数采用除留余数法,解决冲突方法采用链表法。 设计分析:数据元素集合a中共有13个数据元素,取哈希表的内存单元个数m=13。除留余数法的哈希函数为:h(K) = K mod m有: h(16) = 3 h(74) = 9 h(60) = 8 h(43) = 4 h
26、(54) = 2 h(90) = 12 h(46) = 7 h(31) = 5 h(29) = 3 h(88) = 10 h(77) = 12 h(66) = 1 h(55) = 3,方法有两种:第一种方法是为发生哈希冲突的不同的同义词建立不同的单链表;第二种方法是为发生哈希冲突的所有同义词建立一个单链表。,采用链表法的第一种方法建立的哈希表存储结构 如下图所示,4 哈希表设计,例10-3编写一组包括哈希表初始化、哈希表元素插入、哈希表元素删除、哈希表查找和哈希表空间撤消操作的函数。要求哈希函数采用除留余数法,解决哈希冲突方法采用开放定址法的线性探查法。并设计一个测试程序进行测试。 设计: 数
27、据结构设计:结构体HashTable由哈希表数组、数组个数和当前表项个数三部分组成,其中哈希表数组中每个表项的数据类型是结构体HashItem。结构体HashItem由数据元素和表项状态两部分组成,其中数据元素仅包括一个关键字域,表项状态的数据类型为枚举类型,表项状态域有Empty, Active和Deleted三种状态,分别表示表项的空、已占用和被删除三种状态。,typedef enum Empty, Active, Deleted KindOfItem ; typedef struct KeyType key; DataType; typedef struct DataType data;
28、 KindOfItem info; HashItem; typedef struct HashItem *ht; int tableSize; int currentSize; HashTable;,int Initiate(HashTable *hash, int mSize) hash-tableSize = mSize; hash-ht = (HashItem *)malloc(sizeof(HashItem)*mSize); if(hash-ht = NULL) return 0; else hash-currentSize = 0; return 1; ,int Find(HashT
29、able *hash, DataType x) int i = x.key % hash-tableSize; int j = i; while(hash-htj.info = Active ,int Insert(HashTable *hash, DataType x) int i = Find(hash, x); if(i 0) return 0; else if(i != -hash-tableSize) hash-ht-i.data = x; hash-ht-i.info = Active; hash-currentSize+; return 1; else return 0; ,int Delete(HashTable *hash, DataType x) int i = Find(hash, x); if(i = 0) hash-hti.info = Deleted; hash-currentSize-; return 1; else return 0; void Destroy(HashTable *hash) free(hash-ht);,三、测试程序 例10-3 测试程序设计。建立数据元素集合a = 180,750,600,430,541,900,460的哈希表,并分别测试哈希表长度m=13和m=11两种情况得到的哈希表。,
链接地址:https://www.31doc.com/p-2546972.html