第五章 多维数组与广义表.ppt
《第五章 多维数组与广义表.ppt》由会员分享,可在线阅读,更多相关《第五章 多维数组与广义表.ppt(50页珍藏版)》请在三一文库上搜索。
1、第五章 多维数组与广义表,5.1 多维数组 5.1.1多维数组的定义 5.1.2多维数组的存储 5.2 矩阵的压缩存储 5.2.1 特殊矩阵 5.2.2 稀疏矩阵 5.3 广义表,5.1 多维数组,5.1.1多维数组的定义,一维数组 一维数组可以看成是一个线性表或一个向量,它在计算机内是存放在一块连续的存储单元中,适合于随机查找。 有一个直接前驱和一个直接后继 二维数组 二维数组可以看成是向量的推广。 有两个直接前驱和两个直接后继,三维数组 最多可有三个直接前驱和三个直接后继 多维数组 把三维以上的数组称为多维数组, 可有多个直接前驱和多个直接后继 是一种非线性结构。,在C语言中的描述,typ
2、edef int datatype; datatype array1N; datatype array2MN; datatype array3XYZ; 数组一旦被定义,它的维数和维界就不再改变。因此,数组只有存取元素和修改元素值的操作。,考虑问题的基本出发点: 计算机的内存结构是一维的。因此用一维内存来存多维数组,就必须按某种次序将数组元素排成线性序列。 数组一旦建立,结构中的元素个数和元素间的关系就不再发生变化。因此,一般都是采用顺序存储的方法来表示数组。,5.2 多维数组的存储,两种顺序存储方式,行优先顺序将数组元素按行排列 在PASCAL、C语言中,数组就是按行优先顺序存储的。 列优先顺
3、序将数组元素按列向量排列 在FORTRAN语言中,数组就是按列优先顺序存储的。 推广到多维数组的情况: 行优先顺序:先排最右下标,从右到左,最后排最左下标 列优先顺序:先排最左下标,从左向右,最后排最右下标。,计算机如何实现数组元素的随机存取?,按上述两种方式顺序存储的序组,只要知道: 开始结点的存放地址(即基地址), 维数 每维的上、下界 每个数组元素所占用的单元数, 就可以将数组元素的存放地址表示为其下标的线性函数。因此,数组中的任一元素可以在相同的时间内存取,即顺序存储的数组是一个随机存取结构。,如何计算数组元素的地址?,一维数组 二维数组 三维数组,如何计算数组元素的地址?,内存,0,
4、ListSize -1,内存,假设数组各维的下界是1,按“行优先顺序”存储,假设每个元素占用d个存储单元。 二维数组Amn, aij的地址计算函数为: LOC(aij)=LOC(a11)+(i-1)*n+j-1*d 三维数组Amnp,aijk的地址计算函数为: LOC(aijk)=LOC(a111)+(i-1)*n*p+(j-1)*p +(k-1)*d,更一般的二维数组是Ac1d1,c2d2,这里c1,c2不一定是1。 aij的地址计算函数为: LOC(aij)=LOC(ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*d 例如,在C语言中,数组各维下标的下界是0,因此在C语言中,二
5、维数组的地址计算公式为: LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d,最基本的原理,Ai1in的起始地址,=,第一个元素的起始地址,该元素前面的元素个数,单位长度,程序员试题,2006-1,对于二维数组a04,15,设每个元素占1个存储单元,且以行为主序存储,则元素a2,1相对于数组空间起始地址的偏移量是_(40)_。 (40)A5 B10 C15 D25,2003,设数组a316,520的元素以列为主序存放,每个元素占用两个存储单元,则数组元素ai,j(3i16,5j20)的地址计算公式为_(11)_。 (11)Aa-118+2i+28j Ba-116+2i+28j C
6、a-144+2i+28j Da-146+2i+28j,2001,二维数组 X 的行下标范围是05,列下标范围是18,每个数组元素占六个字节,则该数组的体积为_(6)_个字节,若已知 X 的最后一个元素的起始字节地址为382,则 X 的首地址(即第一个元素的起始字节地址)为 _(7)_,记为 Xd。若按行存储,则 X1,5 的起始地址是 _(8)_, 结束字节地址是 _(9)_。若按列存储,则 X4,8的起始字节地址为_(10)_。 (6): A.210 B.240 C.288 D.294 (7): A.0 B.6 C.94 D.100 (8): A.Xd+24 B.Xd+72 C.Xd+78
7、D.Xd+144 (9): A.Xd+29 B.Xd+77 C.Xd+83 D.Xd+147 (10):A.Xd+186 B.Xd+234 C.Xd+270 D.Xd+276,5.2 矩阵的压缩存储,在编程时,简单而又自然的方法,是将矩阵描述为一个二维数组。矩阵在这种存储表示之下,可以对其元素进行随机存取。 但是在一些特殊矩阵中,非零元素呈某种规律分布或者矩阵中有大量的零元素,如果仍用二维数组存,会造成极大的浪费,尤其是处理高阶矩阵的时候。 为了节省存储空间, 我们可以对这类矩阵进行压缩存储。,5.2.1 几种常见的特殊矩阵,对称矩阵,在一个n阶方阵A中,若元素满足下述性质:aij=aji 0
8、i,jn-1,则称A为对称矩阵。 特征:元素关于主对角线对称 压缩存储的办法: 只存矩阵中上三角或下三角中的元素。 所需空间:,三角矩阵,特征: 上三角矩阵中,主对角线的下三角中的元素均为常数。在大多数情况下,常数为零。 下三角矩阵正好相反。 压缩方法: 只存上(下)三角阵中上(下)三角中的元素 常数c可共享一个存储空间 所需空间:,对角矩阵,特征: 所有的非零元素集中在以主对角线为中心的带状区域中, 即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外,其余元素皆为零。 压缩存储的办法: 只存对角线上的元素。 存三对角矩阵所需的空间:,三对角矩阵,特征:只有少量非零元素,且非零元素的分
9、布没有规律。 压缩存储的办法: 只存非零元素。 所需空间:与非零元素的个数和存储方式有关。,稀疏矩阵,5.2.2 特殊矩阵的压缩存储,矩阵类型 对称矩阵 三角矩阵 对角矩阵 压缩的基本思想: 只存有用的元素 由用二维数组改为用一维数组来存放 说明: 按C语言中规定,下标从0开始 不失一般性,按“行优先顺序”存储,关键问题 如何确定一维数组的大小? 如何确定矩阵元素在一维数组中的位置?从而保证对矩阵元素的随机存取,Aij的位置,=,该元素前的元素个数,= 所需空间,1 . 对称矩阵,如何确定一维数组的大小?,设:存放下三角阵中的元素, 则:如何确定元素Aij在一维数组中的位置?,2. 三角矩阵,
10、如何确定一维数组的大小?,设:在下三角阵中, 则:如何确定元素Aij在一维数组中的位置?,3.三对角矩阵,如何确定一维数组的大小?,如何确定元素Aij在一维数组中的位置?,在Aij之前有i行,共有3*i-1个非零元素, 在第i行, aij之前有j-i+1个非零元素,,3*i-1+(j-i+1) = 2*i+j,程序员试题,2004-1 对矩阵压缩存储的主要目的是_(5)_。 (5) A方便运算 B节省存储空间 C降低计算复杂度 D提高运算速度 2003 将一个三对角矩阵Al100,1100中的元素按行存储在一维数组Bl298中,矩阵A中的元素A66,65在数组B中的下标为_(4)_。 (4)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五章 多维数组与广义表 第五 多维 数组 广义
链接地址:https://www.31doc.com/p-3027776.html