数据结构数组和 广义 表2.ppt

《数据结构数组和 广义 表2.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、Chapter5Array&GeneralList教学内容1、数组的定义和顺序存储方式2、特殊矩阵的压缩存储3、广义表的概念及存储表示一、数组的基本概念相同类型的数据元素的集合。记作：A=(A0,A1,…,Am-1)352749860547783410201234567895.1数组二维数组可看作是每个数据元素都是相同类型的一维数组的一维数组。多维数组依此类推。一维数组二维数组三维数组行向量下标m2页向量下标m1列向量下标m3行向量下标m2列向量下标m3二、数组的存储实现一维数组存储方式LOC(i)=LOC(i-1)+l=a

2、+i*lLOC(i)=LOC(i-1)+l=a+i*l,i>0a,i=0352749186054778341020123456789lllllllllla+i*la多维数组存储方式由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。⑴行优先顺序——将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。⑵列优先顺序——将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后通常有两种顺序存储方式：二维数组a[n][m]设数组开始存放位置L

3、OC(0,0)=a,每个元素占用l个存储单元，那么LOC(i,j)=a+(i*m+j)*l-------]][[]][[]][[]][[]][[]][[]][[]][[]][[]][[]][[]][[111101121202111101101000mnananamaaamaaamaaaLMOMMLLL行优先存放例5.1对二维数组floata[5][4]计算：1、数组a中的数组元素数目；2、若数组a的起始地址为2000,且每个数组元素长度为32位(即4个字节),数组元素a[3][2]的内存地址。解：该数组的元素数目共有5*4=20

4、个LOC(a3,2)=LOC(a0,0)+(i*m+j)*l=2000+(3*4+2)*4=2056三维数组各维元素个数为m1,m2,m3（页/行/列）下标为i1,i2,i3的数组元素的存储地址：LOC(i1,i2,i3)=a+(i1*m2*m3+i2*m3+i3)*l前i1页总元素个数第i1页的前i2行总元素个数第i2行前i3列元素个数5.2数组的类定义一维数组的类定义及实现templateclassArray{private:T*data;intsize;//元素存放空间及长度public:Array(int

5、size);Array(constArray&a);~Array(){delete[]data;}T&operator[](inti)const;Array&operator=(constArray&a);……}；一维数组公共操作的实现templateArray::Array(intsz){//构造函数，进行数据成员的初始化if(sz<=0){cout<<“Thesizeofarrayisinvalid!”;data=NULL;}else{size=sz;data=newT[sz];}}t

6、emplateArray::Array(constArray&a){//复制构造函数size=a.size;data=newT[size];for(inti=0;iT&Array::operator[](inti)const{//操作符[]重载,返回下标为i的数据元素if(i<0

7、

8、i>=size)thorwi;//抛出异常，主函数中

9、进行相应的处理returndata[i];}templateArray&Array::operator=(constArray&a){if(this!=&a){size=a.size;delete[]data;data=newT[size];for(inti=0;i

10、阵Ba00a10a11a20a21a22a30a31a32……an-1n-1012345678n(n+1)/2-1úúúúûùêêêêëé-----11121110222120111000nnnnnaaaa0aaa00aa000aLLLLLLLLL若ij,数组