资源描述：
《第5章 数组和稀疏矩阵》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第5章数组和稀疏矩阵5.1数组5.2稀疏矩阵本章小结5.1.1数组的基本概念数组是n(n＞1)个相同类型数据元素a1,a2,…,an构成的有限序列,且该有限序列存储在一块地址连续的内存单元中。由此可见,数组的定义类似于采用顺序存储结构的线性表。数组具有以下性质：(1)数组中的数据元素数目固定。一旦定义了一个数组,其数据元素数目不再有增减变化。(2)数组中的数据元素具有相同的数据类型。(3)数组中的每个数据元素都和一组惟一的下标值对应。(4)数组是一种随机存储结构。可随机存取数组中的任意数据元素。5.1.2数组的存储结构在一维数组中,一旦a1的存
2、储地址LOC(a1)确定,并假设每个数据元素占用k个存储单元,则任一数据元素ai的存储地址LOC(ai)就可由以下公式求出：LOC(ai)=LOC(a1)+(i-1)*k(0≤i≤n)上式说明,一维数组中任一数据元素的存储地址可直接计算得到,即一维数组中任一数据元素可直接存取,因此,一维数组是一种随机存储结构。同样,二维及多维数组也满足随机存储特性。对于一个m行n列的二维数组Am×n,有：将Am*n简记为A,A是这样的一维数组：A=(a1,a2,…,ai…,am)其中,ai=(ai,1,ai,2,…,ai,n)(1≤j≤m)。显然,二维数组同样
3、满足数组的定义。一个二维数组可以看作是每个数据元素都是相同类型的一维数组的一维数组。以此类推,任何多维数组都可以看作一个线性表,这时线性表中的每个数据元素也是一个线性表。多维数组是线性表的推广。对于二维数组来说,由于计算机的存储结构是线性的,如何用线性的存储结构存放二维数组元素就有一个行／列次序排放问题。以行序为主序的存储方式：即先存储第1行,然后紧接着存储第2行,最后存储第m行。此时,二维数组的线性排列次序为：a1,1,a1,2,…,a1,n,a2,1,a2,2,…,a2,n,…,am,1,am,2,…am,n对一个已知以行序为主序的计算机系
4、统中,当二维数组第一个数据元素a1,1的存储地址LOC(a1,1)和每个数据元素所占用的存储单元k确定后,则该二维数组中任一数据元素ai,j的存储地址可由下式确定：LOC(ai,j)=LOC(a1,1)+[(i-1)*n+(j-1)]*k其中n为列数。同理可推出在以列序为主序的计算机系统中有：LOC(ai,j)=LOC(a1,1)+[(j-1)*m+(i-1)]*k其中m为行数。例5.1对二维数组floata[5][4]计算：(1)数组a中的数组元素数目；(2)若数组a的起始地址为2000,且每个数组元素长度为32位(即4个字节),数组元素a[
5、3][2]的内存地址。解：由于C语言中数组的行、列下界均为0,该数组行上界为5-1=4,列上界为4-l=3,所以该数组的元素数目共有(4-0+1)*(3-0+1)=5*4=20个。又由于C语言采用行序为主序的存储方式,则有：LOC(a3,2)=LOC(a0,0)+(i*n+j)*k=2000+(3*4+2)*4=20565.1.3特殊矩阵的压缩存储特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵,为了节省存储空间,特别是在高阶矩阵的情况下,可以利用特殊矩阵的规律,对它们进行压缩存储,也就是说,使多个相同的非零元素共享同一个存储单元,对零元素不
6、分配存储空间。特殊矩阵的主要形式有对称矩阵、对角矩阵等,它们都是方阵,即行数和列数相同。1.对称矩阵的压缩存储若一个n阶方阵A[n][n]中的元素满足ai,j=aj,i(0≤i,j≤n-1),则称其为n阶对称矩阵。由于对称矩阵中的元素关于主对角线对称,因此在存储时可只存储对称矩阵中上三角或下三角中的元素,使得对称的元素共享一个存储空间。这样,就可以将n2个元素压缩存储到个元素的空间中。不失一般性,我们以行序为主序存储其下三角(包括对角线)的元素。n2个元素←→n(n+1)/2个元素A[0..n-1,0..n-1]←→B[0..n(n+1)/2-
7、1]a[i][j]←→b[k]k=+ji≥j+ii＜j上三角矩阵：k=+i–ji≤j时i＞j时下三角矩阵：k=i≥j时i＜j时2.对角矩阵的压缩存储若一个n阶方阵A满足其所有非零元素都集中在以主对角线为中心的带状区域中,则称其为n阶对角矩阵。其主对角线上下方各有b条次对角线,称b为矩阵半带宽,(2b+1)为矩阵的带宽。对于半带宽为b(0≤b≤(n-1)/2)的对角矩阵,其
8、i-j
9、≤b的元素ai,j不为零,其余元素为零。下图所示是半带宽为b的对角矩阵示意图。半带宽为b的对角矩阵当b＝1时称为三对角矩阵。其压缩地址计算公式如下：k=2i+jA←→
10、Ba[i][j]←→b[k]例5.2按行优先顺序和按列优先顺序列出四维数组A[2][2][2][2]所有元素在内存中的存储次序。解：按行优先的存储次序
