|
所谓"查找"(检索)就是在一个含有众多数据元素(记录)的查找表中找出某个"特定的"数据元素。查找表是一种非常重要的数据结构,是由同一类型的数据元素(记录)构成的集合。在查找表中,通常通过查找其关键字是否等于给定值来确定查找是否成功。若查到其关键字等于给定值的记录,则称"查找成功",否则,称"查找失败"。
|
|
|
对查找表而言,除了按关键字查找外,查找表的插入和删除是对查找表进行的另外两个基本操作。
|
|
|
关键字是数据元素(记录)中某个数据项的值,可以标识一个记录,若能唯一标识,则称为主关键字,否则,称为次关键字。
|
|
|
考生特别要注意的是:在查找中是和关键字进行比较,而不是和数据元素进行比较,因而在算法描述中要体现关键字比较的特征。同时,考生要特别注意查找在顺序存储结构和链式存储结构上的区别。
|
|
|
查找的效率通过平均检索长度(ASL)和所需的辅助空间来确定。在查找其关键字等于给定值的过程中,需要与给定值进行比较的关键字个数的期望值称为检索成功时的平均检索长度。
|
|
|