《《线性结构数组》ppt课件》由会员分享，可在线阅读，更多相关《《线性结构数组》ppt课件（34页珍藏版）》请在金锄头文库上搜索。
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(
3、l,m,n) A(3,4,5),k-1,aijk,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,.
5、0,A=,按行优先存放a11 , a21 , a22 , a31 , a32 , , an1 , an2 , , ann,故：求非零元素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,三对角阵,所有非零元素都集
6、中在以主对角线为中心的带状区域内,三对角阵,An,n =,三、稀疏矩阵,一个矩阵中若其非零元素的个数远远小于零元素的个数，则该矩阵称为稀疏矩阵。,稀疏矩阵的压缩存储方式 三元组表示,把非零元素的值和它所在的行号列号做为一个结点存放在一起，用这些结点组成的一个线性表(三元组表)来表示这个稀疏矩阵。 但是这种压缩存储方式将失去随机存储功能。,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,列,行,值,顺序存储结构三元组表示法,用一
7、个具有三个数据域的一维数组表示稀疏矩阵,C+中定义三元组 struct node int i,j; /非0元的行号,列号 int v; /非0元的值 ;,A1.i,A1.v,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,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
8、,1,2,4,5,6,转置,B,A,稀疏矩阵的转置算法 三元组表示,/把矩阵A转置后送入B,struct node /定义一个三元组 int i,j; /非0元的行号,列号 int v; /非0元的值 ;,1 2 3 4 5 6,1 2 3 4 5 6,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; /非
9、0元的行号,列号 int v; /非0元的值 ;,1 2 3 4 5 6,1 2 3 4 5 6,p,q,带辅助向量的三元组表示 为访问稀疏矩阵元素,0 2 0 0 4 6 0 8 0 0 0 10 0 0 0 12 0 0 0 0,A4*5=,映象,1 2 3 4 5 6,NUM,存放每一行的非零元素个数,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 N
10、UM) / 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 +NUMp-1; ,A的行数,A中非零元素个数,1 2 3 4 5 6,i j v,1,2,1,2,1,1,1,+,3,5,6,通过NUM和POS向量 访问稀疏矩阵中任一元素的算法,void srpn(int x,int y, node A,int
11、 POS,int NUM,int ,1 2 3 4 5 6,思想:通过POS可以一下子找到x行的第一个非零元素位置,而通过 NUM又可以知道该行的非零元素个数,便可以在这几个元素中找,若找到则以,找不到就是0,NUM,1 2 3 4,POS,带辅助向量的三元组表示 为提高转置运算效率,1 2 3 4 5 6,NUN,存放每一列的非零元素个数,1 2 3 4 5,POT,存放转置后每一行的第一个非零元素在三元组中的行号,有: POT(1)=1,POT(j)=POT(j-1)+NUM(j-1),2=j=n,1 2 3 4 5 6,转置,通过NUN和POT向量 求转置矩阵的算法,思想:只扫描一遍A的
12、非零元素的列col,每次把该列的元素转置后放入B的正确位置(由POT确定,第一个位置是知道的),1 2 3 4 5 6,1 2 3 4 5,1 2 3 4 5 6,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向量求转置矩阵的算法,数组的链式存储结构,若在运算中,数组中非零元素的位置或个数经常发生变动,应采用链表结构 带指针向量的单链表 十字链表,带指针向量的单链表,设置一个行指针向量，向量中每一个元素为一指针，指向本行矩阵的第一个非零元素。矩阵中每一个非零元素由三个数据域组
13、成：列、元素值和指向本行下一个非零结点的指针。同一行的非零元素构成一个单链表,0 6 0 2 2 0 12 0 0 8 0 0 0 0 0 0 4 0 0 0,B5*4=,2,4,6,2,1,1,1,12,2,8,1,4,1 2 3 4 5,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,*上机作业,*用三元组表实现稀疏矩阵的转置,
