数据结构(线性表、栈、队列、二叉树、图).ppt

常见数据结构 线性表 栈 队列 二叉树 图 一 线性表 线性表是n个类型相同的数据元素的有限序列 数据元素之间是一对一的关系 即每个数据元素最多有一个直接前驱和一个直接后继 如图2 1所示 例如 英文字母表 A B Z 就是一个简单的线性表 表中的每一个英文字母是一个数据元素 每个元素之间存在唯一的顺序关系 如在英文字母表字母B的前面是字母A 而字母B后面是字母C 二 栈 栈是允许在一端进行插入和删除操作的特殊线性表 允许进行插入和删除操作的一端称为栈顶 top 另一端为栈底 bottom 栈底固定 而栈顶浮动 栈中元素个数为零时称为空栈 栈结构也称为后进先出表 LIFO 队列 Queue 的定义队列是限定仅在表的一端进行插入 在另一端进行删除操作的线性表 允许插入的一端称为队尾 rear 允许删除的一端称为队首 front 队列的插入操作 称为入队 队列的删除操作 称为出队 当队列中没有元素时称为空队列 设队列q a0 a1 a2 an 1 则a0称为队头元素 an 1称为队尾元素 元素按a0 a1 a2 an 1的次序入队 出队也只能按照这个次序 队列和栈相反 队列的操作是按先进先出 FirstInFirstOut 的原则进行的 又称为先进先出的线性表 简称FIFO表 三 队列 四 二叉树类型与定义 二叉树或为空树 或是由一个根结点加上两棵分别称为左子树和右子树的 互不交的二叉树组成 根结点 左子树 右子树 E F 二叉树的五种基本形态 N 空树 只含根结点 N N N L R R 右子树为空树 L 左子树为空树 左右子树均不为空树 介绍基本术语 叶子结点结点结点总数深度层 结点的层次从根开始定义起 根为第一层 根的孩子为第二层 依次累计 树中结点的最大层次称为树的深度或高度 性质1 在二叉树的第i层上至多有2i 1个结点 i 1 用归纳法证明 归纳基 归纳假设 归纳证明 i 1层时 只有一个根结点 2i 1 20 1 假设对所有的j 1 j i 命题成立 二叉树上每个结点至多有两棵子树 则第i层的结点数 2i 2 2 2i 1 性质2 深度为k的二叉树上至多含2k 1个结点 k 1 证明 基于上一条性质 深度为k的二叉树上的结点数至多为20 21 2k 1 2k 1 性质3 对任何一棵二叉树 若它含有n0个叶子结点 n2个度为2的结点 则必存在关系式 n0 n2 1 证明 设二叉树上结点总数n n0 n1 n2 又二叉树上分支总数b n1 2n2 而b n 1 n0 n1 n2 1 由此 n0 n2 1 两类特殊的二叉树 满二叉树 指的是深度为k且含有2k 1个结点的二叉树 完全二叉树 树中所含的n个结点和满二叉树中编号为1至n的结点一一对应 性质4 具有n个结点的完全二叉树的深度为 log2n 1 证明 设完全二叉树的深度为k 则根据第二条性质得2k 1 n 2k 即k 1 log2n k 因为k只能是整数 因此 k log2n 1 满二叉树的叶节点为N 则它的节点总数 A NB 2NC 2N 1D 2N 1E 2 N 1 高度为n的均衡的二叉树是指 如果去掉叶结点及相应的树枝 它应该是高度为n 1的满二叉树 在这里 树高等于叶结点的最大深度 根结点的深度为0 如果某个均衡的二叉树共有2381个结点 则该树的树高为 A 10B 11C 12D 13 二叉树的遍历 顺着某一条搜索路径巡访二叉树中的结点 使得每个结点均被访问一次 而且仅被访问一次 一 问题的提出 访问 的含义可以很广 如 输出结点的信息等 对 二叉树 而言 可以有三条搜索路径 1 先上后下的按层次遍历 2 先左 子树 后右 子树 的遍历 3 先右 子树 后左 子树 的遍历 二 先左后右的遍历算法 先 根 序的遍历算法 中 根 序的遍历算法 后 根 序的遍历算法 根 左子树 右子树 根 根 根 根 根 若二叉树为空树 则空操作 否则 1 访问根结点 2 先序遍历左子树 3 先序遍历右子树 先 根 序的遍历算法 若二叉树为空树 则空操作 否则 1 中序遍历左子树 2 访问根结点 3 中序遍历右子树 中 根 序的遍历算法 若二叉树为空树 则空操作 否则 1 后序遍历左子树 2 后序遍历右子树 3 访问根结点 后 根 序的遍历算法 例如 先序序列 中序序列 后序序列 ABCDEFGHK BDCAEHGKF DCBHKGFEA 前缀 后缀表达式 二叉树的应用 中缀表达式转换后缀表达式从左向右扫描表达式 运算数送到输出队列 运算符进栈 如果运算优先级大于栈顶元素直接进栈 如果运算优先级小于或等于栈顶元素 则先弹出栈顶元素 再进栈 左括号直接进栈 右括号则依次弹出栈中的元素 直到遇到第一个左括号为止 有些题目要求写出前缀 中缀和后缀表达式 做这类题目时 可以先通过优先级画出一棵二叉树再分别利用先根 中根和后根遍历写出对应的序列 就是它们的前缀 中缀和后缀表达式 表达式a b c d的后缀表达式是 A abcd B abc d C abc d D abcd假设一棵二叉树的后序遍历序列为DGJHEBIFCA 中序遍历序列为DBGEHJACIF 则其前序遍历序列为 一棵二叉树的中序遍历序列为 DGBAECHF 后序遍历序列为 GDBEHFCA 则前序列遍历序列是 数据结构之 图 什么是图 什么是计算机中所说的图 请先看下面的 柯尼斯堡桥问题 传说在东普鲁士境内 有一座柯尼斯堡城 希雷格尔河流经这个城市的克奈霍福岛后 就将这个城市一分为二 形成如图1 1 左 的A B C D4个地区 人们建造了7座桥将这4个地区连起来 在游览中有人提出 是否可以从A地出发 各座桥恰好通过一次 最后又回到原来出发地呢 这个问题在18世纪被数学家欧拉解决了 他把这个问题转化为图1 1右边所示的图 图上用A B C D4个顶点分别表示4个地区 用两点间的线段表示连接各地的桥 这样原来的问题就转化为 从A顶点出发经过其中每一条线段一次 而且仅一次 再回到A点的 一笔画 问题 欧拉对柯尼斯堡问题作出了否定的结论 因为对于每一个顶点 不论如何经过 必须有一条进路和一条出路 所以对每一个顶点 除起点和终点 来说与它有关的线段 称为边 必须是偶数条 而图1 1 右 的顶点有关的线段都是奇数条 因此不可能一笔画出 欧拉通过对柯尼斯堡桥问题的研究 于1736年发表了著名的关于图论的论文 从而创立了图论的学说 图1 2一类的问题就是图论中所指的图 又如 有6个足球队之间进行循环赛 他们比赛的场次可以用图1 3 1 来表示 有3个人相互写信 可以用图1 3 2 来表示 从上面两个例子可看出 我们这里所说的图 graph 与人们通常所熟悉的图 如圆 四边形 函数图象等是很不相同的 是指某些具体事物和这些事物之间的联系 如果我们用点来表示事物 如地点 队 用线段来表示两事物之间的联系 那么一个图就是表示事物的点集和表示事物之间联系的线段集合所构成 其中线段仅表示两点的关系 它的长短与曲直是无关紧要的 例如图1 4中3个图 被认为是同一个图 图的基本概念 定义 图G定义为一个偶对 V E 记作G V E 其中1 V是一个非空有限集合 它的元素称为顶点 2 E也是一个集合 它的元素称为边例如图1 4中的图有4个顶点 4条边 或者定义 图G Graph 是由顶点的集合V和边的集合E所组成的二元组 记作 G V E 其中V是顶点的集合 E是边的集合 无向图与有向图 边的表示方式是用该边的两个顶点来表示的 如果边的表示无方向 那么 对应的图就是无向图 否则称为有向图 如下图所示 在无向图中 边的两个顶点在边的表示中可以互换 如边 V1 V4 与边 V4 V1 是等价的 表示的是同一条边 无向图中边的表示用圆括号 在有向图中 边的走向不同就认为是不同的边 如在边的集合E 见右上图 中 其中表示该边是由顶点1出发 到顶点4结束 即边表明了该边的方向性 且两个顶点的顺序不能颠倒 有向图中边的表示用尖括号 顶点的度 与顶点关联的边的数目 有向图顶点的度等于该顶点的入度与出度之和 入度 以该顶点为终点的边的数目和出度 以该顶点为起点的边的数目和图的阶 图中顶点的个数 例如图1 3中分别是6和3 度数为奇数的顶点叫做奇点 度数为偶数的点叫做偶点 定理1 图G中所有顶点的度数之和等于边数的2倍 因为计算顶点的度数时 每条边均用到2次 定理2 任意一个图一定有偶数个奇点 连通 如果图中结点U V之间存在一条从U通过若干条边 点到达V的通路 称U V是连通的 连通图 如果一个无向图中 任一对不同顶点U V 都有一条 U V 通路 则称图G是连通的 强连通图 在有向图G中 每一对结点之间都有路径的图 网络 带权的连通图 连通 如果顶点u v属于G u v之间有一条从u通过若干条边到达v的通路 则认为顶点u和v是连通的 连通图 如果对于图G中每一对不同顶点u v都有一条 u v 通路 则称G是连通图 通路指u 边1 顶点1 边2 顶点2 v 点和边交替相接 且互不相同 图的遍历 1 概念 从图中某一结点出发系统地访问图中所有结点 使每个结点恰好被访问一次 这种运算称图的遍历 为了避免重复访问某个结点 可以设一个标志数组visited I 未访问时值为FALSE 访问一次后就改为TRUE 2 分类 深度优先遍历和广度优先遍历 深度优先遍历 类似于树的先序遍历 从图中某个结点V0出发 访问此结点 然后依次访问从V0的未被访问的邻接点出发进行深度优先遍历 直到图中所有和V0有路径相通的结点均被访问到 若此时图中尚有结点未被访问 则另选图中一个未被访问的结点V1作为起点 重复上述过程 直至