3索引顺序表 当顺序表中的数据元素个数非常大时,采用在顺序表上建立 索引表的办法提高查找速度。把要在其上建立索引表的顺序表 称作主表。主表中存放着数据元素的全部信息,索引表中只存 放主表中要查找数据元素的主关键字和索引信息
3.索引顺序表 当顺序表中的数据元素个数非常大时，采用在顺序表上建立 索引表的办法提高查找速度。把要在其上建立索引表的顺序表 称作主表。主表中存放着数据元素的全部信息，索引表中只存 放主表中要查找数据元素的主关键字和索引信息
索引表 主表 下标 key link 位置key其它域 14 索引表中的数据元素 由两个域构成,key域 266 10 10 为被索引的若干个数据 385 15 01234567 22 元素中关键字的最大值, link城为被索引的若干 个数据元素中第一个数 9 据元素的位置编号。 123 66188 索引表结构图
8 14 6 9 10 22 34 18 19 31 40 38 54 66 46 71 78 68 80 85 0 14 0 1 34 5 2 66 10 3 85 15 下标 key link 索引表 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 位置 key 其它域 主表 索引表中的数据元素 由两个域构成，key域 为被索引的若干个数据 元素中关键字的最大值， link域为被索引的若干 个数据元素中第一个数 据元素的位置编号。 索引表结构图
相关术语 完全索引表和主表项完全相同,但只包含索引关键字和该数 据元素在主表中位置信息的索引表 二级索引表:当主表中的数据元素个数非常庞大时,按照建立 索引表的同样方法对索引表再建立的索引表。二级以上 的索引结构称作多级索引结构 等长索引表索引表中的每个索引项对应主表中的数据元素个 数相等反之称为不等长索引表。不等长索引表中的索 引长度可随着动态插入和动态删除过程改变,因此不仅 适用于静态查找问题,而且也适用于动态查找问题
完全索引表:和主表项完全相同，但只包含索引关键字和该数 据元素在主表中位置信息的索引表 二级索引表:当主表中的数据元素个数非常庞大时，按照建立 索引表的同样方法对索引表再建立的索引表。二级以上 的索引结构称作多级索引结构 等长索引表:索引表中的每个索引项对应主表中的数据元素个 数相等;反之称为不等长索引表。不等长索引表中的索 引长度可随着动态插入和动态删除过程改变,因此不仅 适用于静态查找问题，而且也适用于动态查找问题。 相关术语
算法分析 假设索引表的长度为m,主表中每个子表的长度为s,并假 设在索引表上和在主表上均采用顺序查找算法,则索引顺序 表上查找算法的平均查找长度为 m+1 s+l m+s ASl
假设索引表的长度为m，主表中每个子表的长度为s，并假 设在索引表上和在主表上均采用顺序查找算法，则索引顺序 表上查找算法的平均查找长度为： 1 2 2 1 2 1 + + = + + + = m s m s ASL 算法分析
113动态查找表 动态查找表主要有二叉树结构和树结构两种类型。二叉树结 构有二叉排序树、平衡二叉树等。树结构有B树、B+树等。 1131二叉排序树和平衡二叉树 基本概念 二叉排序树或是一棵空树;或者是具有如下性质的非空二 叉树: (1)左子树的所有结点均小于根的值; (2)右子树的所有结点均大于根的值; (3)它的左右子树也分别为二叉排序树
11.3 动态查找表 动态查找表主要有二叉树结构和树结构两种类型。二叉树结 构有二叉排序树、平衡二叉树等。树结构有B-树、B+树等。 11.3.1 二叉排序树和平衡二叉树 一、基本概念 二叉排序树或是一棵空树；或者是具有如下性质的非空二 叉树： （1）左子树的所有结点均小于根的值； （2）右子树的所有结点均大于根的值； （3）它的左右子树也分别为二叉排序树