数据结构（C语言描述）第4章数组

数据结构(,C,语言版,),*,*,第2章 数组、特殊矩阵和广义表,4.1 数组重点,4,.2,特殊矩阵的压缩存储,4.3,广义表,小结,第4章 数组、特殊矩阵和广义表,2024/11/18,本章学习目标,掌握多维数组的概念以及在计算机中的存储表示；,掌握对称矩阵、三角矩阵、对角矩阵的压缩存储表示及地址运算公式；,稀疏矩阵在计算机中的存储表示及根本运算的实现；,广义表的逻辑结构和根本运算。,2024/11/18,4.1 数组4.1.1 数组的根本概念,数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比方：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组的一维数组，三维数组可以看作“数据元素是二维数组的一维数组，依此类推。,数组的定义：,数组array是由下标index和值value组成的序对集合。,在,C,语言中，一维数组定义为：,ElemType arraynameMAXSIZE;,2024/11/18,以下图一个m行n列的二维数组。它可以看成是由行向量组成的向量，也可以看成是由列向量组成的向量。,在数组中通常做下面两种操作：,(1),取值操作：给定一组下标，读其对应的数据元素。,(2)赋值操作：给定一组下标，存储或修改与其相对应的数据元素。,a,00,a,01,a,0,n-1,a,10,a,11,a,1,n-1,a,ij,a,m-1,0,a,m-1,1,a,m-1,n-1,A=,m,行,n,列的二维数组,与线性表的区别：在数组中不能进行插入、删除数据元素的操作。,2024/11/18,4.1.2,数组的存储结构,一维数组在计算机内是存放在一组连续的存储单元中。因此，数组中任一元素Ai的存储位置可用以下公式计算：,LOCAi=LOCA0+(i)L,其中L是每个数据元素所占存储单元的个数。对于一维数组按下标顺序分配即可。,a,00,a,01,a,0,n-1,a,10,a,11,a,1,n-1,a,ij,a,m-1,0,a,m-1,1,a,m-1,n-1,A=,m,行,n,列的二维数组,二维数组的存储器，一般有两种存储方式：一是,以,行为主序的顺序,存放，如,BASIC、C,等程序设计语言，即一行分配完了接着分配下一行。,2024/11/18,C,语言中，数组就是按行优先顺序存储的。,如，一个23的二维数组,A,23,，,以行为主序的分配顺序为：,a,00,，a,01,，a,02,，a,10,，a,11,，a,12,。,以,列,为主序分配顺序为：,a,00,a,10,a,01,a,11,a,02,a,12,a,00,a,01,a,02,a,10,a,11,a,12,A,23,=,23,的二维数组,a,00,a,01,a,02,a,10,a,11,a,12,a,00,a,10,a,01,a,11,a,02,a,12,以,行,为主序,以,列,为主序,2024/11/18,在C语言中，二维数组定义为：,ElemType arraynamem n;,数组中任一元素Aij的存储位置可用以下公式计算：,LOC(Aij)=LOC(A00)+(in+j)L,这是因为数组元素Aij的前面有i行，每一行的元素个数为n，在第i行中Aij的前面还有j个数组元素。L仍然是每个数据元素所占存储单元的个数。,例如23二维数组：,LOC(a,12,)=LOC(a,00,)+(1)*3+2*,L,a,00,a,01,a,02,a,10,a,11,a,12,A=,2024/11/18,【例4-1】选择题。设二维数组M的每个数据元素占6个存储单元，行下标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.,2024/11/18,在科学与工程计算问题中，矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况，比方常见的一些特殊矩阵，如三角矩阵、对称矩阵、带状矩阵、稀疏矩阵等。,4.2.1,对称矩阵,4.2 特殊矩阵的压缩存储,在一个n阶方阵中，对称矩阵的特点是：假设数据元素满足以下性质：,3,6,2,8,5,1,9,8,6,0,3,89,6,58,85 1,6,98 60,A=,Aij=Aji 0i,jn-1,2024/11/18,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,所以只要交换上述对应关系式中的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,a,00,a,10,a,11,a,20,a,21,a,22,对于一个n阶对称矩阵，第i行0in只需要存储i+1个元素，元素总数为：,=,n(n+1)/2,2024/11/18,4.2.2,三角矩阵,以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如下图，它的下三角不包括主对角线中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如下图。在大多数情况下，三角矩阵常数为零。,a,00,c c,a,10,a,11,c c,a,n-1,0,a,n-1,1,a,n-1,n-1,下三角矩阵,a,00,a,01,a,0,n-1,c,a,11,a,1,n-1,c c,a,n-1,n-1,上三角矩阵,2024/11/18,三角矩阵中的重复元素,c,可共享一个存储空间，其余的元素,正好有,n(n+1)/2,个，因此，三角矩阵可压缩存储到向量,SA0.n(n+1)/2,中，其中,c,存放在最后一个分量中。,例1：,10,c c c,8 9,c c,5,6 7,c,1 2 3 4,A1=,a21=6对应的k=i(i+1)/2+j=4,a,00,c c,a,10,a,11,c c,a,n-1,0,a,n-1,1,a,n-1,n-1,下三角矩阵,k=,i*(i+1)/2+j,当,ij,n*(n+1)/2,当,ij,4.2.3 对角矩阵,在,n,阶对角矩阵,A,中，所有的非零元素集中在以主对角线为中心的带状区域中，显然,当,i-j1,时，元素向量,Aij=0(,或同一个常数,c)。,a,00,a,01,0 0,a,10,a,11,a,12,0 0,0,a,21,a,22,a,23,0 0,0 0 ,a,n-1,n-2,a,n-1,n-1,A=,2024/11/18,a,n-1,n-1,a,n-1 n-2,a,21,a,12,a,11,a,10,a,01,a,00,K=0 1 2 3 4 5 3n-2 3n-3,三对角矩阵可按行优先顺序将其压缩存储到一维向量,M03n-3,中，,Mk,和对角矩阵非零元素,Aij,之间的对应关系为：,这是,因为第,i,行前有,i,行，共,3,i-1,个数据元素；第,j,列前有,j-(i-1),个数据元素，所以,k=3,i-1+j-(i-1)=2,i+j,i-j,1,k=2,i+j,例如，,A25=0，,这是因为,i-j,=,2-5,1；,A23,对应,M7，,这是因为,k=2i+j=22+3=7。,2024/11/18,4.2.4,稀疏矩阵,设mn矩阵中有t个非零元素，假设且tmu=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-dataq.v=A-datap.v;q+;/*if*/,/*if(B-tu0)*/,return B;,/*,返回的是转置矩阵的指针,*/,/*,Transpose */,i,j,v,1,2,12,1,3,9,2,5,8,3,1,-3,4,3,24,i,j,v,1,3,-3,2,1,12,3,1,9,3,4,24,5,2,8,2024/11/18,分析该算法，其时间主要消耗在for的二重循环上，所以时间复杂性为O(nt)，即与A的列数和非零元素个数的乘积成正比。而通常用二维数组表示矩阵转置算法的执行时间是0(mn)，它正比于行数和列数的乘积。当上述稀疏矩阵非零元素的个数t大于行数时，算法的时间复杂度大于通常的转置算法的时间。,(2),按照三元组的次序进行转置,首先要知道,A-data,中的元素在,B-data,中的存储位置。这就要预先确定矩阵,M,中每一列的第一个非零元素在,B-data,中应有的位置。为此，需设置两个数组,num1.n,和,cpot1.n，,分别存放在矩阵,M,中每一列的非零元素个数和每一列第1个非零元素在,B-data,中的位置,:,2024/11/18,numcol,表示矩阵,M,中第,col,列中非零元素个数；,cpotcol,的初值表示,M,中第,col,列的第,1,个非零元素在,B-data,中的位置。显然有,根本思想：先求出三元组表A中每一列的非零元素个数填入num1.n数组中；,cpot 1=1;,cpot col=pot col-1+numcol-1 (1coln),表,4-1,三元组表,A,的,num,与,pot,值,col,1,2,3,4,5,6,numcol,2,1,1,2,1,1,cpotcol,1,3,4,5,7,8,2024/11/18,【算法4.2】稀疏矩阵转置的改进算法。,SPMatrix*TransM2(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+;,然后求出,c,pot1.n,各数据值；最后依,次扫描,A-data，,当扫描到一个,col,列元素时，直接将其存放在,B-data,的,cpotcol,位置上，,cpotcol,加，,cpotcol,中始终是下一个,col,列元素在,B.data,中的位置。,2024/11/18,cpot1=1;,for(col=2;colnu;col+),cpotcol=cpotcol-1+numcol-1;,for(p=1;ptu;p+),col=A-datap.j;,q=cpotcol;,B-dataq.i=A-datap.j;,B-dataq.j=A-datap.i;,B-dataq.v=A-datap.v;,cpotcol+;/*for */,return B;,col,1,2,3,4,5,numcol,1,1,2,0,1,cpotcol,0,1,2,4,4,8,2,5,24,4,3,9,1,3,12,1,2,-3,3,1,v,j,i,B,的形成顺序,4,1,2,5,3,A,24,3,4,-3,1,3,8,5,2,9,3,1,12,2,1,v,j,i,2024/11/18,算法复杂度分析：这个算法中有四个循环，分别执行n，t，n-