《数据结构之第5章 数组和稀疏矩阵》由会员分享，可在线阅读，更多相关《数据结构之第5章 数组和稀疏矩阵（74页珍藏版）》请在金锄头文库上搜索。
1、第5章 数组和稀疏矩阵,5.1 数组,5.2 稀疏矩阵,5.1 数组,5.1.1 数组的基本概念,5.1.2 数组的存储结构,5.1.3 特殊矩阵的压缩存储,5.1.1 数组的基本概念 数组是n(n1)个相同类型数据元素a1,a2,an构成的有限序列，且该有限序列存储在一块地址连续的内存单元中。 数组的定义类似于采用顺序存储结构的线性表。,数组具有以下性质： (1)数组中的数据元素数目固定。一旦定义了一个数组，其数据元素数目不再有增减变化。 (2)数组中的数据元素具有相同的数据类型。 (3)数组中的每个数据元素都和一组惟一的下标值对应。 (4)数组是一种随机存储结构。可随机存取数组中的任意数据
2、元素。,5.1.2 数组的存储结构 在一维数组中，一旦a1的存储地址LOC(a1)确定,并假设每个数据元素占用k个存储单元，则任一数据元素ai的存储地址LOC(ai)就可由以下公式求出： LOC(ai)=LOC(a1)+(i-1)*k (0in) 一维数组中任一数据元素的存储地址可直接计算得到，即一维数组中任一数据元素可直接存取，因此，一维数组是一种随机存储结构。同样，二维及多维数组也满足随机存储特性。,对于一个m行n列的二维数组Amn，有：,将Am*n简记为A，A是这样的一维数组： A=(a1,a2,ai,am)其中，ai=(ai,1,ai,2,ai,n) (1jm)。,二维数组同样满足数组
3、的定义。一个二维数组可以看作是每个数据元素都是相同类型的一维数组的一维数组。 以此类推，任何多维数组都可以看作一个线性表，这时线性表中的每个数据元素也是一个线性表。多维数组是线性表的推广。,对于二维数组来说，由于计算机的存储结构是线性的，如何用线性的存储结构存放二维数组元素就有一个行列次序排放问题。 以行序为主序的存储方式：即先存储第1行，然后紧接着存储第2行，最后存储第m行。此时，二维数组的线性排列次序为： a1,1，a1,2,，a1,n，a2,1，a2,2，a2,n，am,1，am,2，am,n,对一个已知以行序为主序的计算机系统中，当二维数组第一个数据元素a1,1的存储地址LOC(a1,
4、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 对二维数组float a54计算：(1)数组a中的数组元素数目；(2)若数组a的起始地址为2000,且每个数组元素长度为32位(即4个字节),数组元素a32的内存地址。,解：由于C语言中数组的行、列下界均为0，该数组行上界为5-1=4，列上界为4-l=3，所以该
5、数组的元素数目共有(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=2056,5.1.3 特殊矩阵的压缩存储 特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，为了节省存储空间，特别是在高阶矩阵的情况下，可以利用特殊矩阵的规律，对它们进行压缩存储，也就是说，使多个相同的非零元素共享同一个存储单元，对零元素不分配存储空间。 特殊矩阵的主要形式有对称矩阵、对角矩阵等,它们都是方阵，即行数和列数相同。,1. 对称矩阵的压缩存储 若一个n阶方阵Ann中的元素满足a
6、i,j=aj,i(0i,jn-1)，则称其为n阶对称矩阵。 由于对称矩阵中的元素关于主对角线对称，因此在存储时可只存储对称矩阵中上三角或下三角中的元素，使得对称的元素共享一个存储空间。这样,就可以将n2个元素压缩存储到个元素的空间中。不失一般性，以行序为主序存储其下三角(包括对角线)的元素。,A=,a00 a01 a02 a0n-1a10 a11 a12 a1n-1a20 a21 . a2n-1.an-10 an-11 an-1n-1,n2个元素 n(n+1)/2个元素 A0.n-1,0.n-1 B0.n(n+1)/2-1 aij bk,k=,+ j ij,+ i ij,上三角矩阵：,k=,+
7、 i j ij时,ij时,n(n+1)/2个上三角上的元素aij bk,A=,a00 a01 a02 a0n-10 a11 a12 a1n-10 0 . a2n-1.0 0 an-1n-1,下三角矩阵：,k=,ij时,ij时,n(n+1)/2个上三角上的元素aij bk,A=,a00 0 0 0a10 a11 0 0a20 a21 . 0.an-10 an-11 an-1n-1,2. 对角矩阵的压缩存储 若一个n阶方阵A满足其所有非零元素都集中在以主对角线为中心的带状区域中，则称其为n阶对角矩阵。 其主对角线上下方各有b条次对角线,称b为矩阵半带宽，(2b+1)为矩阵的带宽。对于半带宽为b(0
8、b(n-1)/2)的对角矩阵，其|i-j|b的元素ai,j不为零，其余元素为零。,半带宽为b的对角矩阵,A=,a00 a01 0 0 0a10 a11 a12 0 0a20 a21 . 0 0 0 .0 0 an-11 an-1n-1,当b1时称为三对角矩阵。其压缩地址计算公式如下： k=2i+j,A B aij bk,例5.2 按行优先顺序和按列优先顺序列出四维数组A2222所有元素在内存中的存储次序。,解： 按行优先的存储次序: A0000, A0001, A0010, A0011, A0100, A0101, A0110, A0111, A1000, A1001, A1010, A101
9、1, A1100, A1101, A1110, A1111,按列优先的存储次序: A0000, A1000, A0100, A1100, A0010, A1010, A0110, A1110, A0001, A1001, A0101, A1101, A0011, A1011, A0111, A1111,例5.3 对于二维数组Amn，其中m80，n80，先读入m和n，然后读该数组的全部元素，对如三种情况分别编写相应函数: (1)求数组A靠边元素之和; (2)求从A00开始的行、列互不相邻的各元素之和; (3)当m=n时，分别求两条对角线上的元素之和,否则打印出mn的信息。,解： (1)对应算法如
10、下： void proc1(ElemType An) int s=0,i,j; for (i=0;im;i+) /*第一列*/ s=s+Ai0; for (i=0;im;i+) /*最后一列*/ s=s+Ain-1; for (j=0;jn;j+) /*第一行*/ s=s+A0j; for (j=0;jn;j+) /*最后一行*/ s=s+Am-1j; s=s-A00-A0n-1-Am-10-Am-1n-1; /*减去4个角的重复元素值*/ printf(s=%dn,s); ,(2)对应算法如下： void proc2(maxix A) int s=0,i=0,j=0; do do s=s+Aij; j=j+2; /*跳过一列*/ while (jn); i=i+1; /*下一行*/ if (j=0) j=1; else j=0; while (im); printf(s=%dn,s); ,(3)对应算法如下： void proc3(maxix A) int i,s=0; if (m!=n) printf(mn); else for (i=0;im;i+) s=s+Aii; /*求第一条对角线之和*/ for (i=0;in;i+) s=s+An-i-1i; /*累加第二条对角线之和*/ s-=An/2n/2; printf(s=%dn,s); ,
