2．对称矩阵、三角矩阵、对角矩阵等特殊矩阵在计算机中的
压缩存储表示及地址计算公式； 3．稀疏矩阵的三元组表示及转置算法实现； 4．稀疏矩阵的十字链表表示及相加算法实现； 5．广义表存储结构表示及基本运算。
2018/10/10 2
5.1 数 组
数组和广义表可看成是一种特殊的线性表，其特殊在于， 表中的数所元素本身也是一种线性表。
5.1 .1 数组的定义
数组是大家都已经很熟悉的一种数据类型，几乎所有高级语
言程序设计中都设定了数组类型。
数组（Array）是由n(n>1)个相同类型数据元素a0，al，…ai…， an-1构成的有限序列。n是数组的长度。其中数组中的数据元素ai
是一个数据结构，即ai可以是线性表中的一个元素，本身也可以
线性表。在每个关系中，每个元素都有一个直接后继。因此， 就其单个关系而言，这n个关系中的每一个仍然是一种线性
关系。
数组中每个元素都是由一个值和一组下标来确定的。同线性 表一样，数组中的所有数据元素都必须属于同一数据类型。 元素下标的个数被称为数组的维数。显然，当维数为1时， 数组就退化为定长的线性表。
可以看成由m个行向量组成的向量，也可以看由n个列向量组成 的向量。 数组中的每个元素由元素值 aij 及一组下标（ i，j）来确定。 aij既属于第i行的行向量，又属于第j列的列向量。 其中，ai=( ai,0 ai,1 … ai,n-1) (0≤i＜n) 可以认为Am*n=A，A是这样的一维数组： A=( a0，al，…，ai，…，am-1)
第5章 数组和广义表
本章主题：多维数组、特殊矩阵和广义表 教学目的：掌握数组和广义表的定义、运算及存储结构 教学难点：矩阵的压缩存储
2018/10/10
1
本章学习导读
本章主要介绍数组的概念及多维数组在计算机中的存放， 特殊矩阵的压缩存储及相应运算，广义表的概念和存储结构及 其相关运算的实现。通过本章学习，要求掌握如下内容： 1．多维数组的定义及在计算机中的存储表示；
2018/10/10 7
5.1.2 数组的基本操作
数组一旦被定义，它的维数和维界就不再改变。因此，除了结 构的初始化和销毁之外，数组的基本操作一般不会含有元素的插入 或删除等操作,数组只有访问数组元素和修改元素值的操作。 (1) value(A，indexl，index2，…，indexd)：A是已存在的d维 数组，indexl，index2，…，indexd是指定的d个下标值，且这些下 标均不超过对应维的上界。其运算结果是返回由下标指定的A中的 对应元素的值。 (2) assign(A，e，indexl，index2，…，indexd)：A 是已存在的 d 维数组， e 为元素变量， indexl，index2，…，indexd 是指定的 d 个 下标值，且这些下标均未越界。其运算结果是将 e 的值赋给由下标 指定的A中的对应元素。
2．二维数组
二维数组，又称矩阵 (matrix)。二维数组中的每一个元素又是
一个定长的线性表（一维数组），都要受到两个关系即行关系和 列关系的约束，也就是每个元素都同属于两个线性表。例如，设A
是一个有m行n列的二维数组，则A可以表示为：
2018/10/10 5
A
m × n
=
a0,0 a0,1 … a0,n-1 a1,0 a1, … a1,n-1 1 … … … … am -1,0 am -1,1… am -1,n-1
2018/10/10 6
显然，二维数组同样满足数组的定义。一个二维数组可以看 作是每个数据元素都是相同类型的一维数组。以此类推，任何多 维数组都可以看作一个线性表，这时线性表中的每个数据元素也
是一个线性表。多维数组是特殊的线性表，是线性表的推广。
数组的性质： (1) 数组中的数据元素数目固定。一旦定义了一个数组，其数据 元素数目不再有增减变化。它属于静态分配存储空间的数据结构。 (2) 数组中的数据元素必须具有相同的数据类型。 (3) 数组中的每个数据元素都有一组唯一的下标值。 (4) 数组是一种随机存储结构。可随机存取数组中的任意数 据元素。
2018/10/10
4
1．一维数组
一维数组可以看成是一个线性表或一个向量，它在计算机内是 存放在一块连续的存储单元中，适合于随机查找。
一维数组记为A[n]或A=( a0，al，…ai，…，an-1)
一维数组中，一旦a0的存储地址、一个数据元素所占存储单元 数k确定，则ai的存储地址LOC(ai)就可求出： LOC(ai)=LOC(a0)+i*k (0≤i<n)
是一个线性表，而线性子表中的每一个数据元素还可以再分 解…… 。根据数组元素ai的组织形式不同，数组可以分为一维数 组、二维数组以及多维（n维）数组。
2018/10/10 3
有时也把一维数组称为向量，二维数组称为矩阵。在二 维或多维数组中，每个数组元素都受到2个或n个关系的约
束。当数组为n维时，其对应线性表中的每个元素又是一个
2018/10/10
9
5.1.3 数组的存储结构
由于数组一般不作删除或插入运算，所以一旦数组被定义后， 数组中的元素个数和元素之间的关系就不再变动。通常采用顺序存 储结构表示数组。 对于一维数组，数组的存储结构关系为: LOC(ai)=LOC(a0)+i * k (0≤i<n)
对于二维数组，由于计算机的存储单元是一维线性结构，如何 用线性的存储结构存放二维数组元素就有行/列次序问题。常用两 种存储方法：以行序(row major order)为主序的存储方式和以列 序(column major order)为主序的存储方式。
2018/10/10Fra bibliotek8(3) disp(A)：输出数组A的所有元素。
在大多数程序设计语言中，取数组元素值操作value(A，indexl， index2，…，indexd) 通常直接写作A[indexl][ index2]…[indexd] ，而对数组元素的赋值操作assign(A，e，indexl，index2，…， indexd)写作e= A[indexl][ index2]…[indexd]，或者类似的形式。