数据结构第5章

《数据结构第5章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第5章数组和广义表5.1数组的定义和运算5.2数组的顺序存储和实现5.3特殊矩阵的压缩存储5.4广义表数组是n(n＞1)个相同类型数据元素a0,a1,…,an-1构成的有限序列,且该有限序列存储在一块地址连续的内存单元中。数组的定义类似于采用顺序存储结构的线性表，是线性表在维数上的扩张，也就是线性表中的元素又是一个线性表。n维数组，bi是第i维的长度，则n维数组共有个数据元素，每个元素受n个关系的制约，就单个关系而言，这n个关系仍然是线性的。1.数组的定义和运算数组具有以下性质：(1)数组中的数据元素数目固定。一旦定义了一个数组,其数据元素数

2、目不再有增减变化。(2)数组中的数据元素具有相同的数据类型。(3)数组中的每个数据元素都和一组惟一的下标值对应。(4)数组是一种随机存储结构。可随机存取数组中的任意数据元素。数组的基本操作(1)取值Value(A,&e,index1,...,indexn)(2)赋值Assign(&A,e,index1,…,indexn)2.数组的存储结构一维数组中,LOC(a0)确定,每个数据元素占用L个存储单元,则任一数据元素ai的存储地址LOC(ai)就可由以下公式求出：LOC(ai)=LOC(a0)+i*L(0≤i≤n-1)二维数组,由于计算机的存储结构是

3、线性的,如何用线性的存储结构存放二维数组元素就有一个行／列次序排放问题。二维数组通常可以描述为两种形式:以行序为主序: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=可以看成A=(α0，α1，，αn-1)...其中αj是一个列向量形式的线性表，0≤j≤n-1αj=(a0j，a1j，，

4、am-1j)...a00a01a02a0,n-1a10a11a12a1,n-1am-1,0am-1,1am-1,2am-1,n-1.....................Am×n=以列序为主序:FORTRAN5.2数组的顺序表示和实现数组一旦被定义，其维数和维界就不再改变，通常数组一般不作插入或删除操作，只是存取或修改元素，故通常采用顺序存储结构。如何将多维数组结构转换对应一组连续的存储单元？以列序为主序a00a10…am-1,0a01a11…am-1,1a0,n-1…am-1,n-1…a1,n-1α0α1αn-1a00a01a02a0,n-1

5、a10a11a12a1,n-1am-1,0am-1,1am-1,2am-1,n-1.....................Am×n以行序为主序a00a01…a0,n-1a10a11…a1,n-1am-1,0…am-1,n-1…am-1,1α0α1αm-1a00a01a02a0,n-1a10a11a12a1,n-1am-1,0am-1,1am-1,2am-1,n-1.....................Am×n对于数组，一旦规定了维数和维界，如何计算数组元素的存储位置。a00a01…a0,n-1a10a11…a1,n-1am-1,0…am-1

6、,n-1…am-1,1α0α1αm-1设数组以行序为主序。设二维数组A(m×n)其数组元素aij的存储位置为LOC(i，j)=LOC(0，0)其中，LOC(0，0)是a00的存储位置；L是每个数组元素占用的存储单元数；L例，LOC(1，1)=LOC(0，0)+(n×1+1)L+(n×i+j)Ln维数组每一元素对应下标(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)L例:对二维数组floata

7、[5][4]计算：(1)数组a中的数组元素数目；(2)若数组a的起始地址为2000,且每个数组元素长度为32位(即4个字节),数组元素a[3][2]的内存地址。元素数目共有5*4=20个。C语言采用行序为主序的存储方式,则有：LOC(a3,2)=LOC(a0,0)+(i*n+j)*k=2000+(3*4+2)*4=2056。3.矩阵的压缩存储特殊矩阵（对称矩阵、三角矩阵、对角矩阵）特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵,为了节省存储空间,特别是在高阶矩阵的情况下,可以利用特殊矩阵的规律,对它们进行压缩存储,也就是说,使多个相同的非零元

8、素共享同一个存储单元,对零元素不分配存储空间。对称矩阵的压缩存储若一个n阶方阵A中的元素满足ai,j=aj,i(1≤i,j≤n),则称其