数据结构与算法第五章数组 和广 义表.ppt

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

1、Chapter5Array&GeneralList教学内容1、数组的定义和顺序存储方式2、特殊矩阵的压缩存储3、广义表的概念及存储表示限制插入、删除位置线性表——具有相同类型的数据元素的有限序列。线性表——具有相同类型的数据元素的有限序列。限制元素类型为字符栈——仅在表尾进行插入和删除操作的线性表。队列——在一端进行插入操作，而另一端进行删除操作的线性表。串——零个或多个字符组成的有限序列。特殊线性表线性表——具有相同类型的数据元素的有限序列。将元素的类型进行扩充广义线性表（多维）数组——线性表中的数据元素可以是线性表，但所有元素的类

2、型相同。广义表——线性表中的数据元素可以是线性表，且元素的类型可以不相同。广义线性表——多维数组一、数组的基本概念相同类型的数据元素的集合。记作：A=(A0,A1,…,Am-1)352749860547783410201234567895.1数组二维数组可看作是每个数据元素都是相同类型的一维数组的一维数组。多维数组依此类推。一维数组a00a01…a0m-1a10a11…a1m-1…………an-10an-11…an-1m-1A=例如，元素a11受两个线性关系的约束，在行上有一个行前驱a10和一个行后继a12，在列上有一个列前驱a01和和一个

3、列后继a21。数组示例A=(A0，A1，……，An-1)其中：Ai=(ai0，ai1，……，aim-1)(0≤i≤n-1)二维数组是数据元素为线性表的线性表。二维数组三维数组行向量下标m2页向量下标m1列向量下标m3行向量下标m2列向量下标m3二、数组的存储实现一维数组存储方式LOC(i)=LOC(i-1)+l=a+i*lLOC(i)=LOC(i-1)+l=a+i*l,i>0a,i=0352749186054778341020123456789lllllllllla+i*la二维数组存储方式⑴行优先顺序——将数组元素按行排列，第i+1个行

4、向量紧接在第i个行向量后面。⑵列优先顺序——将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后通常有两种顺序存储方式：二维数组内存二维结构一维结构l2h2l1h1(a)二维数组aij前面的元素个数=阴影部分的面积=整行数×每行元素个数+本行中aij前面的元素个数=(i-l1)×(h2-l2＋1)＋(j-l2)本行中aij前面的元素个数每行元素个数整行数aij按行优先存储的寻址数组的存储结构——二维数组二维数组a[n][m]设数组开始存放位置LOC(0,0)=a,每个元素占用l个存储单元，那么LOC(i,j)=a+(i*m+j)

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

6、56三维数组各维元素个数为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(intsize);Array(constArray&a);~Array(){delete[]data;}T

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

8、ze=a.size;data=newT[size];for(inti=0;i