索引顺序表

来自计算思维百科
跳转至: 导航搜索
索引顺序表1.png

索引顺序表是一种高效的查找数据的方法,举个例子来说,要在一本书中找到章节名为“计算思维”所在的页,你可以在目录(索引)里面从头到尾挨个匹配,直到找到“计算思维”,这就是索引顺序查找。

基本概念

通常将为顺序表提供索引的表称为索引表,索引表分为两个部分:一个用来存储顺序表中每个单元的最大关键字,另一个用来存储顺序表中每个单元的第一个元素的下标。索引表中的关键字必须是有序的,主表中元素可以是按关键字有序排列,也可以是在单元内或块中是有序的,即后一个单元中的所有元素的关键字都大于前一个单元中的元素的关键字。

索引顺序表的查找就是将顺序表分成几个单元,然后为这几个单元建立一个索引,利用索引在其中一个单元中进行查找。

索引顺序表2.png

从图中可以看出,索引表分成四个单元,每个单元有5个元素。要查找主表中的某个元素,需要分为两步查找,第一步需要确定要查找元素所在的单元,第二步在该单元进行查找。例如,要查找关键字为47的元素,首先需要将47与索引表中的关键字进行比较,因为

41<关键字47<52,所以需要在第三个单元中查找,该单元的起始下标是10,因此从主表中的下标为10的位置开始查找,直到找到关键字为47的元素为止。如果主表中不存在该元素,则只需要将关键字47与第三个单元的5个元素进行比较,如果都不相等则说明查找失败。

应用案例

应用1- 取病历

案例:

校医院的护士在放置病人的病历时,会先看封面的学院,按学院放在一沓,每一沓里按学号来看,有一定的顺序,比如2014级信息工程学院的学生学号的前6位是2014130,而计算机与软件学院的学生学号的前6位是2014150,

这样,2014级深圳大学的每个信息工程学院学生的10位学号都比计算机与软件学院学生学号小。这就满足了索引顺序表中“索引表中关键字必须有序”,“主表中后一个单元中的所有元素的关键字都大于前一个单元中的元素的关键字”的条件。

我们可以尝试用索引顺序表的思路来帮护士分类,帮助病人快速找到病历。

索引顺序表3.png

应用2-图书馆找书

案例:小明想去图书馆找武侠小书“倚天屠龙记”,小明先到图书馆的系统中查找书籍分类目录,找到“小说”一类,然后在小说类中查找作者目录,找到“金庸”,系统会告诉小明到哪个书柜那一行去找,这个目录就是书籍的索引顺序表。

可以体现的计算思维

索引顺序表主要应用在表中含大量的数据元素的时候,通过为顺序表建立索引和分块来提高查找的效率,体现了计算思维的抽象特点。