数据结构知识点总结7686.pdf

《数据结构知识点总结7686.pdf》由会员分享，可在线阅读，更多相关《数据结构知识点总结7686.pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-第一章 概 论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。数据元素是数据的根本单位，可以由假设干个数据项组成。数据项是具有独立含义的最小 标识单位。数据构造的定义：逻辑构造：从逻辑构造上描述数据，独立于计算机。线性构造：一对一关系。线性构造：多对多关系。存储构造：是逻辑构造用计算机语言的实现。顺序存储构造：如数组。链式存储构造：如链表。索引存储构造：稠密索引：每个结点都有索引项。稀疏索引：每组结点都有索引项。散列存储构造：如散列表。数据运算。对数据的操作。定义在逻辑构造上，每种逻辑构造都有一个运算集合。常用的有：检索、插入、删除、更新、排序。数据类型：是一个值的集合以及在这些值

2、上定义的一组操作的总称。原子类型：由语言提供。构造类型：由用户借助于描述机制定义，是导出类型。抽象数据类型 ADT：是抽象数据的组织和与之的操作。相当于在概念层上描述问题。优点是将数据和操作封装在一起实现了信息隐藏。程序设计的实质是对实际问题选择一种好的数据构造，设计一个好的算法。算法取决于数据构造。算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。评价算法的好坏的因素：算法是正确的；执行算法的时间；执行算法的存储空间主要是辅助存储空间；算法易于理解、编码、调试。时间复杂度：是*个算法的时间消耗，它是该算法所求解问题规模 n 的函数。渐近时间复杂度：是指当问题规模趋向无穷大

3、时，该算法时间复杂度的数量级。-评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。时间复杂度按数量级递增排列依次为：常数阶 O 1、对数阶 O log2n、线性阶 O n、线性对数阶 O nlog2n、平方阶 On2、立方阶 On3、k 次方阶 Onk、指数阶 O2n。空间复杂度：是*个算法的空间消耗，它是该算法所求解问题规模 n 的函数。算法的时间复杂度和空间复杂度合称算法复杂度。第二章 线性表 线性表是由 n0 个数据元素组成的有限序列。n=0 是空表；非空表，只能有一个开场结点，有且只能有一个终端结点。线性表上

4、定义的根本运算：构造空表：InitlistL 求表长：ListlengthL 取结点：GetNodeL，i 查找：LocateNodeL，*插入：InsertListL，*，i 删除：DeleteL，i 顺序表是按线性表的逻辑构造次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和 逻辑构造中各结点相邻关系是一致的。地址计算：LOCai=LOCa1+i-1*d；首地址为 1 在顺序表中实现的根本运算：插入：平均移动结点次数为 n/2；平均时间复杂度均为 On。删除：平均移动结点次数为n-1/2；平均时间复杂度均为 On。线性表的链式存储构造中结点的逻辑次序和物理次序不一定一

5、样，为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存储了其后继结点的地址信息即指针或链。这两局部信息组成链表中的结点构造。一个单链表由头指针的名字来命名。单链表运算：建立单链表头插法：s-ne*t=head；head=s；生成的顺序与输入顺序相反。平均时间复杂度均为 On。尾插法：head=rear=null；ifhead=null head=s；else r-ne*t=s；r=s；平均时间复杂度均为 On 加头结点的算法：对开场结点的操作无需特殊处理，统一了空表和非空表。查找按序号：与查找位置有关，平均时间复杂度均为 On。-按值：与输入实例有关，平均时间复杂度均为 On。插入运

6、算：p=GetNodeL，i-1；s-ne*t=p-ne*t；p-ne*t=s；平均时间复杂度均为 On 删除运算：p=GetNodeL，i-1；r=p-ne*t；p-ne*t=r-ne*t；freer；平均时间复杂度均为 On 单循环链表是一种首尾相接的单链表，终端结点的指针域指向开场结点或头结点。链表终止条件是以指针等于头指针或尾指针。采用单循环链表在实用中多采用尾指针表示单循环链表。优点是查找头指针和尾指针的时间都是 O1，不用 遍历整个链表。双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其直接前趋的指针域 prior，形成两条不同方 向的链。由头指针 head 惟一确定。双

7、链表也可以头尾相构成双向循环链表。双链表上的插入和删除时间复杂度均为 O 1。顺序表和链表的比拟：基于空间：顺序表的存储空间是静态分配，存储密度为 1；适于线性表事先确定其大小时采用。链表的存储空间是动态分配，存储密度1；适于线性表长度变化大时采用。基于时间：顺序表是随机存储构造，当线性表的操作主要是查找时，宜采用。以插入和删除操作为主的线性表宜采用链表做存储构造。假设插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。第三章 栈和队列 栈Stack是仅限制在表的一端进展插入和删除运算的线性表，称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原

8、则进展的，我们又称栈为 LIFO 表Last In First Out。通常栈有 顺序栈和链栈两种存储构造。栈的根本运算有六种：构造空栈：InitStackS 判栈空：StackEmptyS 判栈满：StackFullS 进栈：PushS，*退栈：PopS 取栈顶元素：StackTopS-在顺序栈中有上溢和下溢的现象。上溢是栈顶指针指出栈的外面是出错状态。下溢可以表示栈为空栈，因此用来作为控制转移的条件。顺序栈中的根本操作有六种：构造空栈判栈空判栈满进栈退栈取栈顶元素 链栈则没有上溢的限制，因此进栈不要判栈满。链栈不需要在头部附加头结点，只要有链表的头指针就可以了。链栈中的根本操作有五种：构造

9、空栈判栈空进栈退栈取栈顶元素 队列Queue是一种运算受限的线性表，插入在表的一端进展，而删除在表的另一端进展，允许删除的一端称 为队头front，允许插入的一端称为队尾rear，队列的操作原则是先进先出的，又称作 FIFO 表First In First Out.队列也有顺序存储和链式存储两种存储构造。队列的根本运算有六种：置空队：InitQueueQ 判队空：QueueEmptyQ 判队满：QueueFullQ 入队：EnQueueQ，*出队：DeQueueQ 取队头元素：QueueFrontQ 顺序队列的假上溢现象：由于头尾指针不断前移，超出向量空间。这时整个向量空间及队列是空的却产生了

10、上 溢现象。为了克制假上溢现象引入循环向量的概念，是把向量空间形成一个头尾相接的环形，这时队列称循环队列。判定循环队列是空还是满，方法有三种：一种是另设一个布尔变量来判断；第二种是少用一个元素空间，入队时先测试rear+1%m=front？满：空；第三种就是用一个计数器记录队列中的元素的总数。队列的链式存储构造称为链队列，一个链队列就是一个操作受限的单链表。为了便于在表尾进展插入入队的 操作，在表尾增加一个尾指针，一个链队列就由一个头指针和一个尾指针唯一地确定。链队列不存在队满和上溢 的问题。在链队列的出队算法中，要注意当原队中只有一个结点时，出队后要同进修改头尾指针并使队列变空。第四章 串

11、串是零个或多个字符组成的有限序列。空串：是指长度为零的串，也就是串中不包含任何字符结点。-空白串：指串中包含一个或多个空格字符的串。在一个串中任意个连续字符组成的子序列称为该串的子串，包含子串的串就称为主串。子串在主串中的序号就是指子串在主串中首次出现的位置。空串是任意串的子串，任意串是自身的子串。串分为两种：串常量在程序中只能引用不能改变；串变量的值可以改变。串的根本运算有：求串长 strlenchar*s 串复制 strcpychar*to，char*from 串联接 strcatchar*to，char*from 串比拟 charcmpchar*s1，char*s2 字符定位 strch

12、rchar*s，charc 串是特殊的线性表结点是字符，所以串的存储构造与线性表的存储构造类似。串的顺序存储构造简称为顺序串。顺序串又可按存储分配的不同分为：静态存储分配：直接用定长的字符数组来定义。优点是涉及串长的操作速度快，但不适合插入、操作。动态存储分配：是在定义串时不分配存储空间，需要使用时按所需串的长度分配存储单元。串的链式存储就是用单链表的方式存储串值，串的这种链式存储构造简称为链串。链串与单链表的差异只是它的结 点数据域为单个字符。为了解决存储密度低的状况，可以让一个结点存储多个字符，即结点的大小。顺序串上子串定位的运算：又称串的模式匹配或串匹配，是在主串中查找出子串出现的位置。

13、在串匹配中，将主串称为目标串，子串称为模式串。这是比拟容易理解的，串匹配问题就是找出给定模式串 P 在给定目标串 T 中首次出现的有效位移或者是全部有效位移。最坏的情况下时间复杂度是 On-m+1m，假设 m 与 n 同阶 的话则它是 On2。链串上的子串定位运算位移是结点地址而不是整数 第五章 多维数组和广义表 数组一般用顺序存储的方式表示。存储的方式有：行优先顺序，也就是把数组逐行依次排列。PASCAL、C 列优先顺序，就是把数组逐列依次排列。FORTRAN 地址的计算方法：按行优先顺序排列的数组：LOCaij=LOCa11+i-1*n+j-1*d.按列优先顺序排列的数组：LOCaij=L

14、OCa11+j-1*n+i-1*d.矩阵的压缩存储：为多个一样的非零元素分配一个存储空间；对零元素不分配空间。-特殊矩阵的概念：所谓特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。稀疏矩阵的概念：一个矩阵中假设其非零元素的个数远远小于零元素的个数，则该矩阵称为稀疏矩阵。特殊矩阵的类型：对称矩阵：满足 aij=aji。元素总数 nn+1/2.I=ma*i，j，J=mini，j，LOCaij=LOCsa0+I*I+1/2+J*d.三角矩阵：上三角阵：k=i*2n-i+1/2+j-i，LOCaij=LOCsa0+k*d.下三角阵：k=i*i+1/2+j，LOCaij=LOCsa0+k*d.对角矩阵

15、：k=2i+j，LOCaij=LOCsa0+k*d.稀疏矩阵的压缩存储方式用三元组表把非零元素的值和它所在的行号列号做为一个结点存放在一起，用这些结点组成的一个线性表来表示。但这种压缩存储方式将失去随机存储功能。参加行表记录每行的非零元素在三元组表中的 起始位置，即带行表的三元组表。广义表是 nn0个元素的有限序列，其中的元素是原子或者是一个广义表。广义表表头和表尾的概念：假设广义表 LS 非空n1，则这个广义表的第一个元素就是表头。其余的元素组成的表称为 LS 的表尾，所以表尾必是一个子表。广义表有两种表示法，一种是括号表示法，一种是图形表示法。广义表与树形构造相对应，这个广义表就是纯表。如

16、果一个广义表的结点又可以被其他结点所共享，则这个表称为再入表。允许递归的表称为递归表。线性表纯表树再入表递归表.可见，广义表是对线性表和树的推广。广义表有两个特殊的根本运算：取表头 headLS：取表中的第一个数据元素，不能对空表操作。取表尾 tailLS；取除表头外，其余数据元素构成的子表，不能对空表操作。第六章 树 树是 n 个结点的有限集合，非空时必须满足：只有一个称为根的结点；其余结点形成 m 个不相交的子集，并称 根的子树。根是开场结点；结点的子树数称度；度为 0 的结点称叶子终端结点；度不为 0 的结点称分支结点非终端结 点；除根外的分支结点称部结点；有序树是子树有左，右之分的树；

17、无序树是子树没有左，右之分的树；森林是 m 个互不相交的树的集合；树的四种不同表示方法：树形表示法；嵌套集合表示法；凹入表示法广义表表示法。二叉树的定义：是 n0 个结点的有限集，它是空集n=0或由一个根结点及两棵互不相交的分别称作这个根的 左子树和右子树的二叉树组成。-二叉树不是树的特殊情形，与度数为 2 的有序树不同。二叉树的 4 个重要性质：二叉树上第 i 层上的结点数目最多为 2i-1i1。；深度为 k 的二叉树至多有2k-1 个结点k1；在任意一棵二叉树中，假设终端结点的个数为 n0，度为 2 的结点数为 n2，则 n0=n2+1；具有 n 个结点的完全二叉树的深度为 intlog2

18、n+1.满二叉树是一棵深度为 k，结点数为2k-1 的二叉树；完全二叉树是满二叉树在最下层自右向左去处局部结点；二叉树的顺序存储构造就是把二叉树的所有结点按照层次顺序存储到连续的存储单元中。存储前先将其画成完全 二叉树 树的存储构造多用的是链式存储。BinTNode 的构造为 lchild|data|rchild，把所有 BinTNode 类型的结点，加上一个指向根结点的 BinTree 型头指针就构成了二叉树的链式存储构造，称为二叉链表。它就是由根指针 root 唯一确定的。共有 2n 个指针域，n+1 个空指针。根据结点的次序不同可得三种遍历：先序遍历前序遍历或先根遍历，中序遍历或中根遍历

19、、后序遍历或 后根遍历。时间复杂度为 On。利用二叉链表中的 n+1 个空指针域来存放指向*种遍历次序下的前趋结点和后继结点的指针，这些附加的指针就称为线索，加上线索的二叉链表就称为线索链表。线索使得查找中序前趋和中序后继变得简单有效，但对于查找指定结 点的前序前趋和后序后继并没有什么作用。树和森林及二叉树的转换是唯一对应的。转换方法：树变二叉树：兄弟相连，保存长子的连线。二叉树变树：结点的右孩子与其双亲连。森林变二叉树：树变二叉树，各个树的根相连。树的存储构造：有双亲链表表示法：结点 data|parent，对于求指定结点的双亲或祖先十分方便，但不适于求指定结 点的孩子及后代。孩子链表表示法

20、：为树中每个结点 data|ne*t 设置一个孩子链表 firstchild，并将 data|firstchild 存放在一个向量中。双亲孩子链表表示法：将双亲链表和孩子链表结合。孩子兄弟链表表示法：结点构造 leftmostchild|data|rightsibing，附加两个分别指向该结点的最左孩子和右邻兄弟的 指针域。-树的前序遍历与相对应的二叉树的前序遍历一致；树的后序遍历与相对应的二叉树的中序遍历一致。树的带权路径长度是树中所有叶结点的带权路径长度之和。树的带权路径长度最小的二叉树就称为最优二叉树 即哈夫曼树。在叶子的权值一样的二叉树中，完全二叉树的路径长度最短。哈夫曼树有 n 个叶

21、结点，共有 2n-1 个结点，没有度为 1 的结点，这类树又称为严格二叉树。变长编码技术可以使频度高的字符编码短，而频度低的字符编码长，但是变长编码可能使解码产生二义性。如00、01、0001 这三个码无法在解码时确定是哪一个，所以要求在字符编码时任一字符的编码都不是其他字符编码的 前缀，这种码称为前缀码其实是非前缀码。哈夫曼树的应用最广泛地是在编码技术上，它能够容易地求出给定字符集及其概率分布的最优前缀码。哈夫曼编码的构造很容易，只要画好了哈夫曼树，按分支情况在左路径上写代码 0，右路径上写代码 1，然后从上到下到叶结 点的相应路径上的代码的序列就是该结点的最优前缀码。第七章 图 图的逻辑构

22、造特征就是其结点顶点的前趋和后继的个数都是没有限制的，即任意两个结点之间之间都可能相关。图 GraphG=V，E，V 是顶点的有穷非空集合，E 是顶点偶对的有穷集。有向图 Digraph：每条边有方向；无向图 Undigraph：每条边没有方向。有向完全图：具有 n*n-1条边的有向图；无向完全图：具有 n*n-1/2 条边的无向图；有根图：有一个顶点有路径到达其它顶点的有向图；简单路径：是经过顶点不同的路径；简单回路是开场和终端重 的简单路径；网络：是带权的图。图的存储构造：邻接矩阵表示法：用一个 n 阶方阵来表示图的构造是唯一的，适合稠密图。无向图：邻接矩阵是对称的。有向图：行是出度，列是

23、入度。建立邻接矩阵算法的时间是 On+n2+e，其时间复杂度为 On2 邻接表表示法：用顶点表和邻接表构成不是唯一的，适合稀疏图。顶点表构造 verte*|firstedge，指针域存放邻接表头指针。邻接表：用头指针确定。无向图称边表；有向图又分出边表和逆邻接表；邻接表结点构造为 adjve*|ne*t，-时间复杂度为 On+e。，空间复杂度为 On+e。图的遍历：深度优先遍历：借助于邻接矩阵的列。使用栈保存已结点。广度优先遍历：借助于邻接矩阵的行。使用队列保存已结点。生成树的定义：假设从图的*个顶点出发，可以系统地到图中所有顶点，则遍历时经过的边和图的所有顶点 构成的子图称作该图的生成树。最

24、小生成树：图的生成树不唯一，从不同的顶点出发可得到不同的生成树，把权值最小的生成树称为最小生成树 MST。构造最小生成树的算法：Prim 算法的时间复杂度为 On2与边数无关适于稠密图。Kruskal 算法的时间复杂度为 Olge，主要取决于边数，较适合于稀疏图。最短路径的算法：Dijkstra 算法，时间复杂度为 On2。类似于 prim 算法。拓扑排序：是将有向无环图 G 中所有顶点排成一个线性序列，假设EG，则在线性序列 u 在 v 之前，这种线性序列称为拓扑序列。拓扑排序也有两种方法：无前趋的顶点优先，每次输出一个无前趋的结点并删去此结点及其出边，最后得到的序列即拓扑序列。无后继的结点

25、优先：每次输出一个无后继的结点并删去此结点及其入边，最后得到的序列是逆拓扑序列。第八章 排序 记录中可用*一项来标识一个记录，则称为关键字项，该数据项的值称为关键字。排序是使文件中的记录按关键字递增或递减次序排列起来。根本操作：比拟关键字大小；改变指向记录的指针或移动记录。存储构造：顺序构造、链表构造、索引构造。经过排序后这些具有一样关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的，否则排序算法是不稳定的。排序过程中不涉及数据的、外存交换则称之为部排序排序，反之，假设存在数据的外存交换，则称之为外排序。部排序方法可分五类：插入排序、选择排序、交换排序、归并排序和分配排序。评价排序算

26、法好坏的标准主要有两条：执行时间和所需的辅助空间，另外算法的复杂程序也是要考虑的一个因素。插入排序：直接插入排序：逐个向前插入到适宜位置。哨兵监视哨有两个作用：作为临变量存放 Ri 是在查找循环中用来监视下标变量 j 是否越界。-直接插入排序是就地的稳定排序。时间复杂度为 On2，比拟次数为n+2n-1/2；移动次数为n+4n-1/2；希尔排序：等间隔的数据比拟并按要求顺序排列，最后间隔为 1.希尔排序是就地的不稳定排序。时间复杂度为 On1.25，比拟次数为n1.25；移动次数为1.6n1.25；交换排序：冒泡排序：自下向上确定最轻的一个。自上向下确定最重的一个。自下向上确定最轻的一个，后自

27、上向下确定最重的一个。冒泡排序是就地的稳定排序。时间复杂度为 On2，比拟次数为 nn-1/2；移动次数为 3nn-1/2；快速排序：以第一个元素为参考基准，设定、动两个指针，发生交换后指针交换位置，直到指针重合。重复直到排序完成。快速排序是非就地的不稳定排序。时间复杂度为 Onlog2n，比拟次数为 nn-1/2；选择排序：直接选择排序：选择最小的放在比拟区前。直接选择排序就地的不稳定排序。时间复杂度为 On2。比拟次数为 nn-1/2；堆排序 建堆：按层次将数据填入完全二叉树，从 intn/2处向前逐个调整位置。然后将树根与最后一个叶子交换值并断开与树的连接并重建堆，直到全断开。堆排序是就

28、地不稳定的排序，时间复杂度为 Onlog2n，不适宜于记录数较少的文件。归并排序：先两个一组排序，形成n+1/2 组，再将两组并一组，直到剩下一组为止。归并排序是非就地稳定排序，时间复杂度是 Onlog2n，分配排序：箱排序：按关键字的取值围确定箱子数，按关键字投入箱子，所有非空箱。箱排序的平均时间复杂度是线性的 On。基数排序：从低位到高位依次对关键字进展箱排序。基数排序是非就稳定的排序，时间复杂度是 Od*n+d*rd。各种排序方法的比拟和选择：待排序的记录数目 n；n 较大的要用时间复杂度为 Onlog2n的排序方法；记录的大小规模；记录大最好用链表作为存储构造，而快速排序和堆排序在链表

29、上难于实现；关键字的构造及其初始状态；对稳定性的要求；语言工具的条件；存储构造；时间和辅助空间复杂度。第九章 查找 查找的同时对表做修改操作如插入或删除则相应的表称之为动态查找表，否则称之为静态查找表。衡量查找算法效率优劣的标准是在查找过程中对关键字需要执行的平均比拟次数即平均查找长度 ASL。线性表查找的方法：顺序查找：逐个查找，ASL=n+1/2；-二分查找：取中点 intn/2比拟，假设小就比左区间，大就比右区间。用二叉判定树表示。ASL=每层结点数*层数/N.分块查找。要求分块有序，将表分成假设干块部不一定有序，并抽取各块中的最大关键字及其位置建立有序索引表。二叉排序树BST定义是：二

30、叉排序树是空树或者满足如下性质的二叉树：假设它的左子树非空，则左子树上所有结点的值均小于根结点的值；假设它的右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身又是一棵二叉排序树。二叉排序树的插入、建立、删除的算法平均时间性能是 Onlog2n。二叉排序树的删除操作可分三种情况进展处理：*P 是叶子，则直接删除*P，即将*P 的双亲*parent 中指向*P 的指针域置空即可。*P 只有一个孩子*child，此时只需将*child 和*p 的双亲直接连接就可删去*p.*p 有两个孩子，则先将*p 结点的中序后继结点的数据到*p，删除中序后继结点。关于 B-树多路平衡查找树。它适合

31、在磁盘等直接存取设备上组织动态的查找表，是一种外查找算法。建立的方式是从下向上拱起。散列技术：将结点按其关键字的散列地址存储到散列表的过程称为散列。散列函数的选择有两条标准：简单和均匀。常见的散列函数构的造方法：平方取中法：hash=int*2%100 除余法：表长为 m，hash=*%m 相乘取整法：hash=intm*A-int*A；A=0.618 随机数法：hash=random*。处理冲突的方法：开放定址法：一般形式为 hi=hkey+di%m1im-1，开放定址法要求散列表的装填因子 1.开放定址法类型：线性探查法：address=hash*+i%m；二次探查法：address=ha

32、sh*+i2%m；双重散列法：address=hash*+i*hashy%m；拉链法：是将所有关键字为同义词的结点在同一个单链表中。拉链法的优点：拉链法处理冲突简单，且无堆积现象；链表上的结点空间是动态申请的适于无法确定表长的情况；拉链法中 可以大于 1，结点较大时其指针域可忽略，因此节省空间；-拉链法构造的散列表删除结点易实现。拉链法也有缺点：当结点规模较小时，用拉链法中的指针域也要占用额外空间，还是开放定址法省空间。第十章 文件 文件是性质一样的记录的集合。记录是文件中存取的根本单位，数据项是文件可使用的最小单位，数据项有时称字段或者属性。文件 逻辑构造是一种线性构造。操作有：检索和维护。

33、并有实时和批量处理两种处理方式。文件 存储构造是指文件在外存上的组织方式。根本的组织方式有：顺序组织、索引组织、散列组织和链组织。常用的文件组织方式：顺序文件、索引文件、散列文件和多关键字文件。评价一个文件组织的效率，是执行文件操作所花费的时间和文件组织所需的存储空间。检索功能的多寡和速度的快慢，是衡量文件操作质量的重要标志。顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件。主关键字有序称顺序有序文件，否则称顺序无序文件。一切存储在顺序存储器如磁带上的文件都只能顺序文件，只能按顺序查找法存取。顺序文件的插入、删除和修改只能通过复制整个文件实现。索引文件的组织方式：通常是

34、在主文件之外建立一索引表指明逻辑记录和物理记录之间一一对应的关系，它和主文件一起构成索引文件。索引非顺序文件中的索引表为稠密索引。索引顺序文件中的索引表为稀疏索引。假设记录很大使得索引表也很大时，可对索引表再建立索引，称为查找表。是一种静态索引。索引顺序文件常用的有两种：ISAM 索引顺序存取方法：是专为磁盘存取文件设计的，采用静态索引构造。VSAM 虚拟存储存取方法：采用 B+树作为动态索引构造，由索引集、顺序集、数据集组成。散列文件是利用散列存储方式组织的文件，亦称为直接存取文件。散列文件 优点是：文件随机存放，记录不需要排序；插入删除方便；存取速度快；不需要索引区，节省存储空间。缺点是：不能进展顺序存取，只能按关键字随机存取，且询问方式限地简单询问，需要重新组织文件。多重表文件：对需要查询的次关键字建立相应的索引，对一样次关键字的记录建一个链表并将链表头指针、长度、次关键字作为索引表的索引项。-倒排表：次关键字索引表称倒排表，主文件和倒排表构成倒排文件。