第八章查找(Search)2007.9
第八章 查找 (Search) 2007.9
主要内容8.1查找的基本概念8.2线性表的查找8.3树表的查找
主要内容 8.1 查找的基本概念 8.2 线性表的查找 8.3 树表的查找
8.1查找的基本概念
8.1 查找的基本概念
·查找的对象：表·数据的存储结构决定查找的方法与效率.查找的依据：关键字（key）是数据元素（或记录）中某个数据项的值，用它可以标识（或识别）一个数据元素。·查找的定义：if found key=k thensuccess, return theposition;elseffailed.查找的类型：内查找：若整个查找过程全部在内存进行，则称这样的查找为内查找;·外查找：若在查找过程中还需要访问外存，则称之为外查找。·我们仅介绍内查找
查找的对象：表 • 数据的存储结构决定查找的方法与效率 查找的依据：关键字(key)是数据元素(或记录)中某个 数据项的值，用它可以标识(或识别)一个数据元素。 查找的定义： if found key=k then success , return the position; else failed. 查找的类型： 内查找：若整个查找过程全部在内存进行，则称这样的查找为内查 找； 外查找：若在查找过程中还需要访问外存，则称之为外查找。 我们仅介绍内查找
衡量查找算法的优劣?·主要考虑因素：比较次数·指标：平均查找长度：nASL=Zp.c;i=1·P为查找第i个元素的概率，在等概率的情形下1(设有n个元素)P, ==n。Ci为查找第i个元素所用到的比较次数
衡量查找算法的优劣: 主要考虑因素：比较次数 指标：平均查找长度： Ｐi为查找第i个元素的概率，在等概率的情形下 Ｃi为查找第i个元素所用到的比较次数。 = = n i i i ASL p c 1 ( n ) 1 设有 个元素 n Pi =