数据结构(C++版)第7章 查找技术ppt课件.ppt

《数据结构(C++版)第7章 查找技术ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章查找技术本章的主要内容是:查找的基本概念线性表的查找技术树表的查找技术散列表的查找技术查找的基本概念列表：由同一类型的数据元素组成的集合。关键码：数据元素中的某个数据项，可以标识列表中的一个或一组数据元素。键值：关键码的值。主关键码：可以唯一地标识一个记录的关键码。次关键码：不能唯一地标识一个记录的关键码。7.1概述50女李爽000525女齐梅000447女刘楠000325男张亮000238男王刚0001年龄性别姓名职工号1972年9月2003年7月1979年9月2003年7月1990年4月参

2、加工作查找的基本概念查找：在具有相同类型的记录构成的集合中找出满足给定条件的记录。7.1概述查找的结果：若在查找集合中找到了与给定值相匹配的记录，则称查找成功；否则，称查找失败。50女李爽000525女齐梅000447女刘楠000325男张亮000238男王刚0001年龄性别姓名职工号1972年9月2003年7月1979年9月2003年7月1990年4月参加工作静态查找：不涉及插入和删除操作的查找。动态查找：涉及插入和删除操作的查找。7.1概述查找的基本概念静态查找适用于：查找集合一经生成，便只对其

3、进行查找，而不进行插入和删除操作，或经过一段时间的查找之后，集中地进行插入和删除等修改操作；动态查找适用于：查找与插入和删除操作在同一个阶段进行，例如当查找成功时，要删除查找到的记录，当查找不成功时，要插入被查找的记录。7.1概述查找的基本概念查找结构：面向查找操作的数据结构，即查找操作所基于的数据结构。查找结构查找方法集合中元素之间不存在明显的组织规律，不便查找。集合线性表树表散列表本章讨论的查找结构：线性表：适用于静态查找，主要采用顺序查找技术、折半查找技术。树表：适用于动态查找，主要采用二叉排

4、序树的查找技术。散列表：静态查找和动态查找均适用，主要采用散列技术。7.1概述查找结构：面向查找操作的数据结构，即查找基于的数据结构。查找的基本概念查找算法的性能查找算法时间性能通过关键码的比较次数来度量。关键码的比较次数与哪些因素有关呢？⑴算法；⑵问题规模；⑶待查关键码在查找集合中的位置；⑷查找频率。7.1概述查找频率与算法无关，取决于具体应用。通常假设pi是已知的。查找算法的性能查找算法时间性能通过关键码的比较次数来度量。查找算法的时间复杂度是问题规模n和待查关键码在查找集合中的位置k的函数，记

5、为T(n，k)。同一查找集合、同一查找算法，关键码的比较次数与哪些因素有关呢？平均查找长度：将查找算法进行的关键码的比较次数的数学期望值定义为平均查找长度。计算公式为：其中：n：问题规模，查找集合中的记录个数；pi：查找第i个记录的概率；ci：查找第i个记录所需的关键码的比较次数。结论：ci取决于算法；pi与算法无关，取决于具体应用。如果pi是已知的，则平均查找长度只是问题规模的函数。查找算法的性能ASLå==niiicp17.2线性表的查找技术顺序表的查找普通的顺序查找方法带监视哨的顺序查找方法折

6、半查找折半查找的判定树顺序查找（线性查找）基本思想：从线性表的一端向另一端逐个将关键码与给定值进行比较，若相等，则查找成功，给出该记录在表中的位置；若整个表检测完仍未找到与给定值相等的关键码，则查找失败，给出失败信息。101524612354098550123456789i7.2线性表的查找技术例：查找k＝35iii顺序查找（线性查找）7.2线性表的查找技术intSeqSearch1(intr[],intn,intk)//数组r[1]~r[n]存放查找集合{i=n;while(i>0&&r[i]!=

7、k)i--;returni;}基本思想：设置“哨兵”。哨兵就是待查值，将它放在查找方向的尽头处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。改进的顺序查找101524612354098550123456789i例：查找k＝35iii哨兵35查找方向基本思想：设置“哨兵”。哨兵就是待查值，将它放在查找方向的尽头处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。改进的顺序查找101524612354098550123456789i例：查找k＝25

8、ii25查找方向iiiiiiiintSeqSearch2(intr[],intn,intk)//数组r[1]~r[n]存放查找集合{r[0]=k;i=n;while(r[i]!=k)i--;returni;}顺序查找的性能ASL==å=niicp1å+-=niiinp1)1(i=(n+1)/2=O(n)单链表的顺序查找intLinkSearch::SeqSearch2(Node*first,intk){Node*p;intcount=0;p=first->next;i