什么是查找表
精华
小牛编辑
154浏览
2023-03-14
在日常生活中,几乎每天都要进行一些查找的工作,在电话簿中查阅某个人的电话号码;在电脑的文件夹中查找某个具体的文件等等。本节主要介绍用于查找操作的
数据结构——
查找表。
查找表 是由同一类型的数据元素构成的集合。例如电话号码簿和字典都可以看作是一张查找表。
一般对于查找表有以下几种操作:
关键字又细分为 主关键字和 次关键字。 若某个关键字可以唯一地识别一个数据元素时,称这个关键字为 主关键字,例如学生的学号就具有唯一性; 反之,像学生姓名、年龄这类的关键字,由于不具有唯一性,称为 次关键字。
查找表 是由同一类型的数据元素构成的集合。例如电话号码簿和字典都可以看作是一张查找表。
一般对于查找表有以下几种操作:
- 在查找表中查找某个具体的数据元素;
- 在查找表中插入数据元素;
- 从查找表中删除数据元素;
静态查找表和动态查找表
在查找表中只做查找操作,而不改动表中数据元素,称此类查找表为 静态查找表;反之, 在查找表中做查找操作的同时进行插入数据或者删除数据的操作,称此类表为 动态查找表。关键字
在查找表查找某个特定元素时,前提是需要知道这个元素的一些属性。例如,每个人上学的时候都会有自己唯一的学号,因为你的姓名、年龄都有可能和其他人是重复的,唯独学号不会重复。 而学生具有的这些属性(学号、姓名、年龄等)都可以称为 关键字。关键字又细分为 主关键字和 次关键字。 若某个关键字可以唯一地识别一个数据元素时,称这个关键字为 主关键字,例如学生的学号就具有唯一性; 反之,像学生姓名、年龄这类的关键字,由于不具有唯一性,称为 次关键字。
如何进行查找?
不同的查找表,其使用的查找方法是不同的。例如每个人都有属于自己的朋友圈,都有自己的电话簿,电话簿中数据的排序方式是多种多样的,有的是按照姓名的首字母进行排序,这种情况在查找时,就可以根据被查找元素的首字母进行顺序查找;有的是按照类别(亲朋好友)进行排序。在查找时,就需要根据被查找元素本身的类别关键字进行排序。本章从 静态查找表、 动态查找表和 哈希表的角度具体分析针对不同的查找表可供选择的查找算法。具体的查找方法需要根据实际应用中具体情况而定。