《线性结构数组》PPT课件.ppt

《《线性结构数组》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《线性结构数组》PPT课件.ppt（36页珍藏版）》请在三一办公上搜索。

1、第三节 数组,数组,1.数组的逻辑结构定义以及存储方式2.了解特殊结构的矩阵：如三角矩阵，三对角阵和稀疏矩阵的存储及其相应的运算。,本节重点,a1 a11 a12.a1n,a2 a21 a22.a2n,am am1 am2.amn,.,ai=(ai1,ai2,.,ain)(1=i=m),一、数组的概念,二维数组可以看成是一个复杂的线性表,二、数组的顺序存储结构,计算机的内存结构是一维的，因此将数组元素排成线性序列，然后将这个线性序列存放在存储器中 行优先顺序：把数组按一行一行的顺序依次排列。列优先顺序：就是把数组按一列列的顺序依次排列。,多维数组的顺序存储结构按行优先顺序存放,存放在计算机内：

2、,m,n,地址的计算方法 二维按行优先顺序存放,存放在计算机内：,m,j-1,aij,i-1,n,Loc（aij）=Loc(a11)+(i-1)*n+(j-1)(1=i=m,1=j=n),aij前的元素个数,地址的计算方法 二维按行优先顺序存放,LOC(Aij)=LOC(A00)+(in+j)L（0im,0jn）,三维数组按行优先顺序存放,存放在计算机内：,m,l,n,三维数组A(l,m,n),把三维数组看成是叠在一起的一张张卡片，先把第一张按行优先顺序放入计算机，接着放第二张，直到放完。,地址的计算方法 三维按行优先顺序存放,m,l,n,三维数组A(l,m,n)A(3,4,5),k-1,ai

3、jk,j-1,i-1,Loc（aijk）=Loc(a111)+(i-1)*m*n+(j-1)*n+(k-1)(1=i=l,1=j=m,1=k=n),多维数组的顺序存储结构按列优先顺序存放,存放在计算机内：,m,n,地址的计算方法 二维按列优先顺序存放,存放在计算机内：,m,j-1,aij,i-1,n,Loc（aij）=Loc(a11)+(j-1)*m+(i-1)(1=i=m,1=j=n),三维数组按列优先顺序存放,存放在计算机内：,m,l,n,三维数组A(l,m,n)A(3,4,5),把三维数组看成是叠在一起的一张张卡片，先把第一张按列优先顺序放入计算机，接着放第二张，直到放完。,地址的计算方

4、法 三维按列优先顺序存放,m,l,n,三维数组A(l,m,n)A(3,4,5),k-1,aijk,j-1,i-1,Loc（aijk）=Loc(a111)+(k-1)*l*m+(j-1)*l+(i-1)(1=i=l,1=j=m,1=k=n),随机存储结构,因为在顺序存储的情况下，每一个元素都有与其下标相对应的地址，因此可以对数组中的元素进行随机存储。,特殊矩阵的压缩存储,指非零元素或零元素分布有一定规律的矩阵。下三角阵三对角阵稀疏矩阵,a11 0 0.0,a21 a22 0.0,an1 an2 an3.ann,.0,A=,按行优先存放a11,a21,a22,a31,a32,an1,an2,ann

5、,故：求非零元素aij的地址：Loc(aij)=Loc(a11)+i(i-1)/2+(j-1)(1=j=i=n),下三角阵,aij,a11 a12 0.0,a21 a22 a23 0.0,0 0 an-1,n-2 an-1.n-1 an-1,n,.,A=,0 a32 a33 a34 0.0,0 0.an,n-1 an,n,按行优先存放a11,a12,a21,a22,a23,a32,a33,an,n-1,an,n,三对角阵,所有非零元素都集中在以主对角线为中心的带状区域内,三对角阵,An,n=,三、稀疏矩阵,一个矩阵中若其非零元素的个数远远小于零元素的个数，则该矩阵称为稀疏矩阵。,稀疏矩阵的压缩

6、存储方式三元组表示,把非零元素的值和它所在的行号列号做为一个结点存放在一起，用这些结点组成的一个线性表(三元组表)来表示这个稀疏矩阵。但是这种压缩存储方式将失去随机存储功能。,7,1,1,列,行,值,7 0 0 0 15 0,0-4 0 0 0 0,-2 0 0 0 0 21,0 0 0-1 0 0,M=,21,6,4,-2,1,4,-1,4,3,-4,2,2,15,5,1,7,1,1,列,行,值,顺序存储结构三元组表示法,用一个具有三个数据域的一维数组表示稀疏矩阵,C+中定义三元组struct nodeint i,j;/非0元的行号,列号int v;/非0元的值;,A1.i,A1.v,21,

7、6,4,-1,4,3,-4,2,2,15,5,1,7 0 0-2,0-4 0 0,15 0 0 0,0 0 0 0,0 0-1 0,0 0 0 21,顺序存储结构稀疏矩阵的转置,A4*6,A6*4,21,6,4,-1,4,3,-4,2,2,15,5,1,7 0 0-2,0-4 0 0,15 0 0 0,0 0 0 0,0 0-1 0,0 0 0 21,顺序存储结构稀疏矩阵的转置运算,A4*6,A6*4,1,1,2,4,5,6,转置,B,A,稀疏矩阵的转置算法三元组表示,/把矩阵A转置后送入B,struct node/定义一个三元组int i,j;/非0元的行号,列号int v;/非0元的值;,

8、123456,123456,p,q,A,B,稀疏矩阵的转置算法三元组表示,/主程序void main(void)int i,m,n,tu;node Amaxlen,Bmaxlen;cout创建一个三元组表A;disp(A,tu);Transm(A,B,tu,n);disp(B,tu);,struct node/定义一个三元组int i,j;/非0元的行号,列号int v;/非0元的值;,123456,123456,p,q,带辅助向量的三元组表示为访问稀疏矩阵元素,0 2 0 0 46 0 8 0 00 10 0 0 012 0 0 0 0,A4*5=,映象,123456,NUM,存放每一行的非

9、零元素个数,1 2 3 4,POS,存放每一行的第一个非零元素在三元组中的行号,有:POS(1)=1,POS(i)=POS(i-1)+NUM(i-1),2=i=m,+,+,+,A,构造NUM和POS向量的算法,void posnum(node A,int tu,int m,int POS,int NUM)/A为稀疏矩阵的三元组，tu为A中非零元素个数，m为 A的行数 int p;for(p=1;p=m;p+)NUMp=0;/初始化NUM向量 for(p=1;p=tu;p+)NUMAp.i=NUMAp.i+1;/i为A中的行下标 POS1=1;for(p=2;p=m;p+)POSp=POSp-1

10、+NUMp-1;,A的行数,A中非零元素个数,123456,i j v,1,2,1,2,1,1,1,+,3,5,6,通过NUM和POS向量访问稀疏矩阵中任一元素的算法,void srpn(int x,int y,node A,int POS,int NUM,int,123456,思想:通过POS可以一下子找到x行的第一个非零元素位置,而通过 NUM又可以知道该行的非零元素个数,便可以在这几个元素中找,若找到则以,找不到就是0,NUM,1 2 3 4,POS,带辅助向量的三元组表示为提高转置运算效率,123456,NUN,存放每一列的非零元素个数,1 2 3 4 5,POT,存放转置后每一行的第

11、一个非零元素在三元组中的行号,有:POT(1)=1,POT(j)=POT(j-1)+NUM(j-1),2=j=n,123456,转置,通过NUN和POT向量求转置矩阵的算法,思想:只扫描一遍A的非零元素的列col,每次把该列的元素转置后放入B的正确位置(由POT确定,第一个位置是知道的),123456,1 2 3 4 5,123456,col(Ap.j),POT,2 1 2,4,5 1 4,7,1 2 6,2,3 2 8,6,2 3 10,5,1 4 12,3,q=Potcol,通过NUN和POT向量求转置矩阵的算法,数组的链式存储结构,若在运算中,数组中非零元素的位置或个数经常发生变动,应采

12、用链表结构带指针向量的单链表十字链表,带指针向量的单链表,设置一个行指针向量，向量中每一个元素为一指针，指向本行矩阵的第一个非零元素。矩阵中每一个非零元素由三个数据域组成：列、元素值和指向本行下一个非零结点的指针。同一行的非零元素构成一个单链表,0 6 0 22 0 12 00 8 0 0 0 0 0 04 0 0 0,B5*4=,2,4,6,2,1,1,1,12,2,8,1,4,12345,7 0 0 0 15 0,0-4 0 0 0 0,-2 0 0 0 0 21,0 0 0-1 0 0,M=,十字链表,本节复习,多维数组的两种顺序存储方式：行优先顺序和列优先顺序。这两种存储方式下的地址计算方法。几种特殊矩阵的特征及其压缩存储地址对应关系。稀疏矩阵的三元组表示。,作业,P112 12,13,*上机作业,*用三元组表实现稀疏矩阵的转置,