数据结构：数组ppt课件

.,第五章数组,5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.3.1特殊矩阵5.3.2稀疏矩阵5.4广义表的定义5.5广义表的存储,.,5.1数组的定义数组可看成是一种特殊的线性表，其特殊在于，表中的元素本身也是一种线性表。多维数组是向量（一维数组）的推广。例如，二维数组：a00a01a0,n-1a10a11a1,n-1am-1,0am-1,1am-1,n-1,.,ADTArray数据对象：ji=0,bi-1,i=1,2,n,D=aj1j2jn|n称为数组的维数，bi是数组第i维的长度，ji是数组元素的第i维下标，aj1j2jnElemSet数据关系：R=R1，R2，RnRi=|0jkbk-1,1kn,且ki，0jibi-2，aj1jijn,aj1ji+1jnD,i=2,n基本操作：Value（A,等价于：typedefElemTypeArray1n;typedefArray1Array2m;数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组的基本操作只有存取元素和修改元素值的操作。,.,5.2数组的顺序表示和实现由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一个序列，然后将这个线性序列存放在存储器中。又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。通常有两种顺序存储方式：低下标优先高下标优先,.,对二维数组而言：以行序为主序将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。在C语言中，数组就是按行优先顺序存储的。以列序为主序将数组元素按列排列，第i+1个列向量紧接在第i个列向量后面。顺序存储的数组是一个随机存取结构。,.,1、一维数组,LOC(i)=LOC(i-1)+l=+i*l,数组元素存储地址的计算：,.,2、二维数组,行优先：LOC(i,j)=+(i*n+j)*l,3、n维数组,LOC(j1,j2,jn)=LOC（0，0，0）+ciji其中Cn=L,Ci-1=bi*ci,1in,.,5.3矩阵的压缩存储高级语言编制程序时，常将一个矩阵描述为一个二维数组。这种存储表示可以对元素随机存取，各种矩阵运算也非常简单。矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，存储空间大量浪费。当一个矩阵中的元素有很多都是零时，零元素的个数远大于非零元素，则称该矩阵为稀疏矩阵。矩阵的压缩存储为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。,.,5.3.1特殊矩阵非零元素或零元素的分布有一定规律的矩阵。1、对称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji0i,jn-1则称A为对称矩阵。只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。例如，存下三角阵。,.,下三角阵sak的下标k和aij的对应关系是：i*(i+1)/2+j当ijj*(j+1)/2+i当ij,k=,在下三角矩阵中，第i行恰有i+1个元素，元素总数为：n(n+1)/2,可将这些元素存放在sa0.n(n+1)/2-1中。为了便于访问对称矩阵A中的元素，我们必须在aij和sak之间找一个对应关系。,k=0123.n(n+1)/2-1,.,.,.,3、对角矩阵（带状矩阵）对角矩阵中，所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。,.,对角矩阵可按行为主序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。,例：三对角矩阵,a00a01a10a11a12a21a22a23.an-2n-3an-2n-2an-2n-1an-1n-2an-1n-1,.,如果按行为主序来存储，除第0行和第n-1行是2个元素外，每行的非零元素都是3个，因此，需存储的元素个数为3n-2。sa0.3n-1,K=0123453n-1数组sa中的元素sak与三对角带状矩阵中的元素aij存在一一对应关系，在aij之前有i行,共有3*i-1个非零元素，在第i行，有j-i+1个非零元素。故sak的下标k和aij的对应关系是:K=3*i-1+(j-i+1)=2*i+j,.,压缩存储原则：只存矩阵的行列数和每个非零元的行列下标及其值。例如：M由矩阵行列数（6,7）和三元组表（(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)）唯一确定。,5.3.2稀疏矩阵,.,一、三元组顺序表以顺序存储结构来表示三元组表。#defineMAXSIZE12500typedefstructinti,j;ElemTypee;Triple;typedefstructTripledataMAXSIZE+1;intmu,nu,tu;TSMatrix;,.,求转置矩阵,问题描述：已知一个稀疏矩阵的三元组表，求该矩阵的转置矩阵的三元组表。,例如：,.,思路：1)将矩阵行、列数互换2)将每个三元组中的i和j相互调换3)重排三元组次序，使N.data中元素以N的行(M的列)为主序三元组表M的mu，nu，tu的值分别为：6，7，8三元组表N的mu，nu，tu的值分别为：7，6，8,.,方法一：即按N.data中三元组次序依次在M.data中找到相应的三元组进行转置。为找到M中每一列所有非零元素，需对其三元组表M.data从第一行起扫描一遍。由于M.data中以M行序为主序,所以由此得到的恰是N.data中应有的顺序。其算法实现如下：StatusTransposMatrix(TSMatrixM,TSMatrix/TransposeSMatrix,.,13-3,1615,2112,2518,319,3424,46-7,6314,col=1,col=2,算法示意：,.,而一般传统矩阵的转置算法为：for(col=0;col=n-1;+col)for(row=0;row=m;+row)tcolrow=mrowcol;其时间复杂度为O(n*m)。,三元组顺序表虽节省存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算法的难度。因此，此算法仅适用于t=m*n的情况。,.,方法二：快速转置的算法。按M.data中三元组次序转置，转置结果放入N.data中恰当位置。此法关键是要预先确定M中每一列第一个非零元N.data中位置，为确定这些位置，转置前应先求得M的每一列中非零元个数。实现：设两个数组：numcol：表示矩阵M中第col列中非零元个数。cpotcol：指示M中第col列第一个非零元在N.data中的位置。,.,1,3,5,7,8,8,9,.,13-3,1615,2112,2518,319,3424,46-7,6314,4,6,2,9,7,5,3,.,二、行逻辑链接的顺序表（带行表的三元组表）有时为了方便某些矩阵运算，我们在按行存储的三元组中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。当将行表作为三元组表的一个新增属性加以描述时，我们就得到了稀疏矩阵的另一种顺序存储结构：带行表的三元组表。其类型描述如下：typedefstructTripledataMAXSIZE+1;intrposMAXRC+1;intmu,nu,tu;RLSMatrix;,.,两个矩阵相乘的经典算法:若设Q=M*N，其中，M是m1*n1矩阵，N是m2*n2矩阵。当n1=m2时有：for(i=1;i=m1;+i)for(j=1;j=n2;+j)qij=0for(k=1;k=n1;+k)qij+=mik*nkj;此算法的复杂度为O(m1*n1*n2)。,.M=,0210-2400,N=,则Q=M*N为：,06-1004,Q=,例如M和N分别为：,.,M和N的三元组、和分别为：ijvijvijv11312212614521121-132-131-2324312324Q.dataM.dataN.data,当M和N是稀疏矩阵并用三元组表存储结构时，经典算法不再适用。,.,稀疏矩阵相乘的基本思想是：对于M中每个元素M.datap，找到N中所有满足条件M.datap.j=N.dataq.i的元素N.dataq，求得M.datap.e和N.dataq.e的乘积，而从求乘积的式子得知，乘积矩阵Q中每个元素的值是个累加和，这个乘积M.datap.e*N.dataq.e只是其中的一部分。为了便于操作，应对每个元素设一累加和的变量，其初值为零，然后扫描三元组表M，求得相应元素的乘积并累加到适当的累加器上。,.,链式存储结构（十字链表）,设行指针数组和列指针数组，分别指向每行、列第一个非零元。,结点：,.,广义表也称为列表，是线性表的一种扩展。记作：LS=(d1,d2,.dn)其中di既可以是单个元素，也可以是广义表。说明:1）广义表的定义是一个递归定义，因为在描述广义表时又用到了广义表；2）在线性表中数据元素是单个元素，而在广义表中，元素可以是单个元素,称为单元素(原子)，也可以是广义表，称为广义表的子表；3）n是广义表长度；,5.4广义表的定义,.,4）广义表示例:A=()空表，表长为0；B=(a,(b,c,d)表长为2，两个元素分别为a和子表（b,c,d)；C=(e)C中只有一个元素e，表长为1；D=(A,B,C,f)D的表长为4，它的前三个元素A，B，C为广义表,第4个是单元素；E=(a,E)递归表。5）若广义表不空，则可分成表头和表尾，反之，一对表头和表尾可唯一确定广义表。对非空广义表：称第一个元素为表头，其余元素组成的表称为表尾。,广义表最重要的两个基本操作：1）取表头；2）取表尾。,.,例如：B=(a,(b,c,d)表头：a，表尾(b,c,d)即HEAD（B）=a，TAIL(B)=(b,c,d)C=(e)表头：e表尾()D=(A,B,C,f)表头：A表尾(B,C,f)运算可以嵌套，如：HEAD（TAIL（B）=(b,c,d)TAIL(TAIL(B)=(),广义