多维数组与广义表课件

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语言中的描述typedef int datatype;dat

2、atype array1N; datatype array2MN;datatype array3XYZ; 数组一旦被定义，它的维数和维界就不再改变。因此，数组只有存取元素和修改元素值的操作。考虑问题的基本出发点： 计算机的内存结构是一维的。因此用一维内存来存多维数组，就必须按某种次序将数组元素排成线性序列。数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。5.2 多维数组的存储两种顺序存储方式行优先顺序将数组元素按行排列在PASCAL、C语言中，数组就是按行优先顺序存储的。列优先顺序将数组元素按列向量排列在FORTRAN语言中，数组就是按列

3、优先顺序存储的。推广到多维数组的情况：行优先顺序：先排最右下标，从右到左，最后排最左下标列优先顺序：先排最左下标，从左向右，最后排最右下标。计算机如何实现数组元素的随机存取？ 按上述两种方式顺序存储的序组，只要知道：开始结点的存放地址（即基地址），维数每维的上、下界每个数组元素所占用的单元数， 就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。如何计算数组元素的地址？一维数组二维数组三维数组如何计算数组元素的地址？内存0ListSize -1a0a1a2an a00 a01 a0n-1 a10 a11 a1n-1

4、 . am-1 0 am-1 1 am-1 n-1 a00 a01 a0n-1 a10 a11 a1n-1 . am-1 0 am-1 1 am-1 n-1 a0a1an内存a00a0na10a1n假设数组各维的下界是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更一般的二维数组是Ac1.d1,c2.d2，这里c1,c2不一定是1。 aij的地

5、址计算函数为： LOC(aij)=LOC(ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*d 例如，在C语言中，数组各维下标的下界是0，因此在C语言中，二维数组的地址计算公式为： LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d 最基本的原理Ai1in的起始地址=第一个元素的起始地址该元素前面的元素个数单位长度程序员试题2006-1对于二维数组a04,15，设每个元素占1个存储单元，且以行为主序存储，则元素a2,1相对于数组空间起始地址的偏移量是_(40)_。(40)A5 B10 C15D25 2003设数组a3.16，5.20的元素以列为主序存放，每个元素占用两个

6、存储单元，则数组元素ai,j(3i16，5j20)的地址计算公式为_(11)_。(11)Aa-118+2i+28jBa-116+2i+28j Ca-144+2i+28j Da-146+2i+28j2001二维数组 X 的行下标范围是05,列下标范围是18,每个数组元素占六个字节,则该数组的体积为_(6)_个字节,若已知 X 的最后一个元素的起始字节地址为382,则 X 的首地址(即第一个元素的起始字节地址)为 _(7)_,记为 Xd。若按行存储,则 X1,5 的起始地址是 _(8)_, 结束字节地址是 _(9)_。若按列存储,则 X4,8的起始字节地址为_(10)_。(6): A.210 B.

7、240 C.288 D.294(7): A.0 B.6 C.94 D.100(8): A.Xd+24 B.Xd+72 C.Xd+78 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(6)C(7)D(8)B(9)B(10)D5.2 矩阵的压缩存储在编程时，简单而又自然的方法，是将矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取。 但是在一些特殊矩阵中，非零元素呈某种规律分布或者矩阵中有大量的零元素，如果仍用二维数组存，会造成极大的浪费，尤其是处理高阶

8、矩阵的时候。 为了节省存储空间， 我们可以对这类矩阵进行压缩存储。5.2.1 几种常见的特殊矩阵1234523456345674567856789对称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji 0i,jn-1，则称A为对称矩阵。特征：元素关于主对角线对称压缩存储的办法： 只存矩阵中上三角或下三角中的元素。所需空间：三角矩阵特征：上三角矩阵中，主对角线的下三角中的元素均为常数。在大多数情况下，常数为零。下三角矩阵正好相反。压缩方法：只存上(下)三角阵中上(下)三角中的元素常数c可共享一个存储空间所需空间：12345034560056700078000091234543456445

9、67444784444910000230003650047970581291444423444365444797458129对角矩阵特征：所有的非零元素集中在以主对角线为中心的带状区域中， 即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。压缩存储的办法： 只存对角线上的元素。存三对角矩阵所需的空间：1100023700045300067500089三对角矩阵特征：只有少量非零元素，且非零元素的分布没有规律。压缩存储的办法： 只存非零元素。所需空间：与非零元素的个数和存储方式有关。稀疏矩阵12005030000400000600000805.2.2 特殊矩阵的压缩存储

10、矩阵类型对称矩阵三角矩阵对角矩阵压缩的基本思想：只存有用的元素由用二维数组改为用一维数组来存放说明：按C语言中规定，下标从0开始不失一般性，按“行优先顺序”存储关键问题如何确定一维数组的大小？如何确定矩阵元素在一维数组中的位置？从而保证对矩阵元素的随机存取Aij的位置=该元素前的元素个数= 所需空间123345456712345234563456745678567891 . 对称矩阵如何确定一维数组的大小？设：存放下三角阵中的元素，则：如何确定元素Aij在一维数组中的位置？123345456712345234563456745678567892. 三角矩阵1444423444365444797

11、4581291233654如何确定一维数组的大小？设：在下三角阵中，则：如何确定元素Aij在一维数组中的位置？3.三对角矩阵1100023700045300067500089如何确定一维数组的大小？如何确定元素Aij在一维数组中的位置？1123745367589在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 将一个三对角矩阵Al.100，1.100中的元素按行存储在一维数组B

12、l.298中，矩阵A中的元素A66,65在数组B中的下标为_(4)_。 (4) A195 B196C197D1985.2.3 稀疏矩阵的压缩存储顺序存储：三元组表链式存储：十字链表1.三元组表存稀疏矩阵考虑：只存非零元素一个非零元素的必需信息有： (i, j, aij)记录一个稀疏矩阵的必需信息有：行数M，列数N，非零元素个数T1200503000040000060000080ijAij001012045113214326438M=5N=5T=7三元组表的C语言描述#define maxsize 10000typedef int datatype;typedef struct /*三元组结点*

13、/ int i,j; datatype v; TriTupleNode;typedef struct TriTupleNode datamaxsize; /*三元组表*/ int m,n,t;/*稀疏矩阵的行数,列数,非零元素个数*/ TriTupleTable; ijV2带行指针的三元组表把具有相同行号的非零元用一个单链表连接起来，稀疏矩阵中的若干行组成若干个单链表，合起来称为带行指针的链表。029000000000-300004002400001800001500-7003.十字链表ijVal/Next列指针col行指针row5.2.4应用举例： 稀疏矩阵的转置1.矩阵转置的数学解释 一个

14、mn的矩阵A，它的转置B是一个nm的矩阵，且aij=bji，0im，0jn。Aij=Bji2.利用三元组表实现转置120030040006ijAij001012113214326M=4N=2T=5100023400006ijBij001012113214326M=2N=4T=5Aij=Bji思想一：直接交换a.data中i和j的内容 问题：b.data是一个按列优先顺序存储的稀疏矩阵B 解决方法：重新排列B中三元组的顺序。025030040006ijAij012025113214326M=4N=2T=5000023405006ijBij102205113124236Aij=BjiijBij10

15、2113124205236按i排序M=2N=4T=5b.m=a.n; b.n=a.m; b.t=a.t; /*基本信息的赋值*/*按交换i、j的方式给B的三元组赋值*/for ( i=0; ib.t; i+ ) b.datai.i=a.datai.j; b.datai.j=a.datai.i; b.datai.v=a.datai.v;/*扫描B，按i排序*/ijAij012025113214326M=4N=2T=5ijBij102205113124236ijBij102113124205236按i排序M=2N=4T=5思想二：在A中按列序找三元组，写入BB的行优先即A的列优先对A的第col列

16、，扫描三元组表a.data，找出所有列号等于col的三元组，将它们的行号和列号互换后依次放入b.data中，即可得到B的按行优先的压缩存储表示。025030040006ijAij012025113214326M=4N=2T=5000023405006Aij=BjiijBij102113124205236M=2N=4T=5col=0，没有匹配的三元组col=1，找到2，3，4col=2，找到5，6 Void transmatrix(tripletable a,tripletable b) int pa, pb, col; b.m=a.n; b.n=a.m; b.t=a.t; /*基本信息的赋值*

17、/ if(b.t=0) printf(“A=0n”); return 0; /*无非零元素*/ pb=0; /*pb指向三元组表B中的当前位置*/ for(col=0;cola.n;col+) /*按列col扫描表A*/ for(pa=0;pa=a.t;pa+) /*pb指向表A中的当前位置*/ /*找所有列号等于col的三元组，i,j互换写放入B*/ if(a.datapa.j=col) b.datapb.i=a.datapa.j; b.datapb.j=a.datapa.i; b.datapb.v=a.datapa.v; pb+; 算法分析 主要的工作是在pa和col的两个循环中完成的，故

18、算法的时间复杂度为O(n*t)，即矩阵的列数和非零元的个数的乘积成正比。传统矩阵的转置算法的时间复杂度为O(n*m)当非零元素的个数t和m*n同数量级时，该算法的时间复杂度为O(m*n2)。（最坏情况）三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算法的难度。因此，此算法仅适用于t=m*n的情况。思想三：快速转置基本思想：在A中按行序找三元组，确定该三元组在B中的位置，写入B.关键问题：如何确定每个三元组在B中的位置A中三元组在B的中位置= 每列的第一个非零元素在数组B中应有的位置 + 每一列非零元素的个数025030040006ijAij01202

19、5113214326M=4N=2T=5000023405006Aij=BjiijBij102113124205236M=2N=4T=5col列号012cposi每列第一个非零元素在B中的位置003cnumi每列非零元素个数032由递推关系得出cpos的值：cpos0=0cposi=cposi-1+cnumi-1void fasttranstri(tritupletable b, tritupletable a) int col；/*当前列号*/ int pa, pb; /*pa,pb:三元组a,b的下标*/ int cnum0.a.n, cpos0.a.n; b基本信息m,n,t的赋值； 若a

20、无非零元素，则返回； 初始化数组cnum； /*统计a中每列非零元素的个数；*/ for(pa=0; paa.t; pa+) col=a.datapa.j; cnumcol+; /*由递推关系计算cpos的值*/ cpos0=0; for(col=1;col=a.n;col+) cposcol = cposcol-1 + cnumcol-1; /*扫描a，将元素交换i,j写入b*/ for( pa=0; paa.t; pa+ ) col = a.datap.j; pb = cpotcol; b.datapb.i = a.datapa.j; b.datapb.j = a.datapa.i; b.datapb.v = a.datapa.v; cposcol+; 算法分析时间复杂度O（n+t）。当非零元素的个数t和m*n同数量级时，该算法的时间复杂度为O(m*n)，与不压缩存储的情况相同。5.3 广义表5.5.1 基本概念广义表是第2章提到的线性表的推广。线性表中的元素仅限于原子项，即不可以再分，而广义表中的元素既可以是原子项，也可以是子表（另一个线性表）。1广义表的定义广义表是n0个元素a1，a2，an