数据结构第7章小结

  第七章首先介绍了和查找相关的概念和术语。查找表是由同一类型的数据元素构成的集合。关键字是数据元素中某个数据项的值。在查找的同时对表做修改操作，相应的表称之为动态查找表，否则称为静态查找表。平均查找长度是为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值。然后讲了线性表的三种查找方法：顺序查找、折半查找和分块查找。顺序查找的优点是算法简单，既适用于顺序结构，也适用于链式结构。缺点是平均查找长度较大，当n很大时，不适合用顺序查找。折半查找的优点是查找效率高，缺点是只能用于顺序存储的有序表，查找前需排序，不适合于数据元素经常变动的线性表。分块查找的优点是插入和删除比较容易，无需进行大量的移动，既要快速查找又经常动态变化，则可采用分块查找。缺点是要增加一个索引表的存储空间。然后讲了树表的查找，二叉排序树是一种对排序和查找都很有用的特殊二叉树。平衡二叉树是一种特殊类型的二叉排序树，平衡因子是该节点的左子树和右子树的深度之差，平衡二叉树上所有节点的平衡因子只可能是-1、0、1。接着讲了散列表的查找，在记录的存储位置p和其关键字key之间建立一个确定的对应关系H，使p=H（key），H为散列函数，p为散列地址。散列表是一个有限连续的地址空间。对不同的关键字可能得到同一散列地址，这种现象称为冲突。具有相同函数值的关键字称作同义词。构造散列函数有四种方法：数字分析法、平方取中法、折叠法和除留余数法。处理冲突有开放地址法和链地址法，其中开放地址法有线性探测法、二次探测法和伪随机探测法。