《数据结构与算法》第5章数组和广义表

第5章数组和广义表5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5·4广义表5.5广义表的存储结构5.1数组的定义说明：

A是数组的名字

A是一个n维数组，共有

bi个元素

bi是第i维的长度，称为维界，表示该维的下标变化为0∽bi-1

每一个数组元素的类型都是int

除第一个元素外，每个元素都有一个直接前驱

除最后一个元素外，每个元素都有一个直接后继在C中定义：intA[b1][b2]…..[bn];因此，可以把数组看成是一个定长的线性表，表中每个元素也可以是一个定长的线性表，…...1.给定一组下标，存取或修改相应元素的值2.查找满足条件的数组元素3.对数组元素进行排序数组的使用：数组元素数组的ADTADTArray{数据对象：D={aj1j2….jn|n(>0)称为数组的维数，

bi是数组的第i维的长度

ji是数组元素的第i维下标，ji=0,…,bi-1,1≤i≤naj1j2….jn∈ElemSet}

数据关系：R={R1,R2,….,Rn}Ri={<aj1…ji….jn，aj1…ji+1...jn>|0≤jk≤bk-1,1≤k≤n且k≠i,0≤ji≤bi-2,aj1…ji….jn，aj1…ji+1...jn∈D,i=1,2,…,n}根本操作：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。}ADTArray5.2数组的顺序表示和实现行序：越是后面的下标变化越快列序：越是前面的下标变化越快数组一旦定义，可由下标知道任意元素的位置一维：Loc[i]=Loc[0]+i*h

//h为每个元素占用的存储单元长度h

h

h

hh

hhh

h

h0123456789二维：Loc[i,j]=Loc[0,0]+(b2*i+j)*h三维：Loc[i,j,k]=Loc[0,0,0]+(b2*b3*i+b3*j+k)*h下标i

下标

i下标j

下标

j

下标

kn维：Loc[j1,j2,….,jn]=Loc[0,0,…,0]+(b2*b3*…*bn*j1+b3*b4*…*bn*j2+….+bn*jn-1+jn)*h令C1=b2*b3*…*bn*hC2=b3*b4*….*bn*h……..Cn-1=bn*hCn=hLoc[j1,j2,….jn]=Loc[0,0,…,0]+

ji*CiCi=Ci+1*bi+1函数中可变个数参数的使用方法：//实例：printf(*format,……)1.参加相关的头文件#include<stdarg.h>2.定义指向第一个可变参数的指针typedefvoid*va_list;3.利用最后一个固定参数找到第一个可变参数voidva_start(va_listargptr,last_parm)//最后一个固定参数名为last_parm//argptr指向变长参数表中的第一个参数4.依次找到下一个可变参数typeva_arg(va_listargptr,type)//返回argptr指向的type类型的参数，argptr指向下一个参数5.指针悬空〔不指向任何地方〕voidva_end(va_listargptr)//-----数组的顺序存储表示-----

#include<stdarg.h>

//标准头文件，提供宏va_start、va_arg和va_end//用于存取变长参数表#defineMAX_ARRAY_DIM8

//假设数组维数的最大值为8typedefstruct{ElemType*base;//数组元素基址,由InitArray分配

intdim//数组维数

int*bounds;//数组维界基址,由InitArray分配,biint*constants

//数组映象函数常量基址，由InitArray分配,ci}Array;//-----根本操作函数原型说明-----StatusInitArray(Array&A,intdim,…);//假设维数dim和随后的各维长度合法，那么构造相应的数组A，并返回OK。StatusDestroyArray(Array&A);//销毁数组A。StatusValue(ArrayA,ElemType&e,…);//A是n维数组，e为元素变量，随后是n个下标值。//假设各下标不超界，那么e赋值为指定的A的元素值，并返回OK。StatusAssign(Array&A,ElemTypee,…);//A是n维数组，e为元素变量，随后是n个下标值。//假设各下标不超界，那么将e的值赋给指定的A的元素，并返回OK。//-----根本操作的算法描述-----StatusInitArray(Array&A,intdim,…);1.获得dim2.申请空间存放bi的值4.计算数组元素个数elemtotal3.获得bi的值5.申请空间存放A中所有元素的值6.申请空间存放Ci的值存放bici的值给A分配存储空间//-----根本操作的算法描述-----StatusInitArray(Array&A,intdim,…){//假设维数dim和各维长度合法，那么构造相应的数组A，并返回OK。if(dim<1||dim>MAX_ARRAY_DIM)returnERROR;A.dim=dim;A.bounds=(int*)malloc(dim*sizeof(int));if(!A.bounds)exit(OVERFLOW);//假设各维长度合法，那么存入A.bounds,并求出A的元素总数elemtotalelemtotal=1;va_start(ap,dim);//ap为va_list类型，是存放变长参数表信息的数组for(i=0;i<dim;++i){A.bounds[i]=va_arg(ap,int);if(A.bounds[i]<0)returnUNDERFLOW;elemtotal*=A.bounds[i];}va_end(ap);A.base=(ElemType*)malloc(elemtotal*sizeof(ElemType));if(!A.base)exit(OVERFLOW);

//求映象函数的常数Ci,A.constants[i-1],i=1,…,dimA.constants=(int*)malloc(dim*sizeof(int));if(!A.constants)exit(OVERFLOW);A.constants[dim-1]=1;//h=1,指针的增减以元素的大小为单位

for(i=dim-2;i>=0;--i)A.constants[i]=A.bounds[i+1]*A.constants[i+1];returnOK;}StatusDestroyArray(Array&A){//销毁数组Aif(!A.base)returnERROR;

free(A.base);A.base=NULL;if(!A.bounds)returnERROR;

free(A.bounds);A.bounds=NULL;if(!A.constants)returnERROR;

free(A.constants);A.constants=NULL;returnOK;}StatusLocate(ArrayA,va_listap,int&off){//假设ap指示的各下标值合法，//那么求出该元素在A中的相对地址offoff=0;for(i=0;i<A.dim;++i){ind=va_arg(ap,int);if(ind<0||ind>=A.bounds[i])returnOVERFLOW;off+=A.constants[i]*ind;}returnOK;}StatusValue(ArrayA,ElemType&e,…){//A是n维数组，e为元素变量，随后是n个下标值。//假设各下标不超界，那么将e的值赋给指定的A的元素，并返回OK。va_start(ap,e);if((result=Locate(A,ap,off))<=0)returnresult;e=*(A.base+off);returnOK;}StatusAssign(Array&A,ElemTypee,…){//A是n维数组，e为元素变量，随后是n个下标值。//假设各下标不超界，那么将e的值赋给指定的A的元素，并返回OK。va_start(ap.e);if((result=Locate(A,ap,off))<=0)returnresult;*(A.base+off)=e;returnOK;}5.3矩阵的压缩存储一、特殊矩阵1．对称矩阵

n阶矩阵满足：aij=aji

a11a12a13a14a15a16

a21a22a23a24a25a26

a31a32a33a34a35a36

a41a42a43a44a45a46

a51a52a53a54a55a56a61a62a63

a64a65a66a11a12a13a14a15a16

a21a22a23a24a25a26

a31a32a33a34a35a36

a41a42a43a44a45a46

a51a52a53a54a55a56a61a62a63

a64a65a66将n2个矩阵元素压缩存储到n(n+1)/2个存储单元中a[1..n2]与sa[0..n(n+1)/2-1]的对应关系?a11a21a22a31a32a33a41a42a43a44

a51a52a53a54a55a61a62a63

a64a65

a66A中任意一元素aij与sa[k]之间存在对应关系:k=i

(i-1)/2+j-1当i≥j时j

(j-1)/2+i-1当i<j时2．对角矩阵带宽为2b+1的带状矩阵当0

i,j

n-1且|i-j|>b时ai,j=0带状区域中共有(2b+1)n-b(b+1)个元素a11a12

a21a22a23

an-1,nan,n-1an,n0元素非0元素0元素bb存储方法：除去第一行和最后一行，每行都存放2b+1个元素整个带状矩阵放在(2b+1)n-2b个单元中，增补了b(b-1)个元素，增补的方法是以对角线为中心,左右各b个元素,缺乏补齐Loc(a[i][i])=Loc(a[i-1][i-1])+(2b+1)h=Loc(a[0][0])+(2b+1)*i*hLoc(a[i][j])=Loc(a[i][i])+(j-i)*h=Loc(a[0][0])+(2bi+j)h例：b=1,n=61,11,22,12,22,33,23,33,44,34,44,55,45,55,66,56,61,1 1,2 2,1 2,2 2,3 3,2 3,3 3,44,3 4,4 4,5 5,4 5,5 5,6 6,5 6,6例：b=2,n=61,11,21,32,12,22,32,43,13,23,33,43,54,24,34,44,54,65,35,45,55,66,46,56,61,11,21,32,12,22,32,43,13,23,33,43,54,24,34,4 4,54,65,35,4 5,55,6 6,46,56,6非零元比零元少，且分布没有规律

=t/(m*n)

0.05二、稀疏矩阵

(SparseMatrix)行数m=6,列数n=7,非零元素个数t=6

1·稀疏矩阵的ADTADTSpareMatrix{数据对象：D={aij|i=1,2,…,m;j=1,2,…,n;ai,j∈ElemSet,m和n分别称为矩阵的行数和列数}数据关系：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}根本操作：CreateSMatrix(&M);操作结果：创立稀疏矩阵M。DestroySMatrix(&M);初始条件：稀疏矩阵M存在。操作结果：销毁稀疏矩阵M。

PrintSMatrix(M);

初始条件：稀疏矩阵M存在。操作结果：输出稀疏矩阵M。

CopySMatrix(M,&T);

初始条件：稀疏矩阵M存在。操作结果：由稀疏矩阵M复制得到T。

AddSMatrix(M,N,&Q);

初始条件：稀疏矩阵M与N的行数和列数对应相等。操作结果：求稀疏矩阵的和Q=M+N。

SubSMatrix(M,N,&Q);

初始条件：稀疏矩阵M与N的行数和列数对应相等。操作结果：求稀疏矩阵的差Q=M-N。MulSMatrix(M,N,&Q);

初始条件：稀疏矩阵M的列数等于N的行数。操作结果：求稀疏矩阵的积Q=M*N。

TransposeMatrix(M,&T);

初始条件：稀疏矩阵M存在。操作结果：求稀疏矩阵M的转置疏矩T。}ADTSparseMatrix2·稀疏矩阵的压缩存储用一个三元组(i,j,aij)表示矩阵中的一个非零元再加上行数m和列数n就可以唯一确实定一个稀疏矩阵0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0三元组表((1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))稀疏矩阵〔1〕三元组顺序表用顺序结构表示三元组，以行序为主序//-----稀疏矩阵的三元组顺序表存储表示-----#defineMAXSIZE12500//假设非零元素个数的最大值为12500typedefstruct{inti,j;//该非零元素的行下标和列下标ElemTypee;}Triple；typedefstruct{Tripledata[MAXSIZE+1];//非零元素三元组表，data[0]未用intmu,nu,tu;//矩阵的行数、列数和非零元素个数}TSMatrix;((1,3,-3),(1,6,15),(2,1,12),(2,5,18),(3,1,9),(3,4,24),(4,6,-7),(6,3,14))矩阵转置01290 00 0 00 0 0 00 0 -30 0 0 0140 00 24 0 00 0 018 0 0 00 0 1500 -7 000三元组表((1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))StatusTransposeSMatrix(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;}//TransposeMatrix应确切知道转置前每一列的第一个非零元在T中的位置用num[col]表示M中第col列中非零元的个数

cpos[col]表示M中第col列的第一个非零元在T的位置按三元组的顺序进行转置col 1 2 3 4 5 6 7 num[col] 2 2 2 1 0 1 0 cpos[col] 1 3 5 7 8 8 9 01290 00 0 00 0 0 00 0 -30 0 0 0140 00 24 0 00 0 018 0 0 00 0 1500 -7 000((1,3,-3),(1,6,15),(2,1,12),(2,5,18),(3,1,9),(3,4,24),(4,6,-7),(6,3,14))((1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))StatusFastTransposeSMatrix(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)num[col]=0;for(t=1;t<=M.tu;++t)++num[M.data[t].j];

//求M中每一列含非零元素个数

cpos[1]=1;for(col=2;col<=M.nu;++col)

//求第col列中第一个非零元素在T.data中的序号

cpos[col]=cpos[col-1]+num[col-1];for(p=1;p<=M.tu;++p){col=M.data[p].j;q=cpos[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;++cpos[col];}}returnOK;}//FastTransposeMatrix〔2〕行逻辑链接的顺序表两个矩阵相乘的一般方法：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];}假设M和N都是稀疏矩阵，那么M[i][k]和N[k][j]中有一个是零，就不用相乘，因此，实际是M中的三元组的j与N中三元组的i相同才相乘因而要记录矩阵中每一行的第一个非零元和最后一个非零元在三元组中的位置行逻辑顺序表类型typedefstruct{Tripledata[MAXSIZE+1];//非零元素三元组表

intrpos[MAXRC+1];//各行第一个非零元素的位置表

intmu,nu,tu;//矩阵的行数、列数和非零元素个数}RLSMatrix;30 050-10 020 0 0M.data=((1,1,3),(1,4,5),(2,2,-1),(3,1,2))M.rpos:M.mu=3M.nu=4M.tu=4row 1 2 3 rpos[row] 1 3 4N.data=((1,1,1),(1,2,2),(3,2,4),(4,1,-2))N.rpos: 1 20 00 4-2 0row 1 2 3 4rpos[row] 1 3 3 4N.mu=4N.nu=2N.tu=4可能与(1,1,3)相乘的元素有:(1,1,1)、(1,2,2)存(1,1)、(1,2)可能与(1,4,5)相乘的元素有:(4,1,-2)存(1,1)可能与(3,1,2)相乘的元素有:(1,1,1)、(1,2,2)存(3,1)、(3,2)30 050-10 020 0 0M.data=((1,1,3),(1,4,5),(2,2,-1),(3,1,2))M.rpos:M.mu=3M.nu=4M.tu=4row123 rpos[row] 13 4N.data=((1,1,1),(1,2,2),(3,2,4),(4,1,-2))N.rpos: 1 20 00 4-2 0row 1 2 3 4rpos[row] 1 3 3 4N.mu=4N.nu=2N.tu=4第1行：(1,4,5)

(4,1,-2)30 050-10020 00M.data=((1,1,3),(1,4,5),(2,2,-1),(3,1,2))M.rpos:M.mu=3M.nu=4M.tu=4row123 rpos[row] 13 4N.data=((1,1,1),(1,2,2),(3,2,4),(4,1,-2))N.rpos: 1 20 00 4-2 0row 1 2 3 4rpos[row] 1 3 3 4N.mu=4N.nu=2N.tu=4(1,1,3)(1,1,1)(1,1,3)(1,2,2)Q初始化；if〔Q是非零矩阵〕{//逐行求积for(arow=1;arow<=M.mu;++arow)//处理M的每一行{ctemp[]=0;//累加器清零计算Q中第arow行的积并存入ctemp[]中；将ctemp[]中非零元素压缩存储到Q.data;}//forarow}//if两个稀疏矩阵相乘〔Q=M*N〕的大致过程：StatusMultSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix&Q){

//求矩阵乘积Q=M*N，采用行逻辑链接存储表示

if(M.nu!=N.mu)returnERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;

//Q初始化

if(M.tu*N.tu!=0)//Q是非零矩阵

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

{//处理M的每一行

ctemp[1..N.nu]=0;

//当前行各元素累加器清零

Q.rpos[arow]=Q.tu+1;

if(arow<M.mu)tp=M.rpos[arow+1];elsetp=M.tu+1;for(p=M.rpos[arow];p<tp;++p)

{

//对当前行中每一个非零元素

brow=M.data[p].j;

//找到对应元素在N中的行号

if(brow<N.mu)t=N.rops[brow+1];elset=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中第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}//forarow}//ifreturnOK;}//MultSMatrix〔3〕十字链表当稀疏矩阵中非零元的个数和位置变化较大时，可采用链式存储结构:ij edown right同一行的非零元通过right链接成一个线性表同一列的非零元通过down链接成一个线性表30 0 50-10 020 0 0//-----稀疏矩阵的十字链表表示和建立十字链表的算法-----typedefstructOLNode{inti,j;//该非零元素的行和列下标

ElemTypee;structOLNode*right,*down;//该非零元素所在行表和列表的后继链域}OLNode;*OLink;typedefstruct{OLink*rhead,*chead;//行和列链表头指针向量基址由CreatSMATRIX分配

intmu,nu,tu;//稀疏矩阵的行数、列数和非零元素个数}CrossList;ij edown right5·4广义表广义表是线性表的推广，又称列表(张三，李四，王五，马六，......)((张三，...),(李四,王五，....),(马六,孙七,......),...)

一、广义表的表示广义表一般记作：LS=(a1,a2,……,an)

其中：LS为广义表的名称，n为广义表的长度，

ai为广义表的元素每个元素既可以是单个不可分的元素

-----广义表LS的原子也可以是一个广义表

--------广义表LS的子表一般用大写字母表示广义表的名称，用小写字母表示原子非空广义表的第一个元素称为LS的表头(head)

其余元素组成的表称为LS的表尾(tail)1．广义表是一个多层次的结构2．广义表可以为其他广义表所共享3．广义表可以是一个递归的表4．〔〕与〔〔〕〕不同二、广义表特性例： A=() B=(e) C=(a,(b,c,d)) D=(A,B,C) E=(a,E)长度：01232三、抽象数据类型广义表定义ADTGlist{数据对象：D={ei|i=1,2,…,n;n≥0;ei∈AtomSet或ei∈Glist,AtomSet为某个数据对象}数据关系：R1={<ei-1,ei>|ei-1,ei∈D,2≤i≤n}根本操作：InitGlist(&L);操作结果：创立空的广义表L。CreateGlist(&L,S);初始条件：S是广义表的书写形式串。操作结果：由S创立广义表L。DestroyGlist(&L);初始条件：广义表L存在。操作结果：销毁广义表LCopyGlist(&T,L);

初始