搜索
第五章数组与广义表第五章数组与广义表1.多维数组2.矩阵的压缩存储3.广义表第五章数组与广义表多维数组•多维数组和广义表是一种复杂的非线性结构，它们的逻辑特征是：一个数据元素可能有多个直接前驱和多个直接后继。•1、数组（向量）——常用数据类型一维数组（向量）是存储于计算机的连续存储空间中的多个具有统一类型的数据元素。同一数组的不同元素通过不同的下标标识。（a1,a2,…,an)第五章数组与广义表•2、二维数组二维数组A[m][n]可视为由m个行向量组成的向量，或由n个列向量组成的向量。多维数组第五章数组与广义表多维数组•三维数组A[m][n][p]可视为以二维数组为数据元素的向量。四维数组可视为以三维数组为数据元素的向量……三维数组中的每个元素a[i][j][k]都属于三个向量。四维数组中的每个元素都属于四个向量……第五章数组与广义表多维数组•4、数组的顺序存储方式由于计算机内存是一维的，多维数组的元素应排成线性序列后存入存储器。数组一般不做插入和删除操作，即结构中元素个数和元素间关系不变化。一般采用顺序存储方法表示数组。•行优先顺序•列优先顺序第五章数组与广义表多维数组•（1）行优先顺序将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量后面。【例】二维数组A[m][n]的按行优先存储的线性序列为：•a11,a12,…,a1n，a21,a22,…,a2n,……，am1,am2,…，amn•注意：①PASCAL和C语言中，数组按行优先顺序存储。②行优先顺序推广到多维数组，可规定为先排最右的下标。第五章数组与广义表•5、数组元素的地址计算公式（1）按行优先顺序存储的二维数组A[m][n]地址计算公式LOC(aij)=LOC(a11)+[(i-1)×n+j-1]×d其中：①LOC(a11)是开始结点的存放地址（即基地址）②d为每个元素所占的存储单元数③由地址计算公式可得，数组中任一元素可通过地址公式在相同时间内存取。即顺序存储的数组是随机存取结构。第五章数组与广义表•（2）列优先顺序将数组元素按列向量排列，第i+1个列向量紧接在第i个列向量后面。【例】二维数组A[m][n]的按列优先存储的线性序列为：a11,a21,…,am1，a12,a22,…,am2,……，a1n,a2n,…，amn注意：①FORTRAN语言中，数组按列优先顺序存储。②列优先顺序推广到多维数组，可规定为先排最左的下标。多维数组第五章数组与广义表•（2）按列优先顺序存储的二维数组A[m][n]地址计算公式LOC(aij)=LOC(a11)+[(j-1)×m+i-1]×d第五章数组与广义表•在C语言中，二维数组任一元素的地址计算公式如下（下标从0开始）•LOC(a[i][j])=LOC(a[0][0])+(i×n+j)×d•注意：以下讨论的数组存储结构都以C语言下标表示。第五章数组与广义表压缩矩阵•矩阵是科学与工程计算问题中常用的数学对象之一。矩阵的存储1、矩阵的二维数组描述矩阵用二维数组描述时，存储的密度为1。可以对其元素进行随机存取，各种矩阵运算也非常简单。第五章数组与广义表压缩矩阵•2、矩阵的压缩存储矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，为了节省存储空间，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。第五章数组与广义表特殊矩阵•所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。常见的有对称矩阵、三角矩阵和对角矩阵等。1．对称矩阵（1）对称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji(0≤i，j≤n-1)则称A为对称矩阵。【例】下图是一个5阶对称矩阵。第五章数组与广义表特殊矩阵•（2）对称矩阵的压缩存储对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间。这样，能节约近一半的存储空间。①按行优先顺序存储主对角线(包括对角线)以下的元素第五章数组与广义表•即按a00,a10,a11,……，an-1,0,an-1,1…，an-1,n-1次序存放在一个向量sa[0．．n(n+1)／2-1]中（下三角矩阵中，元素总数为n(n+1)／2）。其中：sa[0]=a00,sa[1]=a10,……，sa[n(n+1)／2-1]=an-1n-1②元素aij的存放位置aij元素前有i行(从第0行到第i-1行)，一共有：1+2+…+i=i×(i+1)／2个元素；在第i行上，aij之前恰有j个元素(即ai0，ail，…，aij-1)，因此有：sa[i×(i+1)／2+j]=aij第五章数组与广义表00189263025170615137508S[0]15137508……1133若在五阶矩阵中查找任一位置的数据，如第二行第三列(a[1][2])，问：它存储在数组S中的下标是多少呢？S[7]k=i*N+j第五章数组与广义表00263025170615137508Sa[0]151908……11331、若想查找下三角数据第三行第二列(a[2][1])，它在Sa中下标ｋ？2、上三角的数据如何在Sa中找到呢？Sa[4]189k=i*(i+1)/2+j第五章数组与广义表•③aij和sa[k]之间的对应关系：若i≥j：k=i×(i+1)／2+j若i＜j，k=j×(j+1)／2+i其中0≤kn(n+1)／2令I=max(i，j)，J=min(i，j)，则k和i，j的对应关系可统一为：k=I×(I+1)／2+J0≤kn(n+1)／2第五章数组与广义表•（3）对称矩阵的地址计算公式LOC(aij)=LOC(sa[k])=LOC(sa[0])+k×d=LOC(sa[0])+[I×(I+1)／2+J]×d通过下标变换公式，能立即找到矩阵元素aij在其压缩存储表示sa中的对应位置k。因此是随机存取结构。【例】a21和a12均存储在sa[4]中，这是因为k=I×(I+1)／2+J=2×(2+1)／2+1=4第五章数组与广义表•2、三角矩阵（1）三角矩阵的划分以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种。①上三角矩阵•下三角(不包括主角线)中的元素均为常数c②下三角矩阵•主对角线上方均为常数c注意：在多数情况下，三角矩阵的常数c为零。第五章数组与广义表•（2）三角矩阵的压缩存储三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n×(n+1)／2个，因此，三角矩阵可压缩存储到向量sa[0．．n(n+1)／2]中，其中c存放在向量的最后一个分量中。第五章数组与广义表CCCC3025C7061CCCC50CSa[0]151908……1133189C对于下三角矩阵aij和sa[k]之间的对应关系如下：当i≥j时，k=i×(i+1)／2+j当ij时，k=n(n+1)／2第五章数组与广义表•①上三角矩阵中aij和sa[k]之间的对应关系上三角矩阵中，主对角线之上的第p行(0≤pn)恰有n-p个元素，按行优先顺序存放上三角矩阵中的元素aij时：aij元素前有i行(从第0行到第i-1行)，一共有：(n-0)+(n-1)+(n-2)+…+(n-i+1)=i×(2n-i+1)／2个元素；在第i行上，aij之前恰有j-i个元素(即aii，aii+l，…，aij-1)，因此有：sa[i×(2n-i+1)／2+j-i]=aij所以：┌i×(2n-i+1)／2+j-i当i≤jk=│└n×(n+1)/2当i＞j第五章数组与广义表•3．对角矩阵所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零的矩阵为对角矩阵。【例】下图给出了一个三对角矩阵。第五章数组与广义表•其中：非零元素仅出现在主对角上(aii，0≤i≤n-1)，紧邻主对角线上面的那条对角线上(ai，i+1，0≤i≤n-2)和紧邻主对角线下面的那条对角线上(ai+1，i，0≤i≤n-2)。当|i-j|1时，元素aij=0。由此可知，一个k对角线矩阵(k为奇数)A是满足下述条件的矩阵：若|i-j|(k-1)／2，则元素aij=0。第五章数组与广义表稀疏矩阵设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数(即sm×n)，则称A为稀疏矩阵。1、稀疏矩阵的压缩存储为了节省存储单元，可只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。稀疏矩阵的压缩存储会失去随机存取功能。其中每一个非零元素所在的行号、列号和值组成一个三元组(i，j，aij)，并由此三元组唯一确定。稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。第五章数组与广义表•2、三元组表将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素)，并依次存放在向量中，这种稀疏矩阵的顺序存储结构称为三元组表。注意：以下的讨论中，均假定三元组是按行优先顺序排列的。第五章数组与广义表【例】下图(a)所示的稀疏矩阵A的三元组表表示见图(b)8第五章数组与广义表•（1）三元组表的类型说明为了运算方便，将矩阵的总行数、总列数及非零元素的总数均作为三元组表的属性进行描述。其类型描述为：#defineMaxSize100//由用户定义typedefintDataType；//由用户定义typedefstruct{inti，j；//非零元素的行、列号DataTypev；//非零元素的值}TriTupleNode；typedefstruct{//三元组表TriTupleNodedata[MaxSize]；//三元组表空间intm,n，t；//矩阵的行数、列数及非零元个数}TriTupleTable；第五章数组与广义表•(2)压缩存储结构上矩阵的转置运算一个m×n的矩阵A，它的转置矩阵B是一个n×m的矩阵，且：A[i][j]=B[j][i]，0≤im，0≤jn，即A的行是B的列，A的列是B的行。8第五章数组与广义表•①三元组表表示的矩阵转置的思想方法第一步：根据A矩阵的行数、列数和非零元总数确定B矩阵的列数、行数和非零元总数。第二步：当三元组表非空（A矩阵的非零元不为0）时，根据A矩阵三元组表的结点空间data（以下简称为三元组表），将A的三元组表a-data置换为B的三元组表b-data。第五章数组与广义表•②三元组表的转置方法一:简单地交换a-data中i和j中的内容，得到按列优先顺序存储倒b-data;再将b-data重排成按行优先顺序的三元组表。1040第五章数组与广义表•②三元组表的转置方法二:由于A的列是B的行，因此，按a-data的列序转置，所得到的转置矩阵B的三元组表b-data必定是按行优先存放的。按这种方法设计的算法，其基本思想是：对A中的每一列col(0≤col≤a-n-1)，通过从头至尾扫描三元组表a-data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放入b-data中，即可得到B的按行优先的压缩存储表示。第五章数组与广义表第五章数组与广义表voidTransMatrix(TriTupleTable*b，TriTupleTable*a){//*a，*b是矩阵A、B的三元组表表示，求A转置为Bintp，q，col；//三元组表中数组元素下标b-m=a-n；b-n=a-m；//A和B的行列总数互换b-t=a-t；//非零元总数if(b-t=0)Error(A=0)；//A中无非零元，退出q=0；for(col=0；cola-n；col++)//对A的每一列for(p=0；pa-t；p++)//扫描A的三元组表if(a-data[p]．j==col){//找列号为col的三元组b-data[q]．i=a-data[p].j；b-data[q]．j=a-data[p].i；b-data[q]．v=a-data[p].v；q++；}}//TransMatri