数据结构期末复习资料.pdf

计算机科学与技术 专升本 数据结构期末考试复习资料 古月编辑整理 祝愿大家考试考出自己理想的成绩 本资料仅供参考 谢谢 1 数据结构 期末考试复习资料 考试时间 考试时间 12 月 27 日 周一下午 14 00 15 30 考试考试地点地点 创新楼 110 复习范围 复习范围 算法与数据结构 第一至第八章 考试题型 考试题型 选择题 每小题 1 5 分 共 30 分 判断题 每小题 2 分 共 20 分 填空题 每空 2 分 共 20 分 应用题 每小题 5 分 共 20 分 设计题 每小题 5 分 共 10 分 知识概要知识概要 第第 1 1 1 1 章章算法与程序算法与程序 1 概念和术语 数据 是能输入到计算机中并能被计算机程序处理的符号的总称 数据元素 是数据的基本单位 它在计算机处理和程序设计中通常作为一个整体进行考虑和处理 一个数 据元素可由若干数据项组成 数据对象 是具有相同特征的数据元素的集合 是数据的一个子集 数据结构 是数据元素的组织形式 或数据元素相互之间存在一种或多种特定关系的集合 数据的逻辑结构 是指数据结构中数据元素之间的逻辑关系 数据的存储结构 是数据的逻辑结构在计算机内存中的存储方式 又称物理结构 数据类型 是一组具有相同性质的操作对象以及该组操作对象上的运算方法的集合 抽象数据类型 是指一个数学模型以及在该模型上定义的一套运算规则的集合 算法 建立在数据结构基础上的 为解决问题而采取的步骤和方法 2 逻辑结构的四种基本形态 根据数据元素之间关系的不同特征 通常有下列四类基本结构 1 集合 结构中的数据元素间除了 同属于一个集合 的关系外 别无其它关系 2 线性结构 结构中的数据元素之间存在一个对一个的关系 3 树型结构 结构中的数据元素之间存在一个对多个的关系 4 图型结构或网状结构 结构中的数据元素之间存在多个对多个的关系 3 数据存储结构的基本组织方式 数据存储结构有顺序和链式两种方式 1 顺序存储结构的特点 要借助数据元素在存储器中的相应位置来体现数据元素相互间的逻辑关系 常 用高级编程语言中的 一维数组 来描述或实现 2 链式存储结构的特点 通过表示数据元素存储地址的指针来表示数据元素之间的逻辑关系 通常用链 表来实现 计算机科学与技术 专升本 数据结构期末考试复习资料 古月编辑整理 祝愿大家考试考出自己理想的成绩 本资料仅供参考 谢谢 2 在顺序存储结构的基础上 又可延伸变化出另外两种存储结构 即索引存储和散列存储 1 索引存储就是在数据文件的基础上增加了一个索引表文件 通过索引表建立索引 可以把一个顺序表 分成几个顺序子表 其目的是在查询时提高查找效率 避免盲目查找 2 散列存储就是通过数据元素与存储地址之间建立起某种映射关系 使每个数据元素与每一个存储地址 之间尽量达到一一对应的目的 这样 查找时同样可大大提高效率 4 数据结构的研究内容 数据结构的核心研究内容包括三个方面 数据的逻辑结构 存储结构以及相应的基本操作运算的定义和实 现 5 算法的五个重要特征 1 有穷性 一个算法必须保证在执行有限步骤之后结束 而不是无限的 2 确定性 算法中每一条指令必须有明确的含义 而不能是模棱两可的 3 可行性 每一个操作步骤都必须在有限的时间内完成 4 输入 一个算法可以有一个或多个输入 也可以没有输入 5 输出 一个算法可以有一个或多个输出 没有输出的算法是没有实际意义的 6 算法的评价标准 1 正确性 2 易读性 3 高效性 4 可维护性 7 算法分析的目的 算法分析主要是指分析算法的效率 算法效率的度量主要从两个方面 算法的运行时间和算法所需的存储 空间 分析的目的是通过考察算法的时间和空间效率 以求改进算法或对不同的算法进行比较 一般情况 下 鉴于运算空间 内存 较为充足 所以把算法的时间复杂度分析作为重点 8 算法的时间复杂度分析 1 算法运算时间的度量的两种方法 事后统计的方法和事前分析估算的方法 2 算法运行时间的分析规则 通常把一个程序的运行时间定义为一个 T n 其中 n 是该程序输入数据的规模 而不是某一个具体的输 入 T n 的单位是不确定的 一般把它看成在一个特定计算机上执行的指令条数 通常记作 T n O f n 其中 f n 表示数据输入规模 常见的算法时间复杂度的形式按性能降序的排列如下 O 1 O n 2 log O n O n n 2 log O 2 n O 3 n O n 2 9 算法空间复杂度的含义 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 算法在计算机存储器内占用的存储 空间主要分为三部分 算法源代码本身占用的存储空间 算法输入输出数据所占用的存储空间 算法运行 过程中临时占用的存储空间 考虑一个算法的空间复杂度时 要综合分析这三个方面的因素 通常记作 S n O f n 其中 n 为问题的规模 或大小 第第 2 2 2 2 3 3 3 3 章章线性表 栈 队列线性表 栈 队列 1 线性表的定义 线性表是 n 个数据元素的有限序列 其中 n n 0 为线性表的长度 计算机科学与技术 专升本 数据结构期末考试复习资料 古月编辑整理 祝愿大家考试考出自己理想的成绩 本资料仅供参考 谢谢 3 线性表中各个元素的类型相同 对于线性表 a1 a2 ai an 而言 数据元素 a1 没有直接前趋 an 没有直接后继 表中的其它元素 ai 2 i n 1 有且仅一个直接前趋 ai 1 和直接后继 ai 1 2 顺序表 顺序表是指线性表的顺序存储结构 即用一组连续的存储单元依次存放线性表的数据元素 在 C 语言中可 用一维数组来表示 在顺序表中 以数据元素在计算机内 物理位置相邻 来表示表中数据元素间的逻辑 关系 顺序表是一种随机存储结构 只要确定了存储顺序表的起始位置 则表中任一元素都可以随机存取 所以 在顺序表中可以方便的进行数据元素的查找及存取 但是在进行插入和删除操作时 将会引起元素的大量 移动 因而效率比较低 并且易产生空间浪费或 上溢 现象 顺序表的操作还应注意元素的存储位置 即数组下标 C 语言中下标从 0 开始 3 链表 链表是线性表的链式存储结构 链表是用一组任意的存储单元 可以是连续的 也可以是不连续的 存放 线性表的数据元素 在链表中 通过指针来表示元素之间的逻辑关系的 不再有逻辑顺序与物理存储顺序 一致的特点 是非顺序存储结构 在单链表中 每个结点由数据域和指针域组成 数据域保存数据元素的 信息 指针域存放其直接后继的存储位置 其类型可描述为 typedefstructNode elemtypedata structNode next LinkList 单链表由头指针唯一确定 为了便于操作 可在链表的第一个结点之前添加一个表头结点 在链表中进行 插入和删除操作只需要修改有关的指针内容 不需要移动元素 因此 链表较顺序表的插入和删除操作更 加方便 高效 为了便于实现各种运算 若无特殊说明 均采用带头结点的链表 4 栈 栈 Stack 是限定仅在表的一端进行插入或删除操作的线性表 通常把允许插入和删除操作的一端称为栈 顶 Top 而另一端称为栈底 Bottom 表为空时称为空栈 在栈上的主要运算是入栈和出栈 栈中元素 如果按 a1 a2 an 的顺序进栈 则出栈顺序为 an an 1 a1 因此 栈又称为 后进先出 Last In First Out 的线性表 简称 LIFO 表 同线性表相似 栈也有顺序栈和链栈两种存储结构 顺序栈易产生 上溢 现象 而链栈不容易产生 另 外 注意对栈的操作只能在栈顶进行 5 队列 队列 Queue 是限定只能在表的一端进行插入 在表的另一端进行删除的线性表 通常把允许插入的一端 称为队尾 rear 允许删除的一端称为队头 front 队列中元素如果按 a1 a2 an 的顺序进队 则出 队的顺序仍为 a1 a2 an 因此 队列又称为 先进先出 First In First Out 的线性表 简称 FIFO 表 队列也有顺序队列和链队列两种存储结构 在顺序队列中 为避免 假满 现象 一般采用循环队列 即 首尾相接 链队列会因为队满而产生 上溢 现象 第第 4 4 4 4 章章串串 计算机科学与技术 专升本 数据结构期末考试复习资料 古月编辑整理 祝愿大家考试考出自己理想的成绩 本资料仅供参考 谢谢 4 1 概念和术语 串 String 或字符串 是由零个或多个字符组成的有限序列 一般记为 s a1a2 an n 0 其中 s 是串的名 用双引号括起来的字符序列是串的值 串的长度 串中字符的个数 n 子串和主串 串中任意个连续的字符组成的子序列称为该串的子串 包含子串的串相应地称为主串 空串 不包含任何字符的串 表示为 空格串 由一个或多个空格字符组成的串 例如 2 串的基本操作 1 用串变量赋值 assign s t 和用串常量赋值 create s ss 2 判等函数 equal s t 3 求长函数 length s 4 连接函数 concat s t 5 求子串函数substring s pos len 6 定位函数 index s t 7 置换函数 replace s t v 8 插入子串 insert s pos t 9 删除子串 delete s pos k 10 串的复制copy s t 3 串的顺序存储结构 顺序串 串的顺序存储方式类似于线性表的顺序存储方式 其存储结构用 C 语言描述为 typedef struct strnode char data maxlen int len SeqString 定义顺序串类型 第第 5 5 5 5 章章数组和广义表数组和广义表 1 多维数组的顺序存储结构 对于多维数组 有两种存储方式 一是以行为主序 或先行后列 的顺序存放 如 BASIC PASCAL C 等程序设计语言中用的是以行为主 的顺序分配 即一行分配完了接着分配下一行 另一种是以列为主序 先列后行 的顺序存放 如 FORTRAN 语言中 用的是以列为主序的分配顺序 即 一列一列地分配 以行为主序的分配规律是 最右边的下标先变化 即最右下标从小到大 循环一遍后 右边第二个下标再 变 从右向左 最后是左下标 以列为主序分配的规律是 最左边的下标先变化 即最左下标从小到 大 循环一遍后 左边第二个下标再变 从左向右 最后是右下标 不论按何种方式存储 只要确定了数组的首地址以及每个数组元素所占用的单元数 就可以将数组元素的 计算机科学与技术 专升本 数据结构期末考试复习资料 古月编辑整理 祝愿大家考试考出自己理想的成绩 本资料仅供参考 谢谢 5 存储地址表示为其下标的线性函数 设有 m n 二维数组 Amn 以 以行为主序 的分配为例 按照元素的 下标确定其地址的计算方法如下 设数组的基址为 LOC a11 每个数组元素占据 L 个地址单元 计算 aij 的物理地址的函数为 LOC aij LOC a11 i 1 n j 1 L 同理 对于三维数组 Amnp 即 m n p 数组 对于数组元素 aijk 其物理地址为 LOC aijk LOC a111 i 1 n p j 1 p k 1 L 注意 在 C 语言中 数组中每一维的下界定 义为 0 则 LOC aij LOC a00 i n j L 2 特殊矩阵压缩存储的意义 在很多科学计算与工程应用中 经常要使用矩阵的概念 矩阵具有与数组相似的性质 如元素数目固定 元素按下标关系有序地排列 所以在编程时可以利用二维数组来存储矩阵 也可以利用程序设计语言中的 各种矩阵运算 在某些情况下 特别是在数值分析中 经常会出现一些阶数很高的矩阵 其中含有许多值相同的元素或零 元素 如三角矩阵 对称矩阵 稀疏矩阵等 从节约存储空间的角度考虑 此时若用二维数组存储会造成 空间的极大浪费 为了节省存储空间 可以对这类矩阵进行压缩存储 即为对多个相同值的元素只分配一 个存储空间 而对零元素可以不分配空间 3 对称矩阵压缩存储的方法 对称矩阵的特点是 在一个 n 阶方阵中 有 aij aji 其中 1 i j n 对称矩阵关于主对角线对称 因此只需存储上三角或下三角部分即可 对于对称矩阵中的任意元素aij 若令I max i j J min i j 则将上面两个式子综合起来得到 k I I 1 2 J 1 给出对称矩阵 A 中任意元素 aij 依据它的下标 i 和 j 就可由上述对应关系式确定其在数组 M 中的位置 K 因此 aij 的地址可由下式计算 Loc aij Loc M K Loc M 0 K L Loc M 0 I I 1 2 J L 其中 L 为每个数据元素所占的存储单元长度 I max i j J min i j K I I 1 2 J 4 三角矩阵压缩存储的方法 形如图的矩阵称为三角矩阵 其中 c 为某个常数 其中下面图 a 为下三角矩阵 主对角线以上均为同一个 常数 b 为上三角矩阵 主对角线以下均为同一个常数 下面讨论它们的压缩存储方法 图 4 1三角矩阵 3 3 3 3cccc 6 6 6 62 2 2 2ccc 4 4 4 48 8 8 81 1 1 1cc 7 7 7 74 4 4 46 6 6 60 0 0 0c 8 8 8 82 2 2 29 9 9 95 5 5 57 7 7 7 a 下三角矩阵 3 3 3 34 4 4 48 8 8 81 1 1 10 0 0 0 c2 2 2 29 9 9 94 4 4 46 6 6 6 cc1 1 1 15 5 5 57 7 7 7 ccc0 0 0 08 8 8 8 cccc7 7 7 7 b 上三角矩阵 计算机科学与技术 专升本 数据结构期末考试复习资料 古月编辑整理 祝愿大家考试考出自己理想的成绩 本资料仅供参考 谢谢 6 三角矩阵中的重复元素 c 可以共享一个存储空间 其余的元素有 n n 1 2 个 因此可压缩存储到向量 sa 0 n n 1 2 中 c 存放在向量的最后一个分量中 排列时以行序为主 aij和 sa k 的对应关系是 下三角矩阵 上三角矩阵 5 稀疏矩阵及其压缩存储的特点 设 m n 矩阵中有 t 个非零元素且 t m n 这样的矩阵称为稀疏矩阵 稀疏矩阵的压缩存储采取如下方法 将非零元素所在的行 列以及它的值构成一个三元组 i j v 然后再按某种规律存储这些三元组 这种方 法可以节约存储空间 6 稀疏矩阵压缩存储的顺序存储方式 以顺序方式组织存储时常用的方法是三元组顺序表 方法是 将三元组按行优先的顺序 同一行中列号从 小到大的规律排列成一个线性表 采用顺序存储方法存储该表 7 稀疏矩阵压缩存储的链式存储方式 稀疏矩阵压缩存储的链式存储方式 即十字链表 当矩阵中非零元素的个数和位置在使用中经常发生变化 时 不宜采用顺序存储结构 可采用十字链表进行存储 其结点结构如图所示 rowcolv Downright 8 广义表 列表 的定义 术语及它与线性表的关系 广义表 Generalized Lists 是 n n 0 个数据元素 a1 a2 ai an 的有序序列 一般记作 Ls a1 a2 ai an 其中 Ls 是广义表的名称 n 是它的长度 每个 ai 1 i n 是 Ls 的成员 它可以是单个元素 也可以 是一个广义表 分别称为广义表 Ls 的单元素和子表 当广义表 Ls 非空时 称第一个元素 a1 为 Ls 的表头 head 称其余元素组成的表 a2 ai an 为 Ls 的表尾 tail 表的深度 表中元素的最深嵌套层数 广义表与线性表的关系 当广义表 Ls 中的元素全部是原子时 广义表即为线性表 因此 可认为线性表是 广义表的特例 广义表是线性表的推广 9 广义表的三个重要性质 1 广义表是一种多层次的数据结构 广义表的元素可以是单元素 也可以是子表 而子表的元素还可以 是子表 2 广义表可以是递归的表 广义表的定义并没有限制元素的递归 即广义表也可以是其自身的子表 例 如表 E 就是一个递归的表 3 广义表可以为其他表所共享 例如 表 A 表 B 表 C 是表 D 的共享子表 在 D 中可以不必列出子 表的值 而用子表的名称来引用 10 广义表的存储结构 k i i 1 2 j 1当 i j n n 1 2 1当 ij 图 4 2十字链表的结点结构 计算机科学与技术 专升本 数据结构期末考试复习资料 古月编辑整理 祝愿大家考试考出自己理想的成绩 本资料仅供参考 谢谢 7 按结点形式的不同 广义表的链式存储结构可分为两种不同的存储方式 一种称为头尾表示法 另一种称 为孩子兄弟表示法 11 广义表的基本运算 广义表有两个重要的基本操作 即取头操作 Head 和取尾操作 Tail 此外 在广义表上可以定义与线性表类似的一些操作 如建立 插入 删除 拆开 连接 复制 遍历等 第第 6 6 6 6 章章树树 从对线性结构的研究过渡到对树形结构的研究 是数据结构课程学习的一次跃变 1 理解树的递归定义 树 Tree 是零个或多个结点的有限集合 结点数为 0 的树称为空树 结点数大于 0 的树称为非空树 在 一棵非空树中 1 有且仅有一个特定的称为根 root 的结点 2 当结点数大于 1 时 除根结点外 其它结点被分成 n n 0 个互不相交的子集 T1 T2 Tn 其中每个子集本身又是一棵树 称之为子树 每一棵子树的根 xi 1 i n 都是根结点 root 的后继 树 T1 T2 Tn 称为根的子树 2 掌握树的基本概念 结点的度 Degree 是指结点拥有的子树的数目 叶子或终端结点 是指度为 0 的结点 非终端结点或分支结点 是指度不为 0 的结点 树的度 是指树内各结点的度的最大值 孩子 Child 和双亲 Parent 某个结点的子树的根称为该结点的孩子 相应的 该结点称为其孩子的双 亲 兄弟 同一个双亲的孩子结点互为兄弟 结点的层次 规定根所在的层次为第 1 层 根的孩子在第二层 依次类推 树的深度或高度 树中结点最大的层数 有序树 是指树中结点的各子树从左至右是有次序的 否则称为无序树 森林 是指 n n 0 棵互不相交的树的集合 3 理解二叉树的递归定义及其与树的区别 二叉树 Binary Tree 是结点的有限集合 这个集合或者为空 或者是由一个根结点和两棵互不相交的分 别称为左子树和右子树的二叉树组成 二叉树中的每个结点至多有两棵子树 且子树有左右之分 次序不 能颠倒 二叉树是一种重要的树型结构 但二叉树不是树的特例 二叉树的 5 种形态分别为 空二叉树 只有根结 点的二叉树 根结点和左子树 根结点和右子树 根结点和左右子树 二叉树与树的区别 二叉树中每个结点的孩子至多不超过两个 而树对结点的孩子数无限制 另外 二叉 树中结点的子树有左右之分 而树的子树没有次序 4 掌握满二叉树和完全二叉树的概念 满二叉树 Full Binary Tree 和完全二叉树 Complete Binary Tree 是两种特殊形态的二叉树 计算机科学与技术 专升本 数据结构期末考试复习资料 古月编辑整理 祝愿大家考试考出自己理想的成绩 本资料仅供参考 谢谢 8 一棵深度为 k 且有 2k 1 个结点的二叉树称为满二叉树 深度为 k 有 n 个结点的二叉树 当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点 一一对应时 称之为完全二叉树 完全二叉树的特点是 1 只允许最后一层有空缺结点且空缺在右边 即叶子结点只能在层次最大的两层上出现 2 对任一结点 如果其右子树的深度为 j 则其左子树的深度必为 j 或 j 1 5 理解二叉树的性质 已知二叉树的深度 h 可求出该二叉树拥有的最多结点数 已知结点数 n 可求出对应树或二叉树的最大和最 小高度 性质 1 在二叉树的第 i 层上最多有 2i 1 个结点 i 1 性质 2 深度为 k 的二叉树最多有 2k 1 个结点 k 1 性质 3 对任何一棵二叉树 T 如果其终端结点数为 n0 度为 2 的结点数为 n2 则 n0 n2 1 性质 4 具有 n 个结点的完全二叉树的深度为 n 2 log 1 性质 5 如果对一棵有 n 个结点的完全二叉树 其深度为 n 2 log 1 其中 k 为不大于 n 2 log 的最大整数 的结点按层序编号 编号方法为从第 1 层到最后一层 每一层从左到右 则对任一结点i 1 i n 有 1 如果 i 1 则结点 i 是二叉树的根 无双亲 如果 i 1 则其双亲是第 2i 个结点 2 如果 2i n 则结点 i 无左孩子 即结点 i 为叶子结点 否则其左孩子是第 2i 个结点 3 如果 2i 1 n 则结点 i 无右孩子 否则其右孩子是第 2i 1 个结点 6 二叉树中结点的编号规则和对应的顺序存储结构 顺序存储二叉树的具体方法是 在一棵具有 n 个结点的完全二叉树中 从根结点开始编号为 1 自上到下 每层自左至右地给所有结点编号 这样可以得到一个反映整个二叉树结构的线性序列 然后将完全二叉树 上编号为 i 的结点依次存储在一维数组 a l n 中下标为 i 的元素中 7 二叉树的链接存储结构及存储结点的类型定义 链式存储是使用链表来存储二叉树中的数据元素 链表中的一个结点相应地存储二叉树中的一个结点 常 见的二叉树的链式存储结构有两种 二叉链表和三叉链表 二叉链表是指链表中的每个结点包含两个指针域和一个数据域 分别用来存储指向二叉树中结点的左右孩 子的指针及结点信息 三叉链表是指链表中的每个结点包含三个指针域和一个数据域 相比二叉链表多出的一个指针域则用来指 向该结点的双亲结点 不论哪种链表 头指针都指向二叉树的根结点 在含有 n 个结点的二叉链表中 共有 2n 个指针域 但实际有效的指针数等于二叉树中的分支数 即 n 1 所以共存在 n 1 个空的指针域 8 掌握二叉树的先序 中序 后序遍历的递归算法和非递归算法 9 能够根据先序 中序 后序 中序的遍历序列确定一棵二叉树 并理解为什么先序 后序不能唯一确定一 棵二叉树 10 掌握线索二叉树的定义及存储结构 会画出先序 中序和后序线索二叉树或相应的线索链表 12 掌握遍历中序线索二叉树的规则及算法 计算机科学与技术 专升本 数据结构期末考试复习资料 古月编辑整理 祝愿大家考试考出自己理想的成绩 本资料仅供参考 谢谢 9 13 掌握树的三种存储结构 双亲表示法 孩子表示法 孩子 兄弟表示法 掌握这三种存储方法的特点 并且能够画出指定树的存储结构图 14 理解二叉树与树或森林转换的目的 掌握树和二叉树之间的相互转换 掌握森林和二叉树之间的相互 转换 15 掌握树的先根 后根和按层遍历的过程 16 掌握森林的先根 后根遍历 17 掌握路径 路径长度 结点的权 结点的带权路径长度 树的带权路径长度的概念 路径 若在树中存在着一个结点序列 k1 k2 kj 使得 ki 是 ki 1 的双亲 1 i j 则此结点序列称 为从 k1 到 kj 的路径 路径长度 从 k1 到 kj 所经过的分支数称为这两点之间的路径长度 它等于路径上的结点数减 1 结点的权 在许多应用中 常常将树中的某个结点赋上一个具有某种意义的数值 这个和某个结点相关的 数值称为该结点的权或权值 结点的带权路径长度 是指从树根到该结点之间的路径长度与结点的权值的乘积 树的带权路径长度 是指树中所有叶子结点的带权路径长度之和 通常记为 WPL n i iiL W 1 其中 n 表示 叶子结点的个数 Wi 表示叶子结点 Ki 的权值 Li 表示根结点到 Ki 的路径长度 18 掌握哈夫曼树的概念 哈夫曼树 Huffman Tree 又称为最优二叉树 它是 n 个带权的叶子结点构成的所有二叉树中带权路径长 度 WPL 最小的二叉树 19 掌握哈夫曼树的构造方法 即根据一组给定的权值构造相应的哈夫曼树 20 理解哈夫曼编码的含义 能够根据实际问题构造哈夫曼编码 第第 7 7 7 7 章章图图 1 基本概念及术语 图 G 由两个集合 V G 和 E G 所组成 记作 G V E 其中 V G 是图中顶点的非空有限集合 E G 是 图中边的有限集合 有向图 Digraph 如果图中每条边都是有向的即每条边在图示时都用箭头表示方向 则称此图为有向图 有向图的边也称为弧 如图 6 1 中 G1 是有向图 它由 V G1 和 E G1 组成 V G1 V1 V2 V3 G1 无向图 Undigraph 如果图中每条边都是顶点无序对 则称为无向图 无向边用圆括号括起的两个相关顶 点来表示 在无向图中 V1 V2 和 V2 V1 是表示同一条边 如图 6 1 所示 G2 和 G3 都是无向图 其中 图 6 1 图示例 1 2 3 G1 4 3 2 1 G2 76 54 32 1 G3 计算机科学与技术 专升本 数据结构期末考试复习资料 古月编辑整理 祝愿大家考试考出自己理想的成绩 本资料仅供参考 谢谢 10 V G2 V1 V2 V3 V4 E G2 V1 V2 V1 V3 V2 V3 V2 V4 V3 V4 V G3 V1 V2 V3 V4 V5 V6 V7 E G3 V1 V2 V1 V3 V2 V4 V2 V5 V3 V6 V3 V7 无向完全图和有向完全图 若一个无向图有 n 个顶点 而每一个顶点与其他 n 1 个顶点之间都有边 这样 的图称之为无向完全图 即共有 n n 1 2 条边 类似地 在有 n 个顶点的有向图中 若有 n n 1 条弧 即任意两顶点之间都有双向相反的两条弧连接 则称此图为有向完全图 子图 设有两个图 A 和 B 且满足条件 V B A 且 E B E A 则称 B 是 A 的子图 路 径 在 图 中 从 顶 点 p 到 q 的 一 条 路 径是 顶 点 序 列 Vp Vi1 Vi2 Vin Vq 且 Vp Vi1 Vi1 Vi2 Vin Vq 是 E G 中的边 路径上边的数目称之为该路径长度 对于有向图 其路径 也是有向的 路径由弧组成 简单路径 如果一条路径上所有顶点除其起始点和终止点外彼此都是不同的 则称该路径是简单路径 回路和简单回路 在一条路径中 如果其起始点和终止点是同 顶点 则称其为回路 简单路径相应的回 路称为简单回路 连通图和强连通图 在无向图 G 中 若从 Vi 到 Vj 有路径 则称 Vi 和 Vj 是连通的 若 G 中任意两顶点都 是连通的 则称 G 是连通图 对于有向图而言 若 G 中每一对不同顶点 Vi 和 Vj 之间都有 Vi 到 Vj 和 Vj 到 Vi 的路径 则称 G 为强连通图 度 入度和出度 若 Vi Vj 是 E G 中的一条边 则称顶点 Vi 和 Vj 是邻接的 并称边 Vi Vj 依附于顶点 Vi 和 Vj 所谓顶点的度 就是依附于该顶点的边数 在有向图中 以某顶点为头 即终止于该顶点的弧的 数目称为该顶点的入度 以某顶点为尾 即起始于该顶点的弧的数目称为该顶点的出度 该顶点的入度和 出度之和称为该顶点的度 若图 G 中每一条边都有一个对应的数 则称 G 为网 这些边上的数字称为权 它可以表示两顶点之间的距 离或所花费的代价 类似地 边上带权的有向图称为有向网 如在图 6 2 中 G4 是一个网 而图 G5 则是一 个有向网 2 图的存储结构 常用的存储结构有邻接矩阵和邻接表 1 邻接矩阵表示法 设 G V E 是有 n n 1 个顶点的图 则 G 的邻接矩阵是按如下定义的 n 阶方阵 20 30 10 34 20 21 2 70 20 1 3 10 图 6 2 网 G4网G5有向网 0其它 1当 i Vj E 或 E 时 cost i j 计算机科学与技术 专升本 数据结构期末考试复习资料 古月编辑整理 祝愿大家考试考出自己理想的成绩 本资料仅供参考 谢谢 11 例如 图 6 1 中 G1 2 的邻接矩阵分别表示为 A1 A2 矩阵的行列号对应于图 6 1 中结点的序号 由邻接矩阵的定义可知 无向图的邻接矩阵必定是对称阵 有向图的邻接矩阵不一定是对称的 根据邻接矩阵 很容易判定任意两个顶点之间是否有边相连 求各顶点的度也是非常容易的 对于无向图 顶点 Vi 的度就是邻接矩阵中第 i 行 或第 j 列 上非零元的个数 即 n i i jitd 1 cos 对于有向图 第 i 行中非零元的个数为顶点 Vi 的出度 而第 i 列上的非零元个数为顶点 Vi 的入度 2 邻接表表示法 图的邻接链表存储结构是一种顺序分配和链式分配相结合的存储结构括两个部分 一部分是向量 另一部 分是链表 邻接链表中的表头部分是向量 用来存储 n 个表头结点 向量的下标指示顶点的序号 例如 对于图 6 1 中 G1 和 G2 其邻接链表如图 6 3 所示 在无向图的邻接表中顶点 vi 的度就是第 i 个链表中结点的个数 在有向图中 第 i 个链表的结点数仅是 vi 的出度 求 vi 的入度 必须查遍 n 个链表才能得出 3 图的遍历 给定一个无向连通图 G G V E 当从 V G 中的任一顶点 v 出发 去访问图中其余顶点 使每个顶点 仅被访问一次 这个过程叫做图的遍历 通常有两种遍历图的方法 种是深度优先搜索法 另 种为广 度优先搜索法 1 深度优先搜索 设有无向连通图 G V E 从 V G 中任一顶点 v 出发深度优先搜索遍历图的步骤是 先访问指定顶点 V1 然后访问与该顶点 V1 相邻的顶点 V2 再从 V2 出发 访问与 V2 相邻且未被访问过的任意顶点 V3 然后 从顶点 V3 出发 重复上述过程 直到一个所有邻接点都被访问过的顶点为止 然后回溯到此顶点的直接 前趋 从这里出发再继续访问 显然搜索是一个递归过程 2 广度优先搜索 设无向图 G V E 是连通的 从 V G 中的任一顶点 V1 出发 广度优先搜索遍历图的步骤是 首先访问指 定的起始顶点 V1 从 V1 出发 依次访问与 V1 相邻的未被访问过的顶点 W1 W2 W3 Wt 然后依 a G1 的邻接表 1 2 3 3 3 2 b G2 的邻接表 图 6 3 邻接表 3 1 2 3 4 1 2 4 4 3 3 2 2 1 0110 1011 1101 0110 A2 A1 011 001 000 计算机科学与技术 专升本 数据结构期末考试复习资料 古月编辑整理 祝愿大家考试考出自己理想的成绩 本资料仅供参考 谢谢 12 次从 W1 W2 W3 Wt 出发 重复上述访问过程 直到所有顶点都被访问过为止 在广度优先搜索过 程中 访问某个顶点之后 要将这个顶点保存起来 以备后面访问这个顶点的邻接点 由搜索这个过程可 知 保存的信息应该组织成一个队列 4 生成树和最小生成树 无向图的连通分量 无向图的连通分量是图的一个极大连通子图 如图 6 7 a 有两个连通分量 分别为图 6 7 b 和 c 而图 6 7 d 不是图 6 7 a 的连通分量 因为它虽是图 6 7 a 的连通子图 却不是极大连能子图 只有加上顶点 3 后 才构成极大连通子图 无向连通图只有一个连通分量 即是图本身 最小生成树 设图 G 是一个连通网 G 上的一棵各边权值之和最小的带权生成树 称为 G 的最小生成树 构造最小生成树的算法有 普里姆算法和克鲁斯卡尔算法 5 普里姆 Prim 算法 假设 N V E 是连通图 TE 是 N 上最小生成树中边的集合 算法从 U u0 u0 TE 开始 重 复执行下述操作 在所有 u U v V U 的边 u v 中找一条代价最小的边 u0 v0 并入集合 TE 同时 v0 并入U 直到 U V 为止 此时 TE 中必有 n 1 条边 则 T V TE 为 N 的最小生成树 6 鲁斯卡尔 Kruskal 算法 克鲁斯卡尔算法是从另一途径求网的最小生成树 假设连通网 N V E 则令最小生成树的初始状态为 只有 n 个顶点而无边的非连通图T V 图中每个顶点自成一个连通分量 在 E 中选择代价最小的边 若该边依附的顶点落在 T 中不同的连通分量上 则将此边加入到 T 中 否则舍去此边而选择下一条代价最 小的边 依次类推 直至 T 中所有顶点都在同一连通分量上为止 7 拓扑排序 1 AOV 网 在有向图中以顶点表示 活动 用有向边表示 活动 之间的优先关系 这样的有向图称 为以顶点表示 活动 的网 Activity On Vertex Network 简称 AOV 网 2 拓扑排序的方法 对于一个 AOV 网 构造其所有顶点的线性序列 使此序列不仅保持网中各顶点间原有的先后次序 而量 使原来没有先后次序关系的顶点之间也建立起人为的先后关系 这样的序列称为拓扑有序序列 构造 AOV 网的拓扑有序序列的运算称为拓扑排序 某个 AOV 网 如果它的拓扑有序序列被构造成功 则该网中不存在有向回路 其各子工程可按拓扑有序 序列的次序进行安排 一个 AOV 网的拓扑有序序列并不是唯一的 b V5 V4 a d c a 无向图 b c 是图 a 的两个连通分量 d 非连通分量 图 6 7 无向图的连通分量 V3 V2V1 V0 V2V1 V0 V3 V2V1 V0 V5 V4 计算机科学与技术 专升本 数据结构期末考试复习资料 古月编辑整理 祝愿大家考试考出自己理想的成绩 本资料仅供参考 谢谢 13 对 AOV 网进行拓扑排序的步骤是 第一步 在网中选择一个没有前趋的顶点且输出之 第二步 在网中删去该顶点 并且删去从该顶点发出的全部有向边 第三步 重复上述两步 直到网中不存在没有前趋的顶点为止 这样操作结果有两种 一种是网中全部顶点均被输出 说明网中不存在有向回路 另一种是网中顶点未被 全部输出 剩余的顶点均有前趋顶点 说明网中存在有向回路 8 掌握关键路径的概念及确定关键路径的算法 若在带权有向图 G 中 以顶点表示事件 边表示活动 权表示活动持续的时间 则此带权有向图称为用边 表示活动的网 Activity On Edge net work 简称 AOE 网 由于整个工程只有一个开始点和一个完成点 故 在正常情况下 在这种工程图中只有一个入度为 0 的顶点 称为源点 和一个出度为 0 的顶点 称为汇点 从源点到汇点之间的长度最长的路径称为关键路径 9 掌握最短路径的概念及确定最短路径的算法 所谓的最短路径是指对所经过的边的值之和为最小的路径 本章给出两个算法 一个是求从某个源点到其 他顶点的最短路径 另一个是求每对顶点间的最短路径 确定单源最短路径可采用迪杰斯特拉 ijkstra 算法 确定所有顶点之间的最短路径有两种方法 一种是每次以一个顶点为源点 重复执行迪杰斯特拉算法 n 次 时间复杂度为 O n3 另一种是弗洛伊德 Floyd 算法 时间复杂度也是 O n3 但形式更简单 第第 9 9 9 9 章章查找查找 1 查找的基本概念 查找也称为检索 进行查找运算的数据元素通常是同一数据类型的数据元素或记录 由它们构成的集合又 称为查找表 查找表分为静态查找表和动态查找表 静态查找表 仅对查找表进行查找操作 即查找关键字等于给定值的数据元素是否在查找表中或检索其属 性 查找前后不能改变表 动态查找表 对查找表除进行查找操作外 可能还要向表中插入数据元素 或删除表中数据元素的表 关键字 主关键字和次关键字 查找表中区别不同记录的数据项的数据元素称为关键字 若此关键字可以 惟一的标识一个记录 则称此关键字为主关键字 Primary Key 反之 称用以识别若干记录的关键字为次 关键字 Secondary Key 查找 Searching 是根据给定的某个值 在查找表中确定一个其关键字等于给定值的记录或数据元素 若 表中存在一个这样的记录 则称查找成功 反之 查找不成功 注意 不同的查找方法 不同的查找表存储结构 具有不同的查找效率 平均查找长度 即在查找成功情况下的平均比较次数 平均查找长度的计算公式为 ASL 其中 n 表示查找表的长度 即表中所包含的数据元素的个数 Pi 是查找第 i 个元素的概率 一般认为查找 每个元素的概率相等 Ci 是查找第 i 个元素时 同给定值 K 的比较次数 在查找每个元素等概率的情况下 则平均查找长度的计算公式变为 n i PiCi 1 计算机科学与技术 专升本 数据结构期末考试复习资料 古月编辑整理 祝愿大家考试考出自己理想的成绩 本资料仅供参考 谢谢 14 ASL 其对应的时间复杂度为 O n 2 线性表查找 线性表查找是指进行查找运算的查找表所采用的存储结构是线性的 1 顺序查找 最简单的查找技术是顺序查找 Sequential Search 这种查找技术适用于基本线性表结构文件 如顺序存 储或链式存储的基本线性表结构文件 顺序查找的算法思想是 从表的末端开始 依次将记录的关键字与给定值 K 进行比较 若出现相等情况 则查找成功 若直至第一个记录仍未发现相等 则查找失败 在顺序存储和链式存储两种方法中 由于每个元素在查找表中位置不同 查找成功时的比较次数也不同 在不等概率的条件下 为了减少整个算法查找的次数 可以把查找概率大的数据元素放在查找表的靠前的 位置 2 折半查找 折半查找 Binary Search 也叫二分查找 算法思想为 在有序表中 取中间元素作为比较对象 若给定 值与中间元素的关键字相等 则查找成功 若给定值小于中间元素的关键字 则在中间元素的左半区继续 查找 若给定值大于中间元素的关键字 则在中间元素的右半区继续查找 不断重复上述查找过程 直到 查找成功 或所查找的区域无数据元素 则查找失败 从折半查找过程看 可用二叉树来描述 称这个描述查找过程的二叉树为判定树 以树高为 k 的满二叉树 n 2k 1 为例 假设表中每个元素的查找是等概率的 即 Pi 1 n 则树的第 i 层 有 2i 1 个结点 因此 折半查找的平均查找长度为 3 树表查找 1 二叉排序树 二叉排序树 Binary Sort Tree 又称二叉查找树 Binary Search Tree 它或者是一棵空树 或者是一棵具 有如下性质的非空二叉树 若它的左子树非空 则左子树上的所有结点的关键字的值均小于根结点的值 若它的右子树非空 则右子树上的所有结点的关键字的值均大于根结点的值 左右子树本身又各是一棵二叉排序树 二叉排序树的查找过程为 i 若查找树为空 查找失败 ii 查找树非空 将给定值 k 与查找树的根结点关键字比较 iii 若相等 查找成功 结束查找过程 否则 继续查找 iv 当给定值 k 小于根结点关键字 查找将在左子树上继续进行 转 i 1 1 log 2 1 nPiCiASL n i 2 1 2 1 1 121 1 1 11 11 nnn n nnn n in n Ci n n i n i 计算机科学与技术 专升本 数据结构期末考试复习资料 古月编辑整理 祝愿大家考试考出自己理想的成绩 本资料仅供参考 谢谢 15 v 当给定值 k 大于根结点关键字 查找将在右子树上继续进行 转 i 算法实现 以二叉链表作为二叉排序树的存储结构来实现 二叉排序树的运算 i 二叉排序树的创建 ii 二叉排序树的插入算法 iii 二叉排序树的删除运算 算法分析 在二叉排序树上查找关键字等于给定值 k 的过程 正好经过了一条从树根到该结点的路径 与关键字 k 比 较的次数试该路径的长度加 1 因此 查找的次数不会超过树的深度 由于二叉排序树的形状取决于输入 的关键字序列 因此 对于同一组关键字 如果输入顺序不一样 所得到的二叉排序树也不一样 最好的 情况是二叉排序树的形态和折半查找的判定树相同 2 平衡二叉树 平衡二叉树的定义 平衡二叉树 Balanced Binary Tree 或 Height Balanced Tree 又称 AVL 树 它或者是一棵空树 或者是具 有下列性质的二叉排序树 它的左子树和右子树都是平衡二叉树 且左子树和右子树高度之差的绝对值不 超过 1 平衡二叉树的调整 i 左单旋转 又称 RR 型 ii 右单旋转 又称 LL 型 iii 左后右双向旋转 又称 LR 型 iv 先右后左双向旋转 又称 RL 型 平衡二叉树的算法 4 哈希表查找 1 哈希表的定义 把关键字与存储位置之间的对应关系 称之为哈希函数 每个关键字通过哈希函数得到一个存储位置 这 个存储位置称为哈希地址 一组关键字通过哈希函数得到一段有限的连续地址 这段地址是所有关键字的 一个映像 称为哈希表 哈希表又称为散列表或杂凑表 2 哈希函数的构造 常用的构造哈希函数的方法有 直接定址法 数字分析法 平方取中法 折叠法 除留余数法 随机数法 实际工作中需视不同的情况采用不同的哈希函数 通常 考虑的因素有 计算哈希函数所需时间 包括硬件指令的因素 关键字的长度 哈希表的大小 关键字的分布情况 记录的查找频率 3 冲突处理方法 假设哈希表的地址集为 0 n 1 冲突是指由关键字得到的哈希地址为 j 0 j n 1 的位置上已存有记 录 则 处理冲突 就是为该关键字的记录找到另一个 空 的哈希地址 通常的处理冲突的方法有下列 几种 开放定址法 线性探测法和二次探测法 再哈希法 拉链法 建立一个公共溢出区 4 查找及分析 计算机科学与技术 专升本 数据结构期末考试复习资料 古月编辑整理 祝愿大家考试考出自己理想的成绩 本资料仅供参考 谢谢 16 在哈希表上进行查找的过程和哈希造表的过程基本一致 给定值 k 根据造表时设定的哈希函数求得哈希 地址 若表中此位置上没有记录 则查找不成功 否则比较关键字 若和给定值相等 则查找成功 否则 根据造表时设定的处理冲突的方法找 下一个地址 直至哈希表中某个位置为 空 或者表中所填记录的 关键字等于给定值时为止 在一般情况下 处理冲突方法相同的哈希表 其平均查找长度依赖于哈希表的装填因子 哈希表的装填因 子定义为 表中填入的记录数 哈希表的长度 表示哈希表的装满程度 越小 发生冲突的可能性就越小 平均查找长度也小 但空间的浪费加大 反 之 越大 表中已填入的记录越多 再填记录时 发生冲突的可能性就越大 则查找时 给定值需与之进 行比较的关键字的个数也就越多 第第 10101010章章内部排序内部排序 1 基本概念 排序 是计算机程序设计中一种重要操作 其功能是对一个数据元素集合或序列重新排列成一个按数据元 素某个项值有序的序列 作为排序依据的数据项称为关键字 排序的确切定义如下 输入 n 个记录 R1 R2 Rn 其相应的关键字分别为 K1 K2 Kn 输出 Ri1 Ri2 Rin 使得 Ki1 Ki2 Kin 或 Ki1 Ki2 Kin 文件 文件是由一组记录组成的 记录则是由若干个数据项 或域 组成 其中有一项可用来标识一个记 录 称为关键字项 该数据项的值称为关键字 Key 稳定性 若对任意的数据元素序列使用某个排序方法 对它按关键字进行排序 若相同关键字元素间的位 置关系排序前与排序后保持一致 称此排序方法是稳定的 而不能保持一致的排序方法则称为不稳定的 排序的分类 1 按是否涉及数据的内 外存交换分类 在排序过程中 若整个文件都是放在内存中处理 排序时不涉及数据的内 外存交换 则称之为内部排序 简称内排序 适合不太大的元素序列 反之 若 排序过程中要进行数据的内 外存交换 则称之为外部排序 适合大元