第5章-数组与广义表

东北大学信息学院计算机应用技术研究所杨雷[e-mail]第五章数组和广义表5.1数组的类型定义前几章讨论的线性结构中的数据元素都是非结构的原子类型，元素的值是不再分解的，本章讨论的两种数据结构---数组和广义表可以看成是线性表在下述含义的扩展：表中的数据元素本身也是一个数据结构。5.1数组的类型定义5.3稀疏矩阵的压缩存储5.2数组的顺序表示和实现5.4广义表的类型定义5.5广义表的表示方法5.6广义表操作的递归函数5.1数组的类型定义ADTArray{数据对象：D＝{aj1,j2,...,,ji,jn|ji=0,...,bi-1,i=1,2,..,n}数据关系：R＝{R1,R2,...,Rn}Ri＝{aj1,...ji,...jn,aj1,...ji+1,...jn|0jkbk-1,1kn且ki,0jibi-2,i=2,...,n}}ADTArray基本操作:二维数组的定义:数据对象:D={aij|0≤i≤b1-1,0≤j≤b2-1}数据关系:R={ROW,COL}ROW={ai,j,ai+1,j|0≤i≤b1-2,0≤j≤b2-1}COL={ai,j,ai,j+1|0≤i≤b1-1,0≤j≤b2-2}基本操作：InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn)InitArray(&A,n,bound1,...,boundn)操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。DestroyArray(&A)操作结果：销毁数组A。Value(A,&e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。Assign(&A,e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。5.2数组的顺序表示和实现类型特点:1)只有引用型操作，没有加工型操作；2)数组是多维的结构，而存储空间是一个一维的结构。有两种顺序映象的方式:1)以行序为主序(低下标优先)；2)以列序为主序(高下标优先)。常用的映射方法有两种：按行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。按列优先：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。数组的存储结构与寻址——二维数组二维数组内存二维结构一维结构例如：称为基地址或基址。以“行序为主序”的存储映象二维数组A中任一元素ai,j的存储位置LOC(i,j)=LOC(0,0)+(b2×i＋j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2LL推广到一般情况，可得到n维数组数据元素存储位置的映象关系称为n维数组的映象函数。数组元素的存储位置是其下标的线性函数。其中cn=L，ci-1=bi×ci,1in。LOC(j1,j2,...,jn)=LOC(0,0,...,0)+∑cijii=1n矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，为了节省存储空间，需要对它们进行“压缩存储”，即为多个值相同的元素分配一个存储空间；对零元不分配空间。值相同的元素或者零元素在矩阵中的分布是否有规律：特殊矩阵和稀疏矩阵。5.3矩阵的压缩存储如果矩阵中值相同的元素或零元素在矩阵中的分布有一定规律，则称之谓特殊矩阵。常见的特殊矩阵：对角矩阵、上（下）三角矩阵、对称矩阵、……特殊矩阵1.对称矩阵：aij=aji1≤i,j≤n2.三角矩阵：若n阶方阵中下(上)三角(不包括对角线)中的元均为常量c或0，则称为上(下)三角矩阵；3.对角矩阵：若n阶方阵中的非零值元都集中在以主对角线为中心的(由k条对角线组成的)带状区域中，则称为k对角矩阵。0974986376524321由于特殊矩阵中的非零值元素在矩阵中的分布有着一定的规律，则可将这些非零值元连续存储在一个一维数组中。即矩阵中的任何一个元素和它们在一维数组中的位置之间存在着某种转换关系，并且这种转换关系可以用数学公式表示之。。存储映象方法nnnnnnnniniiiiijinnnaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...................................................................................................654321113...35343332312252423222111514131211nnnnnnnniiijiaaaaaaaaaaaaaaaa............................................................6543211.333231222111对称矩阵的存储方法0123….K….a11a21a22a31…..aij…..ann假设：一维数组sa(下标为0..n*(n+1)/2-1)则sa[k]和矩阵元素aij之间的关系如下：jiijjjijiik当当12)1(12)1(假设m行n列的矩阵含t个非零元素，则称为稀疏因子。通常认为0.05的矩阵为稀疏矩阵。nmt何谓稀疏矩阵？以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:1)浪费空间;2)是指在进行矩阵的运算中进行了很多与零元素的运算－浪费时间。1)尽可能少存或不存零值元素；解决问题的目标:2)尽可能减少没有实际意义的运算；3)操作方便。即：能尽可能快地找到与下标值(i，j)对应的元素，能尽可能快地找到同一行或同一列的非零值元。•但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i,j)。反之，一个三元组(i,j,aij)唯一确定了矩阵A的一个非零元。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。00070015000001800000240001400003000000000009120((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稀疏矩阵的压缩存储方法:一、三元组顺序表二、行逻辑联接的顺序表三、十字链表#defineMAXSIZE12500typedefstruct{inti,j;//该非零元的行下标和列下标ElemTypee;//该非零元的值}Triple;//三元组类型一、三元组顺序表typedefunion{Tripledata[MAXSIZE+1];//data[0]未用intmu,nu,tu;}TSMatrix;//稀疏矩阵类型0160000200005008000000000070900ijV13915-73484154625516Data域中三元组行序为主序TSMatrixaa.dataa.mu=5,a.nu=6,a.tu=6如何求转置矩阵？02000160007008000000900000050000160000200005008000000000070900TSMatrixMTSMatrixTIJv14531943851-75516642IJv13915-73484154625516M.dataT.dataIJv31951-74381456425516StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){q=1;for(col=1;col=M.nu;++col)for(p=1;p=M.tu;++p)if(M.data[p].j==col){T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++q;}}//ifreturnOK;}//TransposeSMatrix分析算法TransposeSMatrix的时间复杂度：时间复杂度为:O(M.nu*M.tu)for(col=1;col=M.nu;++col)……for(p=1;p=M.tu;++p)……当tu和mu*nu同数量级的时候:时间复杂度为:O(M.mu*M.nu2)用常规的二维数组表示时的算法其时间复杂度为:O(mu×nu)for(col=1;col=nu;++col)for(row=1;row=mu;++row)T[col][row]=M[row][col];用“三元组”表示时如何实现？15-7348415462319551643814551-75516642139首先应该确定每一行的第一个非零元在三元组中的位置。13915-73484154625516col123456Num[pos]101121Cpot[col]122346cpot[1]=1;for(col=2;col=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col=M.nu;++col)num[col]=0;for(t=1;t=M.tu;++t)++num[M.data[t].j];cpot[1]=1;for(col=2;col=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p=M.tu;++p){}}//ifreturnOK;}//FastTransposeSMatrix转置矩阵元素Col=M.data[p].j;q=cpot[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++cpot[col]分析算法FastTransposeSMatrix的时间复杂度：时间复杂度为:O(M.nu+M.tu)for(col=1;col=M.nu;++col)……for(t=1;t=M.tu;++t)……for(col=2;col=M.nu;++col)……for(p=1;p=M.tu;++p)……三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。二、行逻辑联接的顺序表#defineMAXMN500typedefstruct{Tripledata[MAXSIZE+1];intrpos[MAXMN+1];intmu,nu,tu;}RLSMatrix;//行逻辑链接顺序表类型修改前述的稀疏矩阵的结构定义，增加一个数据成员rpos，其值在稀疏矩阵的初始化函数中确定。例如：给定一组下标，求矩阵的元素值ElemTypevalue(RLSMatrixM,intr,intc){p=M.rpos[r];while(M.data[p].i==r&&M.data[p].jc)p++;if(M.data[p].i==r&&M.data[p].j==c)returnM.data[p].e;elsereturn0;}//value矩阵乘法的精典算法:for(i=1;i=m1;++i)for(j=1;j=n2;++j)