《《数据结构（C语言描述）》-马秋菊-电子教案 第4章数组》由会员分享，可在线阅读，更多相关《《数据结构（C语言描述）》-马秋菊-电子教案 第4章数组（34页珍藏版）》请在金锄头文库上搜索。
1、2019年5月24日星期五,第1页,4.1 数组（重点）,4.2 特殊矩阵的压缩存储,4.3 广义表,小结,第4章 数组、特殊矩阵和广义表,2019年5月24日星期五,第2页,本章学习目标,掌握多维数组的概念以及在计算机中的存储表示； 掌握对称矩阵、三角矩阵、对角矩阵的压缩存储表示及地址运算公式； 稀疏矩阵在计算机中的存储表示及基本运算的实现； 广义表的逻辑结构和基本运算。,2019年5月24日星期五,第3页,4.1 数组 4.1.1 数组的基本概念,数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数
2、据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。,数组的定义： 数组（array）是由下标（index）和值（value）组成的序对集合。,在C语言中，一维数组定义为： ElemType arraynameMAXSIZE;,2019年5月24日星期五,第4页,下图一个m行n列的二维数组。它可以看成是由行向量组成的向量，也可以看成是由列向量组成的向量。,在数组中通常做下面两种操作： (1)取值操作：给定一组下标，读其对应的数据元素。 (2)赋值操作：给定一组下标，存储或修改与其相对应的数据元素。,与线性表的区别：在数组中不能进行插入、删除数据元素的操作。
3、,2019年5月24日星期五,第5页,4.1.2 数组的存储结构,一维数组在计算机内是存放在一组连续的存储单元中。因此，数组中任一元素Ai的存储位置可用下列公式计算： LOC（Ai）= LOC（A0）+( i )L 其中L是每个数据元素所占存储单元的个数。对于一维数组按下标顺序分配即可。,二维数组的存储器，一般有两种存储方式：一是以行为主序的顺序存放，如BASIC、C等程序设计语言，即一行分配完了接着分配下一行。,2019年5月24日星期五,第6页,C语言中，数组就是按行优先顺序存储的。,如，一个23的二维数组A23，以行为主序的分配顺序为：a00，a01，a02，a10，a11，a12。,以
4、列为主序分配顺序为：a00,a10,a01,a11,a02,a12,2019年5月24日星期五,第7页,在C语言中，二维数组定义为： ElemType arraynamem n; 数组中任一元素Aij的存储位置可用下列公式计算： LOC(Aij)=LOC(A00)+(in+j)L 这是因为数组元素Aij的前面有i行，每一行的元素个数为n，在第i行中Aij的前面还有j个数组元素。L仍然是每个数据元素所占存储单元的个数。,例如23二维数组： LOC(a12)= LOC(a00)+(1)*3+2* L,2019年5月24日星期五,第8页,【例4-1】选择题。设二维数组M的每个数据元素占6个存储单元，
5、行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要()个字节；若M按行优先方式存储，元素M85的起始地址与当M按列优先方式存储时的()元素的起始地址一致。,() A.90 B.180 C.240 D.540 () A.M85 B.M310 C.M58 D.M09,(1)二维数组M共有(8-0+1)(10-1+1)=90个数据元素，所以共占 906=540个字节，即()选D. (2)M85的存储位置为： LOC(M85)= LOC(M01)+504 在()中只有B.有表达是： LOC(M310)= LOC(M01)+504,因此() 选B.,2019年5月24日星期五,第9页,在
6、科学与工程计算问题中，矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况，比如常见的一些特殊矩阵，如三角矩阵、对称矩阵、带状矩阵、稀疏矩阵等。,4.2.1 对称矩阵,4.2 特殊矩阵的压缩存储,在一个n阶方阵中，对称矩阵的特点是：若数据元素满足下列性质：,Aij= Aji （0i , jn-1）,2019年5月24日星期五,第10页,Aij和SAk之间对应关系: 若ij，则Aij在下三角矩阵中，Aij之前的i行一共有1+2+ i =i(i+1)/2个元素，在第i行上，Aij之前有j个元素，因此有： k=i(i+1)/2+j 若ij，则Aij在上三角矩阵中。因为Aij=Aji,所以只要
7、交换上述对应关系式中的i和j即可得到： k=j(j+1)/2+i (kn(n+1)/2 ) 若令I=max(i,j)，J=min(i,j)，得到： k=I(I+1)/2+J (kn(n+1)/2 ) 因此：LOC(Aij)=LOC(SAk)=LOC(SA0)+kL = LOC(SA0)+I(I+1)/2+J L,对于一个n阶对称矩阵，第i行（0in）只需要存储i+1个元素，元素总数为：,= n(n+1)/2,2019年5月24日星期五,第11页,4.2.2 三角矩阵,以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相
8、反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。,2019年5月24日星期五,第12页,三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量SA0n(n+1)/2中，其中c存放在最后一个分量中。,a21（=6）对应的k= i(i+1)/2+j =4,2019年5月24日星期五,第13页,以行为主序顺序存储上三角部分，最后存储对角线下方的常量。对于第0行，存储n个元素，第1行存储n-1个元素，第p行存储(n-p)个元素，Aij的前面有i行，共存储S个元素：,S=n+(n-1) +(n-i+1)= =i(2n-i+1
9、)/2,而Aij是它所在的行中要存储的第(j-i)个，所以，它是上三角存储顺序中的第 i(2n-i+1)/2+(j-i)个，因此它在SA中的下标为：,k=i(2n-i+1)/2+j-i,2019年5月24日星期五,第14页,SAk 与Aij的对应关系为：,4.2.3 对角矩阵,在n阶对角矩阵A中，所有的非零元素集中在以主对角线为中心的带状区域中，显然,当i-j1时，元素向量Aij= 0(或同一个常数c)。,2019年5月24日星期五,第15页,三对角矩阵可按行优先顺序将其压缩存储到一维向量M03n-3中，Mk和对角矩阵非零元素Aij之间的对应关系为：,这是因为第i行前有i行，共3i-1个数据元
10、素；第j列前有j-(i-1) 个数据元素，所以 k=3i-1+ j-(i-1)=2i+j i-j1,k=2i+j,例如，A25=0，这是因为i-j=2-51； A23对应M7，这是因为k=2i+j=22+3=7。,2019年5月24日星期五,第16页,4.2.4 稀疏矩阵,设mn矩阵中有t个非零元素，若且tmn，这样的矩阵称为稀疏矩阵。,将三元组按行优先的顺序，同一行中列号从小到大的规律排列成一个线性表，得到一个其结点均是三元组的线性表。,2019年5月24日星期五,第17页,typedef int ElemType; typedef struct int i,j; ElemType v; S
11、PNode; typedef struct int mu,nu,tu; SPNode dataMAXSIZE+1; SPMatrix; SPMatrix A，B;,矩阵元素的行、列下标从（1，1）开始。将矩阵的总行数、总列数及非零元素的总数均作为三元组表的属性进行描述。,2019年5月24日星期五,第18页,(1)按照矩阵M的列序进行转置,一个mn的矩阵A，它的转置B是一个nm的矩阵，且aij=bji，1im，1jn，即A的行是B的列，A的列是B的行。转置结果为下。,1.按A的列序转置:将A转置为B，就是将A的三元组表a.elem置换为表B的三元组表b.elem ，由于A的列是B的行，因此，按
12、a.elem的列序转置，所得到的转置矩阵B的三元组表b.elem必定是按行优先存放的。,2019年5月24日星期五,第19页,【算法4.1】稀疏矩阵转置。 SPMatrix *Transpose(SPMatrix *A) SPMatrix *B ; int p,q,col ; B-mu=A-nu; B-nu=A-mu; B-tu=A-tu ; if (B-tu0) q=1 ; for (col=1; colnu); col+) for (p=1; ptu); p+) if (A-datap.j=col ) B-dataq.i=A-datap.j; B-dataq.j=A-datap.i ; B
13、-dataq.v=A-datap.v; q+; /*if*/ /* if(B-tu0) */ return B; /* 返回的是转置矩阵的指针*/ /* Transpose */,2019年5月24日星期五,第20页,分析该算法，其时间主要耗费在for的二重循环上，所以时间复杂性为O(nt)，即与A的列数和非零元素个数的乘积成正比。而通常用二维数组表示矩阵转置算法的执行时间是0(mn)，它正比于行数和列数的乘积。当上述稀疏矩阵非零元素的个数t大于行数时，算法的时间复杂度大于通常的转置算法的时间。,(2)按照三元组的次序进行转置,首先要知道A-data中的元素在B-data中的存储位置。这就要预
14、先确定矩阵M中每一列的第一个非零元素在B-data中应有的位置。为此，需设置两个数组num1n和cpot1n，分别存放在矩阵M中每一列的非零元素个数和每一列第1个非零元素在B-data中的位置:,2019年5月24日星期五,第21页,numcol表示矩阵M中第col列中非零元素个数； cpotcol的初值表示M中第col列的第1个非零元素在B-data中的位置。显然有,基本思想：先求出三元组表A中每一列的非零元素个数填入num1n数组中；,表4-1 三元组表A的num与pot值,2019年5月24日星期五,第22页,【算法4.2】稀疏矩阵转置的改进算法。 SPMatrix * TransM2
15、(SPMatrix *A) SPMatrix *B; int p,q,col,k; int numA-nu+1,cpotA-nu+1; B-mu=A-nu; B-nu=A-mu; B-tu=A-tu; if (B-tu0) for (col=1;colnu;col+) numcol=0; for (k=1;ktu;k+) numA-datak.j+;,然后求出cpot1n各数据值；最后依次扫描A-data，当扫描到一个col列元素时，直接将其存放在B-data的cpotcol位置上， cpotcol加，cpotcol中始终是下一个col列元素在B.data中的位置。,2019年5月24日星期五,第23页,cpot1=1; for (col=2;colnu;col+) cpotcol= cpotcol-1+numcol-1; for (p=1;ptu;p+) col=A-datap.j; q=cpotcol
