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