《第8章查找山西建筑职业技术学院》由会员分享，可在线阅读，更多相关《第8章查找山西建筑职业技术学院（48页珍藏版）》请在金锄头文库上搜索。
1、第8章 查 找,第8章 查 找,8.1 基本概念 8.2 静态查找表 8.3 动态查找 8.4 散列表 8.4 应用举例及分析 习题,8.1 基 本 概 念,一、定义 查找表（search table）:由同一类型的数据元素或记录构成的集合，每个数据元素由若干数据项组成。 关键字（key）：能够标识数据元素（或记录）的一个或几个数据项称为关键字，能够唯一标识一个数据元素的关键字称为主关键字（Primarykey）；若能标识若干个数据元素的关键字称为次关键字（Secondary key）。,查找：根据给定的值，在查找表中查找是否存在关键字等于给定值的记录。若找到，则查找成功，查找结果可以是对应记
2、录在查找表中的位置或数据元素的值；或找不到，则查找不成功，查找结果可以给出一个操作标志或“空”指针。 内部查找与外部查找：若查找过程在内存中进行称之为内部查找，若查找过程需要访问外存，则称为外部查找。,二、在计算机中，查找主要分为以下几类：,静态查找：是指查询某个“特定”数据元素是否在查找表中（顺序查找、二分查找、索引表查找）； 动态查找：是指在查找过程中同时插入查找表中不存在的元素，或从表中删除已存在的某个数据元素，或从表中删除已存在的某个数据元素（二叉树查找）。 哈希查找：利用哈希函数，通过计算求得待查元素的存储地址的过程。,三、查找算法的衡量（散列表及查找）：,l 对于查找算法，把对关键
3、字的最多比较次数称作最大查找长度（MSL：maximum search length）。 l 平均比较次数称做平均查找长度（ASL:Average search length）。常把MSL和MSL和ASL作为基本的技术指标加以考查。,8.2 静态查找表,静态查找表主要有三种结构：顺序表有序顺序表索引顺序表 针对静态查找表的查找算法主要有： 顺序查找（线性查找）折半查找（二分查找）分块查找（索引顺序查找）,8.2.1 顺序表上顺序查找 查找思想:从表的一端开始，顺序扫描查找表，若关键字值与K相等，则查找成功，反回记录在表中的位置值，若查找不成功，则返回值为0。,存储：数据元素采用顺序表或线性链表
4、。数据存储说明：#define MAXSIZE 100#define KEYTYPE inttypedef structkeytype key;otherdata;SSELEMENT;typedef stnctSSELEMENT rMAXSIZEint len; SSTABLE;,8.2.2 有序表查找 二分查找（折半查找）：当静态表中记录的关 键字有序时，并且是按顺序存储结构存储的，则可 用二分查找法，可提高查找效率。 查找思想：用Low和high分别表示有序表的记录下界和上界 ，中间记录位置即为mid= (low+high)/2 当: kst.rmid.key 时,low=mid+1,继续
5、查找. 当下界(low)大于上界(high)时,查找失败并结束。,运算步骤： (1) low =0,high =10 ,故mid =5 ，待查范围是 0,10； (2) 若 S.listmid.key key，说明keylow ,mid-1，则令：high =mid1;重算 mid ； (4)若 S.list mid .key= = key，说明查找成功，元素序号=mid; 结束条件： （1）查找成功 ： S.listmid.key = key （2）查找不成功 ： highlow （意即区间长度小于0）,解：设定3个辅助标志: low,high,mid，有：mid= (low+high)/2
6、,折半查找举例：,Low指向待查元素所在区间的下界,high指向待查元素所在区间的上界,mid指向待查元素所在区间的中间位置,已知如下11个元素的有序表： （05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为21 的数据元素。,(2)算法的实现,int BinarySearch(SeqList S, DataType x) int low = 0, high = S.size-1;/确定初始查找区间上下界int mid;while(low x.key) high = mid - 1;return -1; /查找失败 ,算法效率分析：二分查找的比较次数不会超过二
7、叉树的深度 d= log2n +1,可见，二分查找的优点是速度快，但 前提是记录的关键字必须有序，且为向量（顺序存 储）存储结构。,也称分块查找，它是以索引顺序表表示的静态查找表，此方法在查找表上需建立一个索引表，索引表由若干表项构成，每个表项包括两部分内容。,关键字项指 针 项,8.2.3索引顺序表查找,思路：先让数据分块有序，即分成若干子表，要求每个子表中的数据元素值都比后一块中的数值小（但子表内部未必有序）。 然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。,例：,特点：块间有序，块内无序,分块查找过程举例：,索引表,块内最大关键字,各块起始地址,第
8、1块,第2块,第3块,特点：块间有序，块内无序,查找步骤分两步进行：, 对索引表使用折半查找法（因为索引表是有序表）； 确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；,查找：块间折半，块内线性,8.3 动 态 查 找,动态查找对表中的记录要经常进行插入和删除操作,动态查找的这种特性要求采用灵活的存储方法来组织查找表中的记录,重点介绍二叉排序树查找. 二叉排序树的概念：二叉排序树是一种特殊的二叉树,具有下列特点: (1)若它的左子树不空,则左子树上所有结点的关键字均小于它的根结点的关键字; (2) 若它的右子树不空,则右子树上的所有结点的关键字均大于它的根结点的
9、关键字; (3) 它的左子要、右子树分别也是二叉排序树。若构造了一棵二叉排序树，则其中根遍历的序列是按结点关键字递增排序的有序序列。,二叉排序树存储结构（Binary sort tree）采用二叉链表作为存储结构，结点类型如下： #define KEYTYPE int typedef struct node KEYTYPE key; otherdata struct node *lchile,*rchile; BSTNODE;,8.3.1二叉排序树的生成和插入 二叉排序树生成的形式算法描述为：对于一组关键字结点序列（1）第一个结点做为二叉排序树的要根结点；（2）从第二个结点起，将读入结点的关键
10、字和根结点的关键字进行比较: 读入结点的关键字等于根结点的关键字，则树中已有此结点，不作处理；读入结点的关键字大于根结点的关键字，则此结点插入到根结点的右子树中；读入结点的关键字小于根结点的关键字，则此结点插入到根结点的左了树中；子树中的插入过程与1.2.相同。,算法如下： insert_bst(KEYTYPE k, BSTNODE *p) if(p=NULL) p=malloc(sizeof(BSTNODE);p-lchild=NULL;p-rchild=NULL;p-key=k;else if(kp-key)insert_bst(k,p-rchild); elseinsert_bst(k,
11、p-lchile); ,8.3.2二叉排序树上的查找二叉排序树上查找的形式算法描述为：将给定值与二叉排序树的根结点的关键字比较： （1）给定值等于根结点的关键字，则根结点就是要查找的结点； （2）给定值大于根结点的关键字，则继续在根结点的右子树中查找； （3）给定值小于根结点的关键字，则继续在根结点的左子树中查找； （4）在子树中的查找过程和（1）（2）（3）相同。,45,如果改变输入顺序为（24，53， 45，45，12，24，90），,例：输入待查找的关键字序列=（45，24，53，45，12，24，90）,查找不成功则插入树中,则生成的二叉排序树形态不同,24,这种既查找又插入的过程称为
12、动态查找,二叉排序树上的查找算法： BSTNODE *search_node(KEYTYPE k,BSTNODE *r) BSTNODE *p;if(r=NULL)p=NULL;else if(k=r-key)p=r; else if(kr-key) p=search_nede(k,r_lchild); return p; ,查找算法分析：二叉排序树上进行的查找，查找过程中与结点关键字比较的次数至多不超过二叉排序树的深度，前图的平均查找长度（1+2+2+3+3+3+4+4+4+4）/11=30/11当二叉排序树的形态和二分查找的判定树一样时，它的平均查找长度和为Log2n成正比，当二叉排序树的
13、形态蜕变为单分支树时，平均查找长度与顺序查找一样，变为（n+1）/2.,8.3.3 二叉排序树的删除,l 从二叉排序树中删除一个结点后，要保证删除后 所得的二叉树仍是一棵二叉排序树。 l 删除操作首先进行查找，确定被删除结点是否在 二叉排序树中；然后根据被删结点的情况分别进行不 同的删除操作： l 被删结点为P指针所指，双亲结点用f指针所指， 被删除结点的左右子树用PL和PR表示，则删除结点的 操作可有如下的表达：,（1） 若删除结点是叶子结点，则只需修改被删结点的双亲结点的指针即可，如F-lchild=NULL； （2） 若被删结点只有左子树PL或只有右子树PR，只要令PL或PR直接成为其双
14、亲结点的左子树或右子树即可； （3） 若被删除结点的左子树和右子树均不空时，在删除该结点前为了保持其余结点之间的序列位置相对不变，先要用被删除结点在该树的中序遍历序列中的直接前驱结点的值取代被删除结点的值，然后再从二叉排序树中删除那个直接前驱结点。,84 散 列 表,841 散列表与散列函数,散列:由关键字通过确定的对应关系计算得到记录的存储位置的过程称散列。 哈希表:按散列形式的记录的集合称散列表或哈希表。所使用的对应关系称散列函数或哈希函数 散列查找：也称哈希查找，是由关键字通过计算得到记录存储地址的查找方法。 冲 突：通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不
15、同的关键码映射到同一个哈希地址上，这种现象称为冲突。,例：有数据元素序列(14，23，39，9，25，11)，若规定每个元素k的存储地址H（k）k，请画出存储结构图。,解：根据散列函数H（k）k ，可知元素14应当存入地址为14的单元，元素23应当存入地址为23的单元， 对应散列存储表（哈希表）如下：,根据存储时用到的散列函数H(k)表达式，即可查到结果！ 例如，查找key=9,则访问H(9)=9号地址，若内容为9则成功； 若查不到，应当设法返回一个特殊值，例如空指针或空记录。,14,11,9,23,25,39,明显缺点：空间效率低,有6个元素的关键码分别为：（14，23，39，9，25，11
16、）。 选取关键码与元素位置间的函数为H(k)=k mod 7,通过哈希函数对6个元素建立哈希表：,25,39,23,9,14,冲突现象举例：,6个元素用7个 地址应该足够!,H(14)=14%7=0,11,H(25)=25%7=4 H(11)=11%7=4,有冲突！,所以，哈希方法必须解决以下两个问题：,1）构造好的哈希函数 （a）所选函数尽可能简单，以便提高转换速度； （b）所选函数对关键码计算出的地址，应在哈希地址内集中并大致均匀分布，以减少空间浪费。,2）制定一个好的解决冲突的方案查找时，如果从哈希函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律地查询其它相关单元。,在哈希查找方法中，冲突是不可能避免的，只能尽可能减少。,常用的哈希函数构造方法有：,直接定址法 数字分析法 除留余数法,
