查找比较全的

《查找比较全的》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程的内容17.1基本概念7.2静态查找表7.3动态查找表7.4哈希表第7章查找29.1基本概念——若表中存在特定元素，称查找成功，应输出该记录；——否则，称查找不成功（也应输出失败标志或失败位置）查找表查找查找成功查找不成功静态查找动态查找关键字主关键字次关键字——由同一类型的数据元素（或记录）构成的集合。——查询(Searching)特定元素是否在表中。——只查找，不改变集合内的数据元素。——既查找，又改变（增减）集合内的数据元素。——记录中某个数据项的值，可用来识别一个记录(预先确定的记录的某种标志)——可以唯一标识一个记录的关键字例如“学号”例如“女”是一种数据结构——识

2、别若干记录的关键字3（2）对查找表常用的操作有哪些？查询某个“特定的”数据元素是否在表中；查询某个“特定的”数据元素的各种属性；在查找表中插入一元素；从查找表中删除一元素。（3)有哪些查找方法？查找方法取决于表中数据的排列方式;讨论：（1）查找的过程是怎样的？给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字值等于K的记录，如找到则输出该记录，否则输出查找不成功的信息。例如查字典针对静态查找表和动态查找表的查找方法也有所不同。“特定的”=关键字4明确：查找的过程就是将给定的K值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度（AS

3、L：averagesearchlength）。物理意义：假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为ASL。显然，ASL值越小，时间效率越高。（4）如何评估查找方法的优劣？5针对静态查找表的查找算法主要有：9.2静态查找表静态查找表的抽象数据类型参见教材P216。一、顺序查找（线性查找）二、折半查找（二分或对分查找）三、静态树表的查找四、分块查找（索引顺序查找）6一、顺序查找（Linearsearch，又称线性查找）（1）顺序表的机内存储结构：typedefstruct{ElemType*elem;//表基址，0号单元留空。表容量为全部元素intleng

4、th;//表长，即表中数据元素个数}SSTable;顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。对顺序结构如何线性查找？见下页之例对单链表结构如何线性查找？函数虽未给出，但也很容易编写；只要知道头指针head就可以“顺藤摸瓜”；对非线性树结构如何顺序查找?可借助各种遍历操作！7二、折半查找（又称二分查找或对分查找）优点：算法简单，且对顺序结构或链表结构均适用。缺点：ASL太长，时间效率太低。这是一种容易想到的查找方法。先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至右半部内查找；再取其中值比较，每次缩小1/2的范围，直到

5、查找成功或失败为止。对顺序表结构实现折半查找算法对单链表结构如何折半查找？——无法实现！因全部元素的定位只能从头指针head开始对非线性(树)结构如何折半查找？——可借助二叉排序树来查找（属动态查找表形式）。如何改进？讨论④顺序查找的特点：8②运算步骤：(1)low=1,high=11,mid=6，待查范围是[1,11]；(2)若ST.elem[mid].keykey，说明key[low,mid-1]，则令：high=mid–1

6、;重算mid；(4)若ST.elem[mid].key=key，说明查找成功，元素序号=mid;结束条件：（1）查找成功：ST.elem[mid].key=key（2）查找不成功：high≤low（意即区间长度小于0）解：①先设定3个辅助标志:low,high,mid，折半查找举例：Low指向待查元素所在区间的下界high指向待查元素所在区间的上界mid指向待查元素所在区间的中间位置已知如下11个元素的有序表：（0513192137566475808892）,请查找关键字为21和85的数据元素。显然有：mid=(low+high)/29讨论①若关键字不在表中，怎样得知和停止？——典

7、型标志是：当查找范围的上界≤下界时停止查找。讨论②二分查找的效率（ASL）1次比较就查找成功的元素有1个（20），即中间值；2次比较就查找成功的元素有2个（21），即1/4处（或3/4）处；3次比较就查找成功的元素有4个（22），即1/8处（或3/8）处…4次比较就查找成功的元素有8个（23），即1/16处（或3/16）处………则第m次比较时查找成功的元素会有（2m-1）个；为方便起见，假设表中全部n个元素＝2m-1个，此时就不讨论