数组1

1EssentialofLectureNine：一、数组的定义二、数组的顺序表示三、矩阵的压缩存储难点2一、数组的定义Array前4章介绍的数据结构共同特点：（1）都属于线性数据结构；（2）每种数据结构中的数据元素，都作为原子数据，不再进行分解；数据结构：数组和广义表，其共同特点是：（1）从逻辑结构上看它们，可看成是线性结构的一种扩展；（2）数据元素本身也是一个数据结构；32.二维数组:1.一维数组:a[0],a[1],…,a[n-1]---线性结构a00a01a02…a0j…a0n-1a10a11a12…a1j…a1n-1：：：：：：：：：：Amxn=ai0ai1ai2…aij…ain-1：：：：：：：：：：am-10am-11am-12…am-1j…am-1n-1一、数组的定义Array4其中：1）矩阵Am×n看成n个列向量的线性表2）每个列向量：αj=（a0j,a1j,a2j,…,am-1j）3）a12在列方向上有一个前驱a02,有一个后继a22A=（α0α1α2…αj…αn-1）a00a01a02…a0j…a0n-1a10a11a12…a1j…a1n-1：：：：：：：：：：Amxn=ai0ai1ai2…aij…ain-1：：：：：：：：：：am-10am-11am-12…am-1j…am-1n-15其中：1）矩阵Am×n看成m个行向量的线性表2）每个行向量：βi=（ai0,ai1,ai2,…,ain-1）3）a12在行方向上有一个前驱a11,有一个后继a13β||a00a01a02…a0j…a0n-1β0a10a11a12…a1j…a1n-1β1：：：：：：：：：：：：Amxn=ai0ai1ai2…aij…ain-1βi：：：：：：：：：：：：am-10am-11am-12…am-1j…am-1n-1βm-163.三维数组：1）在amnp中，每个数据元素aijk最多可以有三个直接前驱和三个直接后继；2）同理，可以把三维数组看成是其数据元素为二维数组的线性表4.推广到n维数组：1）每个数组元素aj1j2…jn都受n个关系的约束2）每个数组元素aj1j2…jn有n个直接前驱，n个直接后继（边界除外）3）每个数组元素aj1j2…jn对应于一组下标（j1,j2,…,jn）4)当n=1时，n维数组锐化为一维数组结论：n维数组由线性表辗转合成而得，可以看成是对线性表的推广7数组的结构特性：1）数组是一组有固定个数的元素的集合也就是说，一旦定义了数组的维数和每一维的上下限，数组中元素的个数就固定了。例如二维数组A3×4，它有3行、4列，即由12个元素组成。2）对于数组的操作一般只有两类（1）获得特定位置的元素值（2）修改特定位置的元素值8二、数组的顺序表示二维数组：二维数组Am×n以行为主的存储序列为：a00,a01,…，a0n-1,a10,a11,…,a1n-1,…,am-11,am-12,…,am-1n-1而以列为主的存储序列为：a00,a10,…，am-10，a01,a11,…,am-11,…,a0n-1,a1n-1,…,am-1n-1按行序存储，如高级语言BASIC、COBOL和PASCAL、C语言都是以行序为主；按列序存储，如高级语言中的FORTRAN语言就是以列序为主。一维数组：a0,a1,…，an-1，在内存中顺序存储计算机的内存结构是一维的数组是多维的结构存储？约定以某种次序将数组元素排成一个线性的序列再存入内存9Loc(aij)=Loc(a00)+(i*n+j)*L按行序为主序存放am-1n-1……..am-11am-10……….a1n-1……..a11a10a0n-1…….a01a0001n-1m*n-1na00a01……..a0n-1a10a11……..a1n-1am-10am-11……am-1n-1………………….a=L称为基地址或基址。10三维数组各维元素个数为b1,b2,b3下标为i1,i2,i3的数组元素的存储地址：（按页/行/列存放）Loc(i1,i2,i3)=Loc(a000)+(i1*b2*b3+i2*b3+i3)*L前i1页总元素个数第i1页的前i2行总元素个数第i2行前i3列元素个数11n维数组各维元素个数为b1,b2,b3,…,bn下标为i1,i2,i3,…,in的数组元素的存储地址：LOC(i1,i2,…,in)=LOC(a00…00)+(i1*b2*b3*…*bn+i2*b3*b4*…*bn+……+in-1*bn+in)*L12对于一般意义二维数组A[c1:d1,c2:d2]，设每个元素占用L个存储单元，LOC(c1,c2)是第一个元素ac1c2的存储位置则按行存放时，aij的存储位置为：LOC(i,j)=LOC(c1,c2)+[(d2-c2+1)(i-c1)+(j-c2)]L则列行存放时，aij的存储位置为：LOC(i,j)=LOC(c1,c2)+[(d1-c1+1)(j-c2)+(i-c1)]L当数组下标不从0开始13templateclassElemTypeclassArray{protected:ElemType*base;//数组元素基址intdim;//数组维数int*bounds;//数组各维长度intLocate(intsub0,va_list&va)constpublic://…数组的类定义(略)14矩阵（Matrix）是数值程序设计中经常用到的数学模型A3x4=5-28494-190721通常采用“二维数组”存储压缩存储：对零元不分配空间对多个值相同的元只分配一个空间然而在数值分析的计算中经常出现一些有下列特性的高阶矩阵，即矩阵中有很多值相同的元或零值元，为了节省存储空间，需要对它们进行压缩存储“0090-70000000M6X7=0008005000020000160三、矩阵的压缩存储15templateclassElemTypeclassMatrix//矩阵类{protected://矩阵的数据成员:ElemType*elems;//存储知阵元素introws,cols;//矩阵行数和列数public:Matrix(intrs,intcs);//构造一个rs行cs列的矩阵~Matrix();//析构函数intGetRows()const;//返回矩阵行数intGetCols()const;//返回矩阵列数ElemType&operator()(inti,intj);Matrix(constMatrixElemType©);MatrixElemType&operator=(constMatrixElemType©);};16特殊矩阵特殊矩阵:如果矩阵中值相同的元素或零元素在矩阵中的分布有一定规律，则称之为特殊矩阵1.对称矩阵：若n阶方阵A中的元满足特性aij=aji0≤i,j≤n-1（P156）则称A为n阶对称矩阵1513750800A=189263025170613关于主对角线对称只需存储矩阵的上三角或下三角中的元素存储下三角：a11a21a22a31a32a33a41a42a43a44a51a52a53a54a5517（P156）一维数组大小：1+2+3+…+n=n(n+1)/2压缩到elems[n(n+1)/2]个空间中去a11a21a22a31…an1…ann下标k=0123n(n-1)/2n(n+1)/2-1elems[k]与aij有什么关系？（即如何查找矩阵中的元素？）i≥j：aij在下三角中，前面有i-1行，元素个数给定一组=1+2+3+4+…+（i-1）=i(i-1)/2，第i行中aij前元下标（i,j）素个数=j-1，所以有k=i(i-1)/2+j-1=i(i-1)/2+j-1ij：aij在上三角中，因aij=aji,而aji在sa[j(j-1)+i-1]中，所以，aij在elems[j(j-1)/2+i-1]，即k=j(j-1)/2+i-118a11a21a22：：：：：：：：ai-11ai-12……ai-1i-1ai1ai2ai3…aij…aii：：：：：：：：：：an1an2an3…anj…ani…anni-1行，每行i个元素共:1+2+…+i-1j-1个元素192.三角矩阵：若n阶方阵中下(上)三角(不包括对角线)中的元均为常量c或0，则称为上(下)三角矩阵（P154）Ca11a21a22…an1…ann-1下标k=0123n(n-1)/2+1n(n+1)/2+1anna11a21a22：：：：：：：：ai-11ai-12……ai-1i-1ai1ai2ai3…aij…aii：：：：：：：：：：an1an2an3…anj…ani…ann若将常量C映射到elems[0]中，按行进行映射。i≥j：aij在下三角中，在它之前共有i(i-1)/2+j-1个元素，因此其在数组elems中的位置是i(i-1)/2+j20三对角带状矩阵有如下特点：主对角线：i=j高对角线：i=j-1低对角线：i=j+13.对角矩阵：若n阶方阵中的非零值元都集中在以主对角线为中心的(由k条对角线组成的)带状区域中，则称为k对角矩阵，又称带状矩阵（P152）a11a120…………….0a21a22a230……………000…an-1,n-2an-1,n-1an-1,n00……an,n-1ann.0a32a33a340………0……………………………21（1）确定存储该矩阵所需的一维数组空间的大小主对角线有n个元素，两条次对对角线有n-1个元素。由此得到，所需一维数组空间的大小为：“+1”是存储常数C，一般将C映射到elems[0]的位置。2*（n-1）+n+1=3n–2+1=3n-122前i行非零元素个数+第i行中aij前非零元素个数+1-1(ji)0(j=i)1(ji)j-i=由此可得aij在数组elems中的位置是：3i-4+j-i+1+1=2i+j-2前i行元素个数=3×(i-1)-1（因为第1行只有2个非零元素）（2）确定非零元素在一维数组空间中的位置第i行中aij前非零元素个数=j-i+1，其中a11a120…………….0a21a22a230……………000…an-1,n-2an-1,n-1an-1,n00……an,n-1ann.0a32a33a340………0……………………………23稀疏矩阵如果矩阵中只有少量的非零值元，并且这些非零值元在矩阵中的分布没有一定规律，则称为随机稀疏矩阵，简称为稀疏矩阵。假设在mxn的矩阵中有t个非零值元，令δ=t/m*n，称δ为矩阵的稀疏因子，则通常认定δ≤0.05的矩阵为稀疏矩阵。A6x5=30050000-200010406000000000-1000row该非零元素所在的行值col该非零元素所在的列值该非零元素所在的值value24123456A6x5=1300500200-200031040604000000500-1000整个矩阵的存储：每个非零元结点由（row,col,value）唯一确定—表整个矩阵的（行数，列数，非零元个数）rowcolvalue11314523-231133435653-1((1,1,3),(1,4,5),(2,3,-2),(3,1,1),(3,3,4),(3,5,6),(5,3,-1))---线性表按行序有序已知稀疏矩阵三元组表示为25templateclassElemTypestructTriple{//数据成员:introw,col;//非零元素的行下标与列下标ElemTypevalue;//非零元素的值//构造函数:Triple();//无参数的构造函数Triple(intr,intc,ElemTypev);//已知数数据域建立三元组};三元组类参见test_tri_sparse_matrix/triple.h26templateclassElemTypeclassTriSparseMatrix{protected://稀疏矩阵三元组顺序表的数据成员:TripleElemType*triElems;