数据抽象课件.pptVIP

第八章 数据抽象 主讲：孙剑 聊城大学计算机学院 本章主要内容 本章将研究如何对数据组织形式进行模拟。 数据组织形式→数据存储形式 int Scores [2] [9]; struct{ char Name [25]; int Age; float SkillRating； }Employee； 本章主要内容 8.1 数据结构基础 8.2 数据结构实现 本章主要内容 8.1 数据结构基础 8.1.1 基本数据结构 8.1.2 抽象 8.1.3 静态结构与动态结构 8.1.4 指针 数据结构基础 同构数组：“矩形”数据块，各项具有相同类型 int Scores [2] [9] ; Scores [1] [3]; 异构数组：构成的各项（称为部件）具有不同的类型。 struct{ char Name [25]; int Age; float SkillRating； }Employee； 数据结构基础 表：一种基本数据结构，其中的表项按顺序排列。 学生名单、购物清单等 数据结构基础 两种特殊类型的表——栈和队列 栈：该表只能在表头进行添加和删除。 数据结构基础 两种特殊类型的表——栈和队列 队列：该表只能在表头进行删除，表尾进行添加。 数据结构基础 树：其项具有层次化的数据组织形式。 组织中不同分支不会在下一层相遇。 8.1.1 基本数据结构 树： 结点：树中的每一个位置 根结点：最顶部的结点 结点的度：结点拥有的分支数 叶子（终端）结点：度为0的结点 层次：根为第一层，根的孩子为第二层。 树的深度（或高度）：树中结点的最大层次 8.1.1 基本数据结构 8.1.1 基本数据结构 祖先：从根到该结点所经分支上的所有结点 一个结点的直接祖先称为父结点 一个结点的直接后代称为子结点 拥有同一父结点的结点称为兄弟结点 8.1.1 基本数据结构 子树：若一棵树的任意一个结点与其下层的那些结点构成树的结构。故每个子结点是其父节点下面的子树的根节点。 8.1.1 基本数据结构 二叉树：每个结点至多有二棵子树（不存在度2的结点）；子树有左右之分，称为左子树、右子树。 8.1.1 基本数据结构 同构数组 异构数组 表 栈 队列 树 二叉树 8.1.2 抽象 数据结构的全部在于创造抽象工具，对于数据结构的讨论探索了一条可以把用户从实际数据存储的细节(存储器单元和地址)中解脱出来，并是允许用户通过更便利的方法访问信息的道路。 用户：这个术语在此不仅仅表示人，它的含义随着我们看法的改变而改变。 8.1.3 静态结构与动态结构 判断标准：这个结构的形状与大小是否随时间变化。 静态结构：形状与大小不随时间变化。 处理较简单，仅需要提供访问结构中的不同项的方法，也就是改变指定位置的数据值的方法。 8.1.3 静态结构与动态结构 判断标准：这个结构的形状与大小是否随时间变化。 动态结构：形状与大小随时间变化。 处理较复杂，需要处理增加和删除数据项的问题。 8.1.4 指针 指针：一个存储单元(或一个存储单元块)。存储的是数据所在存储单元的地址。 在数据结构中指针用来记录数据项的存放位置。 CPU中的程序计数器——指令指针 8.1.1 基本数据结构 同构数组 异构数组 表 栈 队列 树 二叉树 本章主要内容 8.2 数据结构实现 8.2.1 数组的存储 8.2.2 表的存储 8.2.3 栈和队列的存储 8.2.4 二叉树的存储 8.2.5 数据结构的操作 8.2.1 数组的存储 同构数组： 一维同构数组：存放一组数据序列，将这组数据序列存放在具有连续地址的存储单元中。假设序列中第一个单元的地址是x，则：第二个数据的地址为x+1，第三个数据的地址为x+2，…… 8.2.1 数组的存储 同构数组： 8.2.1 数组的存储 同构数组： 例如：存储24小时温度的读数序列 int Readings [24]; Readings [4]←67; 8.2.1 数组的存储 同构数组： 二维同构数组： 这是一种静态结构。 可以一行一行的存入数据——行主序 可以一列一列的存入数据——列主序 8.2.1 数组的存储 8.2.1 数组的存储 同构数组： 二维同构数组：行主序的情况下如何找到第3行第4个数值？ 其列数为c，存放第1行第1列的项的单元地址为x，那么第i行第j列的元素地址可以表示为 x+(c×(i-1))+(j-1) ——地址多项式。 列主序？？ 8.2.1 数组的存储 列主序，每项占用一个存储单元，其行数为r，存放第1行第1列的项的单元地址为x，那么第i行第j列的元素地址可以表示为 ： 行主序，每项占用2个存储