数组与广义表相关知识

第五章数组和广义表5.1数组的类型定义5.3矩阵的压缩存储5.2数组的顺序表示和实现5.4广义表的类型定义5.5

广义表的存储结构学习提要：

1.了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。

2.掌握对特殊矩阵进行压缩存储时的下标变换公式。

3.了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。

4.掌握广义表的结构特点及其存储表示方法。ADTArray{

数据对象：

D＝{aj1,j2,...,,ji,jn|ji=0,...,bi-1,i=1,2,..,n}

数据关系：

R＝{R1,R2,...,Rn}Ri＝{<aj1,...ji,...jn

,aj1,...ji+1,...jn

>|0jkbk-1,1kn且ki,0ji

bi-2,i=2,...,n}

}ADTArray基本操作:5.1数组的类型定义基本操作：InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn)InitArray(&A,n,bound1,...,boundn)

操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。DestroyArray(&A)

操作结果：销毁数组A。

Value(A,&e,index1,...,indexn)

初始条件：A是n维数组，e为元素变量，随后是n个下标值。

操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。

Assign(&A,e,index1,...,indexn)

初始条件：A是n维数组，e为元素变量，随后是n个下标值。

操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返OK。二维数组的定义:数据对象:

D={aij|0≤i≤b1-1,0≤j≤b2-1}数据关系:

R={ROW,COL}

ROW={<ai,j,ai,j+1>|0≤i≤b1-2,0≤j≤b2-1}

COL={<ai,j,ai+1,j>|0≤i≤b1-1,0≤j≤b2-2}二维数组的定义:5.2数组的顺序表示和实现类型特点:

（1）

只有引用型操作，没有加工型操作；（2）数组是多维的结构，而存储空间是一个一维的结构。有两种顺序映象的方式:

（1）以行序为主序（2）以列序为主序

a00a01……a0n-1

a10a11……a1n-1

am-10am-11…am-1n-1….

按行序为主序存放

am-1n-1……..

am-11

am-10

……….a1n-1……..

a11a10a0n-1

…….a01

a0001n-1m*n-1nLOC(i,j)=LOC(0,0)+(n×i＋j)×L

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

am-1n-1……..

a1n-1

a0n-1……….am-11……..

a11a01am-10

…….a10

a00

a00

a01

……..

a0n-1

a10

a11……..

a1n-1

am-10

am-11

…am-1n-1….LOC(i,j)=LOC(0,0)+(m×j＋i)×L称为基地址或基址以“行序为主序”的存储映象:二维数组A中任一元素ai,j

的存储位置

LOC(i,j)=LOC(0,0)+(n×i＋j)×

L

以“列序为主序”的存储映象:二维数组A中任一元素ai,j

的存储位置

LOC(i,j)=LOC(0,0)+(m×j＋i)×

L

例5.1:若L=2,LOC[1,1]=1000LOC[3,4]=LOC[1,1]+(5*(3-1)+4-1)*L=1000+13*2=1026一般地，若LOC[0,0]为基地址:

LOC[i,j]=LOC[0,0]+(n*i+j)*L

(0<=i<m,0<=j<n,每个数据元素占L个存储单元)LOC[i,j,k]=LOC[0,0,0]+(n*h*i+h*j+k)*L(0<=i<m,0<=j<n,0<=k<h,每个数据元素占L个存储单元)a11a12a13a14a15A4x5=a21a22a23a24a25a31a32a33a34a35a41a42a43a44a45推广到一般情况

n维数组的行序为主序存储地址计算公式

b1,b2,...,bn是n维的维界,数组元素A(j1,j2,...,jn)的存储位置为LOC[j1,j2,...jn]=LOC[0,0,...,0]+(b2*b3*…*bn*j1+b3*…*bn*j2+......+bn*jn-1+jn)*L

n-1n=LOC[0,0,...,0]+(jibk+jn)*L

i=1k=i+1

例:在C语言中,设数组A[5][6][7][8]的首地址为2000,

每个元素占2个字节;求元素A[3][4][5][4]的地址.LOC[3,4,5,4]=2000+(6*7*8*3+7*8*4+8*5+4)*2=2000+(336*3+56*4+8*5+1*4)*2=2000+(1008+224+40+4)*2=4552推广到一般情况，可得到n维数组数据元素存储位置的映象关系

称为n维数组的映象函数。数组元素的存储位置是其下标的线性函数。其中cn=L，ci-1=bi×ci,1<in。LOC(j1,j2,...,jn)=LOC(0,0,...,0)+∑ciji

i=1n列序为主序:(FORTRAN)Amxn=((a11,a21,a31,...am1),(a12,a22,a32,...am2),...(a1n,a2n,a3n,...amn))LOC[1,1]为基地址:LOC[i,j]=LOC[1,1]+(m*(j-1)+i-1)*L(1<=i<=m,1<=j<=n,每个数据元素占L个存储单元)例5.2:若L=2,LOC[1,1]=1000LOC[3,4]=LOC[1,1]+(4*(4-1)+3-1)*L=1000+14*2=1028LOC[0,0]为基地址:LOC[i,j]=LOC[0,0]+(m*j+i)*L(0<=i<=m,0<=j<=n,每个数据元素占L个存储单元)LOC[i,j,k]=LOC[0,0,0]+(m*((n*k)+j)+i)*La11a12a13a14a15a21a22a23a24a25a31a32a33a34a35a41a42a43a44a45数组顺序存储的表示和实现InitArray(Array&A,intdim,...);//若维数dim和随后的各维长度数合法,构造相应的数组,并返回OKDestroyArray(Array&A);//销毁数组AValue(ArrayA,ElemType&e,...);若各下标不超界,则e赋值为所指定的A的元素值,并返回OK

Assign(Array&A,ElemTypee,...)若各下标不超界,则将e的值赋给所指定的A的元素,并返回OK

basedimboundsconstantsa0a1aiat.........01...dim-1...#include<stdarg.h>#defineMAX_ARRAY_DIM8//维数最大值typedefstruct{ElemType*base;//数组元素基址

intdim;//维数

int*bounds;//维界基址

int*constants;//映像函数常量基址，除dim外，均由InitArray分配}Array;练习假设有二维数组A68，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，计算：（1）数组A的体积（即存储量）；（2）数组A的最后一个元素a57的第一个字节的地址；（3）按行存储时，元素a14的第一个字节的地址；（4）按列存储时，元素a47的第一个字节的地址。

5.3.1特殊矩阵5.3矩阵的压缩存储

5.3.2稀疏矩阵

以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:(1)零值元素占了很大空间;(2)计算中进行了很多和零值的运算。(1)尽可能少存或不存零值元素；解决问题的原则:(2)尽可能减少没有实际意义的运算；(3)操作方便。即：能尽可能快地找到与下标值(i，j)对应的元素，能尽可能快地找到同一行或同一列的非零值元。5.3.1特殊矩阵

特殊矩阵是指非零元素或零元素在矩阵中的分布有一定规律的矩阵。

对称矩阵元素满足条件

aij=aji1=<i,j=<n的n阶矩阵。按行序为主序：

a11a12

….

……..a1n

a21

a22

……..…….a2n

an1

an2

……..ann….a11a21a22a31a32an1ann…...…...k=01234n(n-1)/2n(n+1)/2-1例5.2对称矩阵n=5,1+2+3+4+5=5*(5+1)/2=15一维数组SA[1..15]作为数组A的存储结构:SA=(452313252816795)如:a[5,3]=a[3,5]=7k=5(5-1)/2+3-1=12故:sa[12]=74532152156313272528916795A=4520313252816795A=三角矩阵按行序为主序：Loc(aij)=Loc(a11)+[i*(i-1)/2+(j-1)]*L

a11

00

……..0

a21a22

0

……..0

an1an2an3……..ann

….0a11a21a22a31a32an1ann…...…...k=01234n(n-1)/2n(n+1)/2-1例5.3下三角矩阵4000052000

A=313002528016795如:a[5,3]=7k=5(5-1)/2+3-1=12故:sa[12]=7但a[3,5]=0对角矩阵

a11

a120

…………….0

a21

a22

a23

0

……………00

0

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

an-1,n0

0

……an,n-1ann

0

a32a33

a34

0

………0……………Loc(aij)=Loc(a11)+[2(i-1)+(j-1)]*L

按行序为主序：a11a12a21a22a23ann-1ann…...…...k=012343*n-3sa[k]和a[i,j]的一一对应关系:

sa[k],k=3*(i-1)+j-i,

a[i,j]=当|i-j|<=10当|i-j|>1a11a1200...0a21a22a230...0Anxn=0a32a33a34...0......000...ann-1ann例5.4对角矩阵4300052200A=010400028700095一维数组SA[0..3*5-3]作为数组A的存储结构:SA=(4352210428795)如:a[5,4]=9k=3*(5-1)+4-5=11故:sa[11]=95.3.2稀疏矩阵

假设m行n列的矩阵含t个非零元素，则称为稀疏因子。通常认为

0.05的矩阵为稀疏矩阵。稀疏矩阵的压缩存储方法:一、三元组顺序表二、行逻辑链接的顺序表三、十字链表

#defineMAXSIZE12500

typedefstruct{

inti,j;

//该非零元的行下标和列下标

ElemTypee;

//该非零元的值

}Triple;//三元组类型一、三元组顺序表typedefstruct{

Tripledata[MAXSIZE+1];

intmu,nu,tu;}TSMatrix;//稀疏矩阵类型6

7

8

121213931-3361443245218611564-7ije012345678T如何求转置矩阵？用常规的二维数组表示时的算法

其时间复杂度为:O(mu×nu)for(col=1;col<=nu;++col)

for(row=1;row<=mu;++row)T[col][row]=M[row][col];6

7

8

121213931-3361443245218611564-7ije012345678ije7

6

8

13-3161521122518319342446-76314012345678?M.dataT.data解决思路：

只要做到

将矩阵行、列值互换；将每个三元组中的i和j相互调换；重排三元组次序，使T.data中元素以N的行(M的列)为主序方法一：按M的列序转置按T.data中三元组次序依次在M.data中找到相应的三元组进行转置，即按照矩阵M的列序来进行置换。为找到M中每一列所有非零元素，需对其三元组表M.data从第一行起扫描一遍。由于M.data中以M行序为主序，所以由此得到的恰是T.data中应有的顺序。6

7

8

121213931-3361443245218611564-7ije012345678M.data7

6

8

13-3161521122518319342446-76314ije012345678T.dataqppppppppqqqqppppppppcol=1col=2StatusTransposeSMatix(TSMatrixM,TSMatrix&T){//采用三元组表存储表示，求稀疏矩阵M的转置矩阵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;}//TransposeSMatrixT(n)=O(nu*tu)方法二：快速转置按M.data中三元组次序转置，转置结果放入T.data中恰当位置。此法关键是要预先确定M中每一列第一个非零元在T.data中位置，为确定这些位置，转置前应先求得M的每一列中非零元个数。实现：设两个数组num[col]：表示矩阵M中第col列中非零元个数cpot[col]：指示M中第col列第一个非零元在T.data中位置显然有：cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1];(2colM.nu)6

7

8

121213931-3361443245218611564-7ije012345678M.dataije012345678T.datacolnum[col]cpot[col]1122323524715806817907

6

8

13-3161521122518319342446-76314pppppppp46297536

7

8

121213931-3361443245218611564-7ije012345678for(col=1;col<=M.nu;++col)num[col]=0;for(t=1;t<=M.tu;++t)++num[M.data[t].j];cpot[1]=1;for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];Col1234567Num[col]cpot[col]t1t1t1t1t2t2t2t1001357889StatusFastTransposeSMatrix(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];cpot[1]=1;

for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];

for(p=1;p<=M.tu;++p){//转置矩阵元素

col=M.data[p].j;q=cpot[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;++cpot[col];}//for}//if

returnOK;}//FastTransposeSMatrixT(n)=O(nu+tu)T(n)=O(mu*nu)

三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。#defineMAXMN500typedefstruct{Tripledata[MAXSIZE+1];

//非零元三元组表

intrpos[MAXMN+1];

//各行第一个非零元的位置表

intmu,nu,tu;}RLSMatrix;//行逻辑链接顺序表类型二、行逻辑链接的顺序表M=N=Q=Q=MN113145

ije123431222-1M.data122211

ije123432431-2N.data

21-1

ije1234

Q.dataparow123

rpos[arow]134brow1234rpos[brow]1235ccol12ctempt1tpq6p126tpp2tq-1tp=5p1tq4

324三、十字链表30050-100200011314522-1312^^^^^^^TypestructOLNode{

inti,j;

inte;

structOLNode*right,*down;

}OLNode;*OLink;

Typestruct{

OLink*rhead,*chead;

intmu,nu,tu;

}CrossList;§5.4广义表的类型定义ADTGlist{

数据对象：D＝{ei|i=1,2,..,n;n≥0;ei∈AtomSet或ei∈GList,AtomSet为某个数据对象}

数据关系：

LR＝{<ei-1,ei>|ei-1,ei∈D,2≤i≤n}}ADTGlist

基本操作:广义表是递归定义的线性结构，LS=(1,2,,n)其中：i

或为原子或为广义表例如:A=()F=(d,(e))D=((a,(b,c)),F)C=(A,D,F)B=(a,B)=(a,(a,(a,,)))广义表是一个多层次的线性结构例如：D=(E,F)其中:

E=(a,

(b,

c))

F=(d,(e))DEFa()d()bce广义表

LS=(1,2,…,n)的结构特点:1)广义表中的数据元素有相对次序；2)广义表的长度定义为最外层包含元素个数；3)广义表的深度定义为所含括弧的重数；注意：“原子”的深度为0

“空表”的深度为14)广义表可以共享；5)广义表可以是一个递归的表。递归表的深度是无穷值，长度是有限值。6)任何一个非空广义表LS=(1,2,…,n)

均可分解为

表头

GetHead(LS)=1和

表尾

GetTail(LS)=(2,…,n)两部分。例如:D=(E,F)=((a,(b,c))，F)GetHead(D)=EGetTail(D)=(F)GetHead(E)=aGetTail(E)=((b,c))GetHead(((b,c)))=(b,c)

GetTail(((b,c)))=()GetHead((b,c))=bGetTail((b,c))=(c)GetHead((c))=cGetTail((c))=()练习求下列广义表操作的结果：（1）GetHead((p,h,w));（2）GetTail(((a,b),(c,d)));（3）GetHead(GetTail(((a,b),(c,d))))。

结构的创建和销毁

InitGList(&L);DestroyGList(&L)