20119685L130Q02第1章概论.ppt

* （2） S=(D, R) D={di | 1≤i≤5} R={(di , dj ), ij} d1 d5 d2 d4 d3 该结构是非线性的。 解：上述表达式可用图形表示为： * 解释2：什么叫数据的物理结构？ 答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。 存储结构可分为4大类： 例：（见教材P6）复数3.0－2.3i 的两种存储方式： 顺序、链式、索引、散列 －2.3 0302 3.0 0300 0415 0302 3.0 0300 0415 －2.3 法1：地址 内容 法2：地址 内容 2字节 数据结构---第一章 绪论 * 数据存储方式的四种常用结构 (1)顺序存储：数据元素依次放在连续的存储单元中。 a1 a2 ... ai ... an (2)链式存储：在存储结点中增加若干指针域，记录后继或者相关结点的地址（指针）。 a1 1220 ... a3 1342 ... a2 1072 ... 1000 1004 1000 1004 1072 1076 1220 1224 指针 结点 结点 * (3)索引存储：将数据元素分为若干子表，子表的开始位置存放在索引表中。 索引表 班级 addr 主表 01 1 02 31 03 54 …… (4)散列存储：根据数据元素的关键字值，由散列函数计算出存储地址。LOC(ai)=H(key) …… 432 …… 713 …… 王小二 李一凡 1 a1 2 a2 …… 31 a31 …… * 解释3：什么是数据的运算？ 答：在数据的逻辑结构上定义的操作算法。 它在数据的存储结构上实现。 最常用的数据运算有5种： 插入、删除、修改、查找、排序 * 1.3 抽象数据类型概念 Q1 数据类型与抽象数据类型的区别？ Q2 抽象数据类型如何定义？ Q3 抽象数据类型如何表示和实现？ 讨论： 提示：教材中例1-6和例1-7分别给出了抽象数据类型“三元组”的定义、表示和实现，请试阅读。 * Q1 数据类型与抽象数据类型的区别？ 数据类型：是一个值的集合和定义在该值上 的一组操作的总称。 抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作） 它与数据类型实质上是一个概念，其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。 * Q2 抽象数据类型如何定义？ 抽象数据类型可以用以下的三元组来表示： ADT = （D，S，P） 数据对象 D上的关系集 D上的操作集 ADT抽象数据类型名{ 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作 ：基本操作的定义 } ADT抽象数据类型名 ADT常用定义格式 * 例：给出自然数(Natural Number )的抽象数据类型定义。 ADT Natural_Number is objects: 一个整数的有序子集合，它开始于0，结束于机器能表示的最大整数 (MAX INT) functions: 对于所有的 x, y ? Natural_Number； TRUE, FALSE ? Boolean； +, -, , = = ,=等都是可用的服务。 Zero ( )： Natural Number 返回 0 IsZero(x)： Bo