数组和广义表-信管.ppt

《数组和广义表-信管.ppt》由会员分享，可在线阅读，更多相关《数组和广义表-信管.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章第五章数数组和广义表组和广义表 数组可看成是一种特殊的数组可看成是一种特殊的线性表线性表，其特殊在于，表中的数，其特殊在于，表中的数据元素本身也是一种线性表。据元素本身也是一种线性表。数组数组（ArrayArray）是由）是由n(n1)n(n1)个个相同类型数据元素相同类型数据元素a0a0，alal，aiai，an-1an-1构成的构成的有限序列有限序列。n n是数组的是数组的长度长度。其中。其中数组中的数据元素数组中的数据元素aiai是一个数据结构，即是一个数据结构，即aiai可以是线性表可以是线性表中的一个元素，本身也可以是一个线性表中的一个元素，本身也可以是一个线性表，而线性子表中

2、，而线性子表中的每一个数据元素还可以再分解的每一个数据元素还可以再分解 。根据数组元素。根据数组元素aiai的的组织形式不同，数组可以分为一维数组、二维数组以及多组织形式不同，数组可以分为一维数组、二维数组以及多维（维（n n维）数组。维）数组。有时也把一维数组称有时也把一维数组称为向量为向量，二维数组称，二维数组称为矩阵为矩阵。在二。在二维或多维数组中，每个数组元素都受到维或多维数组中，每个数组元素都受到2 2个或个或n n个关系的约束。个关系的约束。当数组为当数组为n n维时，其对应线性表中的每个元素又是一个线性维时，其对应线性表中的每个元素又是一个线性表。在每个关系中，每个元素都有一个直

3、接后继。因此，就表。在每个关系中，每个元素都有一个直接后继。因此，就其单个关系而言，这其单个关系而言，这n n个关系中的每一个仍然是一种线性关个关系中的每一个仍然是一种线性关系。系。数数组组中中每每个个元元素素都都是是由由一一个个值值和和一一组组下下标标来来确确定定的的。同同线线性性表表一一样样，数数组组中中的的所所有有数数据据元元素素都都必必须须属属于于同同一一数数据据类类型型。元元素素下下标标的的个个数数被被称称为为数数组组的的维维数数。显显然然，当当维维数数为为1 1时，数组就退化为定长的线性表。时，数组就退化为定长的线性表。数数组组1 1一维数组一维数组 一一维维数数组组可可以以看看成

4、成是是一一个个线线性性表表或或一一个个向向量量，它它在在计计算算机机内内是存放在一块连续的存储单元中，适合于随机查找。是存放在一块连续的存储单元中，适合于随机查找。一维数组记为一维数组记为AnAn或或A=(aA=(a0 0，a al l，aai i，a an-1n-1)一一维维数数组组中中，一一旦旦a a0 0的的存存储储地地址址、一一个个数数据据元元素素所所占占存存储储单单元元数数k k确定，则确定，则a ai i的存储地址的存储地址LOC(aLOC(ai i)就可求出：就可求出：LOC(aLOC(ai i)=LOC(a)=LOC(a0 0)+i*k (0in)+i*k (0in)2 2二维

5、数组二维数组 二二维维数数组组，又又称称矩矩阵阵(matrix)(matrix)。二二维维数数组组中中的的每每一一个个元元素素又又是是一一个个定定长长的的线线性性表表（一一维维数数组组），都都要要受受到到两两个个关关系系即即行行关关系系和和列列关系的约束，也就是每个元素都同属于两个线性表。关系的约束，也就是每个元素都同属于两个线性表。例如，设例如，设A A是一个有是一个有m m行行n n列的二维数组，则列的二维数组，则A A可以表示为：可以表示为：数组数组 可可以以看看成成由由m m个个行行向向量量组组成成的的向向量量，也也可可以以看看由由n n个个列列向向量量组组成成的的向量。向量。数数组组

6、中中的的每每个个元元素素由由元元素素值值a aijij及及一一组组下下标标（i i，j j）来来确确定定。a aijij既属于第既属于第i i行的行向量，又属于第行的行向量，又属于第j j列的列向量。列的列向量。其中，其中，a ai i=(a=(ai,0i,0 a ai,1i,1 a ai,n-1i,n-1)(0)(0i in)n)可以认为可以认为A Am*nm*n=A=A，A A是这样的一维数组：是这样的一维数组：A=(a A=(a0 0，a al l，a ai i，a am-1m-1)a00a01am-1,0Amn=Amn=（a00,a01,a0,n-1),(a10,a11,a1,n-1)

7、,(am-1,0,am-1,1,am-1,n-1)(a)(b)显显然然，二二维维数数组组同同样样满满足足数数组组的的定定义义。一一个个二二维维数数组组可可以以看看作作是是每每个个数数据据元元素素都都是是相相同同类类型型的的一一维维数数组组。以以此此类类推推，任任何何多多维维数数组组都都可可以以看看作作一一个个线线性性表表，这这时时线线性性表表中中的的每每个个数数据据元元素素也也是一个线性表。多维数组是特殊的线性表，是线性表的推广。是一个线性表。多维数组是特殊的线性表，是线性表的推广。数组的性质数组的性质数组中的数据元素数目固定。数组中的数据元素数目固定。数组中的数据元素必须具有数组中的数据元素

8、必须具有相同的数据类型。相同的数据类型。数组中的每个数据元素都有一组唯一的下标值。数组中的每个数据元素都有一组唯一的下标值。数数组组是是一一种种随随机机存存储储结结构构。可可随随机机存存取取数数组组中中的的任任意意数据元素。数据元素。数数 组组 由由于于数数组组一一般般不不作作删删除除或或插插入入运运算算，所所以以一一旦旦数数组组被被定定义义后后，数数组组中中的的元元素素个个数数和和元元素素之之间间的的关关系系就就不不再再变动。通常采用变动。通常采用顺序存储结构顺序存储结构表示数组。表示数组。对于一维数组，数组的存储结构关系为对于一维数组，数组的存储结构关系为:LOC(aLOC(ai i)=L

9、OC(a)=LOC(a0 0)+i*k)+i*k (0in)(0in)对于二维数组，由于计算机的存储单元是一维线性结对于二维数组，由于计算机的存储单元是一维线性结构，如何用线性的存储结构存放二维数组元素就有行构，如何用线性的存储结构存放二维数组元素就有行/列列次序问题。常用两种存储方法：次序问题。常用两种存储方法：以行序以行序(row major(row major order)order)为主序为主序的存储方式和的存储方式和以列序以列序(column major(column major order)order)为主序为主序的存储方式。的存储方式。数组的存储结构数组的存储结构|行优先顺序行优

10、先顺序将数组元素将数组元素按行按行排列，第排列，第i+1i+1个行向量紧接个行向量紧接在第在第i i个行向量后面。以二维数组为例，按行优先顺序存储个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：的线性序列为：a a1111,a,a1212,a,a1n1n,a,a2121,a,a2222,a,a2n2n,a,am1m1,a,am2m2,a amnmn 在在PASCALPASCAL、C C语言中，数组就是按行优先顺序存储的。语言中，数组就是按行优先顺序存储的。|列优先顺序列优先顺序将数组元素将数组元素按列按列向量排列，第向量排列，第j+1j+1个列向量个列向量紧接在第紧接在第j j个列

11、向量之后，个列向量之后，A A的的m*nm*n个元素按列优先顺序存储个元素按列优先顺序存储的线性序列为：的线性序列为：a a1111,a,a2121,a,am1m1,a,a1212,a,a2222,a,am2m2,a,an1n1,a,an2n2,a anmnm 在在FORTRANFORTRAN语言中，数组就是按列优先顺序存储的。语言中，数组就是按列优先顺序存储的。顺序存储结构顺序存储结构 二维数组的两种存储结构二维数组的两种存储结构 对对一一个个以以行行序序为为主主序序的的计计算算机机系系统统，当当二二维维数数组组第第一一个个数数据据元元素素a a0,00,0的的存存储储地地址址LOC(aLO

12、C(a0,00,0)以以及及每每个个数数据据元元素素所所占占用用的的存存储储单单元元k k确确定定后后，该该二二维维数数组组中中任任一一数数据据元元素素a ai,ji,j的的存存储储地址可由下式确定地址可由下式确定:LOC(aLOC(ai,ji,j)=LOC(a)=LOC(a0,00,0)+(i)+(in+jn+j)k)k其中其中n n为每行中的列数。为每行中的列数。以以“行序为主序行序为主序”的存储映象的存储映象按行序为主序存放按行序为主序存放01n-1m*n-1n am-1n-1 .am-11 am-10 .a1n-1 .a11 a10 a0n-1 .a01 a00a00a01.a0n-1

13、a10a11.a1n-1am-10am-11am-1n-1.Loc(i,j)=Loc(0,0)+n*i+j*L 【例【例1】对于给定的二维数组】对于给定的二维数组floata34，计算：，计算：(1)数组数组a中的数组元素数目；中的数组元素数目；(2)若若数数组组a的的起起始始地地址址为为1000，且且每每个个数数组组元元素素长长度度为为32位位(即即4个字节个字节)，数组元素，数组元素a23的内存地址。的内存地址。【解解】(1)由由于于C语语言言中中数数组组的的行行、列列下下标标值值的的下下界界均均为为0，该该数数组组行行上上界界为为3-1=2，列列上上界界为为4-1=3，所所以以该该数数组

14、组的的元元素素数数目目共共有有3*4=12个。个。(2)由于由于C语言采用行序为主序的存储方式，有：语言采用行序为主序的存储方式，有：LOC(a2,3)=LOC(a0,0)+(i*n+j)*k=1000+(2*4+3)*4=1044顺序存储结构例顺序存储结构例 【例例5-25-2】有有m m名名学学生生，每每人人考考n n门门功功课课，试试写写出出求求任任一一学学生生总总分分数和任一课程总分数的数据结构和算法。数和任一课程总分数的数据结构和算法。【解解】把把学学生生的的考考试试成成绩绩存存放放在在m m行行n n列列的的二二维维数数组组中中，则则第第i(0im)i(0im)行行第第j(0jn)

15、j(0jn)列列中中存存放放了了第第i i个个学学生生的的第第j j门门课课程程考考试成绩。即数据结构为：试成绩。即数据结构为：#define M 10#define M 10 /假设假设 为为1010人人#define N 3#define N 3 /假设假设 为为3 3int scoreMN;int scoreMN;/学生成绩二维数组学生成绩二维数组顺序存储结构例顺序存储结构例 求第求第j j门课程总分数的算法为：门课程总分数的算法为：intcourse_sum(intscoreMN,intj)inti,sum=0;for(i=0;iM;i+)sum=sum+scoreij;return(

16、sum);求第求第i名学生总分数的算法为：名学生总分数的算法为：intstudent_sum(intscoreMN,inti)intj,sum=0;for(j=0;jN;j+)sum=sum+scoreij;return(sum);1对称矩阵对称矩阵若一个若一个n阶方阵阶方阵A中元素满足下列条件：中元素满足下列条件：aij=aji其中其中0i,jn-1，则称，则称A为对称矩阵。为对称矩阵。例如，下图是一个例如，下图是一个3*3的对称矩阵。的对称矩阵。特殊矩阵特殊矩阵 2三角矩阵三角矩阵上三角矩阵上三角矩阵即即矩矩阵阵上上三三角角部部分分元元素素是是随随机机的的，而而下下三三角角部部分分元元素素

17、全全部部相相同同（为为某某常常数数C）或或全全为为0，具体形式见图（具体形式见图（a）。）。（2）下三角矩阵）下三角矩阵即即矩矩阵阵的的下下三三角角部部分分元元素素是是随随机机的的，而而上上三三角角部部分分元元素素全全部部相相同同（为为某某常常数数C）或或全全为为0，具具体体形形式式见见图（图（b）。）。（a）上三角矩阵（b）下三角矩阵 若若矩矩阵阵中中所所有有非非零零元元素素都都集集中中在在以以主主对对角角线线为为中中心心的的带带状状区区域域中中，区区域域外外的的值值全全为为0 0，则则称称为为对对角角矩矩阵阵。常常见见的的有有三三对对角角矩矩阵阵、五五对对角角矩矩阵阵、七七对对角角矩矩阵阵

18、等等。例例如如，下下图图为为7777的的三三对对角角矩矩阵阵（即即有有三三条条对对角角线上元素非线上元素非0 0）3对角矩阵对角矩阵特殊矩阵压缩特殊矩阵压缩 对于这些特殊矩阵，应该充分利用元素值的对于这些特殊矩阵，应该充分利用元素值的分布规律，将其进行压缩存储。选择压缩存储的分布规律，将其进行压缩存储。选择压缩存储的方法应遵循两条原则：方法应遵循两条原则：一是尽可能地压缩数据量，一是尽可能地压缩数据量，二是压缩后仍然可以比较容易地进行各项基本操二是压缩后仍然可以比较容易地进行各项基本操作。作。对称矩阵对称矩阵 对称矩阵中的元素对称矩阵中的元素关于主对角线对称关于主对角线对称，故只要，故只要存储

19、矩阵中上三角或下三角中的元素，让每两个对存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按的存储空间。不失一般性，我们按“行优先顺序行优先顺序”存储主对角线（包括对角线）存储主对角线（包括对角线）以下以下的元素，其存储的元素，其存储形式如图所示：形式如图所示：特殊矩阵压缩对称矩阵特殊矩阵压缩对称矩阵 1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a23 3 0 2 5 1 .7 0 6 1 3 an-1 0 a n-1 1 a

20、n-1 2 a n-1 n-1在这个下三角矩阵中，第在这个下三角矩阵中，第i行恰有行恰有i+1个元素，元素总数为：个元素，元素总数为：(i+1)=n(n+1)/2因此，我们可以按图中箭头所指的次序将这些元素存放在因此，我们可以按图中箭头所指的次序将这些元素存放在一个向量一个向量sa0.n(n+1)/2-1中。为了便于访问对称矩阵中。为了便于访问对称矩阵A中的中的元素，我们必须在元素，我们必须在aij和和sak之间找一个对应关系。之间找一个对应关系。若若ij，则，则aij在下三角形中。在下三角形中。aij之前的之前的i行（从第行（从第0行到第行到第i-1行）一共有行）一共有1+2+i=i(i+1

21、)/2个元素，个元素，在第在第i行上，行上，aij之前恰有之前恰有j个元素（即个元素（即ai0,ai1,ai2,aij-1），因此有：），因此有：k=i*(i+1)/2+j 0kn(n+1)/2若若ij，则，则aij是在上三角矩阵中。因为是在上三角矩阵中。因为aij=aji，所，所以只要交换上述对应关系式中的以只要交换上述对应关系式中的i和和j即可得到：即可得到：k=j*(j+1)/2+i 0 kn(n+1)/2 特殊矩阵压缩对称矩阵特殊矩阵压缩对称矩阵特殊矩阵压缩对称矩阵特殊矩阵压缩对称矩阵令令I=max(i,j)，J=min(i,j)，则，则k和和i,j的对应关系可统的对应关系可统一为：一

22、为：k=I*(I+1)/2+J 0 kn(n+1)/2 因此，因此，aij的地址可用下列式计算：的地址可用下列式计算：LOC(aij)=LOC(sak)=LOC(sa0)+k*d=LOC(sa0+I*(I+1)/2+J*d有了上述的下标交换关系，对于任意给定一组下标有了上述的下标交换关系，对于任意给定一组下标(i，j)，均可在，均可在sak中找到矩阵元素中找到矩阵元素aij，反之，对所有，反之，对所有k=0,1,2,n(n-1)/2-1，都能确定，都能确定sak中的元素在矩阵中的位置中的元素在矩阵中的位置(i,j)。由此，称。由此，称san(n+1)/2为阶对称矩阵为阶对称矩阵A的的压缩存储压

23、缩存储，见下图：，见下图：k=0123n(n-1)/2n(n-1)/2-1例如例如a21和和a12均存储在均存储在sa4中，这是因为中，这是因为k=I*(I+1)/2+J=2*(2+1)/2+1=4a00a10a11a20an-1 0 an-1,n-1三角矩阵中的重复元素三角矩阵中的重复元素0可共享一个存储空间，其余的可共享一个存储空间，其余的元素正好有元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到个，因此，三角矩阵可压缩存储到sa0.n(n+1)/2中，其中中，其中0存放在向量的最后一个分量中，存放在向量的最后一个分量中，上三角矩阵中，主对角线之上的第上三角矩阵中，主对角线之上的第

24、p行行(0pj下三角矩阵的存储和对称矩阵类似，下三角矩阵的存储和对称矩阵类似，sak和和aij对应关系对应关系是：是：i(i+1)/2+jijn(n+1)/2ij特殊矩阵压缩三角矩阵特殊矩阵压缩三角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵，a00 a01 a10 a11 a12 a21 a22 a23 .可用以行序为主序的 an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1 形式存储特殊矩阵压缩对角矩阵特殊矩阵压缩对角矩阵非零元素

25、仅出现在非零元素仅出现在主对角主对角(aii,0in-1)上，紧邻主对角上，紧邻主对角线线上面上面的那条对角线上的那条对角线上(aii+1,0in-2)和紧邻主对角线和紧邻主对角线下面下面的那条对角线上的那条对角线上(ai+1i,0in-2)。显然，当显然，当 i-j 1时，元素时，元素aij=0。由此可知，一个由此可知，一个k对角矩阵对角矩阵(k为奇数为奇数)A是满足下述条件的是满足下述条件的矩阵：矩阵：若若 i-j(k-1)/2，则元素则元素aij=0。对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素

26、和向量下标的到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。对应关系。特殊矩阵压缩对角矩阵特殊矩阵压缩对角矩阵特殊矩阵压缩对角矩阵特殊矩阵压缩对角矩阵在三对角矩阵里除满足条件i=0，j=0、1，或i=n-1j=n-2、n-1或1in-1,j=i-1、i、i+1的元素aij外，其余元素都是零。对这种矩阵，我们也可按行优序为主序来存储。除第0行和第n-1行是2个元素外，每行的非零元素都要是3个，因此，需存储的元素个数为3n-2。LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1)*d=LOC(0,0)+(2i+j)*d上例中，上例中，a34对应着对应着sa10。k=2*i+j

27、=2*3+4=10a21对应着对应着sa5k=2*2+1=5由此，我们称由此，我们称sa0.3*n-2是阶三对角带状矩阵是阶三对角带状矩阵A的压缩存储表示。的压缩存储表示。特殊矩阵压缩对角矩阵特殊矩阵压缩对角矩阵稀疏矩阵稀疏矩阵上述的各种特殊矩阵，其非零元素的分布都上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取个关系，仍能对矩阵的元素进行随机

28、存取.什么是稀疏矩阵？简单说，设矩阵什么是稀疏矩阵？简单说，设矩阵A A中有中有s s个个非零元素，若非零元素，若s s远远小于矩阵元素的总数（即远远小于矩阵元素的总数（即smnsmn），则称），则称A A为稀疏矩阵。为稀疏矩阵。在存储稀疏矩阵时，为了节省存储单元，很自然在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。但由于非零元素的分地想到使用压缩存储方法。但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的时，还必须同时记下它所在的行和列行和列的位置的位置（i,ji,j)。反之，一个。反之，一个三

29、元组三元组(i,j,ai,j,aijij)唯一确定了唯一确定了矩阵矩阵A A的一个非零元。因此，稀疏矩阵可由表示非的一个非零元。因此，稀疏矩阵可由表示非零元的零元的三元组及其行列数三元组及其行列数唯一确定。唯一确定。稀疏矩阵稀疏矩阵稀疏矩阵例稀疏矩阵例例如 下列三元组表(1,2,12)(1,3,9),(3,1,3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)加上(6,7)这一对行、列值便可作为下列矩阵M的另一种描述。上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。0 12 9 0 0 0 0 0 0 -3 0 0 15 0 0 0 0

30、0 0 0 12 0 0 0 18 0 -3 0 0 0 0 14 0 9 0 0 24 0 0 0 0 24 0 0 0 0 0 0 0 0 0 7 0 18 0 0 0 0 0 0 0 14 0 0 0 15 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0练习题练习题1、假设有二维数组、假设有二维数组A68，每个元素用相邻的，每个元素用相邻的6个字个字节存储，存储器按字节编址。已知节存储，存储器按字节编址。已知A的起始存储的起始存储位置（基地址）位置（基地址）1000，计算：，计算：(1)数组数组A的体积（即存储量）的体积（即存储量）(2)数组数组A的最后一个元素的最后一个元素a57的第一个字节的地址的第一个字节的地址(3)按行存储时，元素按行存储时，元素a14的第一个字节的地址的第一个字节的地址(4)按列存储时，元素按列存储时，元素a47的第一个字节的地址的第一个字节的地址