数据结构-8 查找

《数据结构-8 查找》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、井冈山大学计算机科学系井冈山大学计算机科学系冷明冷明lengming@jgsu.edu.cnlengming@jgsu.edu.cn基本概念基本概念查找表用于查找的数据元素集合称为查找表。查找表由同一类型的数据元素（或记录）构成。静态查找表若只对查找表进行如下两种操作：（1）在查找表中查看某个特定的数据元素是否在查找表中，（2）检索某个特定元素的各种属性，则称这类查找表为静态查找表。静态查找表在查找过程中查找表本身不发生变化。对静态查找表进行的查找操作称为静态查找。动态查找表若在查找过程中可以将查找表中不存在的数据元素插入，或者从查找表中删除某

2、个数据元素，则称这类查找表为动态查找表。动态查找表在查找过程中查找表可能会发生变化。对动态查找表进行的查找操作称为动态查找。关键字是数据元素中的某个数据项。唯一能标识数据元素（或记录）的关键字（即每个元素的关键字值互不相同）称为主关键字；若查找表中某些元素的关键字值相同，称这种关键字为次关键字。例如，银行帐户中的帐号是主关键字，而姓名是次关键字。查找算法的时间效率查找过程的主要操作是关键字的比较，所以通常以“平均比较次数”来衡量查找算法的时间效率。查找在数据元素集合中查找满足某种条件的数据元素的过程称为查找。最简单且最常用的查找条件是“关键字值

3、等于某个给定值”，在查找表搜索关键字等于给定值的数据元素（或记录）。若表中存在这样的记录，则称查找成功，此时的查找结果应给出找到记录的全部信息或指示找到记录的存储位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可以给出一个空记录或空指针。若按主关键字查找，查找结果是唯一的；若按次关键字查找，结果可能是多个记录，即结果可能不唯一。查找方法评价：¾查找速度¾占用存储空间多少¾算法本身复杂程度¾平均查找长度ASL(AverageSearchLength)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值。n对含

4、有n个记录的表，ASL=∑picii=1n其中：pi为查找表中第i个元素的概率，∑pi=1i=1c为找到表中第i个元素所需比较次数i9.1静态查找表静态查找是指在静态查找表上进行的查找操作，在查找表中查找满足条件的数据元素的存储位置或各种属性。9.1.1顺序查找(SequentialSearch)1.顺序查找的基本思想顺序查找是一种最简单的查找方法。其基本思想是将查找表作为一个线性表，可以是顺序表，也可以是链表，依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较，若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之

5、，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。2.顺序查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较。算法描述：Ch7_1.txt找6401234567891011例64513192137566475808892iiiii监视哨比较次数：比较次数=5查找第n个元素：1查找第n-1个元素：2……….查找第1个元素：n查找第i个元素：n+1-i查找失败：n+1顺序查找方法的ASLn对含有n个记录的表，ASL=∑picii=11设表中每个元素的查找概率相等p=innn11n(n+1)n+1则ASL=∑pi

6、ci=∑(n−i+1)=⋅=i=1ni=1n223.链表的顺序查找链表的顺序查找是指将查找表作为线性表并以链式存储结构存储，用顺序查找方法查找与指定关键字值相等的记录。链表的类型定义如下所示：typedefstructnode{keytypekey;//结点的关键字类型anytypeotheritem;//结点的其他成分structnode*next;//指向链表结点的指针}Link_Node,*Link;将查找表中的数据元素用这种结构的结点表示，并以指向头结点的指针标识。对链表实现顺序查找就是在有头结点的链式查找表中查找关键字值等于给定值的记

7、录。若查找成功，返回指向相应结点的指针，否则返回空指针。Link_Node*link_search(Linkh,keytypek){//link为带头结点链表的头指针，查找关键字值等//于k的记录：查找成功，返回指向找到的结点的//指针，查找失败返回空指针p=h->next;while((p!=NULL)&&(p->key!=k))p=p->next;returnp;}顺序查找特点：算法简单，对表的结构无任何要求；但是执行效率较低，尤其当n较大时，不宜采用这种查找方法。平均查找长度：ASL=(n+1)/29.1.2折半查找(BinarySear

8、ch)查找过程：每次将待查记录所在区间缩小一半适用条件：采用顺序存储结构的有序表先求位于搜索区间正中的对象的下标mid，用其关键码与给定值x比较:r[