数据结构期末复习资料

数据结构复习资料数据结构复习资料 第一章第一章 绪论绪论 1 1 基本概念和术语 1 数据数据是对客观事物的符号表示 数据元素数据元素是数据的基本单位 一个数据元素可由若干个数据项组成 数据项是数 据的不可分割的最小单位 数据对象数据对象是性质相同的数据元素的集合 是数据的一个子集 2 数据结构是相互之间存在一种或多种特定关系的数据元素的集合 3 A 数据结构的三要素 数据的逻辑结构 数据的存储结构 数据的运算 算法 B 任何一个算法的设计取决于选定的逻辑结构 而算法的实现依赖于采用的存储结构 4 数据的逻辑结构 集合 线性结构 树型结构 图状结构或网状结构 1 2 算法和算法分析 1 算法的五个特性 有穷性 确定性 可行性 输入 输出 2 时间复杂度 时间复杂度是指执行算法所需要的计算工作量 空间复杂度 空间复杂度是指执行这个算法所需要的内存空间 第二章第二章 线性表线性表 2 1 线性表的顺序表示和实现 1 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素 2 优点 线性表的顺序存储结构是一种随机存取随机存取的存储结构 3 顺序线性表插入 顺序线性表删除 4 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素 可连续 可不连续 5 对数据元素来说 除了存储其自身的信息之外 还需存储一个指示其直接后继的信息 存储位置 这两部分信息 组成数据元素的存储映像 称为结点 结点 他包括两个域 其中存储数据元素信息的域称为数据域 数据域 存储直接后继存 储位置的域称为指针域指针域 指针域中存储的信息称为指针指针或域域 N 个结点链结成一个链表链表 即为线性表的链式存储 结构 又由于此链表的每个结点中只包含一个指针域 故又称为线性链表线性链表或单链表 单链表 6 链表的插入与删除 7 双向链表的插入与删除 第三章第三章 栈和队列栈和队列 3 1 栈 1 栈是限定仅在表尾进行插入或删除操作的线性表 因此 对栈来说 表尾端有其特殊含义 称为栈顶 相应的 表 头端称为栈底 不含元素的空表称为空栈 2 栈又称为后进先出后进先出的线性表 3 栈的进栈与出栈操作 3 2 队列 1 队列是一种先进先出的线性表 它只允许在表的一段进行插入 而在另一端删除元素 2 允许插入的一端叫做队尾队尾 允许删除的一端则称为对头对头 第四章第四章 串串 4 1 串类型的定义 1 串 或字符串 是由零个或多个字符组成的有限序列 串中字符的数目 n 称为串的长度 零个字符的串称为空串 2 串中任意个连续的字符组成的子序列称为该串的子串子串 包含子串的串相应地称为主串主串 通常称字符在序列中的序 号为该字符在串中的位置位置 子串在主串中的位置则以子串的第一个字符在主串中的位置 3 只有当两个串的长度相等 并且各个对应位置的字符都相等时才相等 第五章第五章 树和二叉树树和二叉树 5 1 树的定义和基本术语 1 树是 n 个结点的有限集 2 结点结点 包含一个数据元素及若干指向其子树的分支 结点的度结点的度 结点拥有的子树数 度为 0 的结点称为叶子叶子或终端结点终端结点 度不为 0 的结点称为非终端结点非终端结点或分支结点分支结点 树的度树的度 树内各结点的度的最大值 孩子 孩子 结点的子树的根称为该结点的孩子 相应的 该结点称为孩子的双亲双亲 兄弟兄弟 同一个双亲的孩子之间互称兄弟 兄弟 祖先祖先 结点的祖先是从根到该结点所经分支上的所有结点 反之 以某结点为根的子树中任一结点都称为该结点 的子孙 结点所处层次结点所处层次 从根开始定义起 根为第一层 根的孩子为第二层 树的深度树的深度 树中结点的最大层次称为树的深度或高度 有序树 有序树 如果将树中结点的各子树看成从左至右是有次序的 即不能互换 则称该树为有序树 否则称为无序树 森林 森林 是 m 棵互不相交的树的集合 5 2 二叉树 1 二叉树是另一种树型结构 特点是 每个结点至多只有两棵子树 并且 二叉树的子树有左右之分 次序不能换 2 二叉树的性质 在二叉树的第 i 层上至多有个结点 i 1 深度为 k 的二叉树至多有个结点 k 1 2 12 1 3 满二叉树 满二叉树 每一层上的结点数都是最大结点数 深度为 k 且有个结点的二叉树 2 1 4 完全二叉树完全二叉树 若设二叉树的深度为 h 则共有 h 层 除第 h 层外 其它各层 0 h 1 的结点数都达到最大个数 第 h 层从右向左连续缺若干结点 这就是完全二叉树 5 3 遍历二叉树 1 先序遍历 DLR 遍历结果 遍历结果 a b c d e f 2 中序遍历 LDR 遍历结果 遍历结果 a b c d e f 3 后序遍历 LRD 遍历结果 遍历结果 a b c d e f 4 树的综合算法 求深度 5 4 树和森林 1 森林与二叉树的转换 在同胞兄弟之间加连线 在同胞兄弟之间加连线 保留结点与第一个孩子之间的连线 去掉其余连线 保留结点与第一个孩子之间的连线 去掉其余连线 顺时针旋转顺时针旋转 45 度 以根结点为轴 左孩子不再旋转 度 以根结点为轴 左孩子不再旋转 5 5 赫夫曼树及其应用 1 路径长度路径长度 两个结点之间的路径长度是连接两结点的路径上的分支数 树的路径长度树的路径长度 树的路径长度是各结点到根结点的路径长度之和 树的带权路径长度 树的带权路径长度 树的各叶结点所带的权值与该结点到根的路径长度的乘积的和 赫夫曼树 赫夫曼树 带权路径长度达到最小的二叉树即为赫夫曼树 最优二叉树 在赫夫曼树中 权值大的结点离根最近 2 如何构造赫夫曼树 重点 如何构造赫夫曼树 重点 1 由给定的 n 个权值 w0 w1 w2 wn 1 构造具有 n 棵二叉树的森林 F T0 T1 T2 Tn 1 其中每一棵二叉树 Ti 只有一个带有权值 wi的根结点 其左 右子树均为空 2 在 F 中选取两棵根结点的权值最小的二叉树 做为左 右子树构造一棵新的二叉树 置新的二叉树的根结点的 权值为其左 右子树上根结点的权值之和 3 在 F 中删去这两棵二叉树 同时把新的二叉树加入 F 4 重复 2 和 3 直到 F 只含一棵树为止 这棵树便是赫夫曼树 第六章第六章 图图 6 1 图的定义与术语图的定义与术语 1 图是由顶点集合及顶点间的关系集合组成的一种数据结构 2 在图中的数据元素通常称做顶点顶点 3 x y 表示从 x 到 y 的一条弧弧 x 为弧尾或初始点 y 为弧头或终端点 此时的图称为有向图 有向图 4 无向图 边用 x y 表示 且顶 x 与 y 是无序的 5 n 个顶点间有 n n 1 2 条边 6 完全图 完全图 有 n n 1 2 条边的无向图 7 有向完全图有向完全图 具有 n n 1 条弧弧的有向图 图中各边都有方向 且每两个顶点之间都有两条方向相反的边连接的图 无向完全图无向完全图 边数边数恰好等于 n n 1 2 的 n 个结点的无向图称为完全图 稀疏图稀疏图 有很少条边或弧的图称为稀疏图 反之称为稠密图 8 顶点的度顶点的度 无向图 与该顶点相关的边的数目 有向图 入度 入度 以该顶点为头的弧的数目 出度 出度 以该顶点为尾头的弧的数目 在有向图中在有向图中 顶点的度等于该顶点的入度与出度之和 顶点的度等于该顶点的入度与出度之和 9 邻接点邻接点 无向图 两顶点之间有条边 则两顶点互为邻接点 有向图 从 x 到 y 有一条弧 则 y 是 x 的邻接点 但 x 不是 y 的邻接点 权 某些图的边具有与它相关的数 称之为权 这种带权图叫做网络 10 路径长度路径长度 非带权图的路径长度是指此路径上边 弧的条数 带权图的路径长度是指路径上各边 弧的权之和 11 简单路径 简单路径 若路径上各顶点 v1 v2 vm 均不互相重复 则称这样的路径为简单路径 回路 回路 若路径上第一个顶点 v1 与最后一个顶点 vm 重合 则称这样的路径为回路或环 12 连通图与连通分量连通图与连通分量 在无向图中 若从顶点 v1到顶点 v2有路径 则称顶点 v1与 v2是连通的 如果图中任意一对顶点都是连通的 则称 此图是连通图连通图 非连通图的极大连通子图叫做连通分量连通分量 13 强连通图与强连通分量强连通图与强连通分量 在有向图中 若对于每一对顶点 vi和 vj 都存在一条从 vi到 vj和从 vj到 vi的路径 则称此图是强连通图强连通图 非强连通 图的极大强连通子图叫做强连通分量强连通分量 14 生成树生成树 一个连通图的生成树是它的极小连通子图 在 n 个顶点的情形下 有 n 1 条边 生成树是对指连通图来而言的生成树是对指连通图来而言的 是连同图的极小连同子图是连同图的极小连同子图 包含图中的所有顶点包含图中的所有顶点 有且仅有有且仅有 n 1 条边条边 6 2 图的遍历图的遍历 1 从图中某一顶点出发访遍图中其余顶点 且使每个顶点仅被访问一次 就叫做图的遍历图的遍历 2 图的遍历算法是求解图的连通性问题 拓扑排序和求 关键路径等算法的基础 3 两条遍历图的路径 深度优先搜索 广度优先搜索 深度优先搜索 广度优先搜索 4 深度优先搜索 深度优先搜索 1 从图中的某个顶点 V 出发 访问之 2 依次从顶点 V 的未被访问过的邻接点出发 深度优先遍历图 直 到图中所有和顶点 V 有路径相通的顶点都被访问到 3 若此时图中尚有顶点未被访问到 则另选一个未被访问过的顶点作起始点 重复上述 1 2 的操作 直 到图中所有的顶点都被访问到为止 5 广度优先搜索广度优先搜索 1 从图中的某个顶点 V 出发 访问之 2 依次访问顶点 V 的各个未被访问过的邻接点 将 V 的全部邻接点 都访问到 3 分别从这些邻接点出发 依次访问它们的未被访问过的邻接点 并使 先被访问的顶点的邻接点 先于 后被访问的顶点的邻接点 被访问 直到图中所有已被访问过的顶点的邻接点都被访问到 6 3 最小生成树的构造方法最小生成树的构造方法 1 普里姆算法构造最小生成树的过程 2 克鲁斯卡尔算法构造最小生成树的过程 6 4 有向无环图及其应用有向无环图及其应用 1 一个无环的有向图称为有向无环图有向无环图 2 如果在无有向环的带权有向图中如果在无有向环的带权有向图中 用有向边表示一个工程中的各项活动 用边上的权值表示活动的持续时间 用顶点表示事件 3 完成整个工程所需的时间取决于从源点到汇点的最长路径长度最长路径长度 即在这条路径上所有活动的持续时间之和 这条 路径长度最长的路径就叫做关键路径关键路径 4 关键路径的求解关键路径的求解 必考大题必考大题 事件事件 V1V1V2V2V3V3V4V4V5V5V6V6V7V7V8V8V9V9 最早最早 0 06 64 45 57 77 7161614141818 选最大选最大 最迟最迟 0 06 66 68 87 71010161614141818 V9V9 最早时间最早时间 从从 V9V9 到到 ViVi 路径最长路径最长 活动活动 A1A1A2A2A3A3A4A4A5A5A6A6A7A7A8A8A9A9A10A10A11A11 最早最早 0 00 00 06 64 45 57 77 77 716161414 起点的最迟时间起点的最迟时间 最迟最迟 0 02 23 36 66 68 87 77 7101016161414 V9 Ai V9 Ai 最大长度 最大长度 第七章第七章 查找查找 7 17 1 静态查找表静态查找表 1 顺序查找过程 顺序查找过程 从表中最后一个元素开始 顺序用各元素的关键字与给定值 x 进行比较 若找到与其值相等的元 素 则查找成功 给出该元素在表中的位置 否则 若直到第一个记录仍未找到关键字与 x 相等的对象 则查找 失败 算法 2 顺序查找的平均查找长度 n 1 2 查找成功 1 n 2 1 为最少查找次数 n 为最多查找次数 查找失败 n 1 3 折半查找 折半查找 先确定待查记录所在的范围 然后逐步缩小范围直到找到或找不到该记录为止 4 索引顺序表的查找 索引顺序表的查找 1 分块有序 升序或降序 分块有序 升序或降序 第第 i 块中的最大 小 值小 大 于第块中的最大 小 值小 大 于第 i 1 块中的最 大 小值块中的最 大 小值 2 查找 查找 1 先查索引表 先查索引表 折半查找 折半查找 2 再查顺序表 再查顺序表 顺序查找顺序查找 块间有序 块内无序块间有序 块内无序 7 27 2 动态查找表动态查找表 1 二叉排序树 二叉排序树 二叉查找树 二叉排序树 二叉查找树 或者是一棵空树 或者是具有下列性质的二叉树 或者是一棵空树 或者是具有下列性质的二叉树 每个结点都有一个作为查找依据的关键字 key 所有结点的关键字互不相同 左子树 若非空 上所有结点的关键字都小于根结点的关键字 右子树 若非空 上所有结点的关键字都大于根结点的关键字 左子树和右子树也是二叉排序树 2 二叉排序树的插入二叉排序树的插入 为了向二叉排序树中插入一个新元素 必须先检查这个元素是否在树中已经存在 在插入之前 先使用查找算法在树中检查要插入元素有还是没有 查找成功 树中已有这个元素 不再插入 查找不成功 树中原来没有关键字等于给定值的结点 把新元素加到查找操作停止的地方 3 二叉排序树的删除二叉排序树的删除 要删除二叉排序树中的 p 结点 分三种情况 p 为叶子结点 只需修改 p 双亲 f 的指针 f lchild NULL 或 f rchild NULL p 只有左子树 用 p 的左孩子代替 p p 只有右子树 用 p 的右孩子代替 p p 左 右子树均非空 沿 p 左子树的根 C 的右子树分支找到 S S 的右子树为空 将 S 的左子树成为 S 的双亲 Q 的 右子树 用 S 取代 p 若 C 无右子树 用 C 取代 p 4 二叉排序树的查找分析二叉排序树的查找分析 5 平衡二叉树平衡二叉树 AVL 树树 一棵 AVL 树或者是空树 或者是具有下列性质的二叉查找树 它的左子树和右子树都是 AVL 树 且左子树和右子 树的高度之差的绝对值不超过 1 平衡因子 平衡度 平衡因子 平衡度 结点的平衡度是结点的左子树的高度减去右子树的高度 平衡二叉树 平衡二叉树 每个结点的平衡因子都为 1 1 0 的二叉树 或者说每个结点的左右子树的高度最多差一的二 叉树 注意 注意 完全二叉树必为平衡树 平衡树不一定是完全二叉树 7 37 3 平衡化旋转平衡化旋转 1 平衡化