Ch04 数组串与广义表.ppt

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

1、第四章数组、串与广义表数据结构电子教案1第四章数组、串与广义表一维数组与多维数组特殊矩阵稀疏矩阵字符串广义表2一维数组定义数组是相同类型的数据元素的集合，而一维数组的每个数组元素是一个序对，由下标（index）和值（value）组成。一维数组的示例在高级语言中的一维数组只能按元素的下标直接存取数组元素的值。3527491860547783410201234567893一维数组的定义和初始化#includevoidmain(){inta[3]={3,5,7},*elem,*p,i;//静态数组for(i=0;i<3;i++)cout<

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

3、连续存储方式一维数组LOC(i)=LOC(i-1)+l=a+i*l,i>0a,i=0352749186054778341020123456789lllllllllla+i*la7二维数组一维数组常常被称为向量（Vector）。二维数组A[m][n]可看成是由m个行向量组成的向量，也可看成是由n个列向量组成的向量。一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型。同理，一个三维数组类型可以定义为其数据元素为二维数组类型的一维数组类型。依次类推。8静态定义的数组，其维数和各维的维界不再改变，在编译时静态分配存储空间。一旦数组空间用完则不能扩充。在生存期结束时系统会自动释放其所占

4、的空间。动态定义的数组，其维界不在说明语句中显式定义，而是在程序运行中通过new动态分配和初始化，在对象销毁时通过delete动态释放。用一维内存来表示多维数组，就必须按某种次序将数组元素排列到一个序列中。9二维数组的动态定义和初始化#include…………int**A;introw=3,col=3;inti,j;A=newint*[row];for(i=0;i>A[i][j];10二维数组的动态定

5、义和初始化…………for(i=0;i

6、3)*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特殊矩阵特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间，对可以不存储的元素，如零元素或对称元素，不再存储。对称矩阵三对角矩阵16对称矩阵的压缩存储设有一个nn的对称矩阵A。对称矩阵中的元素关于主对角线对称，aij=

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