资源描述：
《数据机构第5章描述ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第5章数组和广义表5.1数组的定义和运算5.2数组的顺序存储和实现5.3特殊矩阵的压缩存储5.4广义表1数组是n(n＞1)个相同类型数据元素a0,a1,…,an-1构成的有限序列,且该有限序列存储在一块地址连续的内存单元中。数组的定义类似于采用顺序存储结构的线性表，是线性表在维数上的扩张，也就是线性表中的元素又是一个线性表。n维数组，bi是第i维的长度，则n维数组共有个数据元素，每个元素受n个关系的制约，就单个关系而言，这n个关系仍然是线性的。1.数组的定义和运算2数组具有以下性质：(1)数组中的数据元素数目固定。一旦定义了一个
2、数组,其数据元素数目不再有增减变化。(2)数组中的数据元素具有相同的数据类型。(3)数组中的每个数据元素都和一组惟一的下标值对应。(4)数组是一种随机存储结构。可随机存取数组中的任意数据元素。数组的基本操作(1)取值Value(A,&e,index1,...,indexn)(2)赋值Assign(&A,e,index1,…,indexn)32.数组的存储结构一维数组中,LOC(a0)确定,每个数据元素占用L个存储单元,则任一数据元素ai的存储地址LOC(ai)就可由以下公式求出：LOC(ai)=LOC(a0)+i*L(0≤i≤n-1
3、)二维数组,由于计算机的存储结构是线性的,如何用线性的存储结构存放二维数组元素就有一个行／列次序排放问题。4二维数组通常可以描述为两种形式:以行序为主序:PASCAL、C可以看成A=(α0，α1，，αm-1)...其中αi是一个行向量形式的线性表，0≤i≤m-1αi=(ai0，ai1，，ain-1)...a00a01a02a0,n-1a10a11a12a1,n-1am-1,0am-1,1am-1,2am-1,n-1.....................Am×n=5可以看成A=(α0，α1，，αn-1)...其中αj是一个列向量形
4、式的线性表，0≤j≤n-1αj=(a0j，a1j，，am-1j)...a00a01a02a0,n-1a10a11a12a1,n-1am-1,0am-1,1am-1,2am-1,n-1.....................Am×n=以列序为主序:FORTRAN6对于数组，一旦规定了维数和维界，如何计算数组元素的存储位置。a00a01…a0,n-1a10a11…a1,n-1am-1,0…am-1,n-1…am-1,1α0α1αm-1设数组以行序为主序。设二维数组A(m×n)其数组元素aij的存储位置为LOC(i，j)=LOC(0，0
5、)其中，LOC(0，0)是a00的存储位置；L是每个数组元素占用的存储单元数；L例，LOC(1，1)=LOC(0，0)+(n×1+1)L+(n×i+j)L7n维数组每一元素对应下标(j1,j2,…,jn)，0≤ji≤bi-1，bi为第i维的长度。以行序为主序。LOC(j1,j2,…,jn)=LOC(0,0,…,0)+(bn×…×b2×j1+bn×…b3×j2+…+bnjn-1+jn)L8例:对二维数组floata[5][4]计算：(1)数组a中的数组元素数目；(2)若数组a的起始地址为2000,且每个数组元素长度为32位(即4个字节
6、),数组元素a[3][2]的内存地址。元素数目共有5*4=20个。C语言采用行序为主序的存储方式,则有：LOC(a3,2)=LOC(a0,0)+(i*n+j)*k=2000+(3*4+2)*4=2056。93.矩阵的压缩存储特殊矩阵（对称矩阵、三角矩阵、对角矩阵）特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵,为了节省存储空间,特别是在高阶矩阵的情况下,可以利用特殊矩阵的规律,对它们进行压缩存储,也就是说,使多个相同的非零元素共享同一个存储单元,对零元素不分配存储空间。10对称矩阵的压缩存储若一个n阶方阵A中的元素满足ai,j=
7、aj,i(1≤i,j≤n),则称其为n阶对称矩阵。（1）只存储对称矩阵中上三角或下三角中的元素,（2）将n2个元素压缩存储到n(n+1)/2个元素的空间中，以一个一维数组作为A的存储空间。11n2个元素←→n(n+1)/2个元素aij(1≤i,j≤n)←→B[n(n+1)/2]1+2+…+(i-1)+j-1；aij←→ajia11a21a22a31anna12=a13=k=0123n(n+1)2-112下三角矩阵的压缩存储B[n(n+1)/2+1]Ck=0123n(n+1)2-1a11a21a22a31annca12,a13…13对
8、角矩阵：所有的非零元都集中在以主对角线为中心的带状区域内。半带宽为b的对角矩阵14①共有3n-2个非零元。②主对角线左下方的元素下标有关系式：i=j+1k=3(i-1)-1+1-1=3(i-1)-1=2(i-1)+i-2=2(i-1)
