石河子大学信息科学与技术学院数据结构课件第五章 数组.ppt

第五章 数组 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 一维数组  M和N的三元组、和分别为： i j v i j v i j v 1 1 3 1 2 2 1 2 6 1 4 5 2 1 1 2 1 -1 3 2 -1 3 1 -2 3 2 4 3 1 2 3 2 4 Q.data M.data N.data 当M和N是稀疏矩阵并用三元组表存储结构时，经典算法不再适用。 稀疏矩阵相乘的基本思想是： 对于M中每个元素M.data[p]，找到N 中所有满足条件M.data[p].j==N.data[q].i的元素N.data[q]，求得M.data[p].e和N.data[q].e的乘积，而从求乘积的式子得知，乘积矩阵Q中每个元素的值是个累加和，这个乘积M.data[p].e * N.data[q].e只是其中的一部分。为了便于操作，应对每个元素设一累加和的变量，其初值为零，然后扫描三元组表M，求得相应元素的乘积并累加到适当的累加器上。 算法参见P102 row col val down right 1 1 3 4 1 8 2 2 5 2 3 4 ^ ^ ^ ^ ^ ^ ^ 链式存储结构（十字链表） 设行指针数组和列指针数组，分别指向每行、列第一个非零元。 结点： 广义表也称为列表，是线性表的一种扩展。 记作：LS=(d1,d2, . . . . . .dn)其中di既可以是单个元素，也可以是广义表。 说明: 1）广义表的定义是一个递归定义，因为在描述广义表时又用到了广义表； 2）在线性表中数据元素是单个元素，而在广义表中， 元素可以是单个元素, 称为单元素(原子)，也可以是广义表，称为广义表的子表； 3）n 是广义表长度； 5.4 广义表的定义 什么是广义表 * 数据结构 * 《 数据结构》 第五章 数组 数组可看成是一种特殊的线性表，其特殊在于，表中的元素本身也是一种线性表。 5.1 数组的定义 多维数组是向量（一维数组）的推广。 例如，二维数组： a00 a01 … a0,n-1 a10 a11 … a1,n-1 … … … … am-1,0 am-1,1 … am-1,n-1 Amn= 数组的抽象类型定义参见P90。 在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说， typedef ElemType Array2[m][n]; 等价于： typedef ElemType Array1[n]; typedef Array1 Array2[m]; 数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组的基本操作只有存取元素和修改元素值的操作。 5.2 数组的顺序表示和实现 由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一个序列，然后将这个线性序列存放在存储器中。 又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。 通常有两种顺序存储方式： 低下标优先 高下标优先 对二维数组而言： ⑴以行序为主序——将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。 在C语言中，数组就是按行优先顺序存储的。 ⑵以列序为主序——将数组元素按列排列，第i+1个列向量紧接在第i个列向量后面。 在FORTRAN语言中，数组就是按列优先顺序存储的。 只要知道开始结点的存放地址（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的