第5章 数组广义表

《第5章 数组广义表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章数组广义表5.1数组的类型定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的类型定义5.5广义表的存储结构**5.6m元多项式的表示**5.7广义表的递归算法1.二维数组(矩阵)：Amn=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=(a

2、0j,a1j,…,am-1,j)5.1数组的类型定义一个二维数组类型可以定义为其分量类型为一维数组类型的线性表类型;同理，一个n维数组类型可以定义为其数据元素为n-1维数组类型的线性表类型。5.1数组的类型定义ADTArray{数据对象：ji=0,…,bi-1,i=1,2,…,n,D＝{aj1,j2,…,jn

3、n称为数据元素的维数，bi是数组第i维的长度，ji是数组元素的第i维下标，aj1,j2,…,jn∈ElemSet}数据关系：R＝{R1,R2,...,Rn}Ri＝{

4、ji+1,...jn>

5、0jkbk-1,1kn且ki,0jibi-2,aj1,...ji,...jn,aj1,...ji+1,...jn∈D,i=2,...,n}基本操作}ADTArray5.1数组的类型定义基本操作：InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn)***5.1数组的类型定义1、数组元素的地址关系以二维数组为例说明。对于二维

6、数组有两种存储方式：(1)以行序为主的存储方式;(2)以列序为主的存储方式。a00a01a02a03a10a11a12a13a20a21a22a23a00a01a02a03a10a11a12a13a20a21a22a23第7个位置第8个位置假如a00的起始地址是loc(a00),数组中每一个元素所占空间为L,a12的起始地址怎么计算：行序：loc(a12)=loc(a00)+[(1×4)+2]×L列序：loc(a12)=loc(a00)+[(2×3)+1]×L5.2数组的顺序表示和实现以行序为主序的存储结构的元素位置确

7、定给定数组A[b1][b2],每个元素所占空间为L,a00的起始地址记为loc(0,0),aij的起始地址为：LOC[i,j]=LOC[0,0]+(b2i+j)LA[b1][b2][b3]3维数组的数据元素aijk的存储位置：LOC(i,j,k)=LOC(0,0,0,)+(b2b3i+b3j+k)L5.2数组的顺序表示和实现A[b1][b2]...[bn]n维数组的数据元素存储位置：LOC(j1,j2,…jn)=LOC(0,0,…,0)+(b2…bnj1+b3…bnj2+…+bnjn-1+jn)

8、L5.2数组的顺序表示和实现#include//标准头文件，提供宏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

9、

10、dim>MA

11、X_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

12、.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(OV