数据结构单元7-查找

1、数据结构,教学目标,【知识目标】 了解查找的基本概念 掌握顺序查找的基本思想、算法实现和查找效率分析 掌握二分查找的基本思想、算法实现和查找效率分析 掌握分块查找的基本思想、算法实现和查找效率分析 掌握二叉查找树的插入、删除、建树和查找算法及时间性能 掌握哈希查找方法、哈希函数的构造和解决冲突的方法 【能力目标】 具有选择恰当的查询算法解决实际问题的能力,引例描述高校最低录取分数线查询,该系统用于学生、学生家长和其他人员查询各高校的最低录取分数线，为他们的了解高校录取情况、做出正确的选择和决策提供有必要的信息。该系统有以下六项功能：（1）按考生分数查询高校信息； （2）按给定分数查询一定范围内的高校信息，包括：查询录取分数线比给定分数高（包括相等）的高校信息和录取分数线比给定分数低（包括相等）的高校信息； （3）按给定的分数范围查询高校信息； （4）能够添加高校信息； （5）为用户提供系统帮助，以便更好的使用系统； （6）安全退出本系统。,演示执行,一、基本概念 1查找定义 给定一个值K，在含有n个结点的表中找出关键字等于给定值K的结点。若找到，则查找成功，返回该结点的信息或该结点在表

2、中的位置；否则查找失败，返回相关的指示信息。 2动态查找表和静态查找表 若在查找的同时对表做修改操作（如插入和删除），则相应的表称之为动态查找表。否则称之为静态查找表。 3内查找和外查找 若整个查找过程都在内存进行，则称之为内查找；反之，若查找过程中需要访问外存，则称之为外查找。,7.1 查找的基本概念,知识储备,4平均查找长度（Average Search Length）ASL 查找运算的主要操作是关键字的比较，所以通常把查找过程中对关键字需要执行的平均比较次数（也称为平均查找长度）作为衡量一个查找算法效率优劣的标准。 平均查找长度 ASL定义： 即ASL等于每个结点的查找概率pi与比较次数ci的乘积的和。其中： （1）n是结点的个数； （2）pi是查找第i个结点的概率。若不特别声明，认为每个结点的查找概率相等，即pl=p2=pn=1/n； （3）ci是找到第i个结点所需进行的比较次数。,一、顺序查找（sequential search） 顺序查找又称线性查找，是最基本的查找方法之一。顺序查找既适用于顺序表，也适用于链表。 1基本思想 从表的一端开始，顺序扫描线性表，依次按给定值kx

3、与关键字（Key）进行比较，若相等，则查找成功，并给出数据元素在表中的位置；若整个表查找完毕，仍未找到与kx相同的关键字，则查找失败，给出失败信息。 2基于顺序结构的顺序查找算法的类型描述,7.2 静态查找,#define N 20 typedef int KeyType;/关键字字段类型定义 typedef char OtherdataType;/非关键字字段类型定义 typedef struct KeyType key; OtherdataType data; NodeType; typedef NodeType SeqListN+1;/0号单元用作监视哨,3具体算法 4算法分析 （1）算法中监视哨R0的作用 为了在for循环中省去判定防止下标越界的条件i1，从而节省比较的时间。 （2）成功时的顺序查找的平均查找长度 在等概率情况下，pi=1/n(1in)，故成功的平均查找长度为(n+2+1)/n= (n+1)/2，即查找成功时的平均比较次数约为表长的一半，若K值不在表中，则须进行n+1次比较之后才能确定查找失败。 （3）顺序查找的优缺点 优点是算法简单，且对表的结构无任何要求，无

4、论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。缺点是查找效率低，因此，当n较大时不宜采用顺序查找。,int SeqSearch(Seqlist R,KeyType K) /在顺序表R1.n中查找关键字为K的结点 int i; R0.key=K; /设置哨兵 for(i=n;Ri.key!=K;i-);/从表后往前找 return i;/若i为0，表示查找失败，否则Ri是要找的结点 ,2,二、二分查找（binary search） 1二分查找：二分查找又称折半查找，它是一种效率较高的查找方法。 二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有序表是递增有序的。 2二分查找的基本思想 设Rlow.high是当前的查找区间。 （1）首先确定该区间的中点位置：mid=(low+high)/2; （2）然后将待查的K值与Rmid.key比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找，具体方法如下：,若Rmid.keyK，则由表的有序性可知Rmidn. key均大于K，因此若表中存在关键字等于K

5、的结点,则该结点必定是在位置mid左边的子表R1mid-1中，故新的查找区间是左子表R1.mid-1； 若Rmid.keyK，类似地，则新的查找区间是右子表Rmid+1n。下次在新的查找区间进行查找。 因此，从初始的查找区间R1.n开始，每经过一次与当前查找区间的中点位置上的结点关键字的比较，就可确定查找是否成功，不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点，或者直至当前的查找区间为空（即查找失败）时为止。,3二分查找算法 int BinSearch(SeqList R,KeyType K) int low=1,high=n,mid;/置当前查找区间的初值 while(lowK) high=mid-1; else low=mid+1; return 0;/当lowhigh时查找区间为空，查找失败 ,4算法分析 （1）二分查找的平均查找长度：在等概率假设下，二分查找成功时平均查找长度为：ASLbn=(n+1)/n)lg(n+1)-1；最坏情况下查找成功的比较次数为： 。 （2）二分查找的优缺点：二分查找效率高，但要将表按关键字排序；二分查找只适用顺序存储结构。对

6、经常进行插入和删除操作的表，不宜采用此方法。,三、分块查找（block search） 分块查找又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。 1二分查找表存储结构 二分查找表由“分块有序”的线性表和索引表组成。 （1）“分块有序”的线性表：表R1.n均分为b块，前b-1块中结点个数为是s=n/b，第b块的结点数小于等于s；每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是“分块有序”的。 （2）索引表：抽取各块中的最大关键字及其起始位置构成一个索引表IDl.b，即：IDi(1ib)中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表是一个递增有序表。,【示例】图7-1给出的就是满足上述要求的存储结构，其中R只有15个结点，被分成3块，每块中有5个结点，第一块中最大关键字22小于第二块中最小关键字24，第二块中最大关键字44小于第三块中最小关键字47。,2分块查找的基本思想 先在索引表中采用二分查找或顺序查找，以确定待查的结点在哪一块；然后在已确定的块中进行顺序查找。 3算法分析 （1）平均查找长度

7、ASL：将含有n个元素的线性表平均分成b块，每块有s个元素。整个查找过程的平均查找长度是两次查找的平均查找长度之和。 以二分查找来确定块，分块查找成功时的平均查找长度ASLblk=ASLbn+ASLsq =lg(b+1)-1+(s+1)/2。 以顺序查找确定块，分块查找成功时的平均查找长度ASLblk=(b+1)/2+(s+1)/2 =(s2+2s+n)/(2s)。 （2）分块查找的优缺点：在表中插入或删除记录时，只要找到该记录所属的块，就在该块内进行插入和删除运算；因块内记录的存放是任意的，所以插入或删除无须移动大量记录；分块查找的主要代价是增加辅助存储空间和将初始表分块排序的运算。,一、二叉排序树（Binary Sort Tree） 1二叉排序树的定义 二叉排序树又称二叉查找（搜索）树（Binary Search Tree）。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树： （1）若它的左子树非空，则左子树上所有结点的值均小于根结点的值； （2）若它的右子树非空，则右子树上所有结点的值均大于根结点的值； （3）左、右子树本身又各是一棵二叉排序树。 上述性质简称二叉排序树

8、性质（BST性质），故二叉排序树实际上是满足BST性质的二叉树。,7.3 动态查找,2二叉排序树的特点 （1）二叉排序树中任一结点x，其左(右)子树中任一结点y（若存在）的关键字必小（大）于x的关键字。 （2）二叉排序树中，各结点关键字是惟一的。 （3）按中序遍历该树所得到的中序序列是一个递增有序序列。 注意：实际应用中，被查找的数据集中各元素的关键字可能相同，所以可将BST性质（1）里的“小于”改为“小于等于”，或将性质（2）里改为“大于等于”。,【示例】如图7-2所示的两棵树均是二叉排序树，满足BST性质，它们的中序序列均为有序序列2，3，4，5，7，8。,3二叉排序树的结构描述 typedef int KeyType; /关键字类型定义 typedef char OtherdataType; /非关键字字段类型定义 typedef struct node /结点类型 KeyType key; /关键字项 OtherdataType data;/其它数据域 struct node *lchild,*rchild;/左右孩子指针 BSTNode; typedef BSTNode *B

9、STree; /BSTree是二叉排序树的类型,二、二叉排序树上的运算 1二叉排序树的插入 二叉排序树插入新结点的过程：在二叉排序树中插入新结点，要保证插入后仍满足BST性质。插入过程是： （1）若二叉排序树T为空，则为待插入的关键字key申请一个新结点，并令其为根； （2）若二叉排序树T不空，则将key和根的关键字比较： 若二者相等，则树中已有此关键字key，无须插入； 若keykey，则将key插入根的左子树中； 若keyT-key，则将它插入根的右子树中。 子树中的插入过程与上述的树中插入过程相同。如此进行下去，直到将key作为一个新的叶结点的关键字插入到二叉排序树中，或者直到发现树中已有此关键字为止。 二叉排序树插入新结点的递归算法 二叉排序树插入新结点的非递归算法,void InsertBSTR(BSTree *Tptr,KeyType key) if(!(*Tptr) (*Tptr)=(BSTNode *)malloc(sizeof(BSTNode); if(*Tptr =NULL) puts (“内存申请不成功!“);return; (*Tptr)-key=key; (*Tptr)-lchild=NULL; (*Tptr)-rchild=NULL; else if(*Tptr)-key=key) return; if(keykey) InsertBSTR( ,void InsertBST(BSTree *Tptr,KeyType key) /若二叉排序树 *Tptr中没有关键字为key,则插入,否则直接返回 BSTNode *f,*p=*Tptr; /p的初值指向根结点 while(p) /查找插入位置 if(p-key=key) return;/树中已有key,无须插入 f=p; /f保存当前查找的结点 p=(keykey)?p-lchild:p-rchild;/*若keykey，则在左子树中查找，否则在右子树中查找*/ p=(BSTNode *

《数据结构单元7-查找》由会员101****457分享，可在线阅读，更多相关《数据结构单元7-查找》请在金锄头文库上搜索。