数据结构ch数组和广义表

第五章数组和广义表,数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表5.1数组的定义和特点定义,数组特点数组结构固定数据元素同构数组运算给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值,5.2数组的顺序存储结构次序约定以行序为主序以列序为主序,5.3矩阵的压缩存储对称矩阵,三角矩阵,3对角矩阵,若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。,例如，图5-3为77的三对角矩阵（即有三条对角线上元素非0）。,3对角矩阵,我们仅讨论三对角矩阵的压缩存贮，五对角矩阵，七对角矩阵等读者可以作类似分析。在一个nn的三对角矩阵中，只有n+n-1+n-1个非零元素，故只需3n-2个存储单元即可，零元已不占用存储单元。故可将nn三对角矩阵A压缩存放到只有3n-2个存储单元的s向量中，假设仍按行优先顺序存放，则：sk与aij的对应关系为：,3i-1当i=j+1k=3i当i=j3i+1当i=j-1,M由(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）唯一确定,稀疏矩阵定义：非零元较零元少，且分布没有一定规律的矩阵压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值,稀疏矩阵的压缩存储方法顺序存储结构三元组表,#defineM20typedefstructnodeinti,j;intv;JD;JDmaM;,三元组表所需存储单元个数为3(t+1)其中t为非零元个数,678,1212,139,31-3,3614,4324,5218,6115,64-7,ma0.i,ma0.j,ma0.v分别存放矩阵行列维数和非零元个数,求转置矩阵问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表问题分析一般矩阵转置算法：,for(col=0;coln;col+)for(row=0;rowm;row+)ncolrow=mrowcol;T(n)=O(mn),解决思路：只要做到将矩阵行、列维数互换将每个三元组中的i和j相互调换重排三元组次序，使mb中元素以N的行(M的列)为主序,方法一：按M的列序转置即按mb中三元组次序依次在ma中找到相应的三元组进行转置。为找到M中每一列所有非零元素，需对其三元组表ma从第一行起扫描一遍。由于ma中以M行序为主序,所以由此得到的恰是mb中应有的顺序,Ch4_1.c,768,13-3,1615,2112,2518,319,3424,46-7,6314,col=1,col=2,如何求转置矩阵？,用“三元组”表示时如何实现？,1214,15-5,22-7,3136,3428,2114,51-5,22-7,1336,4328,方法二：首先应该确定转置后每一行的第一个非零元在三元组中的位置。,cpot1=1;for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;,StatusFastTransposeSMatrix(TSMatrixM,TSMatrix/FastTransposeSMatrix,转置矩阵元素,Col=M.datap.j;q=cpotcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+cpotcol,链式存储结构带行指针向量的单链表表示每行的非零元用一个单链表存放设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空表头结点与单链表结点类型定义,需存储单元个数为3t+m,十字链表设行指针数组和列指针数组，分别指向每行、列第一个非零元结点定义,tpedefstructnodeintrow,col,val;structnode*down,*right;JD;,5.4广义表的类型定义,ADTGlist数据对象：Dei|i=1,2,.,n;n0;eiAtomSet或eiGList,AtomSet为某个数据对象数据关系：LR|ei-1,eiD,2inADTGlist,基本操作:,广义表是递归定义的线性结构，,LS=(1,2,n)其中：i或为原子或为广义表,例如:A=()F=(d,(e)D=(a,(b,c),F)C=(A,D,F)B=(a,B)=(a,(a,(a,),广义表是一个多层次的线性结构,例如：,D=(E,F),其中:E=(a,(b,c)F=(d,(e),D,E,F,a,(),d,(),b,c,e,广义表LS=(1,2,n)的结构特点:,1)广义表中的数据元素有相对次序；,2)广义表的长度定义为最外层包含元素个数；,3)广义表的深度定义为所含括弧的重数；注意：“原子”的深度为0“空表”的深度为1,4)广义表可以共享；,5)广义表可以是一个递归的表。递归表的深度是无穷值，长度是有限值。,表头：当广义表非空时，称第一个元素为该广义表的表头。表尾：除第一个元素以外，其他的元素组成的表称为该广义表的表尾。,6)任何一个非空广义表LS=(1,2,n)均可分解为表头Head(LS)=1和表尾Tail(LS)=(2,n)两部分。,例如:D=(E,F)=(a,(b,c)，F),Head(D)=ETail(D)=(F),Head(E)=aTail(E)=(b,c),Head(b,c)=(b,c)Tail(b,c)=(),Head(b,c)=bTail(b,c)=(c),Head(c)=cTail(c)=(),5.5广义表的表示方法,通常采用头、尾指针的链表结构,表结点:原子结点：,tag=1hptp,tag=0data,1)表头、表尾分析法：,构造存储结构的两种分析方法:,若表头为原子，则为,空表ls=NIL,非空表ls,tag=1,指向表头的指针,指向表尾的指针,tag=0data,否则，依次类推。,L=(a,(x,y),(x),a,(x,y),(),1,L,L=(),0a,1,1,1,1,1,0 x,(),x,1,0 x,0y,a,(x,y),(x),(x,y),(x),x,(y),y,(x),(x),x,2)子表分