数据结构总复习PPT.ppt

总复习 一 单选题 共15题 二 多选题 共5题 三 判断题 共5题 四 简答题 共5题 五 算法填空 共2题 六 算法设计 共1 2题 考试题型 1 2 2数据结构中结构的相关概念 反映数据元素的逻辑关系 数据的逻辑结构在计算机存储器中的实现 1 逻辑结构 线性结构 线性结构的特点表现为 数据元素之间存在前后次序 直接前驱元素 直接后继元素 线性结构中数据元素之间的正逆关系都是 一对一 的 线性结构又可再分为 线性表 堆栈 队列等 2 逻辑结构 非线性结构 非线性结构特点 数据元素不一定存在确定的前后次序 甚至是无序的数据元素之间存在从属或互为从属或离散关系的关系 数据元素之间存在着 一对多 或 多对多 的关系非线性结构又可再分为树形 图状或网状结构 纯集合结构 一对多 图或网状结构 数据元素之间存在着 多对多 的关系 邻接数据元素相互之间不存在从属关系或理解为相互从属 算法和程序 算法及五大特征 算法与程序关系 程序性能和算法效率 程序性能 算法的好坏标准 空间复杂性的组成 时间复杂性取决因素 第二章线性表 2 2 1线性表顺序存储 用一组地址连续的存储单元依次存储线性表的元素 把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构 线性表的顺序表示又称为顺序存储结构或顺序映像 顺序存储定义 顺序存储方法 简言之 逻辑上相邻的元素 物理上也相邻 可以利用数组V n 来实现 注意 在C语言中数组的下标是从0开始 即 V n 的有效范围是从V 0 V n 1 例1 设有一维数组 下标的范围是 到 每个数组元素用相邻的 个字节存储 存储器按字节编址 设存储数组元素 的第一个字节的地址是 则 的第一个字节的地址是多少 例2 线性表具有两种存储方式 即顺序方式和链接方式 现有一个具有五个元素的线性表L 23 17 47 05 31 若它以链接方式存储在下列100 119号地址空间中 每个结点由数据 占2个字节 和指针 占2个字节 组成 如下图所示 其中指针X Y Z的值分别为多少 该线性表的首结点起始地址为多少 末结点的起始地址为多少 100 119 答 X Y Z 首址 末址 1 104 108 116 112 116 NULL 0 100 108 112 其结点在存储器中的位置是随意的 即逻辑上相邻的数据元素在物理上不一定相邻 如何实现 通过指针来实现 让每个存储结点都包含两部分 数据域和指针域 数据域 存储元素数值数据 指针域 存储直接后继或者直接前驱的存储位置 设计思想 牺牲空间效率换取时间效率 简单链表存储结构及操作 例1 请画出26个英文字母表的链式存储结构 该字母表的逻辑结构为 a b y z 该字母表在内存中链式存放的样式举例如下 讨论1 每个存储结点都包含两部分 数据域和 讨论2 在单链表中 除了首结点外 任一结点的存储位置由指示 其直接前驱结点的链域的值 指针域 链域 一个线性表的逻辑结构为 ZHAO QIAN SUN LI ZHOU WU ZHENG WANG 其存储结构用单链表表示如下 请问其表头指针成员first值是多少 答 表头的first是指向链表中第一个结点的指针 因此关键是要寻找第一个结点的地址 31 例2 在链表中插入一个元素x的示意图如下 链表插入的核心语句 Step1 q link c link Step2 c link q c link q link 思考 Step1和2能互换么 x结点的生成方式 q newChainNode q data x q link 7 简单链表L中第k个数据元素之后插入元素x StatusInsert ChainList L intk EType 如果插入的是空链表current NULL或作为第一个元素结点插入 ChainNode q newChainNode q data x if k 插入在current之后q link current link current link q else k 0 作为第一个元素结点插入q link L first L first q returnOK 在链表中删除某元素b的示意图如下 删除动作的核心语句 要借助辅助指针变量p p q link 首先保存b的指针 靠它才能找到c q link p link 将a c两结点相连 淘汰b结点 deletep 彻底释放b结点空间 q link q link link p 8 从简单链表中删除一个数据元素 StatusDelete ChainList L intk 在线性表L中删除第k个数据元素 如果不存在第k个元素返回出错状态码if kfirst returnERROR ChainNode current L first if k 1 L first current link else ChainNode q L first for intindex 1 indexlink q指向第k 1个结点if q q link returnERROR current q link current指向第k个结点q link current link deletecurrent 释放被删除结点current的空间returnOK 2 8 1结点移至表首运算对链表中被查找过的结点先从链表中删除 删除后不释放 再插入到链表的表首 或指定位置 2 q link current link 1 current q link 3 current link L first 4 L first current if kfirst returnERROR ChainNode current L first if k 1 returnOK 是链表中第一个结点 直接返回else ChainNode q L first for intindex 1 indexlink if q q link returnERROR current q link current指向第k个结点q link current link current link L first L first current 表头指针指向被删除结点currentreturnOK MoveFirst L k 2 8 2链表的逆向运算 1 首先从链表的表头开始将指针向表尾方向推进 可以设三个指针 分别指向连续的三个结点 2 对中间一个结点的链接域的值进行修改 使其指向它的前驱结点 再将三个指针再向尾部推进一个结点位置 重复此过程 直到最前面的指针指向空 e0 e1 e2 e3 en 1 L current p current e4 p current link L first current link L first current p p p link 简单链表L的逆向的算法 Invert StatusInvert ChainList 本章小结 线性结构 包括表 栈 队 数组 的定义和特点 仅一个首 尾结点 其余元素仅一个直接前驱和一个直接后继 2 线性表 逻辑结构 一对一 或 1 1 存储结构 顺序 链式运算 修改 插入 删除 查找和排序另述 3 顺序存储 特征 逻辑上相邻 物理上也相邻 优点 随机查找修改快O 1 缺点 插入 删除慢O n 改进方案 链表存储结构 第三章栈和队列 堆栈的定义 3 1 1堆栈的逻辑结构堆栈 也简称栈 是一个线性表 其数据元素只能从这个有序集合的同一端插入或删除 这一端称为堆栈的栈顶 top 而另一端称为堆栈的栈底 bottom 特点 先进后出 FILO 或后进先出 LIFO 判断堆栈S是否为空S top 1判断堆栈S是否为满S top S MaxSize 1 Q1 堆栈是什么 它与一般线性表有什么不同 堆栈是一种特殊的线性表 它只能在表的一端 即栈顶 进行插入和删除运算 与一般线性表的区别 仅在于运算规则不同 一般线性表堆栈逻辑结构 1 1逻辑结构 1 1存储结构 顺序表 链表存储结构 顺序栈 链栈运算规则 随机存取运算规则 后进先出 LIFO 进 插入 压入 Push an 1 出 删除 弹出 Pop an 例2一个栈的输入序列为1 2 3 若在入栈的过程中允许出栈 则可能得到的出栈序列是什么 答 可以通过穷举所有可能性来求解 1入1出 2入2出 3入3出 即123 1入1出 2 3入 3 2出 即132 1 2入 2出 3入3出 即231 1 2入 2 1出 3入3出 即213 1 2 3入 3 2 1出 即321 合计有5种可能性 不存在输出序列3 1 2 讨论 有无通用的判别原则 有 若输入序列是 Pj Pk Pi Pj Pk Pi 一定不存在这样的输出序列 Pi Pj Pk 即对于输入序列1 2 3 不存在输出序列3 1 2 问 S4 例3 一个栈的输入序列是12345 若在入栈的过程中允许出栈 则栈的输出序列43512可能实现吗 12345的输出呢 答 43512不可能实现 主要是其中的12顺序不能实现 12345的输出可以实现 每压入一数便立即弹出即可 例4 设依次进入一个栈的元素序列为c a b d 则可得到出栈的元素序列是 a b c d c d a b b c d a a c d b A D 可以 B C 不行 答 后缀表达式求值步骤 1 读入表达式一个字符2 若是操作数 压入栈 转43 若是运算符 从栈中弹出2个数 将运算结果再压入栈4 若表达式输入完毕 栈顶即表达式值 若表达式未输入完 转1 4 4 3 7 3 5 Top 1 例计算4 3 5 后缀表达式 435 4 15 19 Top 0 Top 1 Top 2 Top 1 Top 0 3 6队列的定义 与线性表相同 仍为一对一关系 顺序队或链队 以循环顺序队更常见 只能在队首和队尾运算 且访问结点时依照先进先出 FIFO 的原则 关键是掌握入队和出队操作 具体实现依顺序队或链队的不同而不同 只能在表的一端进行插入运算 在表的另一端进行删除运算的线性表 基本操作 入队或出队 建空队列 判队空或队满等操作 尾部插入 首部删除 队列定义 判断队列Q是否为空Q front Q rear判断队列Q是否为满Q front Q rear 1 Q MaxSize 1 队空条件 front rear 初始化时 front rear 队满条件 front rear 1 N N maxsize 1 队列长度 即数据元素个数 L N rear front N 循环队列总结 人为浪费一个单元 即front和rear二者之一指向实元素 另一个指向空闲元素 问3 在具有n个单元的循环队列中 队满时共有多少个元素 n 1个 6 问1 左图中队列maxsizeN 问2 左图中队列长度L 5 r f n f r n n r f n r f n 要分析4种公式哪种最合理 当r f时 A 合理 当r f时 C 合理 答 综合2种情况 以 D 的表达最为合理 例2 在一个循环队列中 若约定队首指针指向队首元素的前一个位置 那么 从循环队列中删除一个元素时 其操作是先 移动队首指针 取出元素 后 例1 数组 n 用来表示一个循环队列 f为当前队列头元素的前一位置 r为队尾元素的位置 假定队列中元素的个数小于n 计算队列中元素的公式为 例3 一循环队列如下图所示 若先删除4个元素 接着再插入4个元素 请问队头和队尾指针分别指向哪个位置 解 由图可知 队头和队尾指针的初态分别为front 0和rear 5 删除4个元素后f 4 再插入4个元素后 r 5 4 6 3 rear 3 本章小结 线性表 栈 队的异同点 相同点 逻辑结构相同 都是线性的 都可以用顺序存储或链表存储 栈和队列是两种特殊的线性表 即受限的线性表 只是对插入 删除运算加以限制 运算规则不同 线性表为随机存取 而栈是只允许在一端进行插入和删除运算 因而是后进先出表LIFO 队列是只允许在一端进行插入 另一端进行删除运算 因而是先进先出表FIFO 用途不同 线性表比较通用 堆栈用于函数调用 递归和简化设计等 队列用于离散事件模拟 OS作业调度和简化设计等 不同点 第3章结束 第5章树和二叉树 Tree BinaryTree 树的定义 树的术语 结点的度树的度终端结点孩子和双亲结点层次树的深度森林 3 满二叉树的定义 若二叉树中所有分枝结点的度数都为2 且叶子结点都在同一层上 则称这类二叉树为满二叉树 5 完全二叉树的定义若二叉树中所有分枝结点的度数要就为2 要就为0 称这类二叉树为完全二叉树 4 顺序二叉树的定义 对满二叉树从上至下 从左至右地从1开始编号 结果是每个结点都可以与满二叉树中编号为1至n的结点一一对应 6 退化二叉树的定义 如果一棵非空的二叉树只有一个叶子 且其余结点均只有一个孩子 由 个结点构成的树有几种形态 由 个结点构成的二叉树呢 答 树有2种形态 二叉树则有5种形态 备注 一棵树至少包含一个树结点 不存在不含树结点的树 树中结点存在着层次关系 但同一层上的树结点之间是无序的 一棵树的每个结点都是某个子树的根 二叉树的定义与树的定义的区别二叉树存在着空树 但树不能为空 二叉树中的每一个结点只可能有0个 1个或2个孩子 也就是说 二叉树不存在度大于2的结点 而树中的每个结点可以有多个子树 二叉树的子树有左右之分 两者不能颠倒 但树的子树一般是无序的 结论 二叉树不是特殊的树 5 2 2二叉树的性质 1 性质1 在二叉树的第i层上最多有2i 1个结点 i 1 性质2 深度为h的二叉树至多有2h 1个结点 性质3 包括n n 0 个元素的二叉树的边数为n 1 性质4 对于任何一棵二叉树 若其终端结点数为n0 其度为2的结点数为n2 则有 n0 n2 1 5 性质5 若一棵满二叉树有n个结点 则深度h 性质6 一棵有n个结点的顺序二叉树 如从左至右 从上至下的 对每个结点从1开始编号 对于其中任意编号为i的结点 1 i n 有 1 若i 1 则i的父亲是 i 2 若i 1 则i是根结点 无父亲 2 若2i n 则i的左孩子是2i 若2i n 则i无左孩子 3 若2i 1 n 则i的右孩子是2i 1 若2i 1 n 则i无右孩子 3 深度为9的二叉树中至少有个结点 9 8 9 1 2 深度为 的二叉树的结点总数 最多为个 k 1 log2k k k 1 树 中各结点的度的最大值称为树 的 高度 层次 深度 度 D C C 课堂练习 4 具有3个结点的二叉树可能有几种不同形态 二 链式存储结构用二叉链表即可方便表示 typedefstructBinaryTreeNode ETypedata BinaryTreeNode LChild BinaryTreeNode RChild BinaryTreeNode 一般从根结点开始存储 相应地 访问树中结点时也只能从根开始 注 如果需要倒查某结点的双亲 可以再增加一个双亲域 直接前趋 指针 将二叉链表变成三叉链表 遍历规则 二叉树由根 左子树 右子树构成 定义为D L R 以根结点为参照系 注 前 中 后 的意思是指访问的结点D是先于子树出现还是后于子树出现 D L R的组合定义了六种可能的遍历方案 LDR LRD DLR DRL RDL RLD若限定先左后右 则有三种实现方案 DLRLDRLRD前序遍历中序遍历后序遍历 6 1 3一般树的遍历概念 一般树对应二叉树前序前序后序中序 前序遍历的结果是 ABFGCDHEIJK后序遍历的结果是 FGBCHDIJKEA 前序遍历结果是 ABFGCDHEIJK中序遍历结果是 FGBCHDIJKEA后序遍历结果是 GFHKJIEDCBA 算法 前中后递归算法前中非递归算法二叉树的层次遍历 从上至下 分类二叉树堆树的定义 初始化一个非空的最大堆算法 堆排序算法及图示的过程 5 7 3树的路径长度和哈夫曼树 Huffman 树的路径长度1 简单路径长度 从树中一个结点到另一个结点之间的分枝构成这两个结点之间的路径 2 树的简单路径长度 是指从树的根结点到每个结点的路径长度之和 3 加权路径长度 树中的每个叶子结点有权值 即每个叶子结点的大小不同 重要性不同 那么从叶子到根结点之间的长度 就是叶子的权值与叶子到根结点之间路径长度 分枝数 的乘积 1 2 2 3 3 3 17 1 2 2 4 3 2 16 结论 如果结点数相同 则顺序二叉树是具有最小简单路径长度的二叉树 2 3 3 4 6 9 构造哈夫曼树 6 9 2 3 3 4 5 6 9 2 3 3 4 5 6 7 9 2 3 3 4 5 6 7 9 11 16 27 A 2 B 4 C 5 D 9 对A B C D进行哈夫曼编码 总码长 加权路径长度 2 4 x3 5x2 9x1 37bit 第六章图 G