数据结构JAVA语言描述习题答案[刘小晶等主编]第8章查找[Java版]

《数据结构JAVA语言描述习题答案[刘小晶等主编]第8章查找[Java版]》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章查找Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.1教学内容8.1查找的基本概念8.2静态表查找8.3动态表查找8.4哈希表查找Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.教学重点与难点重点：掌握查找的基本概念以及各

2、种常见查找方法的实现。难点：动态表查找Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.，就是在由一组记录组成的集合中寻找主关键字值等于给定值的某个记录，或是寻找属性值符合特定条件的某些记录。8.1查找的基本概念1.查找为简单起见，本章所涉及的关键字均指主关键字，且假设关键字的类型为Comparable接口类。Evaluationonly.CreatedwithAspose.Sli

3、desfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.48.1查找的基本概念2.查找表是一种以同一类型的记录构成的集合为逻辑结构，以查找为核心运算的数据结构。由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.58.1查找的基本概念

4、-查找表根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）的过程。查找：若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置；查找成功:查找不成功:若在查找表中不存在这样的记录，则称“查找不成功”。查找结果给出“空记录”或“空指针”。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.68.1查找的基本概念-查

5、找表对查找表经常进行的操作:1）建表；2）查找；3）读表元；4）修改（如插入、删除等）。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.78.1查找的基本概念-查找表仅作查找和读表元操作的查找表。静态查找表：如果在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果在“在查找表中”的数据元素，此类查找表就称为“动态查找表”。

6、动态查找表：查找表可分为两类:需做修改操作的查找表。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.88.1查找的基本概念平均查找长度如何评价查找算法的时间效率？衡量一个查找算法效率优劣的标准是什么？Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011Asp

7、osePtyLtd.98.1查找的基本概念3.平均查找长度(AverageSearchLength)为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值其中:n为表中记录个数，Pi为查找表中第i个记录的概率，且　，Ci为找到该记录时，曾和给定值比较过的关键字的个数。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.108.1查找的基本概念如何进行查找？查找的方法取决于

8、查找表的结构Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.111.顺序查找2.二分查找3.分