数组和广义表.ppt

1、第五章数组和广义表，5.1数组的定义5.2数组的顺序表现和实现5.3.1特殊矩阵5.3.2稀疏矩阵5.4广义表的概念，5.1数组的定义数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可用的数据类型。 阵列中的每个元素具有统一的类型，阵列元素的下标通常具有固定的上边界和下边界，因此阵列的处理比其他复杂结构简单。 多维数组是向量的推广。 例如，二维排列： a11 a-12 a-1 n a-21 a-22 n am-1 amn，Amn=，既可以视为由各个行向量构成的向量，也可以视为由各个列向量构成的向量。 在c语言中，二维数组类型可定义为组件类型为一维数组类型的一维数组类型，即typede

2、f elemtype array2mn。 等效：类型电子阵列1 n； 类型阵列1阵列2 m； 同样，可将一个维数组类型定义为数据元素为维数组类型的一维顺序组类型。 定义数组后，其维数和维边界保持不变。 因此，数组只有访问元素和修改元素值的操作，结构初始化和丢弃除外。5.2数组的顺序表示和实现、一维数组、LOC (i )=LOC (i -1 ) l= i*l、二维数组、行优先LOC (j，k)=的i3、in的数组元素的存储地址：数组的顺序存储表现和实现、p93-94、 5.3矩阵的压缩存储是科学和工程学校正问题中，矩阵是常用的数学对象，用高级语言编程时，简单自然的方法是将一个矩阵描述为一个二维阵

3、列。 矩阵在这样的记忆表示下，能够随机访问其要素，各种矩阵运算也非常简单，记忆的密度是1。 然而，在矩阵中非零元素有规律地分布的情况下，或者在矩阵中出现大量的零元素时，存储密度可看起来仍为1，而实际上存储占有许多小区而重叠的非零元素或零元素对于给高维矩阵带来极大浪费的零元素而言是浪费的5.3矩阵的压缩存储器、特殊矩阵对称矩阵三角矩阵对角矩阵稀疏矩阵、5.3.1特殊矩阵是指在非零元素或零元素分布中具有一定规则的矩阵。 下面讨论几个特殊矩阵的压缩存储器。 1 .对称矩阵满足在一个n阶正方阵a中如果元素是aij=aji 0i，jn-1则将a称为对称矩阵的性质。 图5.1是五阶对称矩阵。 由于对称矩阵

4、中的元素关于主对角线对称，所以如果存储矩阵中的上三角形或下三角形的元素，并且为每两个对称的元素共享一个存储空间，则可以节省接近一半的存储空间。 在不失一般性的情况下，将主对角线(包括对角线)以下的元素存储在“行优先、顺序”中，其存储形式如图所示，1513 a 0050 a 11826 a 20 a 2305.70613 an-1 an-1 an-1 n-11图5.1的对称矩阵在此由于在第I行上正好有i 1个元素，元素的总数为(i 1)=n(n 1)/2，所以可以按图中箭头所示的顺序将这些元素存储在向量sa0.n(n 1)/2-1中。 为了便于访问对称矩阵a的元素，aij和sak、对称矩阵aij

5、=aji，必须用主对角线分隔，三角矩阵有上三角和下三角两种。 上三角矩阵如图所示，其下三角(除了主对角线)的要素都是常数。 下三角矩阵相反，如图所示，在主对角线上有常数。 在大多数情况下，三角矩阵常数为零。三角矩阵被压缩为向量sa0.n(n 1)/2，因为正好有n(n 1)/2个上三角矩阵(b )下三角矩阵的预定元素其中，c存储在向量的最后的分量中，上三角矩阵中，主对角线上的第p行(0pj，k=)中存储的sak和aij的对应关系为i(i 1)/2 j ij n(n 1)/2 ij 3，对角矩阵对角矩阵中全部的非零元素集中在以主对角线为中心的带状区域下图显示了三对角矩阵a00 a01 a10 a

6、11 a12 a21 a22 a23图5.3对角矩阵an-2 n-3 an-1 an-1 n-2 an-1 n-1 n-1、 显然，在i-j1的情况下，要素aij=0。 由此可知，一个k对角矩阵(k为奇数) a是如果是i-j(k-1)/2则满足要素aij=0的条件的矩阵。 对角矩阵可以按行的优先级或对角线顺序进行压缩并存储在一个向量中，也可以找到0以外的各元素与向量下标的对应关系。 的双曲馀弦值。 什么是稀疏矩阵？ 在感觉上有很多要素为零的矩阵。 假设矩阵a中有s个非零的元素，如果s远小于矩阵元素的总数(即smn )，那么就将a称为稀疏矩阵。 在被设定为(量化)的矩阵a中，有s个非零的要素。

7、设e=s/(m*n )，将e称为矩阵的稀疏因子。 一般认为e0.05被称为稀疏矩阵。稀疏矩阵、稀疏矩阵、行数m=6、列数n=7、非零元素数t=8稀疏系数=0.05在存储稀疏矩阵时，为了节省存储单元自然希望使用压缩存储方法。 但是，非零要素的分布一般是不规则的，所以在容纳非零要素的同时，也必须同时记录其存在的行和列的位置(I，j )。 与此相对，3个组(I，j，aij )唯一确定矩阵a的非零元素。 因此，稀疏矩阵可由表示非零元的三元组及其矩阵数唯一确定。 假定稀疏矩阵用连续的存储结构表示三维组表，那么稀疏矩阵的压缩存储方法可以获得三维顺序表。 定义最大尺寸10000类型定义数据类型； 类型构造指数，j； 数据类型v； 三重；三维节目顺序表、稀疏矩阵的压缩存储示例、a的三维节目顺序表图、A=、0129000000000-3001400240018000150-70，例如ma1.row=0。 ma1.col=1，ma1.value=12，稀疏矩阵，转置矩阵，用三元组表示的稀疏矩阵及其转置，5.4广义表(General Lists )，广义表的概念n (0) n是表的长度。 n=0的广义表是空表。 在n 0的情况下，将表的第一显示要素称为广义表的标题(head )，将除此以外的由显示要素构成的表(a1、a2、an-