数据结构：数组只是分享.ppt

《数据结构：数组只是分享.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构：数组ADTArray{数据对象：ji=0,…,bi-1,i=1,2,…,n,D={aj1j2…jn

2、n称为数组的维数，bi是数组第i维的长度，ji是数组元素的第i维下标，aj1j2…jn∈ElemSet}数据关系：R={R1，R2，…Rn}Ri={

3、0≤jk≤bk-1,1≤k≤n,且k≠i，0≤ji≤bi-2，aj1…ji…jn,aj1…ji+1…jn∈D,i=2,…,n}基本操作：Value（A,&e,index1,…,indexn）初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若各个下标不超界，则e赋

4、值为所指定的A的元素值，并返回OKAssign(&A,e,index1,…,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若各个下标不超界，则将e的值赋给所指定的A的元素值，并返回OK}ADTArray数组的抽象类型定义在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，typedefElemTypeArray2[m][n];等价于：typedefElemTypeArray1[n];typedefArray1Array2[m];数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组的基

5、本操作只有存取元素和修改元素值的操作。5.2数组的顺序表示和实现由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一个序列，然后将这个线性序列存放在存储器中。又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。通常有两种顺序存储方式：低下标优先高下标优先对二维数组而言：⑴以行序为主序——将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。在C语言中，数组就是按行优先顺序存储的。⑵以列序为主序——将数组元素按列排列，第i+1个列向量紧接在

6、第i个列向量后面。顺序存储的数组是一个随机存取结构。1、一维数组LOC(i)=LOC(i-1)+l=α+i*l数组元素存储地址的计算：2、二维数组行优先：LOC(i,j)=α+(i*n+j)*la00a01…a0,n-1a10a11…a1,n-1…………am-1,0am-1,1…am-1,n-1Amn=3、n维数组LOC(j1,j2,…,jn)=LOC（0，0，，0）+∑ciji其中Cn=L,Ci-1=bi*ci,1

7、者矩阵中出现大量的零元素的情况下，存储空间大量浪费。当一个矩阵中的元素有很多都是零时，零元素的个数远大于非零元素，则称该矩阵为稀疏矩阵。矩阵的压缩存储——为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。5.3.1特殊矩阵——非零元素或零元素的分布有一定规律的矩阵。1、对称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji0≦i,j≦n-1则称A为对称矩阵。只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。例如，存下三角阵。下三角阵sa[k]的下标k和aij的对应关系是：i*(i+1)/2+j当i≧jj*(j

8、+1)/2+i当i

9、的对应关系是：i(2n-i+1)/2+j-i当i≦jn(n+1)/2当i>jk=下三角矩阵的存储和对称矩阵类似，sa[k]的下标k和aij的对应关系是：i(i+1)/2+j当i≧jn(n+1)/2当i