数组和广义表ppt

第5章数组和广义表---广义线性表5.1数组的概念和存储5.2特殊矩阵的压缩存储5.3稀疏矩阵的压缩存储5.4广义表15.1数组一、数组的定义数组：它是n（n>1)个相同数据类型的数据元素a0,a1,a2,…,an-1构成的占用一块地址连续的内存单元的有限序列。数组的下标：数组元素的位置。注意：（1）C语言的数组定义下标从0开始。①数组中各元素具有统一的类型；②数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。③数组的基本操作比较简单，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。(2)一个二维数组可以看作每个数据元素是一个一维数组的一维数组。二维数组是两维的，内存单元是一维的，存在向内存存储时二维数组中数据元素的存储方法问题，C语言采用以行序为主序的方法存储。2讨论：数组与线性表的区别与联系

相同之处：

它们都是若干个相同数据类型的数据元素a0,a1,a2,…，an-1构成的有限序列。

不同之处：

(1)数组要求其元素占用一块地址连续的内存单元空间，而线性表无此要求；(2)线性表的元素是逻辑意义上不可再分的元素，而数组中的每个元素还可以是一个数组；(3)数组的操作主要是向某个下标的数组元素中存放数据和取某个下标的数组元素，这与线性表的插入和删除操作不同。3二、数组的实现机制１、一维数组（n个元素）中任一元素ai的内存单元地址LOC(ai)=LOC(a０)+i*k(0≤i<n)２、一个m行n列的二维数组LOC(aij)=LOC(a00)+(i*n+j)*k(0≤i<m，0≤j<n)注：C语言中数组元素采用行主序的存放方法，即行优先顺序。a０的内存单元地址每个元素所需的字节个数每个元素所需的字节个数a０0的内存单元地址一个m×n的二维数组可以看成是m行的一维数组，或者n列的一维数组。a0,0a0,1…a0,n-1

a1,0a1,1…a1,n-1

…………

am-1,0am-1,1…am-1,n-1

Amn=4本行中aij前面的元素个数每行元素个数整行数aij前面的元素个数=阴影部分的面积=整行数×每行元素个数+本行中aij前面的元素个数=(i

-l1)×(h2

-l2＋1)＋(j

-l2)二维数组寻址的计算方法（行序优先）l2h2

l1h1(a)二维数组aij5aij前面的元素个数=阴影部分的面积=整列数×每列元素个数+本列中aij前面的元素个数=(j

–l2)×(h1

–l1＋1)＋(i-l1)二维数组寻址的计算方法（列序优先）l2h2

l1h1(a)二维数组aij整列数

每列元素个数

本列中aij前面的元素个数6对于行优先顺序：先变化多维数组中最右边的下标，从右往左，最后变化最左边的下标；对于列优先顺序：先变化数组中最左边的下标，从左往右，最后变化最右边的下标；数组寻址的计算方法结论：7思考：任一元素存储地址的计算方法你能推导出来吗？

思考：

n（n＞2）维数组，一般也采用按行优先和按列优先两种存储方法。请给出基本思想和寻址计算方法？8

下标为i1,i2,i3的数组元素的存储地址：按页/行/列存放

各维元素个数为m1,m2,m3LOC(aijk)=Loc(a000)+(i*m2*m3+j*m3+k)*l

三维数组寻址的计算方法：（按行序优先）9

可将以上规则推广到n维数组：

n维数组A[t1][t2]…[tn]，可看成是由t1个（n1）维数组组成的特殊线性表：a1[t2][t3]…[tn]，a2[t2][t3]…[tn]，…，at1[t2][t3]…[tn]可按线性表的顺序存储方法，先存储第一个n1维数组a1[t2][t3]…[tn]，紧接着存储第二个n1维数组a2[t2][t3]…[tn]，……，最后存储第t1个n1维数组at1[t2][t3]…[tn]。

对于每个n1维数组，又可看成是由t2个n2维的数组组成的特殊线性表，其余类推，直到最后看成是tn个数组元素组成的一维数组。10

同理，若n维数组第一个元素的存储位置为LOC(a00…0)，那么对于任何一组有效的下标i1,i2,…,in，其对应的数组元素ai1,i2,…,in的存储位置LOC(ai1,i2,…,in)为：LOC(ai1,i2,…,in)=LOC(a00…0)+d[i1t2t3…tn+i2t3t4…tn+in1tn+in]=LOC(a00…0)+d式中11注：只要知道以下三要素便可随时求出任一元素的地址（意义：数组中的任一元素可随机存取）

①开始结点的存放首字节地址（即基地址）；

②维数和每维的上、下界；

③每个数组元素所占用的单元数。例１一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是

个字节。答：Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=288例２

设数组a[０…60,０…70]的基地址为2048，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[32,58]的存储地址为

。答：根据行优先公式LOC(aij)=LOC(a00)+(i*n+j)*k(0≤i<m，0≤j<n)得：LOC(a32,58)=2048+(32*71+58)*2＝67082886708125.2特殊矩阵的压缩存储

特殊矩阵:指有许多值相同的元素或有许多零元素、且值相同的元素或零元素的分布有一定规律的矩阵。下面我们讨论几种特殊矩阵的压缩存储。1、n阶对称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji（1≦i,j≦n）则称A为n阶对称矩阵。15137a1150800a21a2218926a31a32a3330251………………..70613an1an2an3…ann

图5.1对称矩阵n阶对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先顺序”存储主对角线（包括对角线）以下的元素。135.2特殊矩阵的压缩存储在矩阵中很多值相同的元素并且它们的分布有一定的规律，我们将这样的矩阵称为特殊矩阵。若矩阵中有很多零元素称为稀疏矩阵

压缩存储的基本思想是：⑴为多个值相同的元素只分配一个存储空间；⑵

对零元素不分配存储空间。

145.2.1特殊矩阵的压缩存储——对称矩阵364786

284248

169746

058295

7A＝5阶对称矩阵对称矩阵特点：在一个n阶方阵中，有aij=aji

，其中1≤i,j≤n。

只需要n×（n＋1）/2个存储单元。讨论：如何只存储下三角部分的元素呢？

15(a)下三角矩阵(b)存储说明(c)计算方法aij在一维数组中的序号=阴影部分的面积=i×(i+1)/2+j+1∵一维数组下标从0开始∴aij在一维数组中的下标k=i×(i+1)/2+j0…

in-10…j…n-1

aij每行元素个数12…iaij在本行中的序号aij第0行第1行…第i-1行对称矩阵按行优先存储寻址示意图16结论：将下三角中的所有元素按行优先存储到一维数组SA中，下三角中的元素aij（i≥j）在数组SA中的下标k与i、j的关系为：k＝i×(i＋1)/2＋j。同理我们可以得到：上三角中的元素aij（i＜j），因为aij＝aji，则访问和它对应的元素aji即可，即：k＝j×(j＋1)/2＋i。即将i,j下标互换。第1行第n-1行第0行a00a10a11a20a21a22aij…an-10an-11…an-1n-1…第2行012345kn(n+1)/2-1对称矩阵的压缩存储

17总结：对称矩阵A中任一元素aij在一维数组SA中的存储位置可用如下公式计算：Loc(aij)=Loc(sa[k])=Loc(sa[0])+k*d=Loc(sa[0])+[I*(I+1)/2+J)]*d其中，I=max(i,j)J=min(i,j)185.2.2特殊矩阵的压缩存储——三角矩阵3c

c

c

c62c

c

c481c

c7460c82957(a)下三角矩阵34810c2946c

c１57c

c

c

08c

c

c

c7(b)上三角矩阵思考：如何只存储下三角部分或上三角部分的元素？

只需存储n×(n＋1)/2＋119012345kn(n+1)/2第1行第n-1行第0行a00a10a11a20a21a22aij…an-10an-11…an-1n-1…第2行c下三角矩阵的压缩存储既要存储下三角中的元素，还要存储对角线上方的常数。因为是同一个常数，所以只存一个即可。

对于上三角矩阵，其存储思想与下三角类似，按行存储上三角部分，最后存储对角线下方的常数。

20结论：1.下三角矩阵中任一元素aij在SA中的下标k与i、j的对应关系为：i×(i＋1)/2＋j当i≥jn×(n＋1)/2当i＜jk=2.上三角矩阵中任一元素aij在SA中的下标k与i、j的对应关系为：

i×(2n－i＋1)/2＋j－i当i≤jn×(n＋1)/2当i＞jk=215.2.3特殊矩阵的压缩存储——对角矩阵

所谓对角矩阵是指所有非零元素都集中在以主对角线为中心的带状区域中，除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。

对角矩阵的压缩存储方法

0

00

000

000

000

A=a00a01a43

a44a10a11

a12a21a22

a23a32a33

a34(a)三对角矩阵按行存储非零元素a00a01a10a11a12a21a22a23a32a33a34a43a440123456789101112元素aij在一维数组中的序号=2+3(i－1)+(j－i+2)=2i+j+1

∵一维数组下标从0开始∴元素aij在一维数组中的下标=2i+j思考：一般的，对于矩阵半宽带为b的对角矩阵按行优先存储到一维数组的通项公式为？225.3稀疏矩阵什么是稀疏矩阵?它有哪些特征?1、稀疏矩阵矩阵中非零元素的个数较少（一般小于5%）。2、稠密矩阵

一个不稀疏的矩阵。说明：稀疏矩阵的压缩存储结构主要有三元组顺序表和三元组链表两大类型。三元组定义:将稀疏矩阵中的每个非零元素表示为：(行号，列号，非零元素值)称为三元组表示法。23三元组表：将稀疏矩阵的非零元素对应的三元组所构成的集合，按行优先的顺序排列成一个线性表。注意：data数组中表示的非零元素以行序为主序顺序排列，它是一种下标按行有序的存储结构。C中，用结构类型来描述三元组：typedefstructthree{intr,c;ElemTyped;}TupNode;把稀疏矩阵的行数、列数和非零元个数定义成三元组顺序表的控制数据结构体：typedefstructthreelist{introws,columns,nums;TupNodedata[MAXSize];}TSMatrix;1.稀疏矩阵的三元组顺序表24稀疏矩阵顺序存储——三元组顺序表采用顺序存储结构存储的三元组表称为三元组顺序表。稀疏矩阵1300780115

01236000

0006500

00000099

00000A=A的三元组顺序表00130378051151112123623654099

空空空闲闲闲567rcd0123456MaxTerm-1矩阵的行数矩阵的列数非零元个数25稀疏矩阵顺序存储——三元组顺序表矩阵运算包括矩阵转置、矩阵加、矩阵减、矩阵乘等。1.从一个二维矩阵创建其三元组表示以行序方式扫描二维矩阵a,将其非零元素插入到三元组t中。voidCreatMat(TSMatrix&t,ElemTypeA[M][N]){inti,j;t.rows=M;t.cols=N;t.nums=0;for(i=0;i<M;i++){for(j=0;j<N;j++)if(A[i][j]!=0){t.data[t.nums].r=i;t.data[t.nums].c=j;t.data[t.nums].d=A[i][j];t.nums++;}}}26先在三元组t中找到适当的位置k,将k~t.nums个元素后移一个位置，将指定元素x插入到t.data[k]处。intValue(TSMatrix&t,ElemTypex,intrs,intcs){inti,k=0;if((rs>=t.rows)||(cs>=t.cols))return0;while(k<t.nums&&rs>t.data[k].r)k++;while(k<t.nums&&rs==t.data[k].r&&cs>t.data[k].c)k++;if(t.data[k].r==rs&&t.data[k].c==cs)t.data[k].d=x;else{for(i=t.nums-1;i>=k;i--){t.data[i+1].r=t.data[i].r;t.data[i+1].c=t.data[i].c;t.data[i+1].d=t.data[i].d;}t.data[k].r=rs;t.data[k].c=cs;t.data[k].d=x;t.nums++;}return1;}稀疏矩阵顺序存储——三元组元素赋值27答：不正确！除了：（1）每个元素的行下标和列下标互换（即三元组中的r和c互换）；还需要：（2）T的总行数rows和总列数columns也要互换；（3）重排三元组内各元素顺序，使转置后的三元组也按行（或列）为主序有规律的排列。上述（1）和（2）容易实现，难点在（3）。

若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种说法正确吗？提问：28稀疏矩阵三元组顺序表存储操作——转置算法Ⅰ直接取，顺序存该算法的基本思想是：在A的三元组顺序表中依次找第0列、第1列、…直到最后一列的三元组，并将找到的每个三元组的行、列交换后顺序存储到B的三元组顺序表中。例：13000990120000360007806500000001150000B=三元组顺序表A的转置29算法的伪代码描述：1.设置转置后矩阵B的行数、列数和非零元素的个数；2.在B中设置初始存储位置q；3.for(v=最小列号;v<=最大列号;v++)3.1在A中查找列号为v的三元组；3.2交换其行号和列号，存入B中q位置；3.3q++；30对于一个m×n的矩阵Am×n,其转置矩阵是一个n×m的矩阵。voidTranTat(TSMatrixt,TSMatrix&tb){intp,1=0,v;tb.rows=t.cols;tb.cols=t.rows;tb.nums=t.nums;if(t.nums!=0){for(v=0;v<t.cols;v++)for(p=0;p<t.nums;p++)if(t.data[p].c==v){tb.data[q].r=t.data[p].c;tb.data[q].c=t.data[p].r;tb.data[q].d=t.data[p].d;q++;}}}31稀疏矩阵三元组顺序表存储操作——转置算法Ⅱ顺序取，直接存分析：如何确定当前从A中取出的三元组在B中的位置。注意到A中第0列的第一个非零元素一定存储在B中下标为0的位置上，该列中其它非零元素应存放在B中后面连续的位置上，那么第1列的第一个非零元素在B中的位置便等于第0列的第一个非零元素在B中的位置加上第0列的非零元素的个数，以此类推。该算法的基本思想：是在A中依次取三元组，交换其行号和列号放到B中适当位置。321.引入两个数组作为辅助数据结构：num[nu]：表示矩阵A中某列的非零元素的个数；cpot[nu]：初始值表示矩阵A中某列的第一个非零元素在B中的位置。算法设计：cpot[1]=1；cpot[col]=cpot[col-1]+num[col-1]；2≤col＜n2.num与cpot递推关系：331.设置转置后矩阵B的行数、列数和非零元素的个数；2.计算A中每一列的非零元素个数；3.计算A中每一列的第一个非零元素在B中的下标；4.依次取A中的每一个非零元素对应的三元组；4.1确定该元素在B中的下标pb；4.2将该元素的行号列号交换后存入B中pb的位置；4.3预置该元素所在列的下一个元素的存放位置；算法的伪代码：342.稀疏矩阵的十字链表表示——十字链表稀疏矩阵链接存储的基本思想是：将每个非零