数据结构串讲.ppt

总结 突破 数据结构 重点难点 数据结构包括数据的逻辑结构 数据的存储结构 数据的运算三部分 逻辑结构是数据元素之间固有的逻辑关系的整体 是针对具体问题抽象出来的数据模型 与计算机无关 而存储结构 又称物理结构 是数据及其逻辑结构在计算机中的表示 映像 存储必须依赖于计算机 常见的逻辑结构 线性结构与非线性结构 1 线性结构 数据元素之间是 一个跟一个 的线性关系 也称为 前 驱 后 继 关系 2 树型结构 数据元素之间是 一对多 关系 也称为层次结构 或 父子关系 上下级关系 3 图结构 数据元素之间是 多对多 关系 线性结构和树型结构的基本区别是 每个结点是否仅仅有一个直接后继 存储结构实质上是内存分配 存储两方面内容 数据元素的存储以及数据元素关系的存储 尤为重要 最常见的存储结构有顺序存储结构和链接存储结构 6 理清课程的主体知识框架三要素之间的关系是怎样的 算法 查找 排序 基本操作 一般线性表特殊线性表 1 一般线性表 34 23 67 43 4 链 链表存储地址存储状态0002李0008钱0014孙0020王0026吴0032赵0038郑0044周 004400140002NULL0038000800200026 数据域 指针域 结点 指针 链表 单链表 顺序表存储地址存储状态0030赵0032钱0034孙0036李0038周003A吴003C郑003E王 思考 考试不考 旅游团如何快速检查是否有人走丢 除了点人数有没有其他的办法 插入前 a1 ai 1 ai an 插入后 a1 ai 1 x ai an 如何在之前插入 算法描述 s newNode s data x s next p next p next s templateTLinkList Get inti p first next j 1 while p p 能否完成指针后移 如何让指针一下子后移两个元素 数组与链表各个操作实现有没有相似的地方 常见链表类型还有循环链表 双链表 注意二者的特点以及操作实现与单链表的不同 比如双链表插入结点时要修改四个指针 注意总结指针勾链先后顺序的规律 y left p y right p right p right left y p right y 删除过程 p left right p right p right left p left a deletep 2 特殊线性表 栈和队列是操作受限的特殊线性表 栈的应用 递归表达式计算问题 中缀变后缀246 35 684 7 A b c d e fA b c d eA b c d e f 输出数组元素逆序输出链表输出二叉树以上三个输出操作如何用递归实现的 体会递归思想的本质 队列应用 层序遍历 树 二叉树和树是两种树结构 具有3个结点的树和具有3个结点的二叉树的形态 非线性结构树 二叉树的性质与遍历满二叉树和完全二叉树层数 深度 结点数之间的关系 N0 n2 1 28 问题 针对二叉树 回答下列问题 1 具有n个结点的非空二叉树的最小深度是多少 最大深度是多少 2 具有n个结点的完全二叉树中有多少个叶子结点 有多少个度为2的结点 3 具有n0个叶子结点的完全二叉树中共有多少个结点 答 1 其最小深度是 log2 n 1 1 最大深度是n 2 具有n个结点的完全二叉树中有 n 2 叶子结点 有 n 2 1个度为2的结点 3 具有n0个叶子结点的完全二叉树中共有2n0个结点或2n0 1个结点 29 一棵完全二叉树有1000个结点 则它必有个叶子结点 有个度为2的结点 有个结点只有非空左子树 有个结点只有非空右子树 练习 正确答案 全部叶子数 1000 2 500个 度为2的结点 叶子总数 1 499个 因为最后一个结点坐标是偶数 所以必为左子树 有1个结点只有非空左子树 有0个结点只有非空右子树 完全二叉树的性质 完全二叉树的结点按层序编号 编号之间关系反映了结点间 父子关系 粗略地讲 编号为i的结点 双亲编号为 i 2 左右孩子编号为2i和2i 1 堆 中用到的堆结构是完全二叉树 二叉树遍历 遍历一定从根出发吗 中序遍历结果 ebIfjagdh后序遍历结果 eIjfbghda中序遍历序列 DGBAECF前序遍历