第5章 数据结构基础.ppt

1、第5章 数据结构基础,5.1 引言 5.2 线性结构 5.3 树形结构 *5.4 图形结构 5.5 内部排序 5.6 检索（查找）,5.1 引言,5.1.1 什么是数据结构 5.1.2 数据的逻辑结构 5.1.3 数据的存储结构 5.1.4 数据的运算,应用举例学籍档案管理,学生信息表： 每个学生的信息占一行，结构类型 表中依据学号的大小存在着一种前后关系，即线性结构 操作通常是插入、删除、更新某个学生的信息，和按条件检索某个学生的信息等,其它应用举例,计算机和人对奕问题 对弈的规则和策略-算法 棋盘及棋盘的格局-模型、树 多叉路口交通灯的管理问题 路口、通路、交通灯颜色-图,5.1.1 什么

2、是数据结构,研究数据之间的相互关系 逻辑结构 存储结构（物理结构） 数据的运算 数据类型 原子类型 - 不可分解 结构类型 - 原子类型构造而成,5.1.2数据的逻辑结构,5.1.3 数据的存储结构,数据的逻辑结构在计算机存储器中的实现，也称物理结构 顺序映射方式 链接映射方式 索引映射方式 散列映射方式,1、 顺序存储,用一组连续地址依次存储类型相同、有序的数据元素的集合 可以采用索引的方式访问其中的元素 一维数组描述 数组名称为b 用b0表示第一个元素 用b1表示第二个元素 内的数是元素的索引下标 可以是常量也可以是变量 也可以用循环结构访问数组元素,插入,删除,2、链式存储,链表是一个链

3、式存储的线性表 链表将物理上不连续的结点连接起来 链表中的每个元素习惯上被称为结点，结点包含两部分： 数据 指针(指针即是存储下一个相同类型元素的地址) 链表包括单链表、双链表、循环链表，在此只讨论单链表,单链表,即每个节点仅有一个指向后继节点的链 通常使用一个指针变量指向第一个元素，称为链表的头指针 通过头指针可以顺序访问其后的所有节点 链表的最后一个元素包含一个空指针，标识链表的结束,链表的操作,对链表的操作很多： 插入节点 删除节点 查找列表 检索列表 遍历列表 ,注意： （1）当向表尾插入、向表头插入、向空表插入节点时，要做特殊处理 （2）删除第一个节点、只有一个节点时，要做特殊处理,

4、5.1.4 数据的运算,5.2 线性结构,5.2.1 线性表 5.2.2 栈 5.2.3 队列,5.2.1 线性表,线性表是一个列表，列表内每个元素都有唯一的前驱和后继元素(除去最开始和末尾的元素) 线性表具有顺序结构 存储 顺序、链表 计算机应用 一元多项式，如7+3x+9x8,5.2.2 栈,栈是一种线性表，对栈的添加和删除只能在“栈顶”进行 栈顶、栈底 “后进先出”原则,栈的“后进先出”原则,1、入栈push 若没有足够的空间，不能添加元素（溢） 栈顶添加新的元素 新的元素成为栈顶,2、出栈pop 当栈为空时不能执行出栈操作 将栈顶元素移走并返回给用户,栈的应用,代数表达式中的括号匹配的

5、检验 遇到左括号时入栈，遇到右括号时让左括号出栈并删除 如果栈最后非空，表明左括号多了 如果遇到右括号而栈已经空了，表明右括号多了 迷宫求解 表达式求值,5.2.3 队列,队列也是一种线性表 数据只能在称为“尾部”的一端插入，只能从称为“头部”的一端删除 “先进先出”原则,5.3 树形结构,5.3.1 树及其遍历 5.3.2 二叉树 5.3.3 遍历二叉树,5.3.1 树及其遍历,树包括一组有限的元素，这些元素称为结点；同时包括一组有向线段，用来连接结点，称为分支。 一个结点的子树个数称为该结点的度数,度为0的结点 称为叶子,父：A 子：C、D 兄弟：E、F,数的遍历,遍历就是按一定的次序系统

6、地访问树的所有结点，并且只访问一次 树的线性化 遍历方法： 深度优先 先根次序 后根次序 广度优先 按层次遍历,5.3.2 二叉树,二叉树是结点的有限集合，它或为空集，或为由一个根结点和两棵互不相交的称为左右的二叉树构成 树至少有一个结点，而二叉树可以为空 树的子树不分次序，二叉树的子树有左右之分 二叉树的任何一个节点只能有0、1或2棵子树 二叉树的存储：链接方式 一般先把树或森林转换为一颗二叉树，再进行存储和运算 只保留父到第一个子结点的连线，作为左子树 子结点的兄弟依次连线，作为右子树,基本形态,二叉树的性质,深度：树中结点的最大层次 深度为k的二叉树的结点总数最大为2k-1 第i层的结点

7、数最大为2i-1 具有n个结点的完全二叉树的深度为 int（log2n）+1 任何一个二叉树T，若其叶子为n0个，而度数为2的结点数为n2，则n0=n2+1,特殊的二叉树,1.平衡二叉树 平衡因子：二叉树中任一结点的右子树与左子树的深度之差 平衡二叉树：所有结点的平衡因子为0,1,-1 2.满二叉树 一个深度为k的二叉树有2k-1个结点 3.完全二叉树 n个结点有k+1层，其中2k-1个结点在前k层，剩下的结点从左向右排列在第k+1层,5.3.3 遍历二叉树,遍历二叉树是按照预定的顺序处理每一个节点且仅处理一次 先根顺序遍历：中左右 中根顺序遍历：左中右 后根顺序遍历：左右中,先根遍历(DLR

8、),首先访问根，再访问左子树，最后访问右子树。,ABCDEF,中序遍历(LDR),首先处理左子树，再访问根，最后访问右子树。,CBDAEF,后序遍历(LRD),首先处理左子树，再访问右子树，最后访问根。,CDBFEA,练习,一棵二叉数共有10个节点（分别用A、BJ表示），已知树的中序遍历结果为：DHBEAFCIGJ，先序遍历结果为：ABDHECFGIJ。回答下列问题。 请画出这棵二叉树。 写出该树的后序遍历结果。,HDEBFIJGCA,*5.4 图形结构,5.4.1 图的概念 5.4.2 图的存储表示法 5.4.3 图的遍历和生成树,5.4.1 图的概念,图：节点和线段的集合，节点称为顶点，线

9、段称为线，线用于连接一对顶点。 有向图：每条线有一个方向(箭头)指向后继节点，有向图中线称为弧，弧的流向只能朝一个指定的方向。 无向图：线是没有方向的，线被称为边，顶点间的流向可以是任意方向。,术语,结点的度是连接到结点的线的数量。有向图中出度是离开结点的弧的数量，入度是进入结点的弧的数量。 如果两个结点之间有路径相连，则称它们是连通的。如果所有结点之间都是连通的，不考虑方向，则该图称为连通的。 在有向图中，如果每个结点都有通往其它结点的路径，称该图是强连通的。 在有向图中，如果至少两个结点是不连通的，则有向图是弱连通的。,5.4.2 图的存储表示法,边上的值表示权，如表示距离、成本等含义,5

10、.4.3 图的遍历和生成树,在给定的图中从任一结点出发，系统地访问图中的每一个结点一次，称为图的遍历 1、深度优先遍历 有向图 ， 无向图 ， 2、广度优先遍历 从结点出度：、 从结点出度：、,5.5 内部排序,5.5.1 简单插入排序 5.5.2 简单选择排序 5.5.3 冒泡排序,5.5.1 简单插入排序,列表被分成两个子列表：已排序和未排序的 初始时已排序部分为空 每次扫描过程中： 取出未排序列表中的第一个元素 然后转到已排序列表中，将其插入到合适的位置上 每次扫描后，未排序列表增加1个，已排序列表减少1个 对于n个数据，需要进行n-1次扫描,插入排序示意,5.5.2 简单选择排序,列表

11、被分成两个子列表：已排序和未排序的；初始时已排序部分为空。 排序时，从未排序列表中找到最小元素，与第一个元素交换。 经过选择和交换后，将未排序列表中的第一个元素划入排序列表中，这一过程称为一次扫描。 每次扫描后，未排序列表减少一个元素，已排序列表增加一个元素。 对于n个数据，需要进行n-1次扫描。,选择排序示意,5.5.3 冒泡排序,列表被分成两个子列表：已排序和未排序的；初始时已排序部分为空。 在未排序的子列表中，最小的元素通过冒泡的方法选出来并移动到已排序子列表中，这一过程称为一次扫描。每次扫描，未排序元素增加1个，已排序元素减少1个。 冒泡时，进行两两比较，如果前者较大，则交换数据。 对

12、于n个数据，需要进行n-1次扫描。,冒泡排序示意,5.6 检索（查找）,查找实现在列表中确定目标所在位置。查找通常返回具有要查找目标值的第一个元素的位置(索引) 5.6.1 顺序检索 5.6.2 二分法检索 5.6.3 分块检索* 5.6.4 散列表检索*,5.6.1 顺序检索（查找）,用于查找无序列表，一般用这种方法查找规模较小的列表。 顺序查找从表头开始逐个元素查找，当找到目标元素或查找完整个列表时，查找过程结束。,顺序查找示意,顺序查找示意,5.6.2 二分法检索（折半查找）,顺序查找很慢，尤其当列表中数据非常多时，逐个元素比较非常费时。当列表有序时，可采用效率非常高的折半查找算法。 折半查找时，先测试中间元素，可以判断出目标在列表的前半部分还是后半部分。如果在前半部分，则不用比较后半部分数据，排除掉一