信息学奥赛-数据结构.ppt

数据结构 数据结构是计算机存储 组织数据的方式 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合 通俗解释 数据相当于书 计算机相当于书架 存放了很多书 书架分为很多格子 书存放在不同格子 内存空间 对应一个地址 中 为了更快的取到想要的书 要用特定的存放方式 数据结构 线性表 线性表 n个数据元素的有序集合 连成线的 是一种常用的数据结构 其中数据元素之间的关系通常是一对一的关系 即除了第一个和最后一个数据元素之外 其它数据元素都是首尾相接的实际应用中常见的特殊线性表 栈 队列 字符串 一维数组 非线性表 非线性表 各个数据元素不再保持在一个线性序列中 每个数据元素可能与零个或者多个其他数据元素发生联系主要代表 树 图结构 多维数组 链表 链是一种存储单元上非连续 非顺序的存储结构 通过链表中的指针依次访问数据 链表由一系列结点 链表中每一个元素称为结点 组成 数据元素可根据需要实时添加 动态生成 由于非连续 链表无法随机读取 需要通过指针依次访问 查找数据时间长 栈 栈是只能在某一端插入和删除的数据结构 想象用桶堆积物品 先堆进来的压在底下 随后一件件往上堆 取走时 只能从上面一件件取 堆和取都在顶部进行 底部一般是不动的 栈进行删除和插入的一端称栈顶 另一堆称栈底 插入一般称为进栈 PUSH 删除则称为退栈 POP 栈的特征是 后进先出 栈 一个栈可以用定长为 的数组 来表示用一个栈指针TOP指向栈顶 若TOP 0 表示栈空 TOP N时栈满 进栈时TOP加 退栈时TOP减 当TOP 0时为下溢 练习某个车站呈狭长形 宽度只能容下一辆车 并且只有一个出入口 已知某时刻该车站状态为空 从这一时刻开始的出入记录为 进 出 进 进 进 出 出 进 进 进 出 出 假设车辆入站的顺序为1 2 3 4 5 6 7 则车辆出站的顺序为 C A 1 2 3 4 5B 1 2 4 5 7C 1 4 3 7 6D 1 4 3 7 2 队列 跟栈相反 队列是限定只能在表的一端进行插入 在表的另一端进行删除的数据结构 队列的特征是 先进先出 就像排队买东西 排在前面的人买完东西后离开队伍 删除 而后来的人总是排在队伍未尾 插入 通常把队列的删除和插入分别称为出队和入队 允许删除的一端 队头 front 允许插入的一端 队尾 rear 队列 队列可以用数组Q m 1 来存储 数组的上界 即是队列所容许的最大容量 在队列的运算中需设两个指针 head 队头指针 指向实际队头元素的前一个位置tail 队尾指针 指向实际队尾元素所在的位置 树 一棵树是由n n 0 个元素组成的有限集合 其中 1 每个元素称为结点 2 有且仅有一个特定的结点 称为根结点或树根 3 除根结点外 其余结点能分成m m 0 个互不相交的有限集合T0 T1 T2 Tm 1 其中的每个子集又都是一棵树 这些集合称为这棵树的子树 2的子节点 5 6的父节点 根节点 2的兄弟 树 一个结点的子树个数 称为这个结点的度如 结点1的度为3 结点3的度为0度为0的结点称为叶结点如 结点3 5 6 8 9度不为0的结点称为分支结点如 结点1 2 4 7根以外的分支结点又称为内部结点如 结点2 4 7树中各结点的度的最大值称为这棵树的度右侧这颗树度为33 树 树节点的层次从根开始定义 根结点的层次为1其它结点的层次等于它的父结点层次加1如 根节点层次为1 结点2 3 4的层次为2 结点5 6 7的层次为3 结点8 9的层次为4 一棵树中所有的结点的层次的最大值称为树的深度 或高度 如 这棵树的深度为4 二叉树 二叉树是一种特殊的树型结构 它是最大度数为2的树 它的两棵子树分别称为左子树 右子树 二叉树的每个结点最多有两个子结点 每个结点的子结点分别称为左孩子 右孩子 二叉树有5中基本形态 二叉树的性质 性质1 在二叉树的第i层上最多有2i 1个结点 i 1 性质2 深度 高度 为k的二叉树至多有2k 1个结点 k 1 二叉树的性质 性质3 N n0 n1 n2 性质4 n0 n2 1 设二叉树中度为0 1 2的结点分别有no n1 n2个 总结点数为N 树的遍历 在应用树结构解决问题时 往往要求按照某种次序获得树中全部结点的信息 这种操作叫作树的遍历 遍历的方法有多种 以二叉树为例 树的遍历 先序遍历 先序 根 遍历 1 先访问根结点 先序遍历左子树 先序遍历右子树如右图先序遍历的结果为 abdehicfg 树的遍历 中序遍历 中序 根 遍历 中序遍历左子树 访问处理根结点 中序遍历右子树如右图中序遍历的结果为 dbheiafcg 树的遍历 后序遍历 后序 根 遍历 后序遍历左子树 后序遍历右子树 访问处理根结点如上图后序遍历的结果为 dhiebfgca 树的遍历 层次遍历 层次遍历 按层次从小到大逐个访问 同一层次按照从左到右的次序 如右图层次遍历的结果为 hIdefgbca 练习 1 二叉树T 已知其前序遍历序列为1243576 中序遍历序列为4215736 则其后序遍历序列为 B A 4257631B 4275631C 4275361D 4723561 22 图 通俗说 各顶点用边连起来就叫做图 图和树的区别 1 树形结构中 每一个数据有可能有多个下层结点 孩子结点 但却只与一个上层结点相关 2 图形结构中 结点之间的关系可以是任意的 图中任意两个数据之间都可能相关 图 a 有向图 图的边有方向 只能按箭头方向从一点到另一点 a 就是一个有向图 b 无向图 图的边没有方向 可以双向 b 就是一个无向图 结点的度 无向图中与结点相连的边的数目 称为结点的度 有向图中结点的度等于该结点的入度和出度之和结点的入度 在有向图中 以这个结点为终点的有向边的数目 结点的出度 在有向图中 以这个结点为起点的有向边的数目 图的遍历 1 深度优先遍历从图中某个顶点v0出发 然后搜索V0的一个邻接点Vi 若Vi未被访问 则访问之 再搜索Vi的一个邻接点按此方式访问 若某顶点的邻接点全部访问完毕 则回到它的上一顶点 然后再从此顶点又按深度优先的方法搜索下去 直到访问完毕为止 深度优先遍历得到的序列为 0 1 3 7 4 2 5 6 图的遍历 2 广度优先遍历类似树的按层次遍历