VC编程教程 第8章 查找

《VC编程教程 第8章 查找》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、查找表是一种非常灵活的数据结构，对于不同的存储结构，其查找方法不同。为了提高查找速度，有时会采用一些特殊的存储结构。本章将介绍以线性结构、树型结构及哈希表结构为存储结构的各种查找算法。第八章查找[本章学习要求]掌握：查找的基本概念和查找算法的评价方法；掌握：顺序表的查找算法，有序表的折半查找算法以及分块查找的算法思想；掌握：二叉排序树的基本概念、二叉排序树的建立、查找、删除操作；了解：平衡二叉树基本概念和其平衡调整方法；了解：B-树查找算法的基本实现思想；掌握：散列查找基本概念、常用哈希算法以及冲突的处理方法。查找——也叫检索，是根据给定的某个值，在查找表中确定一个关

2、键码等于给定值的记录或数据元素查找表——是一种以集合为逻辑结构、以查找为核心的数据结构查找表常做的运算有：建表、查找、读表元、对表做修改（插入或删除）静态查找表：对查找表的操作不包括对表的修改操作动态查找表：在查找的同时插入不存在的数据元素，或删除已存在的指定元素关键码——是数据元素中某个数据项的值，它可以标识一个数据元素主关键码、次关键码8.1基本概念查找方法评价查找速度占用存储空间多少算法本身复杂程度平均查找长度ASL(AverageSearchLength)：为确定记录在表中的位置，所需进行的关键码比较次数的期望值叫查找算法的~8.2静态查找表8.2.1静态查找

3、表结构通常将数据元素组织为一个线性表，存储结构可以是顺序或链式。顺序存储结构：#defineMAXSIZE100typedefstruct{datatypedata[MAXSIZE];intlength;}S_TBL;链式存储结构：typedefstructnode{datatypedata;structnode*next;}NodeType;typedefstruct{KeyTypekey;/*关键码字段*/……/*其它信息*/}datatype;8.2.2顺序查找查找过程：从表的一端开始逐个进行记录的关键码和给定值的比较算法描述i例0123456789101151

4、3192137566475808892找6464监视哨iiii比较次数=5比较次数：查找第n个元素：1查找第n-1个元素：2……….查找第1个元素：n查找第i个元素：n+1-i查找失败：n+1顺序查找方法的ASL查找失败情况下：ASL=n+1优点是算法简单且适应面广，无论查找表中元素是否有序均可使用。缺点是平均检索长度较大，特别是当n很大时，检索效率较低。8.2.3折半查找查找过程：每次将待查记录所在区间缩小一半适用条件：采用顺序存储结构的有序表算法实现设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,kx为给定值初始时，令low=1,h

5、igh=n,mid=(low+high)/2让kx与mid指向的记录比较若kx==tbl->data[mid].key，查找成功若kxdata[mid].key，则high=mid-1若kx>tbl->data[mid].key，则low=mid+1重复上述操作，直至low>high时，查找失败算法描述lowhighmid例1234567891011513192137566475808892找211234567891011513192137566475808892lowhighmid1234567891011513192137566475808892l

6、owhighmid例1234567891011513192137566475808892lowhighmid找701234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhigh1185210741936判定树：1234567891011513192137566475808892ASL=(1

7、*1+2*2+4*3+4*4)/11=3查找过程可以用二叉树来表示。查找某个结点所比较的次数等于该结点的层次数。实际上查找某个结点的过程就是从根结点到相应的结点的路径。描述查找过程的二叉树叫判定树算法评价有n个结点的判定树的深度k=log2n+1判定树非完全二叉树但它的叶子结点所在层次之差最多为1，则n个结点的判定树的深度和n个结点的完全二叉树的深度相同折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度折半查找的ASL8.2.4分块查找思想：将表分成几块，块内无序，块间有序；建立索引表，先在索引表确定待查记录所在块，再在块内查找适用条件