数据结构-C语言-第九章查找

第九章查找4学时数据结构教学目标熟练掌握顺序表和有序表（折半查找）的查找算法及其性能分析方法；熟练掌握二叉排序树的构造和查找算法及其性能分析方法；掌握二叉排序树的插入算法，了解二叉排序树的删除算法；熟练掌握哈希函数（除留余数法）的构造熟练掌握哈希函数解决冲突的方法及其特点数据结构查找的基本概念查找表（SearchTable）：由同一类型的数据元素（或记录）构成的集合，是一种以集合为逻辑结构、以查找为核心运算的数据结构。静态查找表：只对查找表进行查询某个特定的数据元素或某个特定数据元素的各种属性的操作。如：查询成绩表中是否有某学生或该学生某门课程的成绩。动态查找表：对查找表进行插入或删除某个数据元素的操作。如：插入某个学生某门课程的成绩。数据结构查找的基本概念关键字：是数据元素中某个数据项的值，它可以标识一个数据元素主关键字：可以唯一标识一个记录的关键字次关键字：可以标识若干个记录的关键字查找(Search)：也称检索，是根据给定的某个值，在查找表中确定一个关键字等于给定值的记录或数据元素。查找成功：即找到满足条件的数据对象，这时作为结果可报告该对象在结构中的位置,还可给出该对象中的具体信息。查找不成功：或搜索失败。作为结果应报告一些信息,如失败标志、位置等。数据结构查找的基本概念衡量查找算法的标准：平均查找长度ASL(AverageSearchLength)：为确定记录在表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。n：记录的个数pi：查找第i个记录的概率(通常认为pi=1/n)ci：找到第i个记录所需的比较次数算法所需要的存储量和算法的复杂性等niiicpASL111niip数据结构静态查找表(基于线性表的查找)第一节数据结构查找方式：从表的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者符合，查到所要找的元素为止。否则就是表中没有要找的元素，检索不成功。适用范围：顺序表或线性链表表示的静态查找表，表内元素之间无序。顺序表的表示typedefstruct{ElemType*elem;//表基址intlength;//表长}SSTable;顺序查找实现intLocateELem(SqListL,ElemTypee){for(i=0;iL.length;i++)if(L.elem[i]==e)returni+1;return0;}9.1.1顺序查找（线性查找）改进：把待查关键字key存入表头（“哨兵”），从后向前逐个比较，可免去查找过程中每一步都要检测是否查找完毕，加快速度。数据结构9.1.1顺序查找intSearch_Seq(SSTableST,KeyTypekey){//若成功返回其位置信息，否则返回0ST.R[0].key=key;for(i=ST.length;ST.elem[i].key!=key;--i);//不用for(i=n;i0;--i)或for(i=1;i=n;i++)returni;}i例01234567891011513192137566475808892找6464监视哨iiii比较次数=5比较次数：查找第n个元素：1查找第n-1个元素：2……….查找第1个元素：n查找第i个元素：n+1-i查找失败：n+1数据结构9.1.1顺序查找顺序查找方法的特点表结构为有序表、无序表均可适用；存储结构为顺序存储和链式存储的表均适用；适合于短表，方法简单；时间复杂度为O(n)；平均查找长度比其他方法大，查找成功时：212)1(11111nnnnincpASLnpniniiii则概率相等设表中每个元素的查找数据结构9.1.2折半查找查找方法：首先选择表中间的一个记录，比较其关键字与要查找关键字的值；若要找的记录的关键字值大，则再取表的后半部的中间记录进行比较；否则取前半部的中间记录进行比较，如此反复，直到找到为止。适用范围：采用顺序存储结构的有序表数据结构9.1.2折半查找折半查找的实现令low=1,high=n,mid=(low+high)/2若kelem[mid].key，则high=mid-1若kelem[mid].key，则low=mid+1lowhighmid例11234567891011513192137566475808892找21当k==elem[mid].key,查找成功！数据结构9.1.2折半查找lowhighmid1234567891011513192137566475808892找701234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighlowhigh不成功！数据结构9.1.2折半查找算法描述设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点，k为给定值。初始时，令low=1,high=n,mid=(low+high)/2让k与mid指向的记录比较若k==elem[mid].key，查找成功若kelem[mid].key，则high=mid-1若kelem[mid].key，则low=mid+1重复上述操作，直至lowhigh时，查找失败数据结构9.1.2折半查找intSearch.Bin(SSTableST,KeyTypekey){//在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。low=1;high=ST.length;//置区间初值while(low=high){mid=(low+high)/2;ifEQ(key,ST.elem[mid].key)returnmid;//找待查元素elseifLT(key,ST.elem[mid].key)high=mid-1;//继续在前半区间进行查找elselow=mid+1;//继续在后半区间进行查找}return0;//顺序表中不存在待查元素}//Search.Bi数据结构9.1.2折半查找11852107419361234567891011513192137566475808892折半查找的性能分析有n个结点的判定树的深度为log2n+1，折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度。判定树：描述查找过程的二叉树数据结构9.1.2折半查找折半查找方法的特点仅适用于有序表；只适用顺序存储结构的表，要求表中元素基本不变，在需要插入或删除运算时，影响检索效率；平均查找长度最小，ASL=(n+1)/n*log2(n+1)-1ASL=log2(n+1)-1(N50)时间复杂度O(log2n)数据结构9.1.3索引顺序查找（分块查找）查找方法：将n个元素均匀地分成块，每块有s个记录，块间按大小排序，块内元素不排序。要建立一个块的最大（或最小）关键字表。查找时，先用顺序查找或折半查找法由最大关键字查出所在的块，再用顺序查找法在块中查找。适用条件：分块有序表数据结构9.1.3索引顺序查找（分块查找）12345678910111213141516171822121389203342443824486058745786532248861713索引表查38成功算法实现：用数组存放待查记录，每个数据元素至少含有关键字域建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针。数据结构9.1.3索引顺序查找（分块查找）分块查找方法特点：对存储结构为顺序和线性链表的均适用；平均查找长度比顺序查找小；用折半查找确定所在块时：若用顺序查找确定所在块时：21logASL2ssn121ASLssn数据结构9.1.4基于线性表的查找方法比较顺序查找折半查找分块查找ASL最大(N+1)/2最小ASL=log2(n+1)-1两者之间表结构有序表无序表有序表分块有序表存储结构顺序存储线性链表顺序存储顺序存储线性链表数据结构数据结构动态查找表(基于树的查找)第二节数据结构动态查找表的特点表结构在查找过程中动态生成对于给定值key，若表中存在，则成功返回；否则插入关键字等于key的记录二叉排序树平衡二叉树B-树B+树键树数据结构9.2.1二叉排序树二叉排序树的定义：二叉排序树或是空树，或是满足如下性质的二叉树：若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于等于根结点的值；其左右子树本身又各是一棵二叉排序树数据结构9.2.1二叉排序树下列图形中，哪个不是二叉排序树？1624510379831921074658数据结构中序遍历二叉排序树后的结果有什么规律？9.2.1二叉排序树353123745100246190783，12，24，37，45，53，61，78，90，100递增得到一个关键字的递增有序序列数据结构9.2.1二叉排序树二叉排序树的操作－查找若查找的关键字等于根结点，成功否则若小于根结点，查其左子树若大于根结点，查其右子树在左右子树上的操作类似7218123810找8数据结构7.2.1数组（邻接矩阵）表示法二叉排序树查找的算法思想若二叉排序树为空，则查找失败，返回空指针。若二叉排序树非空，将给定值key与根结点的关键字T-data.key进行比较：①若key等于T-data.key，则查找成功，返回根结点地址；②若key小于T-data.key，则进一步查找左子树；③若key大于T-data.key，则进一步查找右子树。数据结构9.2.1二叉排序树BiTreeSearchBST(BiTreeT,KeyTypekey){//在根指针bst所指二叉排序树中，递归查找某关键字等于key的元素，若查找成功，返回指向该元素结点指针，否则返回空指针if((!T)||key==T-data.key)returnT;//查找成功elseif(T-data.keykey)returnSearchBST(T-lchild,key);//在左子树继续查找elsereturnSearchBST(T-rchild,key);//在右子树继续查找}数据结构9.2.1二叉排序树StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&P){//在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元//素，若查找成功，则指针p指向该数据元素结点，并返回TRUE，否//则指针p指向查找路径上访问的最后一个结点并返回FALSE，指针f指向T的双亲，其初始调用值为NULLif(!T){p=f;returnFALSE;}//查找不成功elseifEQ(key,T-data.key){p=T;returnTRUE;}//查找成功elseifLT(key,T-data.key)returnSearchBST(T-lchild,key,T,P)//在左子树中继续查找elsereturnSearchBST(T-rchild,key,T,P)//在右子树中继续查找}//SearchBST数据结构9.2.1二叉排序树二叉排序树的操作－插入若二叉排序树为空，则插入结点应为根结点否则，继续在其左、右子树上查找树中已有，不再插入树中没有，查找直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子插入的元素一定在叶子结点上35312374510024619078插入2020数据结构9.2.1二叉排序树二叉排序树的操作－创建从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树。第一个关键字是根结点。例{10，18，3，8，12，2，7