数据结构名词术语.doc

数据元素: 数据元素是组成数据的基本单位.队列: 队列是一种操作受限制的线性表，它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端被称为队头（Front），允许插入的一端被称为队尾（Rear）。没有元素的队列称为空队列。中缀表达式: 在程序语言中，运算符位于两个操作数中间的表达式被称为中缀表达式。后缀表达式:运算符位于两个操作数后面的表达式被称为后缀表达式。一维数组: 一个一维数组就是若干个元素的一个有限序列，每个元素都通过一个下标来指定，元素本身就是一个数据结构（或是整型、逻辑型、字符型，或是数组、记录）. 对一维数组唯一的限制是所有的数组元素都必须具有相同的类型，即每个数组元素都占据相同大小的存储空间. 树的路径长度: 树的路径长度是从根结点到树中每个叶子结点的路径长度之和。增长树: 为了使问题的处理更为方便，可以让二叉树形增长，即每当原二叉树中的结点没有左子树形或右子树形时，就增加特殊的结点，由此生成的二叉树称为增长的二叉树，简称增长树。完全平衡二叉树: 一棵增长树，如果存在k，并使所有的外结点都在k层上或者都在k层和k+1层上，则称该增长树为完全平衡二叉树。图: 图G由两个集合V和E组成，记为G = (V , E) . 其中V是顶点的有限集合，E是连接V中两个不同顶点（顶点对）的边的有限集合。如果E中的顶点对是有序的，即E中的每条边都是有方向的，则称G为有向图。如果顶点对是无序对，则称G是无向图。一般情况下，图G的边集合记为E(G)，顶点集合记为 V(G)。邻接表: 由顺序存储的顶点表和链接存储的边链表构成的图的存储结构被称为邻接表。递归: 如果一个对象部分地包含它自己，或者利用自己定义自己的方式来定义或表述，则称这个对象是递归的；如果一个过程直接或间接地调用自己，则称这个过程是一个递归过程. 红-黑树: 是一棵树中结点颜色为红色或黑色的二叉搜索树，满足如下三个条件： （1）根结点和所有外结点的颜色为黑色； （2）根结点到任意一个外结点的路径中没有连续的两个红色结点； （3）根结点到任意外结点的路径上都有相同数目的黑色结点. 结点的阶（rank）：红-黑树中，一个结点的阶是从该结点到其子树中任一外结点的路径上的黑色指针的个数. 杂凑表（散列表）: 根据给定的杂凑函数Hash (Key)和处理冲突的方法，将一组关键词映射到一个有限的连续的地址区间上，并以关键词在地址集上的“映像”作为该记录在表中的存储位置，这种表称为杂凑表或者散列表. 这种映射过程称为杂凑，所得到的存储位置称为杂凑地址或者散列地址. 记录的大小: 记录的大小就是记录所占计算机字的个数。按行优先顺序: 所谓按行优先顺序，就是将数组元素按行向量的顺序存储，第 i个行向量存储在第i+1 个行向量之后。按列优先顺序: 所谓按列优先顺序，就是将数组元素按列向量的顺序存储，第 i个列向量存储在第i+1 个列向量之后。静态数组: 所谓静态数组，是指在声明一个数组时，就为整个数组分配了固定大小的内存空间.AOV网: 用顶点表示活动，用有向边表示活动之间的先后关系，称这样的有向图为AOV网(Activity On Vertex Network)。拓扑排序: 构造AOV网的拓扑序列的操作被称为拓扑排序。 时间复杂性：一个算法的时间复杂性是指该算法的基本运算次数。数据结构：（1）按某种逻辑关系将一批数据元素组织起来；（2）按一定的存储方式把它们存储起来；（3）在数据上定义一个运算集合，就得到（或者说形成）了一个数据结构。类：用高级程序设计语言实现的一个ADT描述被称为类，其中的数据项和函数（又称为方法）分别被称为类的数据成员和函数成员（或称成员函数），它们又被统称为类成员。对像：通过类说明定义的变量被称为对象动态数组：所谓动态数组，是指在运行时根据具体需要为整个数组分配内存空间. 稀疏矩阵：稀疏矩阵，简单的讲，就是零元素很多的矩阵. 三元组表：将表示稀疏矩阵 的非零元素的三元组结点按行优先的顺序排列，可以得到一个线性表，将此线性表用顺序存储结构存储起来，称之为三元组表. 排序：按指定的顺序排列一个给定对象集合中的诸元素. 这个过程我们把它称为排序（或者称为分类）. 自组织表：在实际中我们很难预知表中每个元素的发生概率Pi . 一般的想法是把经常出现的元素（它的发生概率较大）自动向表的前端移动，把不经常出现的元素自动向表的后端移动，并称以该方式组织的表为自组织表 .二叉查找树：一棵二叉查找树（或称为二叉搜索树）是一棵可能为空的二叉树形，一棵非空的二叉查找树中的所有结点在中根次序下按其关键词由小到大排序，并且关键词各不相同. 隐式释放和显式释放：程序释放单元的方式一般有两种。一种称为隐式释放，另一种称为显式释放。隐式释放是指每当AVAIL表为空时，内存管理程序就把所有废品加上标志进行回收的过程；显式释放是程序每释放一个记录，内存管理程序就将其回收到AVAIL表中的管理方式。线性表：一个线性表是由零个或多个具有相同类型的结点组成的有序集合。包含零个结点的线性表被称为空表。顺序存储结构：顺序存储结构就是按逻辑次序把线性表的结点依次存放在一组地址连续的存储单元中。遍历：所谓遍历一个结构，是指按一定的次序访问结构中的所有结点，且每个结点恰被访问一次。 堆栈（简称栈）：是一种操作受限制的线性表，它只允许在表的同一端进行插入和删除操作。通常将进行插入和删除的一端称为栈顶（top），称另一端为栈底（bottom） 。当表中没有元素时称该表为空栈。字符串：字符串是由零个或多个字符组成的有限序列.整型集合：简单地说，整型集合是由数据类型为整型的元素构成的集合. 优先级队列：优先级队列中的每个元素都具有各自的优先级，元素入队同队列一样是将该元素插入队尾，但出队一个元素是指删除优先级队列中优先级最高的元素，若队列中有两个（或两个以上）优先级最高的元素，则按照先进先出的原则。 树：是由唯一的起始结点“根结点”出发的结点集合，其中，任何非根结点都有且仅有一个前趋结点，称之为该结点的父结点；任何结点都可能有多个后继结点，称之为该结点的子结点；若某结点没有后继结点，则称之为叶子结点。子树：如果断掉一个结点与其父结点的连接，把该结点和它的子孙们单独拿出，那么就是一棵以该结点为根结点的树，我们称之为“子树”。结点的层数：从根结点到某个结点的路径长度被称为结点的层数。树的高度是指树中结点的最大层数。二叉树：是结点的有限集合，它必须满足下面的一个条件：（1） 它是空集。（2） 它由一个根结点和根结点的左右子树构成，且其左右子树满足二叉树定义。先根（中根、后根）序列：先根（中根、后根）遍历次序是树中结点的一个有序序列，我们称之为二叉树的先根（中根、后根）序列。内排序和外排序：排序分为内排序和外排序当所有待排序的记录都在内存中时，我们称排序过程为内排序；当输入文件中的记录个数n大到计算机内存不能容纳时，排序过程必需借助外存来完成，这时的排序就称为外排序. 废料收集：废料收集技术，是在废品被回收之前为每个废品设置一个废品标志，从而报告内存管理程序哪些活动记录是废品，哪些是真正的活动记录。AOE网：边表示一个活动，边上的权值表示该活动所需的时间的图称为AOE网(Activity On Edge network)。顶点表示它的入边的活动已经完成、它的出边的活动可以开始的一种状态，也称之为一个事件。关键路径：从一个源点（入度为0的顶点）到一个汇点（出度为0的顶点）具有最大长度的路径被称为关键路径。这里的路径长度是指路径上的各边权值之和。堆：如果完全二叉树中的任意结点的关键词大于等于它的两个儿子结点的关键词，则 我们把这样的数据结构称为堆. 查找（又称检索）：简单地说就是查表. 表通常指小文件，文件一般指大表，一个大的文件或一组文件通常被称为一个数据库。这里我们用各种数据结构（如数组、链表和树形等）组成一个表，表中每个记录都