数据结构第四章数组和广义表.doc

第四章 数组和广义表数组和广义表是线性表的推广在前面介绍的线性结构中数据元素都只属非结构的原子类型，而数组和广义表中的数据元素本身也是一个线性表§ 4.1 数组一、 数组的逻辑结构1. 一维数组: A[1:n] 是一个线性表2. 二维数组: A[1:m,1:n]，类型定义如下： A:array[1..m,1..n]of elementype;数组可表示为：a11 a12a13 … a1na21a22 a23 … a2n … … … … … … … … …an1 an2 an3 … ann它可看成是由m个行向量或者n个列向量组成的线性表也就是说，二维数组可以看成是一种推广的线性表，这种线性表的每一个数据元素本身也是一个线性表 对于上述二维数组A，我们可以将A看成是下述线性表 A'=(d1,d2,...dn) 其中每一个数据元素dj本身又是一个列向量线性表 dj=(d1j,d2j,...dmj),1≤j≤n同样，也可将二维数组A看成线性表A"=(β1,β2,...βm)，其中每个βi本身是一个行向量线性表 βi=(β1,β2,...βm) ,1≤i≤m类似地，一个三维数组可以看成是数据元素为二维数组的线性表。

一般的，一个n维数组可视为其数据元素为n-1维数组的线性表二、数组的顺序存储分配1.一维数组与线性表一样，它的寻址公式为： loc(ai)=loc(a1)+(i-1)*l 2.二维数组 A[1:m,1:n] 按行存储的寻址公式为：loc(A[i,j])=loc(A[1,1])+[n(i-1)+(j-1)]*l3.三维数组 A[1:p,1:m,1:n] 按行存储的寻址公式为： loc(A[j1,j2,j3])=loc(A[1,1,1])+ [m*n(j1-1)+(j2-1)*n+(j3-1)]*l4.n维数组 A[1:d1,1:d2,1:d3,...,1:dn]按行存储的寻址公式为： loc(A[j1,j2,...,jn])=loc(A[1,1,...,1])+ [(j1-1)*d2*d3*...*dn+(j2-1)*d3* ...*dn+...+(jn-1-1)*dn+(jn-1)]*l =loc(A[1,1,...,1]+∑(ji-1)*αi) αi=l*∏dk (1≤i≤n-1) αn=l (∏=l)例：已知A[1:2,1:3,1:4]，设l=1,求A[2,3,2]的地址。

loc(A[2,3,2])=loc(A[1,1,1])+∑(ji-1)*αi =A+1+(j1-1)α1+(j2-1)α2+(j3-1)+α3 =A+1+(2-1)*12+(3-1)*4+(2-1)=A+22其中:α1=l*∏dk=12;α2=l*∏dk=4;α3=l=1三、 数组的压缩存储所谓压缩存储是指：若有一定规律的矩阵,我们可以只存储一部分;相同的元只分配一个存储空间；对零元不分配空间 若在矩阵中值相同的元素或者零元素的分布有一定规律，则我们称此类矩阵为特殊矩阵 若矩阵中大多数元素为0，且无一定规律，我们称这种矩阵为稀疏矩阵1. 特殊矩阵 若一个n阶矩阵A中的元素满足下述性质： aij=aji (1≤i,j≤n) 则称为n阶对称矩阵 一般地，对于n*n的对称矩阵A，只需存储对角线以下或以上的元素就可以了假如只存储对角线以下的元素，则如下图所示a[1,1] 0 ... 0a[2,1] a[2,2] ... 0 ... ... ... ... a[n,1] a[n,2] ... a[n,n]此时，仍采用按行为主顺序存储的方法，但每行中存入的元素的个数为1个，2个，...，n个。

因此，可用一维数组V[1:n(n+1)/2]作为n阶对称矩阵的存储结构这时对一个a[i,j]元素可按下式寻址公式确定: loc[i,j]=loc[1,1]+(i*(i-1) +j-1)*1 (i>=j)另外，在数值分析中经常出现的还有另一类特殊矩阵是对角矩阵在这种矩阵中，所有的非零元素都集中在以主对角线为中心的带状区域中如下页图所示：loc[i,j]=loc[1,1]+(i*(i-1)2+j-1)*1 (i>=j)A[i,j]=0 (i

在实际应用中还经常会遇到一类矩阵，其非零元较零元少得多，且分布没有一定规律，称之为稀疏矩阵下面我们就讨论稀疏矩阵的压缩存储和运算2. 稀疏矩阵 对于稀疏矩阵，按照压缩存储的概念，只存储稀疏矩阵的非零元素为了能由给定的下标(i,j)确定其存储位置，除了需要在机器内保存非零元素的值以外还应将它们所在的行、列下标值同时保存起来，即需存储一个三元组(i,j,ai,j)，其中i是行值，j是列值， ai,j是元素的值15 0 0 22 0 -15 0 11 3 0 0 0 0 0 0 -6 0 0 0 0 0 0 0 091 0 0 0 0 0 0 0 28 0 0 0 如下图所示：上图所示的稀疏矩阵中,36个元素中只有8个非零元素,可用下列8个三元组表示: (1,1,15),(1,4,22),(1,6,-15),(2,2,11), (2,3,3),(3,4,-6),(5,1,91),(6,3,28) 若以某种方式(例如:以行的顺序,每一行中按列顺序)将这8个三元组排列起来,再加上一个表示矩阵M的行数,列数及非零元素个数的三元组(6,6,8),则所形成的表就唯一确定了稀疏矩阵M.这就是稀疏矩阵的一种压缩存储表示.上述这样一个三元组表显然可以用一个9行3列的二维数组A表示(如下页所示)。

表示稀疏矩阵M的三列的二维数组 1] 2] 3]A[0, 6 6 8A[1, 1 1 15A[2, 1 4 22A[3， 1 6 -15A[4, 2 2 11A[5, 2 3 3A[6， 3 4 -6A[7, 5 1 91A[8, 6 3 28 一般来说，对于一个m行n列且有t个非零元素的稀疏矩阵，可用一个t+1行3列的二维数组表示其中，第零行的三个元素分别等于m,n和t从第1行到第t行，每行表示一个非零元素并且按以行为主非零元素在矩阵中出现的次序排列这时，对任意给定的(i,j)，且要确定相应的A[i,j]，则查找该二维数组每行的前两列对应的值是否有等于(i,j)的；如有，则找到了相应的元素，其值为该行的第三列的值若没有，则说明该下标对应的元素值为零 下面研究在对上述t+1行3列的二维数组采用顺序分配的存储表示后，如何实现对稀疏矩阵的常见运算，这里我们只讨论两种矩阵运算，转置和矩阵乘法1.求转置矩阵 转置是一种最简单的矩阵运算，对于一个m*n阶矩阵 M，其转置矩阵N乃是一个n*m阶矩阵，且M和N之间有下面的关系： M[i,j]=N[j,i] 1≤i≤m,1≤j≤n例如前例图中的矩阵的转置矩阵为如下图所示。

15 0 0 0 91 0 0 11 0 0 0 0 0 3 0 0 0 2822 0 -6 0 0 0 0 0 0 0 0 0-15 0 0 0 0 0此矩阵当然也是一个稀疏矩阵，我们用下图所示的三列二维数组B表示此矩阵 1] 2] 3]B[0, 6 6 8B[1, 1 1 15B[2, 1 5 91B[3, 2 2 11B[4, 3 2 3B[5, 3 6 28B[6, 4 1 22B[7, 4 3 -6B[8, 6 4 -15现在的问题是如何由上图所示的数组A求出数组B来，可以采用下面两种不同的方法解决：1)按照矩阵M的列序来进行转置： 对A数组从第一行起，整个扫描一遍，把A中第二列的元素值为1的依次挑出来，将挑出来的元素，(第一列和第二列)两列进行交换，依次作为B数组的元素然后从A数组的第一行起扫描一遍，把A中第二列的元素值为2的依次挑出来(将两列的号进行交换）依次作为B数组的元素，...直到把A中第二列的元素值为n的挑出来，依次作为B数组的元素为止。

算法如下：PROCEDURE transmat(A,B); /*A,B分别表示矩阵M和其转置矩阵N的三列的二维数组，现由A求出B，算法中q指示B的行号；p指示A的行号；col指示M的列号，即N的列号*/ BEGIN （m,n,t):=(A[0,1],A[0,2],A[0,3]); (B[0,1],B[0,2],B[0,3]):=(n,m,t); IF t<>0 /*M为非零矩阵*/ THEN [q:=1; FOR col:=1 to n DO FOR p:=1 to t DO IF [P,2]=col THEN [B[q,1]:=A[p,1],B[q,2]:=A[p,1], B[q,3]:=A[p,3]; q:=q+1] END;对该算法的时空复杂性进行分析,可以看出其存储量开销3*(t+1)当t<1/3*(m*n)时，所需存储量就要比按矩形结构存储的二维数组要少算法中的主要时间花费在执行位于两重循环内的语句上,其数量级(语句执行频度)。