第5章 数组与广义表.ppt

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

1、第五章数组和广义表数组稀疏矩阵广义表数组定义相同类型的数据元素的集合。一维数组的示例352749186054778341020123456789一维数组数组的定义和初始化main(){inta1[3]={3,5,7},*elem;for(inti=0;i<3;i++)printf(“%d”,a1[i],“”);//静态数组elem=a1;for(inti=0;i<3;i++){printf(“%d”,*elem,“”);//动态数组elem++;}//endfor}//endmain一维数组存储方式35274918605477834102012345

2、6789llllllllllLOC(i)=LOC(i-1)+l=a+i*l(i>=0)LOC(i)=LOC(i-1)+l=a+i*l,i>0a,i=0a+i*la二维数组行优先存放：设数组开始存放位置LOC(0,0)=a,每个元素占用l个存储单元LOC(i,j)=a+(i*m+j)*li>=0,j>=0三维数组各维元素个数为m1,m2,m3下标为i1,i2,i3的数组元素的存储地址：（按页/行/列存放）LOC(i1,i2,i3)=a+(i1*m2*m3+i2*m3+i3)*l前i1页总元素个数第i1页的前i2行总元素个数i1>=0,i2>=0,i3>=0n维

3、数组各维元素个数为m1,m2,m3,…,mn下标为i1,i2,i3,…,in的数组元素的存储地址：LOC(i1,i2,…,in)=a+(i1*m2*m3*…*mn+i2*m3*m4*…*mn++……+in-1*mn+in)*l二维数组三维数组行向量下标i页向量下标i列向量下标j行向量下标j列向量下标k数组的顺序存储表示#defineMAX_ARRAY_DIM8typedefstruct{ElenmType*base;//数组元素基址intdim;//维数int*bounds;//数组维界基址int*constants;//数组映像函数基址}Array;Sta

4、tusInitArray(Array&A,intdim,...){va_listap;//ap是存放变长参数表信息的数组if(dim<1

5、

6、dim>MAX_ARRAY_DIM)returnERROR;A.dim=dim;A.bounds=(int*)malloc(dim*sizeof(int));if(!A.bounds)exit(OVERFLOW);//若各维长度合法，则存入A.bounds,并求出元素总数elemtotal=1;va_start(ap,dim);for(i=0;i

7、/取得各维大小if(A.bounds[i]<0)returnUNDERFLOW;elemtotal*=A.bounds[i];}//endforva_end(ap);A.base=(ElemType*)malloc(elemtotal*sizeof(ElemType));if(!A.base)exit(OVERFLOW);//求映像函数的常数ci,并存入A.constants[i-1],i=1,...,dimA.constants[dim-1]=1;//L=1,指针增减以元素大小为单位for(i=dim-2;i>=0;--i){A.constants[i]=

8、A.bounds[i+1]*A.constants[i+1];}returnOK;}//endfunction//若ap指示的各下标值合法，则求出该元素在A中相对地址offStatusLocate(ArrayA,va_listap,int&off){off=0;for(i=0;i

9、

10、ind>=A.bounds[i])returnOVERFLOW;off+=A.constants[i]*ind;}returnOK;}//求取指定位置的值StatusValue(ArrayA,ElemT

11、ype&e,...){va_start(ap,e);if((result=Locate(A,ap,off)<=0)returnresult;e=*(A.base+off);returnOK;}//endfunction特殊矩阵的压缩存储特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间，对可以不存储的元素，如零元素或对称元素，不再存储。对称矩阵三对角矩阵对称矩阵的压缩存储设有一个nn的对称矩阵A。在矩阵中，aij=aji为节约存储空间，只存对角线及对角线以上的元素，或者只存对角线及对角线以下的

12、元素。前者称为上三角矩阵，后者称为下三角矩阵。把它们