第8章查找 数据结构(C++描述)
第8章 查找 数据结构（C++描述）
目录 81查找的基本概念 8.2线性表的查找 8.3树表查找 8.4散列查找 退出
目录 8．4 散列查找 8．3 树表查找 8.1 查找的基本概念 8．2 线性表的查找 退出
8,1查找的基本概念 查找,也称为检索。在我们日常生活中,随处可见查找 的实例。如查找某人的地址、电话号码;查某单位45岁 以上职工等,都属于查找范畴。本书中,我们规定查找 是按关键字进行的,所谓关键字(key)是数据元素(或记 录)中某个数据项的值,用它可以标识(或识别)一个数据 元素。例如,描述一个考生的信息,可以包含:考号 姓名、性别、年龄、家庭住址、电话号码、成绩等关键 字。但有些关键字不能唯一标识一个数据元素,而有的 关键字可以唯一标识一个数据元素。如刚才的考生信息 中,姓名不能唯一标识一个数据元素(因有同名同姓的 人),而考号可以唯一标识一个数据元素(每个考生考号 是唯一的,不能相同)。我们将能唯一标识一个数据元素 的关键字称为主关键字,而其它关键字称为辅助关键字 或从关键字
8.1 查找的基本概念 查找，也称为检索。在我们日常生活中，随处可见查找 的实例。如查找某人的地址、电话号码；查某单位45岁 以上职工等，都属于查找范畴。本书中，我们规定查找 是按关键字进行的，所谓关键字(key)是数据元素(或记 录)中某个数据项的值，用它可以标识(或识别)一个数据 元素。例如，描述一个考生的信息，可以包含：考号、 姓名、性别、年龄、家庭住址、电话号码、成绩等关键 字。但有些关键字不能唯一标识一个数据元素，而有的 关键字可以唯一标识一个数据元素。如刚才的考生信息 中，姓名不能唯一标识一个数据元素(因有同名同姓的 人)，而考号可以唯一标识一个数据元素(每个考生考号 是唯一的，不能相同)。我们将能唯一标识一个数据元素 的关键字称为主关键字，而其它关键字称为辅助关键字 或从关键字
它洧了主关键字及关键字后,我们可以给查找下一个完整 的定义。所谓査找,就是根据给定的值,在一个表中查 找出其关键字等于给定值的数据元素,若表中有这样的 y元素,则称查找是成功的,此时查找的信息为给定整个 数据元素的输出或指出该元素在表中的位置;若表中不 存在这样的记录,则称查找是不成功的,或称查找失败, 并可给出相应的提示 入因为查找是对已存入计算机中的数据所进行的操作,所 以采用何种查找方法,首先取决于使用哪种数据结构来 表示“表”,即表中结点是按何种方式组织的。为了提 髙査找速度,我们经常使用某些特殊的数据结构来组织 表。因此在研究各种査找算法时,我们首先必须弄清这 些算法所要求的数据结构,特别是存储结构。 查找有内查找和外查找之分。若整个查找过程全部在内 存进行,则称这样的查找为内查找;反之,若在查找过 程中还需要访问外存,则称之为外查找。我们仅介绍内 查找
有了主关键字及关键字后，我们可以给查找下一个完整 的定义。所谓查找，就是根据给定的值，在一个表中查 找出其关键字等于给定值的数据元素，若表中有这样的 元素，则称查找是成功的，此时查找的信息为给定整个 数据元素的输出或指出该元素在表中的位置；若表中不 存在这样的记录，则称查找是不成功的，或称查找失败， 并可给出相应的提示。 因为查找是对已存入计算机中的数据所进行的操作，所 以采用何种查找方法，首先取决于使用哪种数据结构来 表示“表” ，即表中结点是按何种方式组织的。为了提 高查找速度，我们经常使用某些特殊的数据结构来组织 表。因此在研究各种查找算法时，我们首先必须弄清这 些算法所要求的数据结构，特别是存储结构。 查找有内查找和外查找之分。若整个查找过程全部在内 存进行，则称这样的查找为内查找；反之，若在查找过 程中还需要访问外存，则称之为外查找。我们仅介绍内 查找
它要衡量一种查找算法的优劣,主要是看要找的值与关键字 的比较次数,但我们将找到给定值与关键字的比较次数的 平均值来作为衡量一个査找算法好坏的标准,对于一个含 有个元素的表查找成功时的斗均查找长度可示为 般情形下我们认为查找每个元素的概率相等,Ci为查找 第个元素所用到的比较次数 要衡量一种查找算法的优劣,主要是看要找的值与关键字 的比较次数,但我们将找到给定值与关键字的比较次数的 平均值来作为衡量一个査找算法好坏的标准,对于一个含 有n个元素的表,查找成功时的平均查找长度可表示为 ASL 其中Pi为査找第i个元素的概率,且=1。一般情 形下我们认为查找每个元素的概率相等,Ci为查找第个 元素所用到的比较次数
要衡量一种查找算法的优劣，主要是看要找的值与关键字 的比较次数，但我们将找到给定值与关键字的比较次数的 平均值来作为衡量一个查找算法好坏的标准，对于一个含 有n个元素的表，查找成功时的平均查找长度可表示为 ASL= ，其中Ｐi为查找第i个元素的概率，且 =1。 一般情形下我们认为查找每个元素的概率相等，Ｃi为查找 第i个元素所用到的比较次数。 要衡量一种查找算法的优劣，主要是看要找的值与关键字 的比较次数，但我们将找到给定值与关键字的比较次数的 平均值来作为衡量一个查找算法好坏的标准，对于一个含 有n个元素的表，查找成功时的平均查找长度可表示为 ASL= ，其中Ｐi为查找第i个元素的概率，且=1。一般情 形下我们认为查找每个元素的概率相等，Ｃi为查找第i个 元素所用到的比较次数。 = n i i i p c 1 = n i i p 1