多维数组与广义表课件.ppt

1、第五章第五章 多维数组与广义表多维数组与广义表5.1 多维数组5.1.1多维数组的定义5.1.2多维数组的存储5.2 矩阵的压缩存储 5.2.1 特殊矩阵 5.2.2 稀疏矩阵5.3 广义表5.15.1 多维数组多维数组5.1.15.1.1多维数组的定义多维数组的定义一维数组一维数组可以看成是一个线性表或一个向量，它在计算机内是存放在一块连续的存储单元中，适合于随机查找。有一个直接前驱和一个直接后继二维数组二维数组可以看成是向量的推广。有两个直接前驱和两个直接后继a00 a01 a0n-1 a10 a11 a1n-1.A=am-1 0 am-1 1 am-1 n-1 三维数组最多可有三个直接前

2、驱和三个直接后继多维数组把三维以上的数组称为多维数组，可有多个直接前驱和多个直接后继是一种非线性结构。在在C C语言中的描述语言中的描述typedef int datatype;datatype array1N;datatype array2MN;datatype array3XYZ;数组一旦被定义，它的维数和维界就不再改变。因此，数组只有存取元素和修改元素值的操作。考虑问题的基本出发点：计算机的内存结构是一维的。因此用一维内存来存多维数组，就必须按某种次序将数组元素排成线性序列。数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。5.2 5

3、.2 多维数组的存储多维数组的存储两种顺序存储方式两种顺序存储方式行优先顺序将数组元素按行排列在PASCAL、C语言中，数组就是按行优先顺序存储的。列优先顺序将数组元素按列向量排列在FORTRAN语言中，数组就是按列优先顺序存储的。推广到多维数组的情况：行优先顺序：先排最右下标，从右到左，最后排最左下标列优先顺序：先排最左下标，从左向右，最后排最右下标。计算机如何实现数组元素的随机存取？计算机如何实现数组元素的随机存取？按上述两种方式顺序存储的序组，只要知道：开始结点的存放地址（即基地址），维数每维的上、下界每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数

4、组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。如何计算数组元素的地址？如何计算数组元素的地址？一维数组二维数组三维数组如何计算数组元素的地址？如何计算数组元素的地址？内存0ListSize-1a0a1a2an a00 a01 a0n-1 a10 a11 a1n-1.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的地址计算函数为：L

5、OC(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的地址计算函数为：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的起始地址=第一个元素的起始地址该元素

6、前面的元素个数单位长度程序员试题程序员试题2006-12006-1对于二维数组a04,15，设每个元素占1个存储单元，且以行为主序存储，则元素a2,1相对于数组空间起始地址的偏移量是_(40)_。(40)A5 B10 C15D25 20032003设数组a3.16，5.20的元素以列为主序存放，每个元素占用两个存储单元，则数组元素ai,j(3i16，5j20)的地址计算公式为_(11)_。(11)Aa-118+2i+28jBa-116+2i+28j Ca-144+2i+28j Da-146+2i+28j20012001二维数组 X 的行下标范围是05,列下标范围是18,每个数组元素占六个字节,

7、则该数组的体积为_(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 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

8、.Xd+276(6)C(7)D(8)B(9)B(10)D5.25.2 矩阵的压缩存储矩阵的压缩存储在编程时，简单而又自然的方法，是将矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取。但是在一些特殊矩阵中，非零元素呈某种规律分布或者矩阵中有大量的零元素，如果仍用二维数组存，会造成极大的浪费，尤其是处理高阶矩阵的时候。为了节省存储空间，我们可以对这类矩阵进行压缩存储。5.2.15.2.1 几种常见的特殊矩阵几种常见的特殊矩阵1 12 23 34 45 52 23 34 45 56 63 34 45 56 67 74 45 56 67 78 85 56 67 78 89 9对

9、称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji 0i,jn-1，则称A为对称矩阵。特征：元素关于主对角线对称压缩存储的办法：只存矩阵中上三角或下三角中的元素。所需空间：2)1()1(10nniNni三角矩阵三角矩阵特征：上三角矩阵中，主对角线的下三角中的元素均为常数。在大多数情况下，常数为零。下三角矩阵正好相反。压缩方法：只存上(下)三角阵中上(下)三角中的元素常数c可共享一个存储空间所需空间：1 12 23 34 45 50 03 34 45 56 60 00 05 56 67 70 00 00 07 78 80 00 00 00 09 91 12 23 34 45 54 43

10、 34 45 56 64 44 45 56 67 74 44 44 47 78 84 44 44 44 49 91 10 00 00 00 02 23 30 00 00 03 36 65 50 00 04 47 79 97 70 05 58 81 12 29 91 14 44 44 44 42 23 34 44 44 43 36 65 54 44 44 47 79 97 74 45 58 81 12 29 912)1(nnN对角矩阵对角矩阵特征：所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。压缩存储的办法：只存对角

11、线上的元素。存三对角矩阵三对角矩阵所需的空间：1 11 10 00 00 02 23 37 70 00 00 04 45 53 30 00 00 06 67 75 50 00 00 08 89 9三对角矩阵三对角矩阵23 nN特征：只有少量非零元素，且非零元素的分布没有规律。压缩存储的办法：只存非零元素。所需空间：与非零元素的个数和存储方式有关。稀疏矩阵稀疏矩阵1 12 20 00 05 50 03 30 00 00 00 04 40 00 00 00 00 06 60 00 00 00 00 08 80 05.2.25.2.2 特殊矩阵的压缩存储特殊矩阵的压缩存储矩阵类型对称矩阵三角矩阵对角

12、矩阵压缩的基本思想：只存有用的元素由用二维数组改为用一维数组来存放说明：按C语言中规定，下标从0开始不失一般性，按“行优先顺序”存储关键问题如何确定一维数组的大小？如何确定矩阵元素在一维数组中的位置？从而保证对矩阵元素的随机存取Aij的位置=该元素前的元素个数=所需空间12334545671 12 23 34 45 52 23 34 45 56 63 34 45 56 67 74 45 56 67 78 85 56 67 78 89 91 1 .对称矩阵对称矩阵如何确定一维数组的大小？2)1(nnN设：存放下三角阵中的元素，则：如何确定元素Aij在一维数组中的位置？12334545671 1

13、2 2 3 3 4 4 5 52 2 3 3 4 4 5 5 6 63 3 4 4 5 5 6 6 7 74 4 5 5 6 6 7 7 8 85 5 6 6 7 7 8 8 9 9在下三角阵中当根据在上三角阵中当ijjiijijAjijiiAAjiijjijALoc,2)1()A(,2)1()(2.2.三角矩阵三角矩阵1 14 44 44 44 42 23 34 44 44 43 36 65 54 44 44 47 79 97 74 45 58 81 12 29 912)1(nnN1233654如何确定一维数组的大小？设：在下三角阵中，则：如何确定元素Aij在一维数组中的位置？即下三角阵中的

14、元素，当即下三角阵中的常数，当,2)1(2)1()(jijiijinnijALoc3.3.三对角矩阵三对角矩阵1 11 10 00 00 02 23 37 70 00 00 04 45 53 30 00 00 06 67 75 50 00 00 08 89 923 nN如何确定一维数组的大小？如何确定元素Aij在一维数组中的位置？1123745367589)(ijALoc在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节省存储

15、空间 C降低计算复杂度D提高运算速度2003 将一个三对角矩阵Al.100，1.100中的元素按行存储在一维数组Bl.298中，矩阵A中的元素A66,65在数组B中的下标为_(4)_。(4)A195 B196C197D1985.2.3 5.2.3 稀疏矩阵的压缩存储稀疏矩阵的压缩存储顺序存储：三元组表链式存储：十字链表1.1.三元组表存稀疏矩阵三元组表存稀疏矩阵考虑：只存非零元素一个非零元素的必需信息有：(i,j,aij)记录一个稀疏矩阵的必需信息有：行数M，列数N，非零元素个数T1 12 20 00 05 50 03 30 00 00 00 04 40 00 00 00 00 06 60 0

16、0 00 00 00 08 80 0ijAij001012045113214326438M=5N=5T=7三元组表的三元组表的C C语言描述语言描述#define maxsize 10000typedef int datatype;typedef struct /*三元组结点*/int i,j;datatype v;TriTupleNode;typedef struct TriTupleNode datamaxsize;/*三元组表*/int m,n,t;/*稀疏矩阵的行数,列数,非零元素个数*/TriTupleTable;i ij jV V2 2带行指针的三元组表带行指针的三元组表把具有相同

17、行号的非零元用一个单链表连接起来，稀疏矩阵中的若干行组成若干个单链表，合起来称为带行指针的链表。0 1 2 0 行指针 1 3 4 5 2 0 2 9 2 5 4 5 3 -7 2 0 -3 3 2 24 4 1 18 5 0 15 0 02 29 90 00 00 00 00 00 00 00 00 0-3-3 0 00 00 00 04 40 00 0 2424 0 00 00 00 0 1818 0 00 00 00 01515 0 00 0-7-7 0 00 03.3.十字链表十字链表i ij jVal/NexVal/Next t列指针col 行指针row 6 7 0 0 0 0 0

18、0 0 0 0 0 0 0 0 0hm 0 1 12 0 2 9 0 0 0 0 0 0 2 0-3 2 5 14 0 0 3 2 24 0 04 118 0 0 5 0 15 5 3-75.2.45.2.4应用举例：应用举例：稀疏矩阵的转稀疏矩阵的转置置1.矩阵转置的数学解释 一个mn的矩阵A，它的转置B是一个nm的矩阵，且aij=bji，0im，0jn。007650020060052700Aij=Bji2.2.利用三元组表实现转置利用三元组表实现转置1 12 20 00 03 30 00 04 40 00 00 06 6ijAij001012113214326M=4N=2T=51 10 0

19、0 00 02 23 34 40 00 00 00 06 6ijBij001012113214326M=2N=4T=5Aij=Bji思想一：直接思想一：直接交换交换a.dataa.data中中ii和和j j的内容的内容 问题：b.data是一个按列优先顺序存储的稀疏矩阵B 解决方法：重新排列B中三元组的顺序。0 02 25 50 03 30 00 04 40 00 00 06 6ijAij012025113214326M=4N=2T=50 00 00 00 02 23 34 40 05 50 00 06 6ijBij102205113124236Aij=BjiijBij102113124205

20、236ji 按i 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=5ijBij102205113124236ijBij102113124205236ji 按i i排序M=2N=4T=5思想二：在思想二：在A A中按列序找中按列序找三元组，写入三元组，写入B BB的行优先即A的列优先

21、对A的第col列，扫描三元组表a.data，找出所有列号等于col的三元组，将它们的行号和列号互换后依次放入b.data中，即可得到B的按行优先的压缩存储表示。0 02 25 50 03 30 00 04 40 00 00 06 6ijAij012025113214326M=4N=2T=50 00 00 00 02 23 34 40 05 50 00 06 6Aij=BjiijBij102113124205236M=2N=4T=5col=0，没有匹配的三元组col=1，找到2，3，4col=2，找到5，6 Void transmatrix(tripletable a,tripletable b

22、)int pa,pb,col;b.m=a.n;b.n=a.m;b.t=a.t;/*基本信息的赋值*/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

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

24、个三元组在关键问题：如何确定每个三元组在B B中的位置中的位置A A中三元组在中三元组在B B的中位置的中位置=每列的第一个非零元素在数组每列的第一个非零元素在数组B B中应有的位置中应有的位置 +每一列非零元素的个数每一列非零元素的个数0 02 25 50 03 30 00 04 40 00 00 06 6ijAij012025113214326M=4N=2T=50 00 00 00 02 23 34 40 05 50 00 06 6Aij=BjiijBij102113124205236M=2N=4T=5colcol列号列号0 01 12 2cposcpos i i 每列第一个非每列第一个非

25、零元素在零元素在B B中中的位置的位置0 00 03 3cnumcnum i i 每列非零元素每列非零元素个数个数0 03 32 2由递推关系得出由递推关系得出cposcpos的值：的值：cpos0=0cpos0=0cposi=cposi-1+cnumi-1cposi=cposi-1+cnumi-1void fasttranstri(tritupletable b,void fasttranstri(tritupletable b,tritupletable a)tritupletable a)int int colcol；/*当前列号当前列号*/int pa,pb;int pa,pb;/*p

26、a,pb:pa,pb:三元组三元组a,ba,b的下标的下标*/int cnum0.a.n,cpos0.a.n;int cnum0.a.n,cpos0.a.n;b b基本信息基本信息m,n,tm,n,t的赋值；的赋值；若若a a无非零元素，则返回；无非零元素，则返回；初始化数组初始化数组cnumcnum；/*统计统计a a中每列非零元素的个数；中每列非零元素的个数；*/for(pa=0;paa.t;pa+)col=a.datapa.j;cnumcol+;for(pa=0;paa.t;pa+)col=a.datapa.j;cnumcol+;/*由递推关系计算由递推关系计算cposcpos的值的值*

27、/cpos0=0;cpos0=0;for(col=1;col=a.n;col+)for(col=1;col=a.n;col+)cposcol=cposcol-1+cnumcol-1;cposcol=cposcol-1+cnumcol-1;/*扫描扫描a a，将元素交换，将元素交换i,j i,j写入写入b b*/for(pa=0;paa.t;pa+)for(pa=0;paa.t;pa+)col=a.datap.j;col=a.datap.j;pb=cpotcol;pb=cpotcol;b.datapb.i=a.datapa.j;b.datapb.i=a.datapa.j;b.datapb.j=a

28、.datapa.i;b.datapb.j=a.datapa.i;b.datapb.v=a.datapa.v;b.datapb.v=a.datapa.v;cposcol+;cposcol+;算法分析算法分析时间复杂度O（n+t）。当非零元素的个数t和m*n同数量级时，该算法的时间复杂度为O(m*n)，与不压缩存储的情况相同。5.3 5.3 广义表广义表5.5.1 基本概念基本概念广义表是第广义表是第2章提到的线性表的推广。线性表中的元素仅限于原子项，即不章提到的线性表的推广。线性表中的元素仅限于原子项，即不可以再分，而广义表中的元素既可以是原子项，也可以是子表（另一个线可以再分，而广义表中的元素

29、既可以是原子项，也可以是子表（另一个线性表）。性表）。1广义表的定义广义表的定义广义表是广义表是n0个元素个元素a1，a2，an的有限序列，其中每一个的有限序列，其中每一个ai或者是原子或者是原子，或者是一个子表。广义表通常记为，或者是一个子表。广义表通常记为LS=(a1,a2,an)，其中，其中LS为广义表的为广义表的名字，名字，n为广义表的长度，为广义表的长度，每一个每一个ai为广义表的元素。但在习惯中，一般用为广义表的元素。但在习惯中，一般用大写字母表示广义表，小写字母表示原子。大写字母表示广义表，小写字母表示原子。2广义表举例广义表举例（1）A=()，A为空表，长度为为空表，长度为0。

30、（2）B=(a,（b,c）)，B是长度为是长度为2的广义表，第一项为原子，第二项为子表。的广义表，第一项为原子，第二项为子表。（3）C=(x,y,z)，C是长度为是长度为3的广义表，每一项都是原子。的广义表，每一项都是原子。（4）D=(B,C)，D是长度为是长度为2的广义表，每一项都是上面提到的子表。的广义表，每一项都是上面提到的子表。（5）E=(a,E)，是长度为，是长度为2的广义表，第一项为原子，第二项为它本身。的广义表，第一项为原子，第二项为它本身。3广义表的表示方法广义表的表示方法1）用）用LS=(a1，a2，an)形式，其中每一个形式，其中每一个ai为原子或广义表为原子或广义表例如：

31、例如：A=(b,c),B=(a,A),E=(a,E)都是广义表。都是广义表。2）将广义表中所有子表写到原子形式，并利用圆括号嵌套）将广义表中所有子表写到原子形式，并利用圆括号嵌套例如，上面提到的广义表例如，上面提到的广义表A、B、C可以描述为：可以描述为：A(b,c)B(a,A(b,c)E(a,E(a,E（）)3）将广义表用树和图来描述）将广义表用树和图来描述4广义表的深度广义表的深度一个广义表的深度是指该广义表展开后所含括号的层数。一个广义表的深度是指该广义表展开后所含括号的层数。.（1）A=(b,c)（2）B=(a,A)（3）C=(A,B)(4)E=(a,E)depth=1 depth=2 depth=3 depth=BACbacAbcBaAbc5广义表的分类广义表的分类（1）线性表：元素全部是原子的广义表。）线性表：元素全部是原子的广义表。（2）纯表：与树对应的广义表，见图）纯表：与树对应的广义表，见图(1)和和(2)。（3）再入表：与图对应的广义表）再入表：与图对应的广义表(允许结点共享允许结点共享)，见图，见图(3)。（4）递归表：允许有递归关系的广义表，例如）递归表：允许有递归关系的广义表，例如(4)。这四种表的关系满足：这四种表的关系满足：递归表递归表 再入表再入表 纯表纯表 线性表线性表Ea