第5章 数组和广义表习题解答

第5章 数组和广义表本章学习要点◆掌握多维数组在行优先顺序存储结构中地址的计算方法◆了解特殊矩阵压缩存储时的下标转换方法◆掌握稀疏矩阵常用的两种压缩存储表示方法（三元组表和十字链表表示法）的特点和存储

5 第章数组和广义表 本章学习要点 ◆ 掌握多维数组在行优先顺序存储结构中地址的计算方法 ◆ 了解特殊矩阵压缩存储时的下标转换方法 ◆ 掌握稀疏矩阵常用的两种压缩存储表示方法（三元组表和十字链表表示法）的特点和存储 结构 ◆ 掌握稀疏矩阵在三元组表表示下的基本运算（矩阵加法、减法、转置和乘法等）方法 ◆ 了解广义表的有关概念、广义表的各种表示方法和存储结构 ◆ 掌握广义表的基本操作（求广义表的表头、表尾、表的深度以及广义表的复制等） 数组是最常用的数据结构之一，几乎所有的高级程序设计语言都把数组类型设定为内部 类型。在前面讨论的线性结构中，其数据元素都是非结构的原子类型，元素的值是不可再分 解的。本章所讨论的数组可以看成是线性表的一种扩展，即线性表中的每个数据元素本身也 是一个线性表。 稀疏矩阵是一种特殊的二维数组，因其在压缩存储方面的特点而被广泛使用。 广义表是一种较为复杂的数据结构，它是线性结构和树型结构的拓广。广义表被广泛应 用于人工智能等领域。 5.1 数组的概念 5.1.1 数组的定义 如果一个向量的所有元素又都是向量（或称子向量），且这些子向量具有相同的上限和 下限标号，那么这种特殊形式的向量称为。是一个向量，它的每一个元素都是 数组一维数组 n-1 n(n>1) 该结构中不可分割的最小单位。是一个向量，它的每个元素都是维数组，且 维数组 具有相同的上限和下限。 nArray 从逻辑结构上看，维数组中各元素的位置由该元素的下标唯一确定，一旦给定一 (j,j,j,…,j)a 组，都存在唯一的一个与其相对应的元素值称为，记为 下标数组元素 0,12n-1 a(j,j,j,…,j)0<=j<bbi(i=0,1,2,…,n-1) 。其中，，称为第维的。 长度 0,12n-1iii 5.1.2 数组的基本操作 数组一旦被定义，它的元素类型（即数组类型）、维数、各维的界（长度）就不再改变。 所以数组的基本操作主要有： 1InitArray(Array&A,intdim,int*bounds)dim （）：该操作根据数组元素类型、维数 初始化 boundsA 和长度定义一个数组（初始化数组）。 2Value(ArrayA,int*script,EType&e)scriptA （）：该操作根据下标读取数组中的 读取操作 e 元素到中。