第5章数组和广义表课件

数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的所有元素本身也是一种线性表。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的数据结构较为简单。多维数组是向量的推广。例如，二维数组：5.1数组的定义二维数组可以看成是由行向量组成的向量，也可以看成是由列向量组成的向量。同样，可把三维数组看成是一个线性表，表中每一个数组元素为一个二维数组。依次类推，可把n维数组看成是一个线性表，表中每一个数据元素是一个n-1维数组。数组的运算：数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作，即给定一组下标，存取或修改相应的数组元素。5.1数组的定义1、顺序存储结构5.2数组的顺序表示和实现用一组地址连续的存储单元依次存放数组的数据元素，称为数组的顺序存储结构。由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。

通常有两种顺序存储方式：2、顺序存储方式⑴行优先顺序——将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：a11,a12,…,a1n,a21,a22,…,a2n,……,am1,am2,…,amn

在PASCAL、C语言中，数组就是按行优先顺序存储的。⑵列优先顺序——将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后。以二维数组为例，按列优先顺序存储的线性序列为：a11,a21,…,am1,a12,a22,…,am2,……,a1n,a2n,…,amn

在FORTRAN语言中，数组就是按列优先顺序存储的。

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

….Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*l

按行序为主序存放amn……

am2am1………a2n……

a22a21a1n

……a12

a1101n-1m*n-1n

按列序为主序存放01m-1m*n-1mamn……

a2na1n………am2……

a22a12am1

……a21

a11

a11

a12

……..

a1n

a21

a22……..

a2n

am1

am2

……..amn

….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l

以上规则推广到多维数组的情况：行优先顺序可规定为先排最右的下标，从右到左，最后排最左的下标；3、n维数组按上述两种方式顺序存储的数组，只要知道开始结点的存放地址（即基地址）、维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。列优先顺序与此相反，先排最左的下标，从左向右，最后排最右的下标。例如，二维数组Amn按“行优先顺序”存储在内存中，假设每个元素占用d个存储单元。4、地址公式

元素aij的存储地址应是数组的基地址加上排在aij前面的元素所占用的单元数。因为aij位于第i行、第j列，前面i-1行一共有(i-1)×n个元素，在第i行上aij前面又有j-1个元素，故它前面一共有(i-1)×n+j-1个元素，因此，aij的地址计算函数为：LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d同样，三维数组Aijk按“行优先顺序”存储，其地址计算函数为：LOC(aijk)=LOC(a111)+[(i-1)*n*p+(j-1)*p+(k-1)]*d上述讨论均是假设数组各维的下界是1，更一般的二维数组是A[c1..d1,c2..d2]，这里c1,c2不一定是1。aij前一共有i-c1行，二维数组一共有d2-c2+1列，故这i-c1行共有(i-c1)*(d2-c2+1)个元素，在第i行上aij前一共有j-c2个元素，因此，aij的地址计算函数为：LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+j-c2)]*d例如，在C语言中，数组各维下标的下界是0，因此在C语言中，二维数组的地址计算公式为：LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d4、地址公式在高级语言编制程序时，将一个矩阵描述为一个二维数组。但是在矩阵中非零元素呈某种规律重复分布或者矩阵中出现大量的零元素的情况下，实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，可以对这类矩阵进行压缩存储。5.3矩阵的压缩存储压缩存储：为多个值相同的非零元素只分配一个存储空间；对零元素不分配空间。假若值相同的元素或零元素在矩阵中的分布有一定规律，则称此类矩阵为特殊矩阵；反之，称为稀疏矩阵。1、对称矩阵5.3.1特殊矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji0≦i,j≦n-1

则称A为对称矩阵。对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，按“行优先顺序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示：

a00a01

….

……..a0n-1

a10

a11

……..…….a1n-1

an-10

an-11

……..an-1n-1

….a00a10a11a20a21a22………………..an-10an-11an-12…an-1n-1

a00a01

….

……..a0n-1

a10

a11

……..…….a1n-1

an-10

an-11

……..an-1n-1

….图5.1对称矩阵在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为：n(n+1)/2。这样可将n2个压缩到n(n+1)/2个元的空间中。因此，可以按将这些元素存放在一个向量sa[0..n(n+1)/2-1]中。为了便于访问对称矩阵A中的元素，必须在aij和sa[k]之间找一个对应关系。1、对称矩阵若i≧j，则aij在下三角形中。aij之前的i行（从第0行到第i-1行）一共有1+2+…+i=i(i+1)/2个元素，在第i行上，aij之前恰有j个元素（即ai0,ai1,ai2,…,aij-1），因此有：1、对称矩阵

k=i*(i+1)/2+j0≦k<n(n+1)/2若i<j，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到：

k=j*(j+1)/2+i0≦k<n(n+1)/2令I=max(i,j)，J=min(i,j)，则k和i,j的对应关系可统一为：

k=I*(I+1)/2+J0≦k<n(n+1)/2因此，aij的地址可用下列式计算：

LOC(aij)=LOC(sa[k])=LOC(sa[0])+k*d=LOC(sa[0])+[I*(I+1)/2+J]*da00a10a11a20……an-10……an-1,n-1有了上述的下标交换关系，对于任意给定一组下标(i，j)，均可在sa[k]中找到矩阵元素aij，反之，对所有的k=0,1,2,…n(n-1)/2-1，都能确定sa[k]中的元素在矩阵中的位置(i,j)。由此，称sa[n(n+1)/2]为n阶对称矩阵A的压缩存储，见下图：k=0123…n(n-1)/2n(n-1)/2-1例如a21和a12均存储在sa[4]中，这是因为

k=I*(I+1)/2+J=2*(2+1)/2+1=4以主对角线划分，三角矩阵有上三角和下三角两种。2、三角矩阵a00a01…a0n-1ca11…a1n-1……………..cc…an-1n-1(a)上三角矩阵a00c…ca10a11…c……………..an-10an-11…an-1

n-1

(b)下三角矩阵上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角矩阵中的常数c为零。在带状矩阵中，所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。这个带状区域若包含主对角线下面及上面各d条对角线上的元素，那么，该方阵称为半带宽为d的带状矩阵。2d+1称为带状矩阵的带宽。3、带状（对角）矩阵

a11a120

…………….

0

a21

a22a23

0

……………0

0

0

…an-1,n-2an-1,n-1

an-1,n

0

0

……an,n-1

ann

0

a32

a33a34

0

………0……………非零元素仅出现在主对角上、紧邻主对角线上面的d条对角线上和紧邻主对角线下面的d条对角线上。显然，当∣i-j∣>d时，元素aij=0。对带状矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个一维数组中，并且一般都能找到矩阵中的元素与该一维数组元素的对应关系，通过这个关系，能对矩阵的元素进行随机存取。5.3.2稀疏矩阵什么是稀疏矩阵？精确地，设在m×n的矩阵A中，有t个非零元素。

令δ=t/(m*n)，称δ为矩阵的稀疏因子。通常认为δ≤0.05时可称之为稀疏矩阵。简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即s<<m×n），则称A为稀疏矩阵。在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。但由于其非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i，j)。1、三元组顺序表

反之，一个三元组(i，j，aij)唯一确定了矩阵A的一个非零元。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。例如，下列三元组表((1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))加上(6,7)这一对行、列值便可作为下列矩阵M的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。

图5.4稀疏矩阵M和T1、三元组顺序表

#defineM20typedefstructnode{inti,j;intv;}JD;JDma[M];三元组表所需存储单元个数为3(t+1)，其中t为非零元个数678

121213931-3361443245218611564-7maijv012345678ma[0].i,ma[0].j,ma[0].v分别存放

矩阵行、列维数和非零元个数行列下标非零元值2、稀疏矩阵的压缩存储方法3、求转置矩阵问题描述：已知一个稀疏矩阵M的三元组表ma，求该矩阵的转置矩阵T的三元组表mb。解决思路：

（1）将矩阵行、列维数互换

（2）将每个三元组中的i和j相互调换

（3）重排三元组次序，使mb中元素以T的行(M的

列)为主序67

8

121213931-3361443245218611564-7ijv012345678maijv76

8

13-3161521122518319342446-76314012345678mb?一个m×n的矩阵A，它的转置B是一个n×m的矩阵，且aij=bji，0≤i≤m-1，0≤j≤n-1，即A的行是B的列，A的列是B的行。方法一将A转置为B，就是将A的三元组表a.data置换为表B的三元组表b.data，如果只是简单地交换a.data中i和j的内容，那么得到的b.data将是一个按列优先顺序存储的稀疏矩阵B。要得到按行优先顺序存储的b.data，就必须重新排列三元组的顺序。

由于A的列是B的行，因此，按a.data的列序转置，所得到的转置矩阵B的三元组表b.data必定是按行优先顺序存放的。按这种方法设计的算法，其基本思想是：对A中的每一列col(0≤col≤n-1)，通过从头至尾扫描三元表a.data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放入b.data中，即可得到B的按行优先顺序的压缩存储表示。方法一

#defineMAXSIZE12500typedefstruct{inti,j;ElemTypee;}Triple;typedefstruct{Tripledata[MAXSIZE+1];intmu,nu,tu;}TSMatrix;

StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)

{q=1;

for(col=1;col<=M.nu;++col)for(p=1;p<=M.tu;++p)

if(M.data[p].j==col){

T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++q;}

}returnOK;}6

7

8

121213931-3361443245218611564-7ijv012345678ma7

6

8

13-3161521122518319342446-76314ijv012345678mbqppppppppqqqqppppppppcol=1col=2方法一这个算法，主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(nu*tu)，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为：for(col=1;col<=nu;++col)

for(row=1;row<=mu;++row)t[col][row]=m[row][col];

其时间复杂度为O(nu*mu)。方法一当非零元素的个数tu和mu*nu同数量级时，方法一的时间复杂度为O(mu*nu2)。三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算法的难度。因此，此算法仅适用于tu<<mu*nu的情况。方法一按照a.data中三元组的次序进行转置，并将转置后的三元组置入b.data中的恰当位置。方法二：快速转置算法如果能预先确定矩阵M中每一列（即T中每一行）的第一个非零元素在b.data中应有的位置，那么在对a.data中的三元组依次作转置时，便可直接放到b.data中恰当的位置上去。为了确定这些位置，在转置前，应先求得M的每一列中非零元的个数，进而求得每一列的第一个非零元在b.data中应有的位置。快速转置算法的思想：对A扫描一次，按A第二列提供的列号依次确定装入B的一个三元组的位置。具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。

实现：需要附设num和cpot两个数组。num[col]：表示矩阵M中第col列中非零元的个数；cpot[col]：指示矩阵M中第col列第一个非零元在mb中的位置显然有：cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1];(2cola.nu)1357889colnum[col]cpot[col]12223241506170方法二：快速转置算法StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col<=M.nu;++col)num[col]=0;for(t=1;t<=M.tu;++t)++num[M.data[t].j];//求M中每一列含非零元个数cpot[1]=1;方法二：快速转置算法for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];//求第col列中第1个非零元素在b.data中的序号。for(p=1;p<=M.tu;++p){col=M.data[p].j;q=cpot[col];}//ifreturnOK;}

T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++cpot[col];}方法二：快速转置算法这个算法仅比前一个算法多用了两个辅助数组。快速转置算法分析从时间上看，算法中有四个并列的单循环，循环次数分别为nu和tu，因而总的时间复杂度为O（nu＋tu）。在M的非零元素个数tu和mu×nu等数量级时，其时间复杂度为O（mu×nu），和经典算法的时间复杂度相同。67

8

121213931-3361443245218611564-7ijv012345678maijv012345678mbcolnum[col]cpot[col]1122323524715806817907

6

8

13-3161521122518319342446-76314pppppppp4629753typedefstructOLNode{inti，j;ElemTypee;structOLNode*down,*right;}OLNode,*OLink;ijedownright在链表中，每个非零元素可用一个含5个域的结点表示，right域用以链接同一行中下一个非零元素，down域用以链接同一列中下一个非零元素。4、十字链表ijedownright4、十字链表同一行的非零元素通过right域链接成一个线性表，同一列的非零元素通过down域链接成一个线性表，每个非零元素既是某个行链表中的一个结点，又是某个列链表中的一个结点，整个矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链表。十字链表可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示。113418225234^^^^^^^4、十字链表例题：两个矩阵相加假设两个矩阵相加后的结果为A’，则和矩阵A’中的非零元aij’只可能有三种情况:aij+bij

由此，当将B加到A上去时，对A矩阵的十字链表来说：改变结点的e值（aij+bij0）aij(bij=0)bij(aij=0)不变(bij=0)插入一个新结点(aij=0)还有一种情况是：和A矩阵中的某个非零元相对应，和矩阵A’中是零元，即对A的操作是删除一个结点（aij+bij=0）。由此，整个运算过程可从矩阵的第一行起逐行进行。对每一行都从表头出发分别找到A和B在该行中的第一个非零元结点后，开始比较，然后按上述四种不同情况分别处理。例题：两个矩阵相加广义表（lists，又称列表）是线性表的推广。

在第2章，线性表定义为n0个元素a1,a2,a3,…,an的有限序列。线性表的元素仅限于原子项。原子是作为结构上不可分割的成分，它可以是一个数或一个结构，若放松对表元素的这种限制，容许它们具有其自身结构，这样就产生了广义表的概念。5.4广义表的定义广义表是n(n0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表。通常记作

LS=（a1,a2,a3,…,an)

LS是广义表的名字，n为它的长度。

若ai是广义表，则称它为LS的子表。通常用圆括号将广义表括起来，用逗号分隔其中的元素。为了区别原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。若广义表LS（n>=1)非空，则a1是LS的表头，其余元素组成的表(a2,a3,…,an)称为LS的表尾。显然广义表是递归定义的，这是因为在定义广义表时又用到了广义表的概念。广义表的例子如下：

（1）A=（）——A是一个空表，其长度为零。

（2）B=（e）——表B只有一个原子e，B的长度为1。

（3）C=（a,(b,c,d))——表C的长度为2，两个元素分别为原子a和子表(b,c,d)。

（4）D=（A，B，C）——表D的长度为3，三个元素都是广义表。显然，将子表的值代入后，则有D=((),(e),(a,(b,c,d)))。5.4广义表的定义

（5）E=（a,E）——这是一个递归的表，它的长度为2，E相当于一个无限的广义表E=(a,(a,(a,(a,…)))).例如：D=(E,F)

其中:

E=(a,(b,c))F=(d,(e))DEFa()d()bce从上述定义和例子可推出广义表的三个重要结论：（1）广义表的元素可以是子表，而子表的元素还可以是子表。由此，广义表是一个多层次的结构，可以用图形象地表示。5.4广义表的定义（2）广义表可为其它表所共享。例如在上述例（4）中，广义表A，B，C为D的子表，则在D中可以不必列出子表的值，而是通过子表的名称来引用。（3）广义表的递归性。综上所述，广义表不仅是线性表的推广，也是树的推广。广义表中所含括弧的重数称为表的深度，表中元素的层数就是包括该元素的括弧重数。例如：F（a，b，（c，（d）））其中，单元素a、b在第一层，d在第三层，广义表的深度为3。5.4广义表的定义由于广义表(a1,a2,a3,…,an)中的数据元素可以具有不同的结构（或是原子，或是广义表），因此，难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素可用一个结点表示。tag=1hptptag=0atom表结点原子结点由于广义表中有两种数据元素：原子或广义表，因此，需要两种结构的结点：一种是表结点，一种是原子结点。表结点由三个域组成：标志域、指示表头的指针域和指示表尾的指针域；而原子结点只需两个域：标志域和值域。5.5广义表的存储结构L=(a,(x,y),((x)))a(x,y)(

)

1

L0a

1

1

1

1

10x()xBCDE10e110a1∧1110a110d0c0b11广义表的存储结构示例（1）A=（）（2）B=（e）（3）C=（a,（b,c,d））（4）D=（A，B，C）（5）E=（a,E）**5.6m元多项式的表示1、一元多项式一个多项式可以用一个长度为m且每个数据元素有两个数据项（系数项和指数项）的线性表来表示。2、m元多项式一个m元多项式的每一项，最多有个m变元，如果用线性表来表示，则每个数据元素需要m+1个数据项，以存储一个系数值和m个指数值。将产生两个问题：造成浪费线性表中结点大小不一样因此，由于m元多项式中每一项的变化数目不均匀性和变元信息的重要性，故不适于用线性表表示。例如：上式是变元Z的多项式，即

其中：A和B本身又是一个（x,y）的二元多项式，15是Z的零次项的系数。进一步考察A(x,y)，又可把它看成是y的多项式。Cy3+Dy2，而其中C和D为x的一元多项式。循环以往，每个多项式都可看作是由一个变量加上若干个系数指数偶对组成。**5.6m元多项式的表示任何一个m