《2022年数据结构概念名词解释大全 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构概念名词解释大全 .pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、学习好资料欢迎下载数据：是对客观事物的符号表示。数据元素：是数据的基本单位，也称节点（node）或记录（ record） 。数据对象：是性质相同的数据元素的集合，是数据的一个子集。数据项：有独立含义的数据最小单位，也称域(field) 。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。根据数据元素间关系的基本特性，有四种基本数据结构集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。线性结构：结构中的数据元素之间存在一个对一个的关系。树形结构：结构中的数据元素之间存在一个对多个的关系。图状结构或网状结结构：结构中的数据元素之间存在多个对多个的关系。逻辑结构：抽象
2、反映数据元素之间的逻辑关系。（算法设计）物理结构（存储结构） ：数据结构在计算机中的表示。（算法实现）存储结构分为：顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系。算法：对特定问题求解步骤的一种描述。算法的五个重要特性：有穷性，确定性，可行性，输入和输出。算法设计的原则或要求：正确性，可读性，健壮性，效率与低存储量需求。衡量算法效率的方法：事后统计法和事前分析估算法。算法执行时间的增长率和f(n) 的增长率相同，则可记作：T (n) = O(f(n) ，称 T (n) 为算法的 (渐近 )时间复杂度算法运行
3、时间的衡量准则：以基本操作在算法中重复执行的次数。栈：限定仅在表尾进行插入或删除操作线性表。入栈：插入元素的操作；出栈： 删除栈顶元素的操作。队列：只能在队首进行删除、队尾进行插入的线性表。允许插入的一端叫队尾，删除的一端叫队头。串：由零个或多个字符组成的有限序列；空串：零个字符的串；长度：串中字符的数目；空串：零个字符的串；子串：；串中任意个连续的字符组成的子序列；位置：字符在序列中的序号；相等：串的值相等；空格串：由一个或多个空格组成的串，空格串的长度为串中空格字符的个数。存储位置： LOC(i ,j)=LOC(0,0)+(b2*i+j)L结点 :包含一个数据元素及若干指向其子树的分支；结
4、点的度: 结点拥有的子树；树的度 :树中所有结点的度的最大值；叶子结点: 度为零的结点；分支结点: 度大于零的结点树的深度：树中叶子结点所在的最大层次森林： m 棵互不相交的树的集合。二叉树的性质：性质 1 ：在二叉树的第 i 层上至多有2i-1 个结点。 (i 1) 性质 2 ：深度为 k 的二叉树上至多含 2k-1 个结点。（k1）性质 3: 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。性质 4: 具有 n 个结点的完全二叉树的深度为 log2n +1 。满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含
5、的n 个结点和满二叉树中编号为1 至n 的结点一一对应。路径长度：路径上分支的数目。树的路径长度：树根到每个结点的路径长度之和。树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作：WPL(T) =wklk带权路径长度最小的二叉树，称为最优树二叉树或赫夫曼树。关键路径：路径长度最长的路径。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 9 页学习好资料欢迎下载顶点：数据元素vi 称为顶点边、弧： P (vi,vj)表示顶点vi 和顶点 vj 之间的直接连线，在无向图中称为边，在有向图中称为弧。任意两个顶点构成的偶对(vi,vj)E
6、是无序的，该连线称为边。是有序的，该连线称为弧。弧头、弧尾：带箭头的一端称为弧头，不带箭头的一端称为弧尾。顶点的度 (TD)=出度 (OD)+入度 (ID) 图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。通常有两条遍历图的路径：深度优先搜索和广度优先搜索。排序的分类：按待排序记录所在位置内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行访问的排序按排序依据原则插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序归并排序： 2-路归并排序基数排序一、名词总结：ADT ：抽象数据型是一个数学模型和在该模型上定义的
7、操作的集合线性表 ： 线性表是由 n(n0)个相同类型的元素组成的有序集合。栈：线性表的一种特殊形式， 是一种限定性数据结构， 也就是在对线性表的操作加以限制后， 形成的一种新的数据结构。 是限定只在表尾进行插入和删除操作的线性表。栈又称为后进先出的线性表。队列：将线性表的插入和删除操作分别限制在表的两端进行，和栈相反， 队列是一种先进先出的线性表。串：线性表的一种特殊形式，表中每个元素的类型为字符型，是一个有限的字符序列。广义表： 由零个原子，或若干个原子或若干个广义表组成的有穷序列。树：1、 一个结点 x 组成的集 x 是一株树 (Tree) ，这个结点 x 也是这株树的根。精选学习资料
8、- - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 9 页学习好资料欢迎下载2、假设 x 是一个结点， T1，T2， Tk是 k 株互不相交的树，我们可以构造一株新树：令 x 为根，并有 k 条边由 x 指向树 T1，T2， Tk。这些边也叫做分支， T1，T2， Tk 称作根 x 的树之子树。二叉树： 有限个结点的集合，这个集合或者是空集，或者是由一个根结点和两株互不相交的二叉树组成，其中一株叫根的做左子树，另一棵叫做根的右子树。满二叉树： 深度为 k 且有 2k 1 个结点的二叉树称为满二叉树。完全二叉树： 深度为 k 的，有 n 个结点的二叉树，当
9、且仅当其每个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应，称之为完全二叉树。线索二叉树： 若结点 p有左孩子，则 p-lchild指向其左孩子结点，否则令其指向其（中序）前驱。若结点p 有右孩子，则 p-rchild指向其右孩子结点，否则令其指向其（中序）后继。堆：如果一棵完全二叉树的任意一个非终端结点的元素都不小于其左儿子结点和右儿子结点（如果有的话）的元素，则称此完全二叉树为最大堆。同样，如果一棵完全二叉树的任意一个非终端结点的元素都不大于其左儿子结点和右儿子结点（如果有的话）的元素，则称此完全二叉树为最小堆。选择树：一棵选择树是一棵二叉树， 其中每一个结点都代表该结
10、点两个儿子中的较小者。这样，树的根结点就表示树中最小元素的结点。二叉排序树： 二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：1、若它的左子树非空，则左子树上的所有结点的值均小于它的根结点的值。2、若它的右子树非空，则右子树上的所有结点的值均大于或等于它的根结点的值。3、它的左右子树分别为二叉排序树。图：一个图 G= （V，E）是一个由非空的有限集 V 和一个边集 E所组成的。若E中的每条边都是顶点的有序对（v , w），就说该图是有向图（ directed graph，digraph ）。若 E中的每条边是两个不同顶点无序对，就说该图是无向图，其边仍表示成（ v, w ）。开放树： 连
11、通而无环路的无向图称作开放树。最小生成树： 设 G=( V, E )是一个连通图， E中每一条边 (u, v) 的权为 C(u, v) ，也叫做边长。图 G的一株生成树 (spanning tree) 是连接 V中所有结点的一株精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 9 页学习好资料欢迎下载开放树。将生成树中所有边长之总和称为生成树的价(cost) 。使这个价最小的生成树称为图 G的最小生成树。无向图双连通分量： 设 Vi 是 Ei 中各边所连接的点集（ 1i k）, 每个图 Gi = ( Vi , E i) 叫做 G 的一个双
12、连通分量。双连通图： 若对 V中每个不同的三元组v,w,a ；在 v 和 w之间都存在一条不包含 a 的路，就说 G是双连通的强连通性： 设 G =（V, E）是一个有向图，称顶点v ,wV是等价的，要么 v = w；要么从顶点v到w有一条有向路 ，并且从顶点w到v也有一条有向路。拓扑排序： 给定一个无环路有向图G=(V,E) , 各结点的编号为v=(1,2, ,n) 。要求对每一个结点i 重新进行编号，使得若i是j 的前导，则有 Label i labelj 。即拓扑分类是将无环路有向图排成一个线性序列，使当从结点 i 到结点 j 存在一条边，则在线性序列中，将i 排在 j 的前面。AOE网
13、：在带权的有向图中，用结点表示事件，用边表示活动，边上权表示活动的开销（如持续时间），则称此有向图为边表示活动的网络, 简称 AOE网。关键路径： 在 AOE 网中，由于有些活动可以并行，所以完成工程的最短时间是从源点到汇点的最大路径长度。 因此，把从源点到汇点具有最大长度的路径称为关键路径。查找表： 由同一类型的数据元素（或纪录）构成的集合。关键字： 数据元素中某一数据项的值，用以表示一个数据元素。AVL树：AVL树或者是一颗空二叉树，或者具有如下性质的二叉查找树：其左子树和右子树都是高度平衡的二叉树，且左子树和右子树高度之差的绝对值不超过 1。B-树：B-树是一种非二叉的查找树除了要满足查
14、找树的特性，还要满足以下结构特性：一棵 m 阶的 B- 树：（1）树的根或者是一片叶子(一个节点的树 ), 或者其儿子数在 2 和 m之间。（2）除根外，所有的非叶子结点的孩子数在m/2和 m之间。（3）所有的叶子结点都在相同的深度。B+树：B-树的一种变形，二者区别在于：1、有 k 个子结点的结点必然有k 个关键码；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 9 页学习好资料欢迎下载2、非叶子结点仅具有索引作用，与记录有关的信息均放在叶结点中。地址散列法： 被查找元素的存储地址 = Hash ( Key ) 。堆分类： 把具有如下
15、性质的数组A表示的二元树称为堆（ Heap ）: (1) 若 2*i n，则 Ai.key A2*i.key ; (2) 若 2*i+1 n，则 Ai.keyA2*i+1.key; 小顶堆把具有如下性质的数组A表示的二元树称为堆（ Heap ）: (1) 若 2*i n，则 Ai.key A2*i.key ; (2) 若 2*i+1 n，则 Ai.keyA2*i+1.key; 大顶堆词典排序： 设集合 S中的元素为整数元组，关系 为 S的线性序，对两个元素( s1,s2,sp )和 ( t1,t2,tq )存在( s1,s2,sp ) ( t1,t2,tq )， 当存在一个整数 j ，1jma
16、xp,q ，使得 sj tj ，且所有 1i j ，si ti ；或者 pq，并且 si ti ，1i p，则关系 称为词典序。归并方法： 首先将文件中的数据输入到内存，采用内部分类方法进行分类（归并段），然后将有序段写回外存；对多归并段进行多遍归并，最后形成一个有序序列。索引： 指的是记录的关键字值与记录驻留在外存的地址组成数对的集合。每个数对称为一个索引项。二、重要算法总结第二章： 1、模式匹配法（ KMP 算法）2、串的 Substr 算法第三章： 1、二叉树的先、中、后序遍历（递归算法）2、二叉树的中序非递归遍历（辅助栈、非辅助栈）3、二叉树交换左右子树；4、二叉树求深度、结点赋层号精
17、选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 9 页学习好资料欢迎下载5、哈夫曼树的构造第四章： 1、DFS 、BFS 2、最小生成树3、强连通性4、拓扑排序5、Dijkstra算法单源最短路径第五章： 1、二叉排序树2、AVL树3、地址散列法第六章：简单排序算法及快排1 数据结构是一门研究什么内容的学科？数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间的关系和施加于对象的操作等的学科。 2 数据元素之间的关系在计算机中有几种表示方法？各有什么特点？四种表示方法 （1）顺序存储方式。数据元素顺序存放，每个存储结点
18、只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作（如插入、删除）效率较差。（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。（3）索引存储方式。除数据元素存储在一地址连续的内存空间外， 尚需建立一个索引表， 索引表中索引指示存储结点的存储位置（下标）或存储区间端点 （下标），兼有静态和动态特性。（4）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关
19、键字所在元素的存储地址，这种存储方式称为散列存储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。 3 数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？数据类型是程序设计语言中的一个概念，它是一个值的集合和操作的集合。如 C语言中的整型、实型、字符型等。整型值的范围（对具体机器都应有整数范围），其操作有加、减、乘、除、求余等。实际上数据类型是厂家提供给用户的已实现了的数据结构。“抽象数据类型（ADT ）”指一个数学模型及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。抽象数据
20、类型的定义仅取决于它的逻辑特性， 而与其在计算机内部如何表示和实现无关。无论其内部结构如何变化， 只要它的数学特性不变就不影响它的外部使用。抽象数据类型和数精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 9 页学习好资料欢迎下载据类型实质上是一个概念。 此外，抽象数据类型的范围更广， 它已不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类型。使用抽象数据类型定义的软件模块含定义、表示和实现三部分， 封装在一起，对用户透明（提供接口），而不必了解实现细节。抽象数据类型的出现使程序设计不再是“艺术”，而是向“科
21、学”迈进了一步。 4 对于一个数据结构，一般包括哪三个方面：逻辑结构、存储结构、操作（运算）。 5 根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？集合、线性结构、树形结构、图形或网状结构。 6 线性表有两种存储结构： 一是顺序表，二是链表。试问：（1）如果有 n 个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。 在此情况下，应选用哪种存储结构？为什么？选链式存储结构。它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O （1）。 （2）若线性表的总数基本稳定，且很少进行插入和删除， 但要求以最快的速度存取线性表中的元素
22、，那么应采用哪种存储结构？为什么？选顺序存储结构。 顺序表可以随机存取， 时间复杂度为 O （1）。7线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用； 其三，表的容量难以扩充。 线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克
23、服顺序存储的缺点。8栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出（LIFO ）表。9队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开（删除），故队列也常称先进先出（FIFO ）表。10什么是循环队列？用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和队头删除），容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度（容量）。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循
24、环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。11若元素的进栈序列为：A、B、C、D、E，运用栈操作，能否得到出栈序列B、C、A、 E 、D 和 D、B、A、C、E ？为什么？能得到出栈序列B、C、 A、E、D，不能得到出栈序列D、B、A、C、E 。其理由为：若出栈序列以D 开头，说明在 D 之前的入栈元素是A、B 和 C，三个元素中C是栈顶元素， B 和 A 不可能早于C 出栈，故不可能得到D、B、 A、C、E 出栈序列。12串？串是零个至多个字符组成的有限序列。从数据结构角度讲，串属于线性结构。与线性表的特殊性在于串的元素是字符。13描述以下概念
25、的区别：空格串与空串。空格是一个字符，其ASCII码值是 32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。14数组A1.8，-2.6，0.6以行为主序存储，设第一个元素的首地址是78，每个元素的长度为4，试求元素A4,2,3的存储首地址。958 三维数组以行为主序存储，其元素地址公式为：LOC(ALOC(ALOC(ALOC(Aijkijkijkijk)=LOC(A)=LOC(A)=LOC(A)=LOC(Ac1c2c3c1c2c3c1c2c3c1c2c3)+(i)+(i)+(i)+(i-cccc1111)V)V)V)V2222VVVV3333+(j+
26、(j+(j+(j-cccc2222)V)V)V)V3333+(k+(k+(k+(k-cccc3333)*L+1)*L+1)*L+1)*L+1 其中 ci,di 是各维的下界和上界，Vi=di-ci+1 是各维元素个数，L 是一个元素所占的存储单元数。15数组 A 中，每个元素Ai,j的长度均为32 个二进位 ,行下标从 -1 到 9，列下标从1 到 11，从首地址S开始连续存放主存储器中，主存储器字长为16 位。求：（1）存放该数组所需精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 9 页学习好资料欢迎下载多少单元？（2）存放数组第4
27、列所有元素至少需多少单元？（3）数组按行存放时，元素A7,4的起始地址是多少？（4）数组按列存放时，元素A4,7的起始地址是多少？答：每个元素32 个二进制位，主存字长 16 位，故每个元素占2 个字长， 行下标可平移至1 到 11。（1） 242 （2） 22 （3）s+182 （4）s+142 16. 从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算
28、法去解决树和森林中的问题。树和二叉树的区别有三：一是二叉树的度至多为2， 树无此限制； 二是二叉树有左右子树之分，即使在只有一个分枝的情况下，也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。 17请分析线性表、树、广义表的主要结构特点，以及相互的差异与关联。线性表属于约束最强的线性结构，在非空线性表中，只有一个 “第一个” 元素， 也只有一个 “最后一个” 元素；除第一个元素外，每个元素有唯一前驱；除最后一个元素外，每个元素有唯一后继。树是一种层次结构，有且只有一个根结点，每个结点可以有多个子女，但只有一个双亲（根无双亲），从这个意义上说存在
29、一（双亲）对多（子女）的关系。广义表中的元素既可以是原子，也可以是子表，子表可以为它表共享。从表中套表意义上说，广义表也是层次结构。从逻辑上讲，树和广义表均属非线性结构。但在以下意义上，又蜕变为线性结构。如度为1 的树，以及广义表中的元素都是原子时。另外，广义表从元素之间的关系可看成前驱和后继，也符合线性表， 但这时元素有原子，也有子表，即元素并不属于同一数据对象。18一棵二叉树中的结点的度或为0 或为 2，则二叉树的枝数为2(n0-1)，其中n0 是度为 0 的结点的个数。证明： 设二叉树度为0 和 2 的结点数及总的结点数分别为n0，n2 和 n，则n=n0+n2 (1) 再设二叉树的分支
30、数为B, 除根结点外，每个结点都有一个分支所指，则n=B+1 (2) 度为零的结点是叶子，没有分支，而度为2 的结点有两个分支，因此（2）式可写为n=2*n2+1 (3) 由 （1） 、（3） 得 n2=n0-1,代入 （1） ， 并由 （ 1） 和 （2） 得 B=2*(n0-1) 。证毕。19 （1） 如果 G1 是一个具有n 个顶点的连通无向图，那么G1 最多有多少条边？G1 最少有多少条边？（2） 如果G2 是一个具有n 个顶点的强连通有向图，那么G2 最多有多少条边？G2最少有多少条边？（3） 如果 G3是一个具有n 个顶点的弱连通有向图，那么G3 最多有多少条边？G3 最少有多少条
31、边？答： （1）G1 最多 n(n-1)/2 条边，最少n-1 条边(2) G2 最多 n(n-1)条边，最少n条边(3) G3 最多 n(n-1)条边，最少n-1 条边(注：弱连通有向图指把有向图看作无向图时，仍是连通的) 20n 个顶点的无向连通图最少有多少条边？n 个顶点的有向连通图最少有多少条边？n-1，n 21内部排序（名词解释）假设含 n 个记录的序列为 R1, R2, ， Rn ，其相应的关键字序列为 K1, K2, ， Kn ，这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系Ks1Ks2Ksn，按此固有关系将n 个记录序列重新排列为 Rs1, Rs2, ， Rsn
32、 。若整个排序过程都在内存中完成，则称此类排序问题为内部排序。22在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。排序方法平均时间最坏情况辅助空间稳定性不稳定排序举例直接插入排序O（n2） O（n2） O（1） 稳定折半插入排序O（n2） O（n2） O（1） 稳定二路插入排序O（n2） O（n2） O（n） 稳定表插入排序O（n2） O（n2） O（1） 稳定起泡排序O（n2） O（n2） O（1） 稳定直接选择排序O（n2） O（n2） O（1） 不稳定2,2,1 希尔排序O（n1.3）O （ n1.3） O （ 1） 不稳定3,2,2,1(
33、d=2,d=1) 快速排序O （nlog2n） O （ n2） O （log2n） 不稳定2,2 ,1 堆排序O （ nlog2n） O （nlog2n） O （1） 不稳定2,1,1 (极大堆 ) 2-路归并排序O （nlog2n） O （nlog2n）O（n） 稳定基数排序O ( d*(rd+n) ) O ( d*(rd+n) ) O (rd ) 稳定23文件文件是由大量性质相同的记录组成的集合，按记录类型不同可分为操作系统文件和数据库文件。24文件存储结构的基本精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 9 页学习好资料欢迎下
34、载形式有哪些？一个文件采用何种存储结构应考虑哪些因素？文件的基本组织方式有顺序组织、索引组织、散列组织和链组织。文件的存储结构可以采用将基本组织结合的方法，常用的结构有顺序结构、索引结构、散列结构。（1） 顺序结构，相应文件为顺序文件，其记录按存入文件的先后次序顺序存放。 顺序文件本质上就是顺序表。若逻辑上相邻的两个记录在存储位置上相邻，则为连续文件；若记录之间以指针相链接，则称为串联文件。顺序文件只能顺序存取，要更新某个记录，必须复制整个文件。顺序文件连续存取的速度快，主要适用于顺序存取，批量修改的情况。（2） 带索引的结构，相应文件为索引文件。索引文件包括索引表和数据表，索引表中的索引项包
35、括数据表中数据的关键字和相应地址，索引表有序，其物理顺序体现了文件的逻辑次序，实现了文件的线性结构。索引文件只能是磁盘文件，既能顺序存取，又能隋机存取。（3） 散列结构，也称计算寻址结构，相应文件称为散列文件，其记录是根据关键字值经散列函数计算确定其地址，存取速度快，不需索引，节省存储空间。 不能顺序存取，只能随机存取。其它文件均由以上文件派生而得。文件采用何种存储结构应综合考虑各种因素，如：存储介质类型、记录的类型、大小和关键字的数目以及对文件作何种操作。25索引文件在主文件外，再建立索引表指示关键字及其物理记录的地址间一一对应关系。这种由索引表和主文件一起构成的文件称为索引文件。索引表依关键字有序。主文件若按关键字有序称为索引顺序文件，否则称为索引非顺序文件（通常简称索引文件）。索引顺序文件因主文件有序，一般用稀疏索引， 占用空间较少。 常用索引顺序文件有ISAM和 VSAM。 ISAM 采用静态索引结构， 而 VSAM采用B+树的动态索引结构。索引文件既能顺序存取，也能随机存取。26索引顺序文件在索引文件中，若（数据区）主文件中关键字有序，则文件称为索引顺序文件。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 9 页