资源描述：
《第5章_数组和广义表07》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第5章数组和广义表学习要点了解数组在以行序为主的存储中的地址计算方法。掌握特殊矩阵和稀疏矩阵的存储方法。掌握广义表的结构特点及其存储表示方法。5.1数组的基本概念a00a01…a0,n-1a10a11…a1,n-1…………am-1,0am-1,1…am-1,n-1Am×n=数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组可看成由若干个行向量组成的向量，也可以看成是若干个列向量组成的向量。5.1数组的定义和特性
2、二维数组可看成一个线性表A=(a0，a1，……，ap)(p=m-1或n-1)，其中aj是一个列向量形式的线性表：aj=（a0j，a1j，……，am-1,j），0≤j≤n-1或ai是一个行向量形式的线性表：ai=（ai0，ai1，……，ai,n-1），0≤i≤m-1a00a01…a0,n-1a10a11…a1,n-1…………am-1,0am-1,1…am-1,n-1a00a01…a0,n-1a10a11…a1,n-1…………am-1,0am-1,1…am-1,n-1a0a1…apa0a1…ap5.2数组的顺序表示与实现由于计算机的内存结构是一维的，用一维内存来表示多维数组，就必须按某种次序将
3、数组元素排成一列序列，然后将这个线性序列存放在存储器中。通常有两种顺序存储方式：1.行优先顺序——将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，其存储线性序列为：a00,a01,…,a0,n-1,a10,a11,…,a1,n-1,……,am-1,0,…,am-1,n-12.列优先顺序——将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，二维数组按列优先顺序存储的线性序列为：a00,a10,…,am-1,0,a01,a11,…am-1,1,……,am-1,1,…,an-1,m-1a00a01…a0,n-1a10a11…a1,n-1…………am-1,
4、0am-1,1…am-1,n-1am-1,n-1……am-1,1am-1,0……a1,n-1……a11a10a0,n-1……a01a00am-1,n-1……a1,n-1a0,n-1……am-1,1……a11a01am-1,0……a10a00a00a01…a0,n-1a10a11…a1,n-1…………am-1,0am-1,1…am-1,n-1行优先顺序列优先顺序数组的顺序表示与实现按上述两种方式顺序存储的数组，只要知道开始结点的地址，维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素存放地址表示为其下标的线性函数。例如，二维数组Amn按“行优先顺序”存储在内存中，假设每个
5、元素占用L个存储单元。元素aij的存储地址应是数组的基地址加上排在aij前面的元素所占用的单元数。因为aij位于第i+1行、第j+1列，前面i行一共有i×n个元素，第i+1行上aij前面又有j个元素，故它前面一共有i×n+j个元素，因此，aij的地址计算函数为：LOC(i,j)=LOC(0,0)+[i×n+j]×L数组的顺序表示与实现在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，实际上占用
6、了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。5.3特殊矩阵的压缩存储对称矩阵若n阶矩阵A中的数据元素满足下述性质aij=aji(1≤i，j≤n)则称A为n阶对称矩阵；因aij与aji相等，二者只需分配一个存储单元。这样，可将n×n个存储单元压缩到n(n+1)/2个单元。5.3.1对称矩阵1357326956387984a11a12….……..a1na21a22……..…….a2n………………….an1an2……..ann为节约存储空间，只存对角线及对角线
7、以上的元素，或者只存对角线及对角线以下的元素。不失一般性，假设以行主序存储下三角（包括对角线）中的元素。以一维数组sa[n(n+1)/2]作为n阶对称矩阵A的存储结构，则sa[k]和矩阵元aij之间存在着一一对应的关系：i(i-1)/2+j-1当i≧jj(j-1)/2+i-1当i
