数据结构2（清华大学）ppt

《数据结构2（清华大学）ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构（用面向对象方法与C++语言描述）第二版2清华大学计算机系殷人昆1第四章数组、串与广义表数据结构电子教案殷人昆王宏2第四章数组、串与广义表一维数组与多维数组特殊矩阵稀疏矩阵字符串广义表3一维数组定义数组是相同类型的数据元素的集合，而一维数组的每个数组元素是一个序对，由下标（index）和值（value）组成。一维数组的示例在高级语言中的一维数组只能按元素的下标直接存取数组元素的值。3527491860547783410201234567894一维数组的定义和初始化#includemain(){inta[3]={3,5,7},

2、*elem,i;//静态数组for(i=0;i<3;i++)cout<>elem[i];while(elem){cout<<*elem<

3、量下标i页向量下标i列向量下标j行向量下标j列向量下标k7数组的连续存储方式一维数组LOC(i)=LOC(i-1)+l=a+i*l,i>0a,i=0352749186054778341020123456789lllllllllla+i*la8二维数组一维数组常被称为向量（Vector）。二维数组A[m][n]可看成是由m个行向量组成的向量，也可看成是由n个列向量组成的向量。一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型:typedefTarray2[m][n];//T为元素类型等价于：typedefTarray1[n];//列向量类型typ

4、edefarray1array2[m];//二维数组类型9同理，一个三维数组类型可以定义为其数据元素为二维数组类型的一维数组类型。静态定义的数组，其维数和维界不再改变，在编译时静态分配存储空间。一旦数组空间用完则不能扩充。动态定义的数组，其维界不在说明语句中显式定义，而是在程序运行中创建数组对象时通过new动态分配和初始化，在对象销毁时通过delete动态释放。用一维内存来表示多维数组，就必须按某种次序将数组元素排列到一个序列中。10二维数组的动态定义和初始化#include…………int**A;introw=3,col=3;inti

5、,j;A=newint*[row];for(i=0;i>A[i][j];…………11二维数组中数组元素的顺序存放行优先存放：设数组开始存放位置LOC(0,0)=a,每个元素占用l个存储单元LOC(j,k)=a+(j*m+k)*l12列优先存放：设数组开始存放位置LOC(0,0)=a,每个元素占用l个存储单元LOC(j,k)=a+(k*n+j)*l13三维数组各维元素个数为m1,m2,m3下标为i1,i2,i3的数组元素的存储地址

6、：（按页／行／列存放）LOC(i1,i2,i3)=a+(i1*m2*m3+i2*m3+i3)*l前i1页总元素个数第i1页前i2行总元素个数第i2行前i3列元素个数14n维数组各维元素个数为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)*l15特殊矩阵特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间，对可以不存储的元素，如零元素或对称元素

7、，不再存储。对称矩阵三对角矩阵16对称矩阵的压缩存储设有一个nn的对称矩阵A。对称矩阵中的元素关于主对角线对称，aij=aji，0≤i,j≤n-117为节约存储，只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。下三角矩阵18上三角矩阵把它们按行存放于一个一维数组B中，称之为对称矩阵A的压缩存储方式。数组B共有n+(n-1)++1=n*(n+1)／2个元素。19下三角矩阵若ij,数组元素A[i][j]在数组B中的存放位置为1+2++i+j=(i+1)*i/2+jBa00a10a11a20a

8、21a22a30a31a32……an-1n-1012