数据抽象课件.ppt

《数据抽象课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第八章数据抽象主讲：孙剑聊城大学计算机学院本章主要内容本章将研究如何对数据组织形式进行模拟。数据组织形式→数据存储形式intScores[2][9];struct{charName[25];intAge;floatSkillRating；}Employee；2本章主要内容8.1数据结构基础8.2数据结构实现3本章主要内容8.1数据结构基础8.1.1基本数据结构8.1.2抽象8.1.3静态结构与动态结构8.1.4指针4数据结构基础同构数组：“矩形”数据块，各项具有相同类型intScores[2][

2、9];Scores[1][3];异构数组：构成的各项（称为部件）具有不同的类型。struct{charName[25];intAge;floatSkillRating；}Employee；5数据结构基础表：一种基本数据结构，其中的表项按顺序排列。学生名单、购物清单等6数据结构基础两种特殊类型的表——栈和队列栈：该表只能在表头进行添加和删除。后进先出a1a2a3...an出栈入栈7数据结构基础两种特殊类型的表——栈和队列队列：该表只能在表头进行删除，表尾进行添加。先进先出a1a2a3……an入队列

3、出队列队头元素队尾元素8数据结构基础树：其项具有层次化的数据组织形式。组织中不同分支不会在下一层相遇。总裁销售副总裁财务副总裁服务副总裁地区销售经理地区销售经理地区销售经理地区服务经理地区服务经理98.1.1基本数据结构树：结点：树中的每一个位置根结点：最顶部的结点结点的度：结点拥有的分支数叶子（终端）结点：度为0的结点层次：根为第一层，根的孩子为第二层。树的深度（或高度）：树中结点的最大层次108.1.1基本数据结构ABCDEFGIJKH根节点叶子节点DEFHIJK深度为4118.1.1基本数

4、据结构祖先：从根到该结点所经分支上的所有结点一个结点的直接祖先称为父结点一个结点的直接后代称为子结点拥有同一父结点的结点称为兄弟结点ABCDEFG128.1.1基本数据结构子树：若一棵树的任意一个结点与其下层的那些结点构成树的结构。故每个子结点是其父节点下面的子树的根节点。ABCDEFG138.1.1基本数据结构二叉树：每个结点至多有二棵子树（不存在度>2的结点）；子树有左右之分，称为左子树、右子树。148.1.1基本数据结构同构数组异构数组表栈队列树二叉树158.1.2抽象数据结构的全部在于创

5、造抽象工具，对于数据结构的讨论探索了一条可以把用户从实际数据存储的细节(存储器单元和地址)中解脱出来，并是允许用户通过更便利的方法访问信息的道路。用户：这个术语在此不仅仅表示人，它的含义随着我们看法的改变而改变。168.1.3静态结构与动态结构判断标准：这个结构的形状与大小是否随时间变化。静态结构：形状与大小不随时间变化。处理较简单，仅需要提供访问结构中的不同项的方法，也就是改变指定位置的数据值的方法。178.1.3静态结构与动态结构判断标准：这个结构的形状与大小是否随时间变化。动态结构：形状与

6、大小随时间变化。处理较复杂，需要处理增加和删除数据项的问题。188.1.4指针指针：一个存储单元(或一个存储单元块)。存储的是数据所在存储单元的地址。在数据结构中指针用来记录数据项的存放位置。CPU中的程序计数器——指令指针198.1.1基本数据结构同构数组异构数组表栈队列树二叉树抽象静态结构与动态结构指针20本章主要内容8.2数据结构实现8.2.1数组的存储8.2.2表的存储8.2.3栈和队列的存储8.2.4二叉树的存储8.2.5数据结构的操作218.2.1数组的存储同构数组：一维同构数组：存

7、放一组数据序列，将这组数据序列存放在具有连续地址的存储单元中。假设序列中第一个单元的地址是x，则：第二个数据的地址为x+1，第三个数据的地址为x+2，……228.2.1数组的存储同构数组：238.2.1数组的存储同构数组：例如：存储24小时温度的读数序列intReadings[24];Readings[4]←67;248.2.1数组的存储同构数组：二维同构数组：这是一种静态结构。可以一行一行的存入数据——行主序可以一列一列的存入数据——列主序258.2.1数组的存储268.2.1数组的存储同构数

8、组：二维同构数组：行主序的情况下如何找到第3行第4个数值？其列数为c，存放第1行第1列的项的单元地址为x，那么第i行第j列的元素地址可以表示为x+(c×(i-1))+(j-1)——地址多项式。列主序？？第1行x+(c-1)……x+1xx+(2c-1）……x+cx+(2c+3）第2行278.2.1数组的存储列主序，每项占用一个存储单元，其行数为r，存放第1行第1列的项的单元地址为x，那么第i行第j列的元素地址可以表示为：行主序，每项占用2个存储单元，其列数为c，存放第1行第1列的项的单元地址为x，