《《数据结构（第二版）》课件 包振宇 第七章 查找》由会员分享，可在线阅读，更多相关《《数据结构（第二版）》课件 包振宇 第七章 查找（39页珍藏版）》请在金锄头文库上搜索。
1、第七章 查找,7.1 线性表的查找 7.2 树的查找 7.3 *哈希表及其查找 7.4 典型例题,查找也称检索，查找就是在按某种数据结构形成存储的数据集合中，找出满足指定条件的结点。按查找的条件分类，有按结点的关键码，关键码以外的其他数据项或其他数据项的组合查找等。按查找数据在内存或在外存，分为内存查找和外存查找。按查找的目的分类，查找只是为了确定指定条件的结点存在与否，称为静态查找。查找是为确定结点的插入位置或成为了删除找到的结点，称为动态查找。为了叙述简便，这里假定仍按结点的关键码查找，查找值称为查找码。,7.1线性表的查找,7.1 .1顺序存储线性表的查找：设结点集合按线性表组织，采用顺
2、序存储方式，结点只含关键码，并且是整数。 1、无序顺序存储线性的顺序查找。 设线性表的结点之间没有特定的逻辑顺序，顺序查找是对给定的查找码，从线性表的一端开始，逐一查找表的每一结点的关键码，直至所找的结点找到或到达线性表的另一端，而未找到。查找函数为下； int search1(int k,int n,int key) /*设kn供函数存储虚设结点，key为欲查找结点的关键字的值。函数找到返回结点的下标，找不到返回-1*/ int i; for (i=0 ;key!=ki;i+) return in?i:-1; ,2、有序顺序存储线性表的顺序查找 假定线性有表按结点键值递增的顺序存放于线性表中
3、，则顺序查找过程中，发现结点的键值比查找码大时，就可提前得出没有要找结点的结论。相应函数如下； int search2 (int k,int n ,int key) /*设kn供函数存储虚设结点, key为欲查找结点的键值，查找到返回结点的下标，找不到返回-1*/ int i; for(i=0;keyki;i+); if(in ,3、有序顺序存储线性表的二分法查找 假定线性表按结点键值递增顺序存放于线性表中，则可以改进顺序查找的方法。顺序查找时，每比较一次，查找范围只减少1，二分法查找能大大减少查找范围。设分别用low和 high表示当前查找范围的下界和上界，首先计算查找范围的中间位置:mid
4、=(low+high)/2。用查找码与位于mid位置的结点比较,发现查找码大于它时,表示新的查找范围应为mid+1,high,若查找码小于它,表示新的查找范围为 low,mid-1。这样一次比较后,要么因查找码与它相等,查找成功,要么是查找范围缩小一半后,在新的查找范围内继续查找。直到查找成功,或出现highlow,表示不再有查找范围,因而查找失败。,具体函数如下: int bin_search3(int k,int n,int key) /*kn为已知线性表key为欲查结点的值，函数找到返回该结点的下标，找不到返回-1*/ int low=0,high=n-1,mid; while(lowk
5、mid) low=mid+1; else high=mid-1; return 1; ,4、有序顺序存储线性表的插值查找 插值查找是对二分法查找的一种改进依然假定线情表按结点键值递增的顺序存放，并且线情表中的结点的键值几乎均匀出现，则可按查找范围两端结点的键值计算出键为查找码的结点的大致位置；如它存在的话，其位置可通过线性插值来计算。 假定分别用low和 high表示当前查找范围的下界和上界，查找码为 key。首先计算查找范围的插值位置：pos=(key-klow)/(khigh-klow)*(high-low)+low用key与kpos比较，发现结点keykpos,表示新的查找范围应为pos
6、+1，high。若keykpos，表示新的查找范围应为 low,pos-1。这样一次比较后，要么是查找成功（key= kpos），要么是查找范围缩小后，在新的查找范围内继续查找。直到查找成功，或出现high low，表示已没有可找范围，因而查找失败。,具体函数如下： int ins_search4 (int k , int n,int key) /*函数找到返回该结点的下标，找不到返回-1*/ int low=0 , high=n-1,pos; while(lowkposlow=pos+1; else high=pos-1; return 1 ,7.1.2 *分块查找,一般说来，顺序存储的线性
7、表比较适宜于静态查找，前面的算法也都是静态查找的方法。为提高查找速度，将线性表保持有序，并有二分法查找，对提高查找效率是非常有效。但当数据集上有频繁的插入或删除操作时，为能继续保持序需要大量移动数据存储位置的操作。将数据分块组织，块与块之间有序，块内数据任意是一种比较适宜动态查找的数据组织形式。 例如将线性表示分成n块，块内数据可以任意，但块间数据是有序的，前一块中任一结点的键值都小于后一块中所有结点的键值。另外，还要求建立一个索引表，每个索引项对应表中的一块，至少有这样的两项信息，它们是对应块中结点最大键值和块的第一结点的指针，索引表中的索引项按键值有序存储。分块查找的过程分两步，先用二分法
8、在索引表中查索引项，确定要查的结点在哪一块，然后，再在相应块内顺序查找。由于块内结点无序，多数情况增删比较简便，不需要大量的移动结点，而且删除可做标记；可在块内任意位置增添。,7.1.3 链式存储线性表查找,链式存储线性表上的查找只能从链表的首结点开始顺序查找。设链表结点除整数关键码外，只含一个指向后继结点的指针； tyredef struct node int key; struct node *next; NODE;,无序链表的查找,无序链表的结点 之间没有特定逻辑顺序，对给定的查找码，可从链表的首结点 开始，逐一检查链表的每个结点的关键码，直至所找的结点找到，或直至考察了链表的末结点后仍
9、未找到。其函数如下： NODE *search5（NODE *h,int key） /*设h是链表的首结点指针，找到时函数返回该结点的指针，否则返回NULL*/ for(;h!=Null ,有序链表,有序链表按结点键值递增的顺序链接，则顺序查找时，发现结点的键值比查找码大时，就可提早得出没有要找结点的结论。相应函数为下： NODE *search6(NODE *h,int key) /*设h是链表的首结点指针，找到时返回该结点的指针，否则返回NULL*/ for(; h!=NULL ,有序链表的动态查找,假定链表按结点键值递增的顺序连接，且查找是为了增删该结点，需要知道该结点的前驱结点指针。同
10、样地，查找是为了插入新结点，为能正确完成插入，需要知道插在哪一个结点之后。为此，动态查找需返回两个指针：确定查找结束的结点指针和该结点的前驱结点指针。另外，函数还要区分在首结点时找到和直到末结点也未找到的情况。为此，函数增设能带回上述信息的两指针参数p和q；其中*q为确定查找结束的结点指针，*p为它的前驱结点指针查找结果可按两指针结果值的不同情况来区分：,有序链表的动态查找（续）,1、当*p=NULL且*q!=NULL，在链表的首结点找到，*q指向链表的首结点； 2、当*p!=NULL且*q!=NULL在链表的某个中间位置找到，*q指向结束查找时的结点，*p指向重在前驱。 3、当*p!=NUL
11、L且*q=NULL，查找至链表末尾，*p指向链表的末结点。 4、当*p=NULL且*q=NULL，所指链表为空表。 相应的函数如下： int search7(NODE *h,int key,NODE*p,NODE *q) /*设h是链表的首结点指针，找到时，函数返回1，否则返回0*/ NODE *u=Null,*v=h; for(; u!=Null ,7.2 树的查找,7.2.1二叉树查找 1.静态查找 查找树上的静态查找是在查找树上找键值为key的结点是否存在，这可按以下步骤查找树上找值为key的结点： （1）如果查找树T为空二叉树，则查找失败，结束查找； （2）如果查找树的根结点的键值等于
12、key，则查找成功，结束查找； （3）如果key小于根结点的键值，则沿着根结点的左子树查找，即将根据点的左子树作为新的查找树T继续查找。 （4）如果key大于根结点的键值，则沿着根结点的右子树查找，即将根结点的右子树作为新的查找树T继续查找。,函数如下: typedef strcut node char data; strud node *lchild, *rchild; TNODE2; TNODE2 *search(t,key) TNODE2 *t;/查找树根结点指针*/ char key ;/*欲查找值为key的结点*/ while (t！=NULL) if (t-data=key)ret
13、urn t;/*找到*1 else if (keydata)t=t-lchild;/*沿左子树查找*/ else t=t-rchild;/*沿右子树查找*/ return NULL;/*未找到*/ ,2、动态查找 在查找树上，为插入和删除操作需要而使用的查找称为动态查找，动态查找应得到两个指针，一个指向键值为key的结点，另一个指向该结点的父结点。为些查找函数应设四个参数：查找树的根结点指针t，查找值key，存储键值为key结点的父结点的指针变量的指针pkpt,存储键值为key结点的指针变量的指针kpt。但函数要考虑以下几种不同情况：,2、动态查找 因查找树为空，查找失败，函数使*kpt=NU
14、LL,*pkpt=NULL; 因查找树中没有键值为key的结点，函数一直寻找至查找路径的最后一个结点；*pkpt指向该结点，*kpt=NULL如果要插入键值为key的结点，就插 入在该结点之下 ； 查找成功，*kpt指向键值为key的结点，若键值为key的结点是查找树的根结点，则*pkpt=NULL; 查找成功，*kpt指向键值为key的结点，*pkpt指向它的父结点。,相应函数如下： void search(TNODE2 *t,/*查找树的根结点指针*/ char key,/*查找值*/ TNODE2 *pkpt,/*key结点的父结点的指针的指针*/ TNODE2 *kpt)/* key结
15、点的指针的指针*/ *pkpt=NULL; kpt=t;/从查找树的根结点开始寻找*/ while(*kpt!=NULL) if (*kpt)-data=key)return;/*找到*/ pkpt=kpt;/*当前结点作为父结点，继续查找*/ /*按查树的性质，确定查找路径：*/ if (keydata)*kpt=(*kpt)-lchild; else *kpt=(*kpt)-rchild; ,7.2.2平衡二叉树(AVL树),一、AVL树（高度平衡的BST）概念,1、定义AVL或是空树，或是具有下列性质的BST： 它的左、右子树都是AVL树，且右左子树的高度之差的绝对值不超过1。,2、举例
16、, 是二叉搜索树 树和所有子树的右左子树 高度之差绝对值不超过1 属AVL树,3、平衡因子（balance factor）, 结点右子树高度减去左子树高度所得高度差 AVL树中所有结点的平衡因子只能取0，1，1,二、平衡化旋转,1、向AVL树插入结点可能造成不平衡，此时要调整树的结构，使之重新达到平衡,2、平衡化旋转方法, 从插入位置沿通向根的路径检查各结点的平衡 因子 若发现不平衡结点，则从该结点起沿刚才回溯路径取直 接下两层结点 若三个结点在一条直线上(RR、LL型)，则采用单旋转进行平衡化，此时处于中间位置的结点为旋转中心 若三结点不在一条直线上(LR、RL型)，则采用双旋转进行平衡化，此时处于下方位置的结点为旋转中心,3、平衡化旋转示例, RR型（逆时针单旋转）,二、平衡化旋转, LL型（顺时针单旋转）,3、平衡化旋转示例,二、平衡化旋转,3
