第8章查找本章学习内容8.1查找的基本概念8.2线性表的查找8.3树表查找8.4散列查找8.1查找的基本概念在前面几章中，我们介绍了线性表、栈和队列、串等线性结构及多维数组、广义表、树和图等非线性结构，讨论了它们的逻辑结构、存储结构及运算，并且在运算中，曾经讨论过一些简单的查找运算。但由于查找运算的使用频率相当高，几乎在任何一个计算机系统中都会涉及到，所以当问题的规模相当大时，查找算法的效率就显得十分重要。因此，本章将着重讨论各种查找方法，并通过对它们的效率分析来比较各种查找方法的优劣。查找，也称为检索。在我们的日常生活中，随处可见查找的实例。如查找某人的地址、电话号码；查某单位45岁以上职工等，都属于查找范畴。本书中，我们规定查找是按关键字进行的。所谓关键字（key）是数据元素（或记录）中某个数据项的值，用它可以标识（或识别）一个数据元素。例如，描述一个考生的信息，可以包含：考号、姓名、性别、年龄、家庭住址、电话号码、成绩等关键字。但有些关键字不能惟一标识一个数据元素，而有的关键字可以惟一标识一个数据元素。如刚才的考生信息中，姓名不能惟一标识一个数据元素（因有同名同姓的人），而考号可以惟一标识一个数据元素（每个考生考号是惟一的，不能相同）。我们将能惟一标识一个数据元素的关键字称为主关键字，而其他关键字称为辅助关键字或从关键字。有了主关键字及关键字后，我们可以给查找下一个完整的定义。所谓查找，就是根据给定的值，在一个表中查找出其关键字等于给定值的数据元素，若表中有这样的元素，则称查找是成功的，此时查找的信息为给定整个数据元素的输出或指出该元素在表中的位置；若表中不存在这样的记录，则称查找是不成功的，或称查找失败，并可给出相应的提示。因为查找是对已存入计算机中的数据所进行的操作，所以采用何种查找方法，首先取决于使用哪种数据结构来表示“表”，即表中结点是按何种方式组织的。为了提高查找速度，我们经常使用某些特殊的数据结构来组织表。因此在研究各种查找算法时，我们首先必须弄清这些算法所要求的数据结构，特别是存储结构。查找有内查找和外查找之分。若整个查找过程全部在内存进行，则称这样的查找为内查找；反之，若在查找过程中还需要访问外存，则称之为外查找。我们仅介绍内查找。要衡量一种查找算法的优劣，主要是看要找的值与关键字的比较次数，我们将找到给定值与关键字的比较次数的平均值来作为衡量一个查找算法好坏的标准，对于一个含有n个元素的表，查找成功时的平均查找长度可表示为ASL=，niiicp1其中pi为查找第i个元素的概率，且=1。一般情形下我们认为查找每个元素的概率相等，ci为查找第i个元素所用到的比较次数。niip18.2线性表的查找8.2.1顺序查找1．顺序查找的基本思想顺序查找是一种最简单的查找方法，它的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值Ｋ相比较，若相等，则查找成功，若整个表扫描完毕，仍未找到关键字等于Ｋ的元素，则查找失败。顺序查找既适用于顺序表，也适用于链表。若用顺序表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描。另外，顺序查找的表中元素可以是无序的。下面以顺序表的形式来描述算法。2．顺序查找算法实现constintn=maxn//n为表的最大长度structnode{…elemtypekey;//key为关键字，类型设定为elemtype};intseqsearch(nodeR[n+1],elemtypek)//在表R中查找关键字值为k的元素{R[0].key=k;inti=n;//从表尾开始向前扫描while(R[i].key!=k)i--;returni;}在函数seqsearch中，若返回的值为０表示查找不成功，否则查找成功。函数中查找的范围从R[n]到R[1]，R[0]为监视哨，起两个作用：其一，是为了省去判定while循环中下标越界的条件i≥1，从而节省比较时间；其二，保存要找值的副本，若查找时遇到它，表示查找不成功。若算法中不设立监视哨R[0]，程序花费的时间将会增加，这时的算法可写为下面的形式：intseqsearch(nodeR[n+1]，elemtypek){inti=n;while(R[i].key!=k)&&(i>=1)i--;returni;}当然上面的算法也可以改成从表头向后扫描，...
