《第章数组和广义表》习题解答要点

《《第章数组和广义表》习题解答要点》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章数组和广义表第5章数组和广义表本章学习要点◆掌握多维数组在行优先顺序存储结构中地址的计算方法◆了解特殊矩阵压缩存储时的下标转换方法◆掌握稀疏矩阵常用的两种压缩存储表示方法（三元组表和十字链表表示法）的特点和存储结构◆掌握稀疏矩阵在三元组表表示下的基本运算（矩阵加法、减法、转置和乘法等）方法◆了解广义表的有关概念、广义表的各种表示方法和存储结构◆掌握广义表的基本操作（求广义表的表头、表尾、表的深度以及广义表的复制等）数组是最常用的数据结构之一，几乎所有的高级程序设计语言都把数组类型设定为内部类型。在前面讨论的线性结构中，其数据元素都是非结构的原子类

2、型，元素的值是不可再分解的。本章所讨论的数组可以看成是线性表的一种扩展，即线性表中的每个数据元素本身也是一个线性表。稀疏矩阵是一种特殊的二维数组，因其在压缩存储方面的特点而被广泛使用。广义表是一种较为复杂的数据结构，它是线性结构和树型结构的拓广。广义表被广泛应用于人工智能等领域。5.1数组的概念5.1.1数组的定义如果一个向量的所有元素又都是向量（或称子向量），且这些子向量具有相同的上限和下限标号，那么这种特殊形式的向量称为数组。一维数组是一个向量，它的每一个元素都是该结构中不可分割的最小单位。n(n>1)维数组是一个向量，它的每个元素都是n-1维数组

3、，且具有相同的上限和下限。从逻辑结构上看，n维数组Array中各元素的位置由该元素的下标唯一确定，一旦给定一组下标(j0,,j1,j2,…,jn-1)，都存在唯一的一个与其相对应的元素值a称为数组元素，记为a(j0,,j1,j2,…,jn-1)。其中，0<=ji

4、、维数dim和长度bounds定义一个数组（初始化数组）A。（2）读取操作Value(ArrayA,int*script,EType&e)：该操作根据下script标读取数组A中的元素到e中。-.135.-第5章数组和广义表（3）修改操作Assign(Array&A,int*script,ETypee)：该操作根据下标script修改数组A中的元素为e的值。（4）销毁操作：该操作回收一个数组所占的资源（销毁数组）。5.2数组的顺序存储表示和实现5.2.1数组顺序存储的物理结构由于数组不作插入和删除操作，也就是说，一旦建立了数组，则该数组结构中的数据元素

5、个数和元素之间的关系就不再发生变动。因此，采用顺序存储结构表示数组是最合理的方式。但是，由于内存地址是一维结构，而数组可以是多维结构，所以，必须有一个从多维下标到一维地址的对应关系。1．数组的两种顺序存储方法（1）以行（左下标）为主序的存储结构该存储结构以最左面的下标为主序，右下标优先变化，即下标变化顺序是从右到左。以二维数组为例，其内存结构如图5.1（a）所示。对于三维数组：（有2页、2行、3列），按左下标为主序的内存结构如图5.1（b）所示。（2）以列（右下标）为主序的存储结构该存储结构以最右面的下标为主序，左下标优先变化，即下标变化顺序是从左到右

6、。以二维数组：为例，其内存结构如图5.2（a）所示。对于三维数组：-.135.-第5章数组和广义表（有2页、2行、3列），按右下标为主序的内存结构如图5.2（b）所示。2．左下标为主序存储的n维数组中的元素a(j0,j1,...,jn-1)的地址计算公式对于一个已经被定义的二维数组Ab0×b1=(a[i][j])b0×b1，只要给出该数组存放的起始地址LOC(a[0][0])、数组元素的行下标i和列下标j，以及每个元素所占用的存储单元（字节）数L，便可以求得元素a[i][j]在内存中的首地址LOC(a[i][j])。地址计算公式为：其中b1为数组第2维

7、的长度（界）。对于以行为主序的n维数组，数组元素a(j0,j1,...,jn-1)的地址计算公式为：其中为数组元素a[0][0]...[0]的地址，L为每个元素所占内存的字节数，b0,b1,...,bn-1为每一维的长度。如果记：,即可得到映像常数向量：，相应的n维数组元素的地址计算公式可简写为：完全类似地，读者可以自行给出以右下标为主序的n维数组元素a(j0,j1,...,jn-1)的地址计算公式。【例5.1】二维数组M5×6的元素是4个字符（每个字符占1个存储单元）组成的串，那么M按行优先（以左下标为主序）存储时元素M[3][5]的起始地址与M按列

8、优先（以右下标为主序）存储时的哪个元素的起始地址相同？解：按行优先存储时元素M[3][5]的起