数据结构ch数组和广义表

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第五章 数组和广义表,数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表,5.1,数组的定义和特点,定义,数组特点,数组结构固定,数据元素同构,数组运算,给定一组下标，存取相应的数据元素,给定一组下标，修改数据元素的值,(),(),(),(),(),(),(),(),(),5.2,数组的顺序存储结构,次序约定,以行序为主序,以列序为主序,a,11,a,12,.a,1n,a,21,a,22,.a,2n,a,m1,a,m2,.,a,mn,.,Loc(,a,ij,)=Loc(,a,11,)+,(i-1)n+(j-1),*l,按行序为主序存放,a,mn,.,a,m2,a,m1,.,a,2n,.,a,22,a,21,a,1n,.,a,12,a,11,0,1,n-1,m*n-1,n,按列序为主序存放,0,1,m-1,m*n-1,m,a,mn,.,a,2n,a,1n,.,a,m2,.,a,22,a,12,a,m1,.,a,21,a,11,a,11,a,12,.,a,1n,a,21,a,22,.,a,2n,a,m1,a,m2,.,a,mn,.,Loc(aij,)=Loc(,a,11,)+(j-1)m+(i-1)*l,5.3,矩阵的压缩存储,对称矩阵,a,11,a,12,.,.,a,1n,a,21,a,22,.,a,2n,a,n1,a,n2,.,a,nn,.,a,11,a,21,a,22,a,31,a,32,a,n1,a,nn,.,.,k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1,按行序为主序：,三角矩阵,a,11,0 0,.,0,a,21,a,22,0,.,0,a,n1,a,n2,a,n3,.,a,nn,.,0,a,11,a,21,a,22,a,31,a,32,a,n1,a,nn,.,.,k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1,按行序为主序：,3,对角矩阵,若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为,0,，则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。,例如，图,5-3,为,7,7,的三对角矩阵（即有三条对角线上元素非,0,）。,3,对角矩阵,我们仅讨论三对角矩阵的压缩存贮，五对角矩阵，七对角矩阵等读者可以作类似分析。,在一个,n,n,的三对角矩阵中，只有,n+n-1+n-1,个非零元素，故只需,3n-2,个存储单元即可，零元已不占用存储单元。,故可将,n,n,三对角矩阵,A,压缩存放到只有,3n-2,个存储单元的,s,向量中，假设仍按行优先顺序存放，则：,sk,与,aij,的对应关系为：,3i-1,当,i=j+1,k=3i,当,i=j,3i+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）唯一确定,稀疏矩阵,定义：非零元较零元少，且分布没有一定规律的矩阵,压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值,稀疏矩阵的压缩存储方法,顺序存储结构,三元组表,#define M 20,typedef,struct,node,int,i,j;,int,v;,JD;,JD maM;,三元组表所需存储单元个数为,3(t+1),其中,t,为非零元个数,6,7,8,1 2 12,1 3 9,3 1 -3,3 6 14,4 3 24,5 2 18,6 1 15,6 4 -7,ma,i j v,0 1 2 3 4 5 6 7 8,ma0.i,ma0.j,ma0.v,分别存放,矩阵行列维数和非零元个数,行列下标,非零元值,求转置矩阵,问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表,问题分析,一般矩阵转置算法：,for(col,=0;col,n;col,+),for(row=0;rowm;row+),ncolrow,=,mrowcol,;,T(n)=O(m,n),6,7,8,1 2 12,1 3 9,3 1 -3,3 6 14,4 3 24,5 2 18,6 1 15,6 4 -7,i j v,0 1 2 3 4 5 6 7 8,ma,i j v,7,6,8,1 3 -3,1 6 15,2 1 12,2 5 18,3 1 9,3 4 24,4 6 -7,6 3 14,0 1 2 3 4 5 6 7 8,mb,?,解决思路：只要做到,将矩阵行、列维数互换,将每个三元组中的,i,和,j,相互调换,重排三元组次序，使,mb,中元素以,N,的行(,M,的列)为主序,方法一：按,M,的列序转置,即按,mb,中三元组次序依次在,ma,中找到相应的三元组进行转置。,为找到,M,中每一列所有非零元素，需对其三元组表,ma,从第一行,起扫描一遍。由于,ma,中以,M,行序为主序,所以由此得到的恰是,mb,中应有的顺序,Ch4_1.c,6,7,8,1 2 12,1 3 9,3 1 -3,3 6 14,4 3 24,5 2 18,6 1 15,6 4 -7,i j v,0 1 2 3 4 5 6 7 8,ma,7,6,8,1 3 -3,1 6 15,2 1 12,2 5 18,3 1 9,3 4 24,4 6 -7,6 3 14,i j v,0 1 2 3 4 5 6 7 8,mb,k,p,p,p,p,p,p,p,p,k,k,k,k,p,p,p,p,p,p,p,p,col,=1,col,=2,如何求转置矩阵？,用,“,三元组,”,表示时如何实现？,1 2 14,1 5 -5,2 2 -7,3 1 36,3 4 28,2 1 14,5 1 -5,2 2 -7,1 3 36,4 3 28,方法二：,首先应该确定转置后每一行的第一个非零元在三元组中的位置。,cpot1=1;,for,(,col,=2;,col,=,M.nu,;+,col,),cpotcol,=cpotcol-1+numcol-1;,Status,FastTransposeSMatrix(TSMatrix,M,TSMatrix,&,T),T.mu,=,M.nu,;,T.nu,=,M.mu,;,T.tu,=,M.tu,;,if,(,T.tu,),for,(,col,=1;,col,=,M.nu,;+,col,),numcol,=0;,for,(t=1;t=,M.tu,;+t)+,numM.datat.j,;,cpot1=1;,for,(,col,=2;,col,=,M.nu,;+,col,),cpotcol,=cpotcol-1+numcol-1;,for,(p=1;p=,M.tu,;+p),/if,return,OK;,/,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,链式存储结构,带行指针向量的单链表表示,每行的非零元用一个单链表存放,设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空,表头结点与单链表结点类型定义,typedef,struct,node,int,col,;,int,val,;,struct,node *next;,JD;,typedef,struct,node *TD;,1 3,5 7,3 -1,1 -1,2 -2,4 2,需存储单元个数为,3t+m,十字链表,设行指针数组和列指针数组，分别指向每行、列第一个非零元,结点定义,tpedef,struct,node,int,row,col,val,;,struct,node *down,*right;,JD;,row,col,val,down,right,1,1,3,4,1,8,2,2,5,2,3,4,5.4,广义表的类型定义,ADT,Glist,数据对象,：,D,e,i,|i=1,2,.,n;n0;,e,i,AtomSet,或,e,i,GList,AtomSet,为某个数据对象,数据关系：,LR,|e,i-1,e,i,D,2in,ADT,Glist,基本操作:,广义表是,递归,定义的,线性结构,，,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,)=,E,Tail(,D,)=,(F),Head(,E,)=,a,Tail(,E,)=,(b,c),Head(,(b,c),)=,(b,c),Tail(,(b,c),)=,(),Head(,(b,c),)=,b,Tail(,(b,c),)=,(c),Head(,(c),)=,c,Tail(,(c),)=,(),5.5,广义表的表示方法,通常采用头、尾指针的链表结构,表结点,:,原子结点：,tag=1 hp,tp,tag=0 data,1),表头、表尾分析法：,构造存储结构的两种分析方法,:,若表头为原子，则为,空表,ls,=NIL,非空表,ls,tag=1,指向表头的指针,指向表尾的指针,tag=0 data,否则，依次类推。,L=(a,(x,y),(x),a,(x,y),(,),1,L,L=(),0 a,1,1,1,1,1,0 x,(),x,1,0 x,0 y,a,(x,y),(x),(x,y),(x),x,(y),y,(x),(x),x,2),子表分析法：,若子表为原子，则为,空表,ls,=NIL,非空表,1,指向子表,1,的指针,tag=0 data,tp,否则，依次类推。,1,指向子表,2,的指针,1,指向子表,n,的指针,ls,例如,:,0,a,0,x,0,y,1,LS=(a,(x,y),(x),ls,0,x,(x),(x,y),a,(x),