第5章 数组广义表

第五章数组广义表

5.1数组的类型定义

5.2数组的顺序表示和实现

5.3矩阵的压缩存储

5.4广义表的类型定义

5.5广义表的存储结构**5.6m元多项式的表示**5.7广义表的递归算法1.二维数组(矩阵)：Amn=a00a01a02...a0,n-1a10a11a12...a1,n-1……………..am-1,0am-1,1am-1,2...am-1,n-1按行划分:A可看成一个线性表A=(a0,a1,…,am-1)ai=(ai0,ai0,…,ain-1)按列划分:A可看成一个线性表A=(a0,a1,…,an-1)aj=(a0j,a1j,…,am-1,j)5.1数组的类型定义

一个二维数组类型可以定义为其分量类型为一维数组类型的线性表类型;

同理，一个n维数组类型可以定义为其数据元素为n-1维数组类型的线性表类型。

5.1数组的类型定义ADTArray{

数据对象：ji=0,…,bi-1,i=1,2,…,n,D＝{aj1,j2,…,jn|n称为数据元素的维数，bi是数组第i维的长度，ji

是数组元素的第i维下标，aj1,j2,…,jn∈ElemSet}

数据关系：R＝{R1,R2,...,Rn}

Ri＝{<aj1,...ji,...jn,aj1,...ji+1,...jn>|0jkbk-1,1kn且ki,0ji

bi-2,aj1,...ji,...jn,aj1,...ji+1,...jn∈D,i=2,...,n}基本操作}ADTArray

5.1数组的类型定义基本操作：InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn)***5.1数组的类型定义1、数组元素的地址关系

以二维数组为例说明。对于二维数组有两种存储方式：(1)以行序为主的存储方式;(2)以列序为主的存储方式。a00a01a02a03a10a11

a12

a13a20a21a22a23a00a01a02a03a10a11

a12

a13a20a21a22a23第7个位置第8个位置

假如a00的起始地址是loc(a00),数组中每一个元素所占空间为L,a12的起始地址怎么计算：行序：loc(a12)=loc(a00)+[(1×4)+2]×L

列序：loc(a12)=loc(a00)+[(2×3)+1]×L5.2数组的顺序表示和实现以行序为主序的存储结构的元素位置确定给定数组A[b1][b2],每个元素所占空间为L,a00的起始地址记为loc(0,0),aij的起始地址为：

LOC[i,j]=LOC[0,0]+(b2i+j)LA[b1][b2][b3]3维数组的数据元素aijk的存储位置：

LOC(i,j,k)=LOC(0,0,0,)+(b2b3i+b3j+k)L5.2数组的顺序表示和实现A[b1][b2]...[bn]n维数组的数据元素存储位置：LOC(j1,j2,…jn)=LOC(0,0,…,0)+(b2…bnj1+b3…bnj2+…+bnjn-1+jn)L

5.2数组的顺序表示和实现#include<stdarg.h>//标准头文件，提供宏va_start、

//va_arg和va_end,用于存放变长参数表#defineMAX_ARRAY_DIM8//数组维数typedefstruct{Elemtype*base;//基址

intdim;//维数

int*bound;//数组维界基址

int*constants;//数组映像函数常量基址}Array;5.2数组的顺序表示和实现StatusInitArray(Array&A,intdim,…){

if(dim<1||dim>MAX_ARRAY_DIM)returnERROR;A.dim=dim;A.bounds=(int*)malloc(dim*sizeof(int));if(!A.bounds)exit(OVERFLOW);elemtotal=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.bound[i];}va.end(ap);5.2数组的顺序表示和实现A.base=(ElemType*)malloc(elemtotal*sizeof(ElemType));if(!A.base)exit(OVERFLOW);A.constants=(int*)malloc(dim*sizeof(int));if(!A.constants)exit(OVERFLOW);A.constants[dim-1]=1;for(i=dim-2);i>=0;--i)A.constants[i]=A.bounds[i+1]*A.constants[i+1];returnOK;}***5.2数组的顺序表示和实现5.3矩阵的压缩存储

5.3.1特殊矩阵5.3.2稀疏矩阵5.3.3矩阵的压缩存储下(上)三角矩阵与对称矩阵A

1

00022

00453036781

23522

46343

75678下三角矩阵对称矩阵用一维数组存储sa[n*(n+1)/2]当i>=j时aij对应存储在A[i(i-1)/2+j-1]***5.3.1特殊矩阵假设

m行n列的矩阵含

t个非零元素，则称为稀疏因子。通常认为

0.05的矩阵为稀疏矩阵。何谓稀疏矩阵？5.3.2稀疏矩阵ADTSparseMatrix{

数据对象：D＝{aij|i=1,2,…,m;j=1,2,…,n;aij∈ElemSet,m,n分别为行数与列数}

数据关系：R＝{Row,Col}

Row＝{<ai,j,ai,j+1>|i=1,…,m,j=1,…,n-1}Col＝{<ai,j,ai+1,j>|i=1,…,m-1,j=1,…,n}基本操作}ADTArray

5.3.2稀疏矩阵基本操作：CreatSMatrix(&M)DestroyArray(&M)……………..MultSMatrix(M,N,&Q)TransposeSMatrix(M,&T)5.3.2稀疏矩阵随机稀疏矩阵的压缩存储方法:1、三元组顺序表2、行逻辑联接的顺序表3、十字链表5.3.2稀疏矩阵

数组的表示方法稀疏矩阵0

1

000000

2

01

0000((1，2，1)，(2，4，2)，(3，1，1))5.3.3矩阵的压缩存储

#defineMAXSIZE12500typedefstruct{

inti,j;

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

ElemTypee;

//该非零元的值

}Triple;//

三元组类型三元组顺序表typedefstruct{

Tripledata[MAXSIZE+1];//data[0]未用

intmu,nu,tu;

}TSMatrix;

//稀疏矩阵类型5.3.3矩阵的压缩存储如何求转置矩阵？5.3.3矩阵的压缩存储用常规的二维数组表示时的算法其时间复杂度为？

O(mu×nu)

for(col=1;col<=nu;++col)for(row=1;row<=mu;++row)T[col][row]=M[row][col];5.3.3矩阵的压缩存储用“三元组”表示时如何实现？121415-522-731363428211451-522-7133643285.3.3矩阵的压缩存储用“三元组”表示时如何实现？121415-522-731363428211451-522-7133643285.3.3矩阵的压缩存储StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){intp,q,col;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;}//Transpose5.3.3矩阵的压缩存储

分析算法TransposeSMatrix的时间复杂度：时间复杂度为:O(M.nu*M.tu)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;}5.3.3矩阵的压缩存储算法改进：121415-522-7313634281336211422-7432851-5for(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;}分析时间复杂性5.3.3矩阵的压缩存储算法改进：121415-522-7313634281336211422-7432851-5

设置num和cpot两个向量。num[col]表示矩阵M中第col列中有几个非零元，cpot[col]指示M中第col列的第一个非零元在b.data中的恰当位置。

cpot[1]=1cpot[col]=cpot[col-1]+num[col-1]5.3.3矩阵的压缩存储算法改进：121415-522-7313634281336211422-7432851-5col12345Num[col]12011Cpot[col]124455.3.3矩阵的压缩存储StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){intcol,t,p,q;intnum[20],cpot[20];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)//求M中每一列所含非零元的个数

++num[M.data[t].j];5.3.3矩阵的压缩存储cpot[1]=1;//求M中每一列的第一个非零元在b.data中的序号

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}//ifreturnOK;}//FastTransposeSMatrix5.3.3矩阵的压缩存储

分析算法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)……5.3.3矩阵的压缩存储三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。行逻辑联接的顺序表5.3.3矩阵的压缩存储

#defineMAXRC500typedefstruct{Tripledata[MAXSIZE+1];

intrpos[MAXRC+1];intmu,nu,tu;}RLSMatrix;//行逻辑链接顺序表类型将上节快速转置矩阵的算法中创建的指示“行”信息的辅助数cpot固定在稀疏矩阵的存储结构中。5.3.3矩阵的压缩存储两个矩阵相乘的经典算法

Q=M×NM是m1×n1,N是n1×n2,Q是m1×n2矩阵乘法的精典算法: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)5.3.3矩阵的压缩存储

稀疏矩阵相乘×＝5.3.3矩阵的压缩存储

ije11314522-1312

ije12221131-2324

ije12621-1324row1234rpos[row]1245row1234rpos[row]13455.3.3矩阵的压缩存储

StatusMultSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix&Q){intarow,brow,p,q,t,ctemp[30],l,ccol,tp;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是非零矩阵5.3.3矩阵的压缩存储

{for(arow=1;arow<=M.mu;++arow){for(l=1;l<=M.nu;++l)ctemp[l]=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.rpos[brow+1];elset=N.tu+1;5.3.3矩阵的压缩存储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)行的非零元5.3.3矩阵的压缩存储for(ccol=1;ccol<=Q.nu;++ccol)//压缩存储该行非零元

if(ctemp[ccol]){if(++Q.tu>MAXSIZE)returnERROR;Q.data[Q.tu].i=arow;Q.data[Q.tu].j=ccol;Q.data[Q.tu].e=ctemp[ccol];}//if}//forarow}//ifreturnOK;}//MultSMatrix5.3.3矩阵的压缩存储分析上述算法的时间复杂度累加器ctemp初始化的时间复杂度为(M.muN.nu)，求Q的所有非零元的时间复杂度为(M.tuN.tu/N.mu)，进行压缩存储的时间复杂度为(M.muN.nu)，总的时间复杂度就是(M.muN.nu+M.tuN.tu/N.mu)。5.3.3矩阵的压缩存储分析上述算法的时间复杂度若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)。***5.3.3矩阵的压缩存储十字链表30050-100200011314522-1312^^^^^^^5.3.3矩阵的压缩存储typedefstructOLNode{inti,j;ElemTypee;StructOLNode*right,*down;}OLNode;*OLink;typedefstruct{OLink*rhead,*chead;intmu,nu,tu;}CrossList;5.3.3矩阵的压缩存储十字链表StatusCreateSMatrix_OL(CrossList&M){if(M)free(M);scanf(&m,&n,&t);M.mu=m;M.nu=n;M.tu=t;if(!(M.rhead=(OLink*)malloc((m+1)*sizeof(OLink))))returnERROR;if(!(M.chead=(OLink*)malloc((n+1)*sizeof(OLink))))returnERROR;for(inta=1;a<=m;a++)M.rhead[a]=NULL;for(intb=1;b<=n;b++)M.chead[b]=NULL;5.3.3矩阵的压缩存储十字链表for(intc=1;c<=t;c++){//按任意次序输入非零元

scanf(&i,&j,&e);if(!(p=(OLNode*)malloc(sizeof(OLNode))))returnERROR;p->i=i;p->j=j;p->e=e;p->down=NULL;p->right=NULL;//新结点

if(M.rhead[i]==NULL||M.rhead[i]->j>j){p->right=M.rhead[i];M.rhead[i]=p;}5.3.3矩阵的压缩存储十字链表else{for(q=M.rhead[i];(q->right)&&(q->right->j<j);q=q->right);p->right=q->right;q->right=p;}//完成行插入

if(M.chead[j]==NULL||M.chead[j]->i>i){p->down=M.chead[j];M.chead[j]=p;}else{//寻查在列表中的插入位置

for(q=M.chead[j];(q->down)&&q->down->i<i;q=q->down);p->down=q->down;q->down=p;}//完成列插入

}//forreturnOK;}//CreateSMatrix_OL5.3.3矩阵的压缩存储十字链表(董事长、总经理、秘书、人事部、分公司....)(总经理、秘书、人事部、分公司....)5.4广义表的类型定义

广义表是线性表的推广，也称列表（Lists）。

1.定义

广义表是n个元素的有限序列，记作

A=（a1,a2,……an)

其中A是表名，n是广义表的长度，ai是广义表的元素，它可以是单个元素，也可以是广义表。原子：

如果ai是单个元素，称为原子，用小写字母表示;

子表：

如果ai是广义表，称为子表，用大写字母表示。5.4广义表的类型定义

1.定义

广义表是n个元素的有限序列，记作

A=（a1,a2,……an)

表头（Head）：非空广义表的第一个元素a1;

表尾（Tail）：除了表头的其余元素组成的表;

深度：广义表中括号嵌套的最大层数。

2.特点存储空间难以确定，常采用链式存储。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}

基本操作：}ADTGlist5.4广义表的类型定义InitGlist(&L)CreateGlist(&L,S)DestroyGList(&L)CopyGList(&T,L)GListLength(L)GListDepth(L)GetHead(L)GetTail(L)………5.4