多维数组实现.ppt

第六章 封装 抽象 大型程序的构造中，程序员不可避免要涉及到新数据类型的设计和实现。 如：大学中，表示一堂课的数据对象section，包含的信息有：老师名、教室、最大注册数等，还可以包含一个注册学生列表作为部件。 操作包括：创建一个section、注册一个学生、消除一个section等。 其实现主要涉及其表示以及对应相关操作的子程序设计。 语言实现的目标是使得数据的各种形式的不同对程序员透明。因此，基本类型和用户定义类型对程序员的使用来说应不存在差别。 抽象机制 有四种机制可被程序员用来创建新类型和类型上的操作。 1、结构化数据 几乎所有语言都能够用基本数据对象创建复杂的数据对象。 2、子程序 可用子程序来定义实现类型的操作，但如何正确地使用，却是程序员的责任。 3、类型声明 语言包含有定义新类型及其操作的能力。抽象数据类型即是这种机制，它提供了检测错误使用的能力。 4、继承 基于已有类型创建新类型的机制。 6.1 结构数据类型 数据结构——包含其他数据对象作为元素或部件的数据对象。 基本概念 常见结构化数据 向量和数组 记录 列表 集合 结构数据对象和数据类型 结构数据对象——一组其他数据对象构成的聚集，这些数据对象称为元素或部件，可以是基本类型，也可以是结构。 很多和数据结构相关的问题和概念与基本类型数据是相同的，但数据结构更为复杂。 数据结构类型也涉及类型规约和类型实现，只是更为复杂。 两个方面是特别重要的： 结构信息的规约和实现变成了中心问题，用于指出部件对象及其间关系，以便于部件的直接选取（或访问）。 结构上的很多操作带来的存储管理问题。 数据结构类型的规约 规约的主要属性包括： 1、部件数量 结构的部件数量可能是固定的，在其生命期中不变，如：数组、记录等。 也可能是变长的，数量可以动态变化，如：栈、列表、集合、文件、表格等。 变长结构通常需定义插入和删去部件的操作。而且可变长数据对象经常使用指针类型。 数据结构类型的规约 2、每个部件的类型 同构的——所有部件为相同类型，如：数组、字符串、集合、文件等。 异构的——部件有不同类型，如：记录，列表等。 3、用于选取部件的名字 结构类型需要有标识结构中个体部件的选择机制。 对数组，个体部件的名字可以是整数下标或下标序列。 对列表，名字可以是用户定义的标识符。 有的结构，只允许访问特定部件，如栈顶元素。 数据结构类型的规约 4、部件的最大数量 对有的变长结构，结构的最大尺寸可以指定。 5、部件的组织 最常见的组织是简单的线性序列，如：向量、记录、字符串、栈、列表、文件等。 然而，数组、记录和列表类型也可以扩展为多维形式。 多维形式可以看成单独的类型，也可以简单地看成同类结构部件的顺序类型（其元素类型为结构）。 如A(i,j) 和A[i][j]的差异。 数据结构上的操作 结构上操作的定义域和值域规约的方法和基本类型操作是类似的，但是，有些新的操作类型特别重要。 1、部件选择操作 有两种类型： 随机选择——可任意选择结构中某一部件 顺序选择——以预定好的顺序选择部件。 数据对象中部件或数据值的选择和相关的引用操作是有区别的。如：V[4]选择V中第4个元素，分两步： 先引用（确定V的位置（l-值），返回一个指针）， 后选择（得到部件的位置）。 数据结构上的操作 2、整体数据结构操作 以完整的数据结构为参数，产生新的数据结构为结果。 大多数语言中，这样的整体性操作是有限的。如： 两个数组相加、记录间的赋值、集合的并等。 少数语言提供了大量整体操作，然而，程序员很少去选择个体部件。如：APL和SNOBOL4语言。 数据结构上的操作 3、部件的插入/删除 这种操作将改变部件数量，从而影响存储表示和存储管理。 4、数据结构的创建/消除 这类操作将对存储管理有很大影响。 数据结构类型的实现 实现中需要考虑的两个问题： 结构中部件的高效选择， 高效的存储管理。 存储表示 结构的存储管理包括：①结构中部件的存储；②可选的描述子（用于存储结构的属性）。 数据结构类型的实现：存储表示 有两种基本表示： 1、顺序表示 结构存放在单个连续块中（包括描述符和部件）。 常用于固定长的结构，有时也用于同构变长结构。 2、链接表示 结构被存放在几个非连续的存储块中，这些块用指针链接在一起，该指针称为链（link）。 通常用于变长结构。 两种基本存储表示 数据结构操作的实现 大多数结构的实现中，部件选择是最重要的，需要较高的随机和顺序访问效率。对顺序和链接存储表示，这两种类型的选择的实现有所不同。 数据结构操作的实现 顺序表示 部件的随机访问通常涉及“基地址（完整块的开始位置）+位移量（部件在块中的相对位置）”的计算。 对一个顺序存储的同构结构，部件序列的选择按如下步骤： 1、要选择序列的第