"查找表和算法概述：静态与动态查找、哈希表及冲突解决"

这篇文章主要介绍了查找的基本概念以及三种基本查找方法的基本思想和算法，包括静态查找表、动态查找表和哈希表。在计算机中，查找是在一批记录中依照某个域的指定域值，找出相应的记录的操作。被查找的数据对象是由同一类型的记录构成的集合，可称之为查找表。每个记录一般包含有多个数据域，查找是根据其中某一个指定的域进行的，这个作为查找依据的域称为关键字。对于给定的关键字的值，如果在表中经过查找能找到相应的记录，则称查找成功，一般可输出该记录的有关信息或指示该记录在查找表中的位置。若表中不存在相应的记录，则称查找不成功，此时应该给出不成功的信息。查找算法中的基本运算是记录的关键字与给定值所进行的比较，其执行时间通常取决于比较的次数。因此，通常以关键字与给定值进行比较的记录。 本文提出了三种基本查找方法的基本思想和算法，分别是静态查找表、动态查找表和哈希表。静态查找表是指在查找之前已经建立的查找表，其查找方法包括顺序查找和折半查找。顺序查找是逐个查找给定值与记录的关键字相等的记录，其平均查找长度为(n+1)/2，n为记录数。而折半查找是在顺序存储结构的线性表中进行的，前提是线性表中的记录已按关键字的非递减次序排列，它的平均查找长度为log2(n+1)-1。动态查找表是指在构造查找表时，同时进行查找的表，其查找方法包括二叉排序树和平衡二叉树。而哈希表是以关键字值为直接地址或经过一定的函数处理后为地址，将记录存放在查找表中的方法，它的查找方法包括直接定址表和散列函数，以及解决哈希冲突的方法。 在本文中，还具体介绍了二叉排序树查找的基本思想和算法，以及散列法基本思想、散列函数的常用构造方法及解决冲突方法。二叉排序树是一种特殊的二叉树，它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。而散列法是一种查找的技术，它的基本思想是将查找表中的任一关键字K映射为一个地址f(K)，将记录存储在f(K)的位置，当查找一个记录时，将给定的值与表中记录的关键字值进行比较，通过计算产生的地址进行查找。同时，本文还介绍了散列函数的常用构造方法，包括直接定址法、除留余数法、数字分析法和折叠法等，以及解决哈希冲突的方法，包括开放寻址法和链地址法。 综上所述，本文详细介绍了查找的基本概念以及三种基本查找方法的基本思想和算法，对于在计算机中进行查找操作具有一定的参考意义。通过本文的学习，读者可了解不同的查找方法，并根据实际需求选择合适的查找算法，提高查找效率，解决实际问题。