数据结构名词解释(个人备考时结合群里那个文档与王道书自己摘录的-仅供参考)

数据结构数据结构 一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系 与操作等的学科 数据数据 数据是信息的载体 是描述客观事物属性的数 字符以及所有能输入到计算机中并 被计算机程序处理的符号的集合 数据元素数据元素 数据的基本单位 在计算机程序中通常作为一个整体进行考虑与处理 数据类型数据类型 是一个值的集合与定义在此集合上一组操作的总称 包括 原子类型原子类型 其值不可在分的数据类型 结构类型结构类型 其值可以在分解为若干成分的数据类型 抽象数据类型抽象数据类型 ADT 指一个数学模型以及定义在该模型上的一组操作 通常用数据对象 数据关系 基本操作集这样的三元组来表示 有数据抽象与数据封装两个重要特性 数据结构数据结构 是相互之间存在一种或多种特定关系的数据元素的集合 包括 逻辑结构 存 储结构与数据的运算 数据的逻辑结构数据的逻辑结构 指数据元素之间的逻辑关系 包括集合 线性结构 树形结构 图状结 构或网状结构 数据的存储结构数据的存储结构 指数据结构在计算机中的表示 也成物理结构 主要有顺序存储 连接 存储 索引存储 散列存储 数据的运算数据的运算 施加在数据上的运算包括运算的定义与实现 定义是针对逻辑结构 指出运 算的功能 实现是针对存储结构的 指出运算的具体操作步骤 算法算法 对特定问题求解步骤的一种描述 是指令的有限序列 其中每一条指令表示一个或 多个操作 有 5 个重要特性 有穷性 确定性 可行性 输入 输出 算法设计的要求算法设计的要求 正确性 可读性 健壮性 效率与低存储量需求 时间复杂度时间复杂度 一般情况下 算法中基本操作的重复次数是问题规模 n 的某个函数 f n 算法的时间度量记作 T n O f n 表示随着问题规模 n 的增大 算法执行时间增长 率与 f n 的增长率相同 称为时间复杂度 空间复杂度空间复杂度 S n 定义为该算法所耗费的村粗空间 是问题规模 n 的函数 第 2 章 线性表 线性表线性表 具有相同数据类型的 n n 0 个数据元素的有限序列 线性表的顺序存储又称顺序表顺序表 链式存储又称单链表单链表 静态链表静态链表 借助数组来描述线性表的链式存储结构 结点也有数据域与指针域 但指针是 结点的相对地址 数组下标 需要预先分配连续的内存空间 栈栈 限定在表尾进行插入或删除操作的线性表 操作端称为栈顶 后进先出 队列队列 一种先进先出的线性表 只允许在表的一段插入元素 另一端删除元素 在队列中 允许插入的一端为队尾 允许删除的一端为队头 串串 由零个或者多个字符组成的有限序列 串中任意个连续的字符组成的子序列称为该串 的子串 字符在序列中的序号为该字符的位置 树的结点结点包括一个数据元素以及若干指向其子树的分支 结点拥有的子树称为结点的度度 度为 0 的结点称为叶子叶子或终端结点 树的度树的度是树内个结点的度的最大值 结点的子树的根 称为该结点的孩子孩子 相应的该节点为孩子的双亲双亲 同一个双亲的孩子之间互称兄弟兄弟 结点 的祖先祖先是从根到该结点的所经分支上的所有结点 反之 以某结点为根的子树中任一结点 都称为该结点的子孙子孙 结点的层次结点的层次 从树根开始定义 根结点为第 1 层 它的子结点为第 2 层 以此类推 树的高度或深度树的高度或深度 树中结点的最大层数 有序树与无序树有序树与无序树 树中结点的子树从左到右是有次序的 不能交换 叫做有序树 反之为 无序树 路径与路径长度路径与路径长度 树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的 路径长度是路径上经过的边的个数 树的路径长度树的路径长度 树根到每一个结点的路径长度之与 树的带权路径长度 树的带权路径长度 WPL 树中所有叶子结点的带权路径长度之与 哈夫曼树哈夫曼树 在含有 N 个带权叶子结点的二叉树中 其中带权路径长度 WPL 最小的二叉 树称为哈夫曼树或最优二叉树 哈夫曼编码哈夫曼编码 一种广泛应用而且非常有效的数据压缩编码 森林森林 m m 0 棵互不相交的树的集合 二叉树二叉树 是另一种树形结构 每个结点至多有两棵子树 并且 二叉树的子树有左右之分 其次序不能任意颠倒 满二叉树满二叉树 一棵高度为 h 并且含有 2 h 1 个结点的二叉树称为满二叉树 即每层都有最 多的结点 叶子集中在二叉树的最下一层且除叶子之外的每个结点度为 2 完全二叉树完全二叉树 设一个高度为 h 有 n 个结点的二叉树 当且仅当其每一个结点都与高度为 h 的满二叉树中编号为 1 n 的结点一一对应时 称为完全二叉树 二叉排序树二叉排序树 一棵二叉树或是空二叉树或是具有以下性质的二叉树 左子树上所有关键字 均小于根结点的关键字 右子树所有结点关键字大于根结点的关键字 左子树与右子树又 各是一棵二叉排序树 平衡二叉树平衡二叉树 树上任一结点的左子树与右子树的深度之差不超过 1 平衡因子平衡因子 该结点的左子树深度减去它的右子树深度 二叉树的遍历二叉树的遍历 指按某条搜索路径访问树中的每个结点 使得每个结点均被访问一次且仅 被访问一次 线索二叉树线索二叉树 若结点有左 右 子树 则其 lchild rchild 域指向其左 右 孩子 否则 令 lchild rchild 域指向其前驱 后继 这种结点构成的二叉链表作为二叉树的存储结构 称为二叉链表二叉链表 其中指向结点前驱与后继的指针叫做线索线索 加上线索的二叉树称为线索二线索二 叉树叉树 对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化线索化 判定树判定树 树中每个结点表示表中的一个记录 结点里的值为该记录在表中的位置 通常称 这个查找过程的二叉树为判定树 树的先根遍历树的先根遍历 若树非空 则先访问根结点 再按从左到右的顺序遍历根节点的每一颗子 树 其访问顺序与这棵树对应的二叉树的线序遍历顺序相同 树的后跟遍历树的后跟遍历 若树非空 则按从左到右的顺序遍历根结点的每一棵子树 之后再访问根 结点 其访问顺序与其对应的二叉树的中序遍历相同 先序遍历森林先序遍历森林 若森林非空 则按如下规则遍历 访问森林第一棵树的根结点 选序遍历第一棵树中根结点的子树森林 线序遍历除去第一棵树之后剩余的树构成的森林 中序遍历森林中序遍历森林 若森林非空 则按如下规则进行遍历 中序遍历森林中第一棵树的根结点的子树森林 访问第一棵树的根结点 中序遍历除去第一棵树之后剩余的树构成的森林 图图 由顶点集 V 与边集 E 组成 记作 G V E 有向图有向图 E 为有向边的有限集合时 图 G 为有向图 无向图无向图 E 为无向边的有限集合时 图 G 为无向图 简单图简单图 不存在重复边 不存在定点到自身的边称图 G 为简单图 与多重图相对 完全图完全图 在无向图中 若任意两个顶点之间都存在边 则称该图为无向完全图 具有 n n 1 2 条边 有向图中 若任意两个顶点之间存在方向相反的两条弧 称为有向完全 图 含有 n n 1 条有向边 连通连通 若从顶点 v 到顶点 w 存在路径 则 v 与 w 是联通的 若图 G 中任意两个顶点都是联 通的 则称图 G 为连通图连通图 否则非连通图 无向图中的极大连通子图称为连通分量连通分量 在有向图中 若从 V 到顶点 W 与从顶点 W 到顶点 V 都存在路径 则称两个顶点是强连通 的 若图中任一对顶点都是强连通的 则称为强连通图强连通图 有向图中的极大强连通子图称为 有向图的强连通分量强连通分量 生成树生成树与生成森林 生成森林 连通图的生成树是包含图中所有顶点的一个极小连通子图 若顶点为 n 则含有 n 1 条边 非连通图中 连通分量的生成树构成生成森林 最小生成树最小生成树 一个带权连通无向图的生成树中边的权值之与最小的那个叫做此图的最小生 成树 有向树有向树 如果一个有向图恰有一个顶点的入度为 0 其余顶点的入度为 1 则是一棵有向树 路径 路径长度与回路路径 路径长度与回路 顶点 V 到顶点 Q 之间的一条路径是指之间的一个顶点序列 路径 的长度是路径上边的数目 第一个顶点与最后一个顶点相同的路径称为回路或环 最短路径最短路径 带权图中 从一个顶点 V0 到另一个顶点 V1 的一条路径上所经过边的权值之与 定义为该路径的带权路径长度 其中最短的那条称作最短路径 此路径的长度称为从 v 到 u 的距离 图的遍历图的遍历 从图中某一顶点出发 按照某种搜索方法沿着图中的边对图中所有顶点访问一 次且仅访问一次 深度优先搜索深度优先搜索 类似于树的先序遍历 假设从图中某顶点 V 出发 在访问了 V 之后一次从 V 的未被访问的邻接点出发做深度优先遍历 知道图中所有与 v 有路径相同的顶点都被访 问到 若图中还有顶点未访问 则另选图中一个未曾被方位的顶点作为起始点 重复上述 过程 直至图中所有顶点都被访问 广度优先搜索广度优先搜索 类似于树的层次遍历 从顶点 v 出发 访问了 V 之后依次访问 v 的各个未 被访问过的邻接顶点 再依次访问它们的邻接点 并使先被访问的顶点的的邻接点先于后 访问的顶点的邻接点 直到图中所有已被访问顶点的邻接点都被访问到 如果图中还有顶 点未被访问 则另选一个未被访问的顶点作为起始点 重复上述过程 直到图中所有顶点 都被访问 AOV 网网 用有向无环图表示一个工程 顶点表示活动 有向边表示 Vi 必须先于 Vj 进行的关系 则称为 AOV 网 AOE 网网 在带权有向图中 以顶点表示事件 有向边表示活动 边上的权值表示完成该活 动的开销 如时间 则称这个网络为 AOE 网 关键路径关键路径 在 AOE 网中 路径长度最长的路径叫做关键路径 关键路径上的所有活动都是 关键活动关键活动 拓扑排序拓扑排序 由一个有向无环图的顶点组成的序列 当且仅当满足下列条件 称为该图的一 个拓扑排序 1 每个顶点出现且仅出现一次 2 若顶点 a 在 b 之前 不存在 b 到 a 的路 径 查找查找 在数据集合中寻找满足某种条件的数据元素的过程称为查找 查找表查找表 查找结构 用于查找的数据集合称为查找表 静态查找表静态查找表 如果一个查找表的操作仅涉及查询某个特定的数据元素是否在查找表中与检 索满足条件的某个特定的数据元素的各种属性 则称为静态查找表 动态查找表动态查找表 需要动态的插入或删除的查找表称为动态查找表 关键字关键字 数据元素中唯一标识该元素的某个数据项的值 使用基于关键字的查找 查找结 果应该是唯一的 平均查找长度 平均查找长度 ASL 在查找的过程中 一次查找的长度指需要比较的关键字次数 而平 均查找长度则是所有查找过程中进行关键字的比较次数的平均值 折半查找折半查找 仅适用于有序的顺序表 将给定的值 key 与表中间位置元素的关键字比较 相 等则查找成功返回位置 若不等则缩小查找范围 重复查找直到找到或者确定表中没有需 查找的元素 散列函数散列函数 一个把查找表中的关键字映射成该关键字对应的地址的函数 冲突冲突 散列函数可能会把两个或以上的不同关键字映射到同一地址 这种情况为冲突 散列表散列表 是根据关键字而直接进行访问的数据结构 散列表建立了关键字与存储地址指间 的一种直接映射关系 开放定址法开放定址法 指的是可存放新表项的空闲地址既向它的同义词表项开放 又向它的非同义 词表项开放 拉链法 链地址法 拉链法 链地址法 把所有的同义词存储在一个线性链表中 这个线性链表由其散列地 址唯一标识 装填因子装填因子 是哈希表中填入的记录数与哈希表的长度之商 哈希表的平均查找长度是装填 因子的函数 不是规模的函数 散列表的查找效率取决于三个因素 散列函数 处理冲突 的方法与装填因子 二次聚集二次聚集 指在处理冲突过程中发生的两个第一个哈希地址不同的记录争夺同一个后继哈 希地址的现象 第 10 章 内部排序 排序排序 重新排列表中的元素 使表中的元素满足按关键字递增或递减的过程 算法的稳定性算法的稳定性 假设 Ri Rj 且在排序之前 Ri 领先于 Rj 若在排序后的序列中 Ri 仍然领先 于 Rj 则称所用的排序算法是稳定的 反之则称所用的算法是不稳定的 内部排序内部排序 排序期间元素全部存放在内存中的排序 外部排序是指在排序期间元素无法全 部同时存放在内存中 必须在排序的过程中根据要求不断的在内外存指间移动的排序 插入排序插入排序 每次将一个待排序的记录 按关键字大小插入到前面已经排好序的子序列中 直至全部记录插入完成 希尔排序希尔排序 又称缩小增量排序 先将整个记录序列分割成若干子序列分别进行直接插入排 序 待整个序列中记录基本有序时 再对全体进行一次直接插入排序 冒泡排序 冒泡排序 从前往后 或从后往前 两两比较相邻元素的值 若为逆序则交换 知道序列 比较完 既完成一趟冒泡排序 这一趟确定的最小元素不再参与比较 重复上述过程直到 一趟排序没有记录交换 快速排序快速排序 通过一趟排序将带排记录分割成独立两部分 其中一部分的关键字均比另一部 分小 分别对两部分再进行快速排序直至整个序列有序 选择排序选择排序 每一趟在未排序的记录中选择最小