数据结构-数组与广义表课件

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

广义表的表示方法7/22/202325.1数组的类型定义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

>|0

jk

bk-1,1kn且ki,0

ji

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

}ADTArray7/22/20233

N维数组中含有b1*b2*…*bn个数组元素,数组中的每个元素都对应于一组下标：

(j1,j2,…,jn)每个下标的取值范围是：0≤ji≤bi–1,bi称为第i维的长度(i=1,2,…,n)。7/22/20234二维数组的定义:数据对象:

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

R={ROW,COL}

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

COL={<ai,j,ai+1,j>|0≤i≤b1-2,0≤j≤b2-1}7/22/20235二维数组示例:二维数组可看成是由行向量或列向量组成。7/22/20236二维数组可是看成定长线性表，其中的每个元素也是定长线性表，即是一维数组。那么N维数组的元素是？N-1维数组数组一旦被定义，它的维数和维界就不能被改变线性表、栈和队列、串、数组的数据结构的区别与联系？7/22/20237基本操作：InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn)7/22/20238

InitArray(&A,n,bound1,...,boundn)

操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。7/22/20239

DestroyArray(&A)

操作结果：销毁数组A。7/22/202310

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

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

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

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

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

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

OK。7/22/2023125.2数组的顺序表示和实现数组的基本操作⑴存取：给定一组下标，读出对应的数组元素；⑵修改：给定一组下标，修改与其相对应的数组元素。它们本质上只对应一种操作——寻址数组的基本操作与线性表的基本操作有何不同？7/22/202313

类型特点:1)只有引用型操作，没有加工型操作；2)数组是多维的结构，而存储空间是一个一维的结构。

有两种顺序映象的方式:1)以行序为主序(低下标优先)；2)以列序为主序(高下标优先)。7/22/202314例如：

称为基地址或基址。以“行序为主序”的存储映象二维数组A中任一元素ai,j

的存储位置

LOC(i,j)=LOC(0,0)+(b2×i＋j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2

L

b2=3L7/22/202315推广到一般情况，可得到n维数组数据元素存储位置的映象关系称为n维数组的映象函数。数组元素的存储位置是其下标的线性函数。=LOC(0,0,...,0)+(b2×...×bn

×j1+b3×...×bn×j2+...+bn×jn-1+jn)L

LOC(j1,j2,...,jn)=LOC(0,0,...,0)+∑ci

ji

i=1n其中cn=L，ci-1=bi×ci

,1<in。7/22/202316数组的顺序表示和实现见93页。7/22/2023171)特殊矩阵

非零元在矩阵中的分布有一定规则例如:三角矩阵对称矩阵对角矩阵2)稀疏矩阵非零元在矩阵中随机出现有两类矩阵：5.3矩阵的压缩存储7/22/2023181)特殊矩阵如:下三角矩阵,可以采用一个一维数组sa[n(n+1)/2]来存储。a11a21a22a31sa…an1…annk=0123n(n-1)/2n(n+1)/2-1sa的下标k可以用公式：k=i(i-1)/2+j-1进行计算。7/22/202319假设m行n列的矩阵含t个非零元素，则称为稀疏因子。通常认为

0.05的矩阵为稀疏矩阵。何谓稀疏(sparse)矩阵？7/22/202320稀疏矩阵的抽象数据类型定义:ADTSparseMatrix{

数据对象:

D={aij|1≤i≤m,1≤j≤n;aij∈ElemSet}

数据关系:

R={ROW,COL}ROW={<ai,j,ai,j+1>|1≤i≤m,1≤j≤n-1}COL={<ai,j,ai+1,j>|1≤i≤m-1,1≤j≤n}

}ADTSparseMatrix；基本操作：7/22/202321基本操作：CreateSMatrix(&M)DestroySMatrix(&M)PrintSMatrix(M)CopySMatrix(M,&T)AddSMatrix(M,N,&Q)SubtSMatrix(M,N,&Q)MultSMatrix(M,N,&Q)TransposeSMatrix(M,&T)7/22/202322

以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:1)零值元素占了很大空间;2)计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。如何存储稀疏矩阵呢？7/22/2023231)尽可能少存或不存零值元素；解决问题的原则:2)尽可能减少没有实际意义的运算；3)操作方便。即：能尽可能快地找到与下标值(i，j)对应的元素，能尽可能快地找到同一行或同一列的非零值元。7/22/2023242)随机稀疏矩阵的压缩存储方法:一、三元组顺序表二、行逻辑链接的顺序表三、十字链表7/22/202325

#defineMAXSIZE12500

typedef

struct{

inti,j;//该非零元的行下标和列下标

ElemTypee;//该非零元的值

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

struct{

Tripledata[MAXSIZE+1];

int

mu,nu,tu;//矩阵行数,列数,非零元素个数}TSMatrix;//稀疏矩阵类型7/22/202326如何求转置矩阵？7/22/202327用常规的二维数组表示时的算法其时间复杂度为:O(mu×nu)

for(col=1;col<=nu;++col)

for(row=1;row<=mu;++row)

T[col][row]=M[row][col];7/22/202328用“三元组”表示时如何实现？121415-522-731363428211451-522-7133643287/22/202329Status

TransposeSMatrix(TSMatrixM,TSMatrix

&T){

T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;

if(T.tu)

{//非零元素个数不为零

q=1;//q指T中的非零元素下标

for(col=1;col<=M.nu;++col)//T中的行

for(p=1;p<=M.tu;++p)//p指M中的非零元素下标

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;}

}//if

returnOK;}//TransposeSMatrix此算法的时间复杂度:

O(nu·tu)7/22/202330能不能设计出时间复杂度更低的算法呢？关键在于能不能找到一种方法对转换后的每一行的起始位置进行定位。7/22/202331首先应该确定每一行的第一个非零元在三元组中的位置。

cpot[1]=1;

for(col=2;col<=M.nu;++col)

cpot[col]=cpot[col-1]+num[col-1];Num[col]表示矩阵M中第col列非零元素个数Cpot[col]指示矩阵中第col列第一个非零元素在转置后的三元组中的位置7/22/202332Status

FastTransposeSMatrix(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){}

}//if

returnOK;}//FastTransposeSMatrix求转置矩阵元素7/22/202333col=M.data[p].j;q=cpot[col];//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]；//col列的下一个位置求转置矩阵元素7/22/202334分析算法FastTransposeSMatrix的时间复杂度：时间复杂度为:O(M.nu+M.tu)for(col=1;col<=M.nu;++col)……for(t=1;t<=M.tu;++t)……for(col=2;col<=M.nu;++col)……for(p=1;p<=M.tu;++p)……7/22/202335三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。二、行逻辑联接的顺序表7/22/202336

#defineMAXMN500

typedef

struct{Tripledata[MAXSIZE+1];

int

rpos[MAXMN+1];//各行第一个非零

//元素位置

int

mu,nu,tu;}

RLSMatrix;//行逻辑链接顺序表类型修改前述的稀疏矩阵的结构定义，增加一个数据成员rpos，其值在稀疏矩阵的初始化函数中确定。7/22/202337例如：给定一组下标，求矩阵的元素值ElemType

value(RLSMatrixM,intr,intc){

p=M.rpos[r];

while(M.data[p].i==r&&M.data[p].j<c)p++;

if(M.data[p].i==r&&M.data[p].j==c)

returnM.data[p].e;

elsereturn0;}//value7/22/202338矩阵乘法的经典算法:for(i=1;i<=m1;++i)

for(j=1;j<=n2;++j){Q[i][j]=0;

for(k=1;k<=n1;++k)Q[i][j]+=M[i][k]*N[k][j];

}其时间复杂度为:O(m1×n2×n1)7/22/202339

Q初始化；

ifQ是非零矩阵{//逐行求积

for(arow=1;arow<=M.mu;++arow){

//处理M的每一行

ctemp[]=0;//累加器清零

计算Q中第arow行的积并存入ctemp[]中；将ctemp[]中非零元压缩存储到Q.data；

}//forarow}//if两个稀疏矩阵相乘（QMN）

的过程可大致描述如下：示例见P1017/22/202340

Status

MultSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix

&Q){if(M.nu

!=

N.mu)returnERROR;

Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;

if(M.tu*N.tu

!=0){//Q是非零矩阵

for(arow=1;arow<=M.mu;++arow){

//处理M的每一行

}//forarow}//ifreturnOK;}//MultSMatrix7/22/202341

ctemp[]=0;//当前行各元素累加器清零

Q.rpos[arow]=Q.tu+1;for(p=M.rpos[arow];p<M.rpos[arow+1];++p){//对当前行中每一个非零元

brow=M.data[p].j;//N的行与M的列相同

if(brow<N.nu)t=N.rpos[brow+1];

else{t=N.tu+1;}//确定该行非零元的终止位置

for(q=N.rpos[brow];q<t;++q){

ccol=N.data[q].j;//乘积元素在Q中列号

ctemp[ccol]+=M.data[p].e*N.data[q].e;

}//forq

}//求得Q中第crow(=arow)行的非零元

for(ccol=1;ccol<=Q.nu;++ccol)if(ctemp[ccol]){

if(++Q.tu>MAXSIZE)returnERROR;

Q.data[Q.tu]={arow,ccol,ctemp[ccol]};

}//if处理的每一行M7/22/202342分析上述算法的时间复杂度累加器ctemp初始化的时间复杂度为(M.muN.nu)，求Q的所有非零元的时间复杂度为(M.tuN.tu/N.mu)，进行压缩存储的时间复杂度为(M.muN.nu)，总的时间复杂度就是(M.muN.nu+M.tuN.tu/N.mu)。若M是m行n列的稀疏矩阵，N是n行p列的稀疏矩阵，则M中非零元的个数M.tu=Mmn，

N中非零元的个数

N.tu=Nnp，相乘算法的时间复杂度就是(mp(1+nMN))

，当M<0.05和N<0.05及n<1000时，相乘算法的时间复杂度就相当于(mp)。7/22/202343三、十字链表当矩阵的非零元个数和位置在操作过程中变化较大时，不宜采用三元组顺序表的存储表示方式。例如，将矩阵B加到矩阵A，由于非零元的插入和删除都会引起A.Data中元素的移动。因此，此类矩阵操作，采用链式三元组存储表示更为恰当。十字链表就是一种采用链式存储结构的三元组表示方法。7/22/20234430050-100200011314522-1312^^^^^^^增加一个元素M[1,2]=2?7/22/202345稀疏矩阵的十字链表表示：typedef

struct

OLNode{

inti,j;//非零元的行和列下标

ElemTypee;

struct

OLNode*right,*down;//同行,同列的后继域}OLNode,*OLink;typedmf

struct{

OLink*rhead,*chead;//行、列链的头指针

int

mu,nu,tu;}CrossList;7/22/202346十字链表表示的矩阵元素的插入和删除都需要同时修改行链和列链。P104算法5.4给出了十字链表建立的过程。7/22/2023475.4广义表的类型定义广义表(GeneralizedList)是线性表的推广。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}}ADT

Glist基本操作:7/22/202348广义表是递归定义的线性结构，

LS=(1,2,,n)其中：i

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

E=(a,

(b,

c))

F=(d,(e))DEFa()d()bce7/22/202350广义表

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

注意:“原子”的深度为0“空表”的深度为14)广义表可以共享；5)广义表可以是一个递归的表。递归表的深度是无穷值，长度是有限值。7/22/2023516)任何一个非空广义表

LS=(1,2,…,n)

均可分解为

表头

Head(LS)=1和

表尾

Tail(LS)=(2,…,n)两部分。例如:

D=(E,F)=((a,(b,c))，F)Head(D)=ETail(D)=(F)Head(E)=aTail(E)=((b,c))Head(((b,c)))=(b,c)Tail(((b,c)))=()Head((b,c))=bTail((b,c))=(c)Head((c))=cTail((c))=()7/22/202352

结构的创建和销毁

InitGList(&L);DestroyGList(&L);

CreateGList(&L,S);CopyGList(&T,L);基本操作

状态函数

GListLength(L);GListDepth(L);

GListEmpty(L);GetHead(L);GetTail(L);

插入和删除操作

InsertFirst_GL(&L,e);

DeleteFirst_GL(&L,&e);

遍历

Traverse_GL(L,Visit());7/22/2023535.5

广义表的表示方法由于广义表中的数据元素具有不同的结构，因此难以用顺序结构表示，通常采用具有头、尾指针的链表结构。表结点:原子结点：tag=1hptptag=0d